¿Son las teclas de hashmap mutables una práctica peligrosa?

¿Es una mala práctica usar objetos mutables como claves Hashmap? ¿Qué sucede cuando intentas recuperar un valor de un Hashmap usando una clave que ha sido modificada lo suficiente como para cambiar su código hash?

Por ejemplo, dado

class Key { int a; //mutable field int b; //mutable field public int hashcode() return foo(a, b); } 

con código

 HashMap map = new HashMap(); Key key1 = new Key(0, 0); map.put(key1, value1); key1.setA(5); key1.setB(10); 

¿Qué sucede si ahora llamamos map.get(key1) ? ¿Es esto seguro o aconsejable? ¿O el comportamiento depende del idioma?

Muchos desarrolladores respetados como Brian Goetz y Josh Bloch han observado que:

Si el valor hashCode () de un objeto puede cambiar en función de su estado, debemos tener cuidado al usar objetos como claves en colecciones basadas en hash para asegurarnos de no permitir que su estado cambie cuando se utilizan como claves hash. . Todas las colecciones basadas en hash suponen que el valor hash de un objeto no cambia mientras está en uso como una clave en la colección. Si el código hash de una clave cambiara mientras estaba en una colección, podrían producirse algunas consecuencias impredecibles y confusas. Esto no suele ser un problema en la práctica; no es una práctica común utilizar un objeto mutable como una lista como clave en un HashMap.

Esto no es seguro o aconsejable. El valor asignado por key1 nunca se puede recuperar. Al hacer una recuperación, la mayoría de los mapas hash harán algo como

 Object get(Object key) { int hash = key.hashCode(); //simplified, ignores hash collisions, Entry entry = getEntry(hash); if(entry != null && entry.getKey().equals(key)) { return entry.getValue(); } return null; } 

En este ejemplo, key1.hashcode () ahora apunta al cubo incorrecto de la tabla hash, y no podrá recuperar value1 con key1.

Si hubieras hecho algo como,

 Key key1 = new Key(0, 0); map.put(key1, value1); key1.setA(5); Key key2 = new Key(0, 0); map.get(key2); 

Esto tampoco recuperará value1, ya que key1 y key2 ya no son iguales, por lo que esta comprobación

  if(entry != null && entry.getKey().equals(key)) 

fallará.

Esto no funcionará. Está cambiando el valor de la clave, por lo que básicamente está desperdiciando. Es como crear una llave y un candado de la vida real, y luego cambiar la llave e intentar colocarla de nuevo en la cerradura.

Los mapas hash usan código hash y comparaciones de igualdad para identificar un cierto par clave-valor con una clave determinada. Si el mapa tiene la clave como referencia del objeto mutable, funcionaría en los casos en que se use la misma instancia para recuperar el valor. Considere sin embargo, el siguiente caso:

 T keyOne = ...; T keyTwo = ...; // At this point keyOne and keyTwo are different instances and // keyOne.equals(keyTwo) is true. HashMap myMap = new HashMap(); myMap.push(keyOne, "Hello"); String s1 = (String) myMap.get(keyOne); // s1 is "Hello" String s2 = (String) myMap.get(keyTwo); // s2 is "Hello" // because keyOne equals keyTwo mutate(keyOne); s1 = myMap.get(keyOne); // returns "Hello" s2 = myMap.get(keyTwo); // not found 

Lo anterior es verdadero si la clave se almacena como referencia. En Java, generalmente este es el caso. En .NET, por ejemplo, si la clave es un tipo de valor (siempre pasado por valor), el resultado será diferente:

 T keyOne = ...; T keyTwo = ...; // At this point keyOne and keyTwo are different instances // and keyOne.equals(keyTwo) is true. Dictionary myMap = new Dictionary(); myMap.Add(keyOne, "Hello"); String s1 = (String) myMap[keyOne]; // s1 is "Hello" String s2 = (String) myMap[keyTwo]; // s2 is "Hello" // because keyOne equals keyTwo mutate(keyOne); s1 = myMap[keyOne]; // not found s2 = myMap[keyTwo]; // returns "Hello" 

Otras tecnologías pueden tener otros comportamientos diferentes. Sin embargo, casi todos ellos llegarían a una situación en la que el resultado del uso de claves mutables no es determinista, lo cual es una situación muy mala en una aplicación, una tarea difícil de depurar e incluso más difícil de entender.

Si el código hash de la clave cambia después de que el par clave-valor (Entrada) se almacena en HashMap, el mapa no podrá recuperar la Entrada.

El código hash de Key puede cambiar si el objeto clave es mutable. Las teclas mutables en HahsMap pueden provocar la pérdida de datos.

Como otros explicaron, es peligroso.

Una forma de evitar eso es tener un campo const dando explícitamente el hash en tus objetos mutables (para que hagas hash en su “identidad”, no su “estado”). Incluso puede inicializar ese campo hash más o menos aleatoriamente.

Otro truco sería usar la dirección, por ejemplo, (intptr_t) reinterpret_cast(this) como base para hash.

En todos los casos, debe abandonar hashing el estado cambiante del objeto.

El comportamiento de un Mapa no se especifica si el valor de un objeto se cambia de una manera que afecta a la comparación igual que el objeto (Mutable) es una clave. Incluso para Set también usar objetos mutables como clave no es una buena idea.

Veamos un ejemplo aquí:

 public class MapKeyShouldntBeMutable { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Map map=new HashMap(); Employee e=new Employee(); Employee e1=new Employee(); Employee e2=new Employee(); Employee e3=new Employee(); Employee e4=new Employee(); e.setName("one"); e1.setName("one"); e2.setName("three"); e3.setName("four"); e4.setName("five"); map.put(e, 24); map.put(e1, 25); map.put(e2, 26); map.put(e3, 27); map.put(e4, 28); e2.setName("one"); System.out.println(" is e equals e1 "+e.equals(e1)); System.out.println(map); for(Employee s:map.keySet()) { System.out.println("key : "+s.getName()+":value : "+map.get(s)); } } } class Employee{ String name; public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public boolean equals(Object o){ Employee e=(Employee)o; if(this.name.equalsIgnoreCase(e.getName())) { return true; } return false; } public int hashCode() { int sum=0; if(this.name!=null) { for(int i=0;i 

Aquí intentamos agregar el objeto mutable "Empleado" a un mapa. Funcionará bien si todas las claves añadidas son distintas. Aquí he reemplazado equals y hashcode para la clase de empleado.

Ver primero, agregué "e" y luego "e1". Para ambos, equals () será verdadero y hashcode será el mismo. Así que el mapa ve como si la misma clave se está agregando, por lo que debería reemplazar el valor anterior con el valor de e1. Luego hemos agregado e2, e3, e4, estamos bien a partir de ahora.

Pero cuando estamos cambiando el valor de una clave ya agregada, es decir, "e2" como una, se convierte en una clave similar a la que se agregó anteriormente. Ahora el mapa se comportará cableado. Idealmente, e2 debería reemplazar la misma clave existente, es decir, e1. Pero ahora el mapa también toma esto. Y obtendrás esto en o / p:

  is e equals e1 true {Employee@1aa=28, Employee@1bc=27, Employee@142=25, Employee@142=26} key : five:value : 28 key : four:value : 27 key : one:value : 25 key : one:value : 25 

Vea aquí las dos teclas con una que muestre el mismo valor también. Entonces es inesperado. e2.setName("diffnt"); ejecute el mismo progtwig nuevamente cambiando e2.setName("diffnt"); que es e2.setName("one"); aquí ... Ahora el o / p será este:

  is e equals e1 true {Employee@1aa=28, Employee@1bc=27, Employee@142=25, Employee@27b=26} key : five:value : 28 key : four:value : 27 key : one:value : 25 key : diffnt:value : null 

Por lo tanto, no es recomendable agregar cambiar la clave mutable en un mapa.