As chaves hashmap mutáveis ​​são uma prática perigosa?

É uma prática ruim usar objects mutáveis ​​como chaves de hashmap? O que acontece quando você tenta recuperar um valor de um Hashmap usando uma chave que foi modificada o suficiente para alterar seu hashcode?

Por exemplo, dado

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

com código

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

O que acontece se agora chamarmos map.get(key1) ? Isso é seguro ou aconselhável? Ou o comportamento depende da linguagem?

Foi notado por muitos desenvolvedores respeitados como Brian Goetz e Josh Bloch que:

Se o valor de hashCode () de um object puder mudar com base em seu estado, devemos ter cuidado ao usar esses objects como chaves em collections baseadas em hash para garantir que não permitiremos que seu estado seja alterado quando eles estiverem sendo usados ​​como chaves hash . Todas as collections baseadas em hash assumem que o valor de hash de um object não é alterado enquanto está em uso como uma chave na coleção. Se o código hash de uma chave fosse mudar enquanto estava em uma coleção, algumas conseqüências imprevisíveis e confusas poderiam se seguir. Isso geralmente não é um problema na prática – não é uma prática comum usar um object mutável como uma List como uma chave em um HashMap.

Isto não é seguro ou aconselhável. O valor mapeado por key1 nunca pode ser recuperado. Ao fazer uma recuperação, a maioria dos mapas hash fará 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; } 

Neste exemplo, key1.hashcode () agora aponta para o intervalo errado da tabela de hash e você não poderá recuperar valor1 com key1.

Se você tivesse feito algo como

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

Isso também não recuperará valor1, já que key1 e key2 não são mais iguais, portanto, esta verificação

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

vai falhar.

Isso não funcionará. Você está mudando o valor da chave, então basicamente está jogando fora. É como criar uma chave de vida real e bloquear e, em seguida, alterar a chave e tentar colocá-lo de volta na fechadura.

Os mapas de hash usam o código de hash e as comparações de igualdade para identificar um determinado par de valores-chave com uma determinada chave. Se o has has map mantém a chave como uma referência ao object mutável, isso funcionaria nos casos em que a mesma instância é usada para recuperar o valor. Considere, no entanto, o seguinte 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 

O acima é verdadeiro se a chave é armazenada como referência. Em Java geralmente é esse o caso. No .NET, por exemplo, se a chave é um tipo de valor (sempre passado por valor), o 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" 

Outras tecnologias podem ter outros comportamentos diferentes. No entanto, quase todos eles chegam a uma situação em que o resultado do uso de chaves mutáveis ​​não é determinístico, o que é uma situação muito ruim em um aplicativo – difícil de depurar e ainda mais difícil de entender.

Se o código hash da chave for alterado depois que o par de valores-chave (Entrada) for armazenado no HashMap, o mapa não poderá recuperar a Entrada.

O código hash da chave pode mudar se o object chave for mutável. Chaves mutáveis ​​no HahsMap podem resultar em perda de dados.

Como outros explicaram, é perigoso.

Uma maneira de evitar isso é ter um campo const fornecendo explicitamente o hash em seus objects mutáveis ​​(assim você usaria hash em sua “identidade”, não em seu “estado”). Você pode até mesmo inicializar esse campo de hash mais ou menos aleatoriamente.

Outro truque seria usar o endereço, por exemplo, (intptr_t) reinterpret_cast(this) como base para o hash.

Em todos os casos, você deve desistir de alterar o estado do object.

O comportamento de um Mapa não é especificado se o valor de um object é alterado de uma maneira que afeta a comparação de iguais, enquanto o object (Mutável) é uma chave. Mesmo para o Set, também usar object mutável como chave não é uma boa ideia.

Vamos ver um exemplo aqui:

 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 

Aqui estamos tentando adicionar o object mutável "Empregado" a um mapa. Ele funcionará bem se todas as chaves adicionadas forem distintas. Aqui eu anotei equals e hashcode para a class employee.

Veja primeiro eu adicionei "e" e depois "e1". Para ambos, equals () será true e hashcode será o mesmo. Então, o mapa vê como se a mesma chave estivesse sendo adicionada, então deveria replace o valor antigo pelo valor de e1. Então nós adicionamos e2, e3, e4 estamos bem a partir de agora.

Mas quando estamos mudando o valor de uma chave já adicionada, ou seja, "e2" como um, ela se torna uma chave semelhante a uma adicionada anteriormente. Agora o mapa se comportará com fio. Idealmente, o e2 deve replace a mesma chave existente, ou seja, e1. Mas agora o mapa também o substitui. E você vai conseguir isso em 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 

Veja aqui ambas as chaves tendo uma mostrando o mesmo valor também. Então, é inesperado. e2.setName("diffnt"); execute o mesmo programa novamente alterando e2.setName("diffnt"); qual é e2.setName("one"); aqui ... Agora oo / 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 

Então, adicionando alterando a chave mutável em um mapa não é incentivada.