Entendendo o funcionamento de equals e hashCode em um HashMap

Eu tenho este código de teste:

import java.util.*; class MapEQ { public static void main(String[] args) { Map m = new HashMap(); ToDos t1 = new ToDos("Monday"); ToDos t2 = new ToDos("Monday"); ToDos t3 = new ToDos("Tuesday"); m.put(t1, "doLaundry"); m.put(t2, "payBills"); m.put(t3, "cleanAttic"); System.out.println(m.size()); } } class ToDos{ String day; ToDos(String d) { day = d; } public boolean equals(Object o) { return ((ToDos)o).day == this.day; } // public int hashCode() { return 9; } } 

Quando // public int hashCode() { return 9; } // public int hashCode() { return 9; } é descomentado m.size() retorna 2, quando é deixado comentou, retorna três. Por quê?

Você superou equals sem replace o hashCode . Você deve garantir que, para todos os casos em que equals retorne true para dois objects, hashCode retorne o mesmo valor. O código hash é um código que deve ser igual se dois objects forem iguais (o inverso não precisa ser verdadeiro). Quando você coloca seu valor embutido de 9 em, você satisfaz o contrato novamente.

Em seu mapa de hash, a igualdade é testada apenas em um intervalo de hash. Seus dois objects Monday devem ser iguais, mas como estão retornando códigos hash diferentes, o método equals não é chamado para determinar sua igualdade – eles são colocados diretamente em diferentes buckets, e a possibilidade de que eles sejam iguais não é sequer considerada .

HashMap usa hashCode() , == e equals() para pesquisa de input. A sequência de pesquisa de uma determinada chave k é a seguinte:

  • Use k.hashCode() para determinar qual bucket a input é armazenada, se houver
  • Se encontrado, para a chave de cada input k1 nesse intervalo, se k == k1 || k.equals(k1) k == k1 || k.equals(k1) , então retorne a input de k1
  • Quaisquer outros resultados, sem input correspondente

Para demonstrar usando um exemplo, suponha que queremos criar um HashMap onde as chaves são algo que é ‘logicamente equivalente’ se tiverem o mesmo valor inteiro, representado pela class AmbiguousInteger . Em seguida, construímos um HashMap , colocamos em uma input e tentamos sobrepor seu valor e recuperar o valor por chave.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } } HashMap map = new HashMap<>(); // logically equivalent keys AmbiguousInteger key1 = new AmbiguousInteger(1), key2 = new AmbiguousInteger(1), key3 = new AmbiguousInteger(1); map.put(key1, 1); // put in value for entry '1' map.put(key2, 2); // attempt to override value for entry '1' System.out.println(map.get(key1)); System.out.println(map.get(key2)); System.out.println(map.get(key3)); Expected: 2, 2, 2 

Não substitua hashCode() e equals() : por padrão, o Java gera diferentes valores de hashCode() para objects diferentes, portanto, o HashMap usa esses valores para mapear key1 e key2 em diferentes buckets. key3 não tem um bucket correspondente, portanto, não tem valor.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 2, set as entry 2[1] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 2, get as entry 2[1] map.get(key3); // map to no bucket Expected: 2, 2, 2 Output: 1, 2, null 

Substituir hashCode() apenas: HashMap mapeia key1 e key2 no mesmo bucket, mas eles permanecem diferentes porque as verificações key1 == key2 e key1.equals(key2) falham, pois por padrão equals() usa == check e eles se referem a instâncias diferentes. key3 falha nas verificações == e equals() contra key1 e key2 e, portanto, não possui valor correspondente.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[2] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[2] map.get(key3); // map to bucket 1, no corresponding entry Expected: 2, 2, 2 Output: 1, 2, null 

Override equals() only: O HashMap mapeia todas as chaves em diferentes buckets devido ao hashCode() diferente do padrão. == ou equals() é irrelevante aqui, pois o HashMap nunca chega ao ponto em que precisa usá-los.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 2, set as entry 2[1] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 2, get as entry 2[1] map.get(key3); // map to no bucket Expected: 2, 2, 2 Actual: 1, 2, null 

Substitua hashCode() e equals() : o HashMap mapeia key1 , key2 e key3 no mesmo bucket. == verificações falham ao comparar instâncias diferentes, mas as verificações equals() passam, pois todas elas têm o mesmo valor e são consideradas “logicamente equivalentes” por nossa lógica.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return value; } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[1], override value map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[1] map.get(key3); // map to bucket 1, get as entry 1[1] Expected: 2, 2, 2 Actual: 2, 2, 2 

E se hashCode() for random? : HashMap irá atribuir um intervalo diferente para cada operação e, portanto, você nunca encontrará a mesma input que você colocou anteriormente.

 class AmbiguousInteger { private static int staticInt; private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return ++staticInt; // every subsequent call gets different value } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 2, set as entry 2[1] map.get(key1); // map to no bucket, no corresponding value map.get(key2); // map to no bucket, no corresponding value map.get(key3); // map to no bucket, no corresponding value Expected: 2, 2, 2 Actual: null, null, null 

E se hashCode() é sempre o mesmo? : HashMap mapeia todas as chaves em um grande bloco. Nesse caso, seu código está funcionalmente correto, mas o uso do HashMap é praticamente redundante, pois qualquer recuperação precisaria fazer uma iteração em todas as inputs nesse único depósito no tempo O (N) ( ou O (logN) para Java 8 ), equivalente ao uso de uma List .

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return 0; } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[1] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[1] map.get(key3); // map to bucket 1, get as entry 1[1] Expected: 2, 2, 2 Actual: 2, 2, 2 

E se equals é sempre falso? : == verificação passa quando comparamos a mesma instância com ela mesma, mas falha de outra forma, verificações equals sempre falham, então key1 , key2 e key3 são consideradas ‘logicamente diferentes’ e são key3 para inputs diferentes, embora ainda estejam no mesmo bucket devido ao mesmo hashCode() .

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return 0; } @Override public boolean equals(Object obj) { return false; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[2] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[2] map.get(key3); // map to bucket 1, no corresponding entry Expected: 2, 2, 2 Actual: 1, 2, null 

Ok, e se equals é sempre verdade agora? : você está basicamente dizendo que todos os objects são considerados ‘logicamente equivalentes’ a outro, então todos eles mapeiam para o mesmo bucket (devido ao mesmo hashCode() ), a mesma input.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return 0; } @Override public boolean equals(Object obj) { return true; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[1], override value map.put(new AmbiguousInteger(100), 100); // map to bucket 1, set as entry1[1], override value map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[1] map.get(key3); // map to bucket 1, get as entry 1[1] Expected: 2, 2, 2 Actual: 100, 100, 100 

Eu não posso enfatizar o suficiente para que você leia o Capítulo 3 em Java Eficaz (aviso: link pdf). Nesse capítulo, você aprenderá tudo o que precisa saber sobre a substituição de methods no Object e, em particular, sobre o contrato de equals . Josh Bloch tem uma ótima receita para replace o método de equals que você deve seguir. E isso o ajudará a entender por que você deveria estar usando equals e não == em sua implementação particular do método equals .

Espero que isto ajude. POR FAVOR, LEIA. (Pelo menos os primeiros itens … e depois você vai querer ler o resto :-).

-Tom

Quando você não sobrescreve o método hashCode (), sua class ToDos herda o método hashCode () padrão de Object, que dá a cada object um código hash distinto. Isso significa que t1 e t2 têm dois códigos hash diferentes, mesmo que você os comparasse, eles seriam iguais. Dependendo da implementação do hashmap em particular, o mapa é livre para armazená-los separadamente (e isso é, de fato, o que acontece).

Quando você substitui corretamente o método hashCode () para garantir que objects iguais obtenham códigos hash iguais, o hashmap é capaz de localizar os dois objects iguais e colocá-los no mesmo bucket de hash.

Uma implementação melhor forneceria objects que não são iguais a códigos hash diferentes , como este:

 public int hashCode() { return (day != null) ? day.hashCode() : 0; } 

quando você comenta, retorna 3;

porque hashCode () herdado do Object é ONLY chamado que retorna 3 hashcodes diferentes para os 3 objects ToDos. Os hashcodes desiguais significam que os 3 objects são destinados a diferentes buckets e equals () retornam false, pois são o primeiro participante em seus respectivos buckets. Se os hashCodes forem diferentes, é compreendido antecipadamente que os objects são desiguais. Eles vão em baldes diferentes.

quando você descomente, retorna 2;

porque aqui o overhidden hashCode () é chamado, o qual retorna o mesmo valor para todos os ToDos e todos eles terão que ir para um bucket, conectado linearmente. Códigos hash iguais não prometem nada sobre a igualdade ou a desigualdade de objects.

hashCode () para t3 é 9 e, como é o primeiro participante, equals () é false e t3 é inserido no bucket-say bucket0.

Então t2 obtendo o mesmo hashCode () como 9 é destinado para o mesmo bucket0, um subsequente equals () no t3 que já reside no bucket0 retorna false pela definição de equal () substituída.

Agora t1 com hashCode () como 9 também é destinado a bucket0, e uma chamada equals () subsequente retorna true quando comparada com a t2 preexistente no mesmo bucket. t1 não consegue entrar no mapa. Portanto, o tamanho líquido do mapa é 2 -> {ToDos @ 9 = cleanAttic, ToDos @ 9 = payBills}

Isso explica a importância da implementação de equals () e hashCode () e de forma que os campos utilizados para determinar equals () também devam ser tomados ao determinar o hashCode (). Isso garantirá que, se dois objects forem iguais, eles sempre terão os mesmos hashCodes. Os hashCodes não devem ser percebidos como números pseudo-randoms, pois devem ser consistentes com equals ()

De acordo com o Java eficaz,

Sempre replace hashCode () quando você replace equals ()

bem por que? Simples, porque objects diferentes (conteúdo, não referências) devem receber códigos hash diferentes; por outro lado, objects iguais devem obter o mesmo código hash.

De acordo com o acima, as estruturas de dados associativas Java comparam os resultados obtidos pelas chamadas equals () e hashCode () para criar os buckets. Se ambos forem iguais, os objects são iguais; de outra forma não.

No caso específico (ou seja, o apresentado acima), quando hashCode () é comentado , um número random é gerado para cada instância (comportamento herdado por Object) como hash, o equals () verifica as referências de String (lembre-se de Java String Pool) então o equals () deve retornar true mas o hashCode () não, o resultado é 3 objects diferentes armazenados . Vamos ver o que acontece no caso de o hashCode () respeitar o contrato, mas retornar sempre 9, é descomentado . Bem, hashCode () é constantemente o mesmo, o equals () retorna true para as duas Strings no Pool (ex: “Monday”), e para elas o bucket será o mesmo resultando em apenas 2 elementos armazenados .

Portanto, é necessário ter cuidado ao usar a substituição hashCode () e equals (), em especial quando os tipos de dados compostos são definidos pelo usuário e são usados ​​com estruturas de dados associativas Java.

Quando o hashCode é descomentado, o HashMap vê t1 e t2 como sendo a mesma coisa; assim, o valor de t2 atrapalha o de t1. Para entender como isso funciona, observe que quando o hashCode retorna a mesma coisa para duas instâncias, eles acabam indo para o mesmo bucket do HashMap. Quando você tenta inserir uma segunda coisa no mesmo bucket (nesse caso, t2 está sendo inserido quando t1 já está presente), o HashMap varre o bucket para outra chave que é igual a. No seu caso, t1 e t2 são iguais porque têm o mesmo dia. Nesse ponto, “payBills” clobbers “doLaundry”. Quanto ao fato de t2 acertar t1 como chave, acredito que isso seja indefinido; assim, qualquer comportamento é permitido.

Existem algumas coisas importantes para pensar aqui:

  1. Duas instâncias do ToDos são realmente iguais apenas porque têm o mesmo dia da semana?
  2. Sempre que você implementar equals, você deve implementar o hashCode para que quaisquer dois objects que sejam iguais também tenham os mesmos valores de hashCode. Esta é uma suposição fundamental que o HashMap faz. Isso provavelmente também vale para qualquer outra coisa que dependa do método hashCode.
  3. Projete seu método hashCode para que os códigos hash sejam distribuídos uniformemente; caso contrário, você não obterá os benefícios de desempenho do hashing. Dessa perspectiva, retornar 9 é uma das piores coisas que você pode fazer.

Em vez de pensar em hashCode em termos de mapeamento de hash-bucket, acho que é mais útil pensar um pouco mais abstratamente: uma observação de que dois objects têm códigos hash diferentes constitui uma observação de que os objects não são iguais. Como conseqüência disso, uma observação de que nenhum dos objects em uma coleção tem um código hash particular constitui uma observação de que nenhum dos objects em uma coleção é igual a qualquer object que tenha esse código hash. Além disso, uma observação de que nenhum dos objects em uma coleção tem um código hash com algum traço constitui uma observação de que nenhum deles é igual a qualquer object que tenha.

Tabelas de hash geralmente funcionam definindo uma família de características, exatamente uma das quais será aplicável ao código hash de cada object (por exemplo, “sendo congruente a 0 mod 47”, “sendo congruente a 1 mod 47”, etc.) e tendo uma coleção de objects com cada traço. Se alguém recebe um object e pode determinar qual característica se aplica a ele, pode-se saber que ele deve estar em uma coleção de coisas com esse traço.

Essas tabelas de hash geralmente usam uma sequência de buckets numerados é um detalhe de implementação; o essencial é que o código hash de um object seja usado rapidamente para identificar muitas coisas às quais ele não pode ser igual e com as quais ele não terá que ser comparado.

Sempre que você criar um novo object em Java, ele receberá um código hash exclusivo pela própria JVM. Se você não replace o método hashcode, o object receberá um hascode exclusivo e, portanto, um bucket exclusivo (o bucket Imagine não é mais do que um local na memory onde a JVM irá para localizar um object).

(você pode verificar a exclusividade de um código hash chamando o método hashcode em cada object e imprimindo seus valores no console)

No seu caso, quando você não está comentando o método hashcode, o hashmap primeiro procura pelo bucket que possui o mesmo hashcode retornado pelo método. E toda vez que você está retornando o mesmo hashcode. Agora, quando o hashmap localiza esse bucket, ele compara o object atual com o object que reside no bucket usando o método euqals. Aqui encontra “segunda-feira” e assim a implementação de hashmap não permite adicioná-lo novamente porque já existe um object com o mesmo hashcode e a mesma implementação de euqality.

Quando você comenta o método hashcode, a JVM simplesmente retorna o hashcode diferente para todos os três objects e, portanto, ele nunca se incomoda em usar objects iguais usando o método equals. E assim, haverá três objects diferentes no Mapa adicionados pela implementação do hashmap.