Como garantir hashCode () é consistente com equals ()?

Question

Ao substituir os métodos equals () função do java.lang.Object, os javadocs sugerem que,

é geralmente necessário substituir o método hashCode sempre que este método é substituído, de modo a manter o contrato geral para o método hashCode, que afirma que objetos iguais devem ter códigos de hash iguais.

O método hashCode () deve retornar a inteiro único para cada objeto (isto é fácil de fazer quando se compara objetos com base na localização de memória, basta devolver o inteiro único endereço do objeto)

Como deve um método hashCode () ser anulado para que ele retorne a inteiro único para cada objeto com base apenas em properities desse objeto?

public class People{
   public String name;
   public int age;

   public int hashCode(){
      // How to get a unique integer based on name and age?
   }
}
/*******************************/
public class App{
   public static void main( String args[] ){
       People mike = new People();
       People melissa = new People();
       mike.name = "mike";
       mike.age = 23;
       melissa.name = "melissa";
       melissa.age = 24;
       System.out.println( mike.hasCode() );  // output?
       System.out.println( melissa.hashCode(); // output?
   }
}

Answer 1

Ele não diz o hashcode para um objeto tem que ser completamente original, apenas que o hashcode para dois objetos iguais retorna o mesmo código hash. É perfeitamente legal ter dois objetos não-iguais retornar o mesmo código hash. No entanto, a distribuição mais original um hashcode é sobre um conjunto de objetos, o melhor desempenho que você vai sair de HashMaps e outras operações que usam o hashCode.

IDEs como IntelliJ Idea tem built-in geradores para equals e hashCode, que geralmente fazem um trabalho muito bom na vinda acima com o código "bom o suficiente" para a maioria dos objetos (e provavelmente melhor do que algumas funções hash excessivamente inteligentes artesanais ).

Por exemplo, aqui está uma função hashCode que Idea gera para a sua classe Pessoas:

public int hashCode() {
    int result = name != null ? name.hashCode() : 0;
    result = 31 * result + age;
    return result;
}

Answer 2

Eu não vou entrar para os detalhes da singularidade hashCode como Marc já abordou isso. Para sua classe People, primeiro você precisa decidir o que a igualdade de um meio pessoa. Talvez a igualdade é baseada unicamente em seu nome, talvez ele é baseado no nome e idade. Será específica de domínio. Vamos igualdade dizer é baseado no nome e idade. Seu equals substituído pareceria

public boolean equals(Object obj) {
    if (this==obj) return true;
    if (obj==null) return false;
    if (!(getClass().equals(obj.getClass())) return false;
    Person other = (Person)obj;
    return (name==null ? other.name==null : name.equals(other.name)) &&
        age==other.age;
}

Toda vez que você substituir equals você deve substituir hashCode. Além disso, hashCode não pode usar quaisquer mais campos em seu cálculo de equals fez. Na maioria das vezes você deve adicionar ou exclusivo, ou o código de hash dos vários campos (hashCode deve ser rápido para computação). Assim, um método hashCode válido pode parecer:

public int hashCode() {
    return (name==null ? 17 : name.hashCode()) ^ age;
}

Observe que o seguinte é não é válido como ele usa um campo que equals não (altura). Neste caso dois "é igual a" objetos poderia ter um código de hash diferente.

public int hashCode() {
    return (name==null ? 17 : name.hashCode()) ^ age ^ height;
}

Além disso, é perfeitamente válido para dois não é igual a objetos para ter o mesmo código de hash:

public int hashCode() {    
    return age;    
}

Neste caso Jane 30 anos de idade não é igual ao Bob 30 anos de idade, mas ambos os seus códigos de hash são 30. Enquanto válida esta é indesejável para o desempenho em coleções baseadas em hash.

Answer 3

Outra questão pergunta se há algumas coisas básicas de baixo nível que todos os programadores devem saber, e eu acho que as pesquisas de hash é um daqueles. Então aqui vai.

A tabela hash (note que eu não estou usando um nome de classe real) é basicamente um conjunto de listas ligadas. Para encontrar algo na tabela, você primeiro calcular o código hash de que alguma coisa, então mod pelo tamanho da tabela. Este é um índice para a matriz, e você terá uma lista ligada nesse índice. Você, então, percorrer a lista até encontrar o seu objeto.

Uma vez que a recuperação matriz é O (1), e ligada lista travessia é O (n), você quer uma função hash que cria a distribuição de um aleatório quanto possível, de modo que os objetos serão hash para diferentes listas. Cada objeto pode retornar o valor 0 como seu hashcode, e uma tabela hash iria trabalhar ainda, mas seria essencialmente uma lista ligada longa no elemento 0 da matriz.

Você também geralmente querem a matriz para ser grande, o que aumenta as chances de que o objeto estará em uma lista de comprimento 1. O Java HashMap, por exemplo, aumenta o tamanho da matriz quando o número de entradas no mapa é> 75% do tamanho da matriz. Há uma troca aqui: você pode ter uma enorme variedade com muito poucas entradas e memória de resíduos, ou uma matriz menor, onde cada elemento na matriz é uma lista com> 1 entradas, e desperdiçar travessia tempo. Um hash perfeito seria atribuir a cada objecto para uma localização única na matriz, com nenhum espaço desperdiçado.

O termo "de hash perfeito" é um termo real, e em alguns casos você pode criar uma função hash que fornece um número único para cada objeto. Isso só é possível quando você sabe que o conjunto de todos os valores possíveis. No caso geral, você não pode conseguir isso, e haverá alguns valores que retornam o mesmo código hash. Esta é matemática simples:. Se você tem uma cadeia que é mais do que 4 bytes de comprimento, você não pode criar um único hashcode de 4 bytes

Um fato interessante:. Matrizes de hash são geralmente dimensionados com base em números primos, para dar a melhor chance de alocação aleatória quando você mod os resultados, independentemente de quão aleatória os hashcodes realmente são

Editar com base em comentários:

1) Uma lista ligada não é a única maneira de representar os objetos que têm o mesmo código hash, apesar de que é o método utilizado pelo JDK 1.5 HashMap. Embora menos memória-eficiente do que uma matriz simples, ele, sem dúvida, criar menos churn quando requentar (porque as entradas podem ser desvinculados de um balde e relinked para outro).

2) A partir de JDK 1.4, a classe HashMap utiliza uma matriz dimensionada como uma potência de 2; antes que ele usou 2 ^ N + 1, que, creio, é primordial para N <= 32. Isso não acelerar de indexação de matriz per se, mas não permite que o índice de matriz para ser computado com um bit a bit E, em vez de uma divisão, como observado por Neil Coffey. Pessoalmente, eu questiono isso como otimização prematura, mas dada a lista de autores sobre HashMap, eu vou assumir existe algum benefício real.

Answer 4

Em geral, o código hash não pode ser único, uma vez que existem mais valores que possíveis códigos de hash (inteiros). Um código de hash boa distribui os valores bem sobre os inteiros. Um mau pode sempre dar o mesmo valor e ainda ser logicamente correta, seria apenas levar a tabelas hash inaceitavelmente ineficientes.

Os valores iguais devem ter o mesmo valor de hash para tabelas de hash para funcionar corretamente. Caso contrário, você pode adicionar uma chave para uma tabela hash, em seguida, tentar procurá-lo através de um valor igual a um código hash diferente e não encontrá-lo. Ou você poderia colocar um valor igual com um código de hash diferentes e têm dois valores iguais em locais diferentes na tabela de hash.

Na prática, você geralmente selecionar um subconjunto dos campos a serem tidos em conta, tanto no hashCode () e equals () método.

Answer 5

Eu acho que você entendeu mal. O hashcode não tem que ser exclusivo para cada objeto (afinal de contas, é um código hash), embora obviamente você não quer que ele seja idêntico para todos os objetos. Você faz, no entanto, precisa que ele seja idêntico a todos os objetos que são iguais, caso contrário, coisas como as coleções padrão não iria funcionar (por exemplo, você poderia procurar algo no conjunto de hash, mas não iria encontrá-lo).

Para atributos simples, algumas IDEs têm função construtores hashcode.

Se você não usar IDEs, considere o uso Apahce Commons eo HashCodeBuilder classe

Answer 6

A obrigação só contratual para hashCode é para que seja consistente . Os campos usados ??na criação do valor hashCode deve ser o mesmo ou um subconjunto dos campos usados ??no método iguais. Isto significa que retornam 0 para todos os valores é válido, embora não seja eficiente.

Pode-se verificar se hashCode é consistente através de um teste de unidade. Eu escrito uma classe abstrata chamada EqualityTestCase , que faz um punhado de cheques hashCode. Um simplesmente tem que estender o caso de teste e implementar dois ou três métodos de fábrica. O teste faz um trabalho muito grosseira de testar se o hashCode é eficiente.

Answer 7

Isto é o que a documentação diz-nos como para o método de código hash

@ javadoc

Sempre que é chamado em o mesmo objecto de mais do que uma vez durante uma execução de um aplicativo Java, o método hashCode must consistentemente retornar o mesmo número inteiro, sem fornecida informações utilizadas em igual comparações sobre o objecto é modificado. este necessidade inteiro não permanecem consistentes de uma execução de uma aplicação para outra execução do mesmo aplicação.

Answer 8

Há uma noção de chave de negócios, que determina singularidade de instâncias separadas do mesmo tipo. Cada tipo específico (classe) que os modelos de uma entidade separada do domínio de destino (por exemplo, veículo em um sistema de frotas) deve ter uma chave de negócios, que é representado por um ou mais campos de classe. Métodos equals () e hasCode () ambos devem ser implementados usando os campos, que compõem uma chave de negócios. Isto assegura que ambos os métodos consistentes com os outros.