Melhor implementação para o método hashCode para uma coleção

299

Como decidimos sobre a melhor implementação do hashCode()método para uma coleção (assumindo que o método equals foi substituído corretamente)?

Onipotente
fonte
2
com Java 7+, acho que Objects.hashCode(collection)deveria ser uma solução perfeita!
Diablo
3
@Diablo Eu não acho que isso responde a pergunta em tudo - esse método simplesmente retorna collection.hashCode()( hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/... )
cbreezier

Respostas:

438

A melhor implementação? Essa é uma pergunta difícil, porque depende do padrão de uso.

Um por quase todos os casos a aplicação razoável bom foi proposta em Josh Bloch 's Effective Java no item 8 (segunda edição). O melhor é procurar lá em cima, porque o autor explica por que a abordagem é boa.

Uma versão curta

  1. Crie um int resulte atribua um valor diferente de zero .

  2. Para cada campo f testado no equals()método, calcule um código de hash c:

    • Se o campo f for a boolean: calcule (f ? 0 : 1);
    • Se o campo f é um byte, char, shortou int: calcular (int)f;
    • Se o campo f for a long: calcule (int)(f ^ (f >>> 32));
    • Se o campo f for a float: calcule Float.floatToIntBits(f);
    • Se o campo f for a double: calcule Double.doubleToLongBits(f)e manipule o valor de retorno como todo valor longo;
    • Se o campo f for um objeto : use o resultado do hashCode()método ou 0 se f == null;
    • Se o campo f for uma matriz : veja todos os campos como elemento separado e calcule o valor do hash de maneira recursiva e combine os valores conforme descrito a seguir.
  3. Combine o valor do hash ccom result:

    result = 37 * result + c
  4. Retorna result

Isso deve resultar em uma distribuição adequada dos valores de hash para a maioria das situações de uso.

dmeister
fonte
45
Sim, estou particularmente curioso sobre de onde vem o número 37.
Kip
17
Usei o item 8 do livro "Effective Java" de Josh Bloch.
Dreister
39
@dma_k A razão para usar números primos e o método descrito nesta resposta é garantir que o código hash computado seja único . Ao usar números não primos, você não pode garantir isso. Não importa qual nummer nobre que você escolher, não há nada de mágico sobre o número 37 (muito ruim 42 não é um número primo, né?)
Simon Forsberg
34
@ SimonAndréForsberg Bem, o código hash calculado nem sempre pode ser único :) É um código hash. No entanto, tive a ideia: o número primo tem apenas um multiplicador, enquanto o não primo tem pelo menos dois. Isso cria uma combinação extra para o operador de multiplicação resultar no mesmo hash, ou seja, causar colisão.
21813 dma_k
140

Se você estiver satisfeito com a implementação Java Efetiva recomendada pela dmeister, poderá usar uma chamada de biblioteca em vez de fazer a sua própria:

@Override
public int hashCode() {
    return Objects.hashCode(this.firstName, this.lastName);
}

Isso requer o Guava ( com.google.common.base.Objects.hashCode) ou a biblioteca padrão no Java 7 ( java.util.Objects.hash), mas funciona da mesma maneira.

bacar
fonte
8
A menos que se tenha um bom motivo para não usá-los, definitivamente deve-se usá-los em qualquer caso. (Formulando-o mais forte, como IMHO deve ser formulado.) Aplicam-se os argumentos típicos para o uso de implementações / bibliotecas padrão (melhores práticas, bem testadas, menos propensas a erros, etc.).
Kissaki
7
@ justin.hughey você parece estar confuso. O único caso a ser substituído hashCodeé se você tiver um costume equals, e é exatamente para isso que esses métodos de biblioteca foram criados. A documentação é bastante clara sobre o comportamento deles em relação a equals. Uma implementação de biblioteca não alega que você não saiba quais são as características de uma hashCodeimplementação correta - essas bibliotecas facilitam a implementação de uma implementação em conformidade na maioria dos casos em que a equalssubstituição ocorre.
Bacar
6
Para qualquer desenvolvedor Android que observe a classe java.util.Objects, ela foi introduzida apenas na API 19, portanto, verifique se está executando o KitKat ou superior, caso contrário, você obterá NoClassDefFoundError.
Andrew Kelly
3
Melhor resposta IMO, embora, a título de exemplo, eu preferisse ter escolhido o java.util.Objects.hash(...)método JDK7 do que o com.google.common.base.Objects.hashCode(...)método goiaba . Eu acho que a maioria das pessoas escolheria a biblioteca padrão em vez de uma dependência extra.
Malte Skoruppa 04/11
2
Se houver dois argumentos ou mais e se algum deles for uma matriz, o resultado poderá não ser o que você espera, pois hashCode()para uma matriz é apenas o seu java.lang.System.identityHashCode(...).
starikoff
59

É melhor usar a funcionalidade fornecida pelo Eclipse, que faz um bom trabalho e você pode colocar seus esforços e energia no desenvolvimento da lógica de negócios.

Guerreiro
fonte
4
+1 Uma boa solução prática. A solução do dmeister é mais abrangente, mas costumo me esquecer de lidar com nulos quando tento escrever códigos de hash.
Quantum7
1
+1 Concordo com o Quantum7, mas eu diria que também é muito bom entender o que a implementação gerada pelo Eclipse está fazendo e de onde ela obtém seus detalhes de implementação.
Jwir3
15
Desculpe, mas as respostas que envolvem "funcionalidades fornecidas por [algum IDE]" não são realmente relevantes no contexto da linguagem de programação em geral. Existem dezenas de IDEs e isso não responde à pergunta ... ou seja, porque se trata mais de determinação algorítmica e diretamente associada à implementação equals () - algo sobre o qual um IDE nada saberá.
Darrell Teague
57

Embora isso esteja vinculado à Androiddocumentação (Wayback Machine) e ao meu próprio código no Github , ele funcionará para Java em geral. Minha resposta é uma extensão da resposta do dmeister com apenas um código que é muito mais fácil de ler e entender.

@Override 
public int hashCode() {

    // Start with a non-zero constant. Prime is preferred
    int result = 17;

    // Include a hash for each field.

    // Primatives

    result = 31 * result + (booleanField ? 1 : 0);                   // 1 bit   » 32-bit

    result = 31 * result + byteField;                                // 8 bits  » 32-bit 
    result = 31 * result + charField;                                // 16 bits » 32-bit
    result = 31 * result + shortField;                               // 16 bits » 32-bit
    result = 31 * result + intField;                                 // 32 bits » 32-bit

    result = 31 * result + (int)(longField ^ (longField >>> 32));    // 64 bits » 32-bit

    result = 31 * result + Float.floatToIntBits(floatField);         // 32 bits » 32-bit

    long doubleFieldBits = Double.doubleToLongBits(doubleField);     // 64 bits (double) » 64-bit (long) » 32-bit (int)
    result = 31 * result + (int)(doubleFieldBits ^ (doubleFieldBits >>> 32));

    // Objects

    result = 31 * result + Arrays.hashCode(arrayField);              // var bits » 32-bit

    result = 31 * result + referenceField.hashCode();                // var bits » 32-bit (non-nullable)   
    result = 31 * result +                                           // var bits » 32-bit (nullable)   
        (nullableReferenceField == null
            ? 0
            : nullableReferenceField.hashCode());

    return result;

}

EDITAR

Normalmente, quando você substitui hashcode(...), também deseja substituí-lo equals(...). Então, para aqueles que irão ou já implementaram equals, aqui está uma boa referência do meu Github ...

@Override
public boolean equals(Object o) {

    // Optimization (not required).
    if (this == o) {
        return true;
    }

    // Return false if the other object has the wrong type, interface, or is null.
    if (!(o instanceof MyType)) {
        return false;
    }

    MyType lhs = (MyType) o; // lhs means "left hand side"

            // Primitive fields
    return     booleanField == lhs.booleanField
            && byteField    == lhs.byteField
            && charField    == lhs.charField
            && shortField   == lhs.shortField
            && intField     == lhs.intField
            && longField    == lhs.longField
            && floatField   == lhs.floatField
            && doubleField  == lhs.doubleField

            // Arrays

            && Arrays.equals(arrayField, lhs.arrayField)

            // Objects

            && referenceField.equals(lhs.referenceField)
            && (nullableReferenceField == null
                        ? lhs.nullableReferenceField == null
                        : nullableReferenceField.equals(lhs.nullableReferenceField));
}
Christopher Rucinski
fonte
1
Documentação Android agora não inclui o código acima mais, então aqui é uma versão em cache do Wayback Machine - Documentação Android (Fev 07, 2015)
Christopher Rucinski
17

Primeiro, verifique se igual é implementado corretamente. De um artigo do IBM DeveloperWorks :

  • Simetria: Para duas referências, aeb, a.equals (b) se e somente se b.equals (a)
  • Reflexividade: para todas as referências não nulas, a.equals (a)
  • Transitividade: Se a.equals (b) e b.equals (c), então a.equals (c)

Em seguida, verifique se a relação deles com o hashCode respeita o contato (do mesmo artigo):

  • Consistência com hashCode (): dois objetos iguais devem ter o mesmo valor hashCode ()

Finalmente, uma boa função de hash deve se esforçar para abordar a função de hash ideal .

Pantera Cinza
fonte
11

about8.blogspot.com, você disse

se equals () retornar true para dois objetos, hashCode () deverá retornar o mesmo valor. Se equals () retornar false, hashCode () deverá retornar valores diferentes

Eu não posso concordar com você. Se dois objetos têm o mesmo código de hash, isso não significa que eles são iguais.

Se A for igual a B, então A.hashcode deve ser igual a B.hascode

mas

se A.hashcode for B.hascode, isso não significa que A deve ser igual a B

Átila
fonte
3
Se (A != B) and (A.hashcode() == B.hashcode()), é o que chamamos de colisão de função hash. É porque o codomain da função hash é sempre finito, enquanto o domínio geralmente não é. Quanto maior o codomain, menor a ocorrência de colisão. Boas funções de hash devem retornar hashes diferentes para objetos diferentes, com a maior possibilidade possível, dado o tamanho do codomain específico. Raramente isso pode ser totalmente garantido.
Krzysztof Jabłoński
Isso deve ser apenas um comentário para o post acima para Gray. Boa informação, mas ele realmente não responder à pergunta
Christopher Rucinski
Bons comentários, mas tenha cuidado ao usar o termo 'objetos diferentes' ... porque equals () e, portanto, a implementação hashCode () não são necessariamente objetos diferentes em um contexto OO, mas geralmente são mais sobre suas representações de modelo de domínio (por exemplo, duas as pessoas podem ser consideradas iguais se compartilharem um código e um ID de país - embora possam ser dois 'objetos' diferentes em uma JVM - eles são considerados 'iguais' e com um determinado código de hash) ...
Darrell Teague
7

Se você usar o eclipse, poderá gerar equals()e hashCode()usar:

Fonte -> Gerar hashCode () e igual a ().

Usando esta função, você pode decidir quais campos deseja usar para o cálculo da igualdade e do código de hash, e o Eclipse gera os métodos correspondentes.

Johannes K. Lehnert
fonte
7

Há uma boa implementação do Java Eficaz 's hashcode()e equals()lógica no Apache Commons Lang . Checkout HashCodeBuilder e EqualsBuilder .

Rudi Adianto
fonte
1
A desvantagem dessa API é que você paga o custo de construção do objeto toda vez que chamar igual e código de hash (a menos que seu objeto seja imutável e pré-calcule o hash), o que pode ser muito em certos casos.
James McMahon
essa era minha abordagem favorita, até recentemente. Corri para StackOverFlowError enquanto usava um critério para associação SharedKey OneToOne. Além disso , a Objectsclasse fornece hash(Object ..args)e equals()métodos a partir do Java7. Eles são recomendados para todos os aplicativos que usam jdk 1.7+
Diablo
@ Diablo eu acho, seu problema era um ciclo no gráfico de objetos e então você está sem sorte com a maioria das implementações, pois precisa ignorar alguma referência ou interromper o ciclo (exigindo um IdentityHashMap). FWIW Eu uso um hashCode baseado em id e é igual para todas as entidades.
Maaartinus
6

Apenas uma observação rápida para concluir outra resposta mais detalhada (em termos de código):

Se eu considerar a pergunta como criar uma tabela de hash em java e, especialmente, a entrada FAQ do jGuru , acredito que alguns outros critérios sobre os quais um código de hash possa ser julgado são:

  • sincronização (o algo suporta acesso simultâneo ou não)?
  • iteração segura contra falhas (o algo detecta uma coleção que muda durante a iteração)
  • valor nulo (o código de hash suporta valor nulo na coleção)
VonC
fonte
4

Se entendi sua pergunta corretamente, você tem uma classe de coleção personalizada (ou seja, uma nova classe que se estende da interface Collection) e deseja implementar o método hashCode ().

Se sua classe de coleção estender AbstractList, você não precisa se preocupar com isso, já existe uma implementação de equals () e hashCode () que funciona iterando todos os objetos e adicionando seus hashCodes () juntos.

   public int hashCode() {
      int hashCode = 1;
      Iterator i = iterator();
      while (i.hasNext()) {
        Object obj = i.next();
        hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
      }
  return hashCode;
   }

Agora, se o que você deseja é a melhor maneira de calcular o código de hash para uma classe específica, normalmente eu uso o operador ^ (bit a bit exclusivo ou) para processar todos os campos que eu uso no método equals:

public int hashCode(){
   return intMember ^ (stringField != null ? stringField.hashCode() : 0);
}
Mario Ortegón
fonte
2

@ about8: há um bug bastante sério lá.

Zam obj1 = new Zam("foo", "bar", "baz");
Zam obj2 = new Zam("fo", "obar", "baz");

mesmo código hash

você provavelmente quer algo como

public int hashCode() {
    return (getFoo().hashCode() + getBar().hashCode()).toString().hashCode();

(você pode obter o hashCode diretamente do int em Java hoje em dia? Eu acho que ele faz uma autocasting. Se esse for o caso, pule o toString, é feio.)

SquareCog
fonte
3
o bug está na resposta longa de about8.blogspot.com - obter o código hash de uma concatenação de strings deixa você com uma função hash que é a mesma para qualquer combinação de strings que se somam à mesma string.
SquareCog 22/09/08
1
Então isso é meta-discussão e não está relacionado à questão? ;-)
Huppie 22/09/08
1
É uma correção para uma resposta proposta que tem uma falha bastante significativa.
SquareCog 22/09/08
Esta é uma implementação muito limitada
Christopher Rucinski 15/09/2015
Sua implementação evita o problema e apresenta outro; Trocar fooe barleva ao mesmo hashCode. Seu toStringAFAIK não compila e, se o fizer, é terrivelmente ineficiente. Algo como 109 * getFoo().hashCode() + 57 * getBar().hashCode()é mais rápido, mais simples e não produz colisões desnecessárias.
Maaartinus
2

Como você solicitou especificamente coleções, gostaria de adicionar um aspecto que as outras respostas ainda não mencionaram: Um HashMap não espera que suas chaves alterem seu código de hash depois de adicionadas à coleção. Derrotaria todo o propósito ...

Olaf Kock
fonte
2

Use os métodos de reflexão no Apache Commons EqualsBuilder e HashCodeBuilder .

Vihung
fonte
1
Se você for usar isso, lembre-se de que a reflexão é cara. Eu honestamente não usaria isso para nada além de jogar fora o código.
James McMahon
2

Eu uso um invólucro minúsculo, Arrays.deepHashCode(...)porque ele lida com matrizes fornecidas como parâmetros corretamente

public static int hash(final Object... objects) {
    return Arrays.deepHashCode(objects);
}
starikoff
fonte
1

Prefiro usar métodos utilitários da biblioteca de coleções do Google da classe Objects que me ajuda a manter meu código limpo. Muitas vezes, equalse os hashcodemétodos são criados a partir do modelo do IDE, portanto, eles não são limpos para leitura.

nbro
fonte
1

Aqui está outra demonstração da abordagem do JDK 1.7+ com lógicas de superclasse contabilizadas. Eu vejo isso como bastante conveniente com a classe Object hashCode () contabilizada, pura dependência do JDK e nenhum trabalho manual extra. Observe que Objects.hash()é tolerante a nulos.

Não incluí nenhuma equals()implementação, mas, na realidade, é claro que você precisará dela.

import java.util.Objects;

public class Demo {

    public static class A {

        private final String param1;

        public A(final String param1) {
            this.param1 = param1;
        }

        @Override
        public int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param1);
        }

    }

    public static class B extends A {

        private final String param2;
        private final String param3;

        public B(
            final String param1,
            final String param2,
            final String param3) {

            super(param1);
            this.param2 = param2;
            this.param3 = param3;
        }

        @Override
        public final int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param2,
                this.param3);
        }
    }

    public static void main(String [] args) {

        A a = new A("A");
        B b = new B("A", "B", "C");

        System.out.println("A: " + a.hashCode());
        System.out.println("B: " + b.hashCode());
    }

}
Roman Nikitchenko
fonte
1

A implementação padrão é fraca e seu uso leva a colisões desnecessárias. Imagine um

class ListPair {
    List<Integer> first;
    List<Integer> second;

    ListPair(List<Integer> first, List<Integer> second) {
        this.first = first;
        this.second = second;
    }

    public int hashCode() {
        return Objects.hashCode(first, second);
    }

    ...
}

Agora,

new ListPair(List.of(a), List.of(b, c))

e

new ListPair(List.of(b), List.of(a, c))

têm o mesmo hashCode, nomeadamente 31*(a+b) + co multiplicador utilizado paraList.hashCode é reutilizado aqui. Obviamente, colisões são inevitáveis, mas produzir colisões desnecessárias é apenas ... desnecessário.

Não há nada substancialmente inteligente em usar 31. O multiplicador deve ser ímpar para evitar a perda de informações (qualquer multiplicador par perde pelo menos o bit mais significativo, múltiplos de quatro perdem dois, etc.). Qualquer multiplicador ímpar é utilizável. Pequenos multiplicadores podem levar a cálculos mais rápidos (o JIT pode usar turnos e acréscimos), mas, como a multiplicação tem latência de apenas três ciclos na moderna Intel / AMD, isso dificilmente importa. Pequenos multiplicadores também levam a mais colisão de pequenos insumos, o que às vezes pode ser um problema.

Usar um primo é inútil, pois os primos não têm significado no anel Z / (2 ** 32).

Portanto, eu recomendo usar um grande número ímpar escolhido aleatoriamente (sinta-se à vontade para tirar uma primo). Como as CPUs i86 / amd64 podem usar uma instrução mais curta para operandos que cabem em um único byte assinado, há uma pequena vantagem de velocidade para multiplicadores como 109. Para minimizar colisões, use algo como 0x58a54cf5.

O uso de multiplicadores diferentes em locais diferentes é útil, mas provavelmente não o suficiente para justificar o trabalho adicional.

maaartinus
fonte
0

Ao combinar valores de hash, geralmente uso o método de combinação usado na biblioteca boost c ++, a saber:

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

Isso faz um bom trabalho ao garantir uma distribuição uniforme. Para alguma discussão sobre como essa fórmula funciona, consulte a publicação StackOverflow: Número mágico no impulso :: hash_combine

Há uma boa discussão sobre diferentes funções de hash em: http://burtleburtle.net/bob/hash/doobs.html

Edward Loper
fonte
1
Esta é uma pergunta sobre Java, não C ++.
dano 10/10
-1

Para uma classe simples, geralmente é mais fácil implementar o hashCode () com base nos campos da classe que são verificados pela implementação equals ().

public class Zam {
    private String foo;
    private String bar;
    private String somethingElse;

    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }

        if (obj == null) {
            return false;
        }

        if (getClass() != obj.getClass()) {
            return false;
        }

        Zam otherObj = (Zam)obj;

        if ((getFoo() == null && otherObj.getFoo() == null) || (getFoo() != null && getFoo().equals(otherObj.getFoo()))) {
            if ((getBar() == null && otherObj. getBar() == null) || (getBar() != null && getBar().equals(otherObj. getBar()))) {
                return true;
            }
        }

        return false;
    }

    public int hashCode() {
        return (getFoo() + getBar()).hashCode();
    }

    public String getFoo() {
        return foo;
    }

    public String getBar() {
        return bar;
    }
}

O mais importante é manter o hashCode () e o equals () consistentes: se equals () retorna true para dois objetos, o hashCode () deve retornar o mesmo valor. Se equals () retornar false, hashCode () deverá retornar valores diferentes.

Chris Carruthers
fonte
1
Como SquareCog já notei. Se hashcode é gerada uma vez de concatenação de duas cadeias é extremamente fácil de gerar massas de colisões: ("abc"+""=="ab"+"c"=="a"+"bc"==""+"abc"). É uma falha grave. Seria melhor avaliar o código hash para ambos os campos e calcular a combinação linear deles (de preferência usando números primos como coeficientes).
Krzysztof Jabłoński
@ KrzysztofJabłoński Certo. Além disso, trocar fooe barproduzir uma colisão desnecessária também.
Maaartinus