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

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)?

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.

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.

É 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.

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));
}

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 .

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

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.

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

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)

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);
}

@ 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.)

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 ...

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

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);
}

qualquer método de hash que distribua uniformemente o valor do hash no intervalo possível é uma boa implementação. Veja java eficaz ( http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=effective+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-D77qGj0wOxAxiZw&hl=en&sa=X&oi=book_result&resnum=1&ct=result ), não é uma boa dica lá para implementação de código hash (item 9 eu acho ...).

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.

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());
    }

}

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.

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

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.