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

Question

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

Answer 1

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

A 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). A melhor coisa a fazer é procurá-lo lá porque o autor explica por que há a abordagem é bom.

A versão curta

1. Criar um int result e atribuir um diferente de zero valor.

2. Para todos os campos f testado no método equals(), calcular um c código hash por:

   • Se o campo f é um boolean: Calcular (f ? 0 : 1);
   • Se o campo f é um byte, char, short ou int: (int)f calcular;
   • Se o campo f é um long: (int)(f ^ (f >>> 32)) calcular;
   • Se o campo f é um float: Float.floatToIntBits(f) calcular;
   • Se o campo f é um double: Double.doubleToLongBits(f) calcular e manipular o valor de retorno como qualquer valor a longo;
   • Se o campo f é um objeto : Use o resultado do método hashCode() ou 0 se f == null;
   • Se o campo f é um array : ver cada campo como elemento separado e calcular o valor de hash em um forma recursiva e combinar os valores conforme descrito a seguir.

3. Combine o valor de hash c com result:

   result = 37 * result + c
   

4. Voltar result

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

Answer 2

Se você está feliz com a implementação Java Effective recomendado por dmeister, você pode usar uma chamada de biblioteca, em vez de rolar seus próprios:

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

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

Answer 3

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

Answer 4

Embora este está ligado a documentação Android (Wayback Machine) e meu próprio código no Github , ele vai trabalhar para Java em geral. Minha resposta é uma extensão do de dmeister Resposta com apenas código que é muito mais fácil de ler e compreender.

@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ê substituir hashcode(...), você também quiser substituir equals(...). Portanto, para aqueles que serão ou já implementou 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));
}

Answer 5

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

• Symmetry: Para duas referências, a e b, a.Equals (b) se e somente se b.equals (a)
• 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, certifique-se de que a sua relação com aspectos hashCode o contato (do mesmo artigo):

• Coerência com hashCode (): objetos Dois iguais devem ter o mesmo valor hashCode ()

Finalmente uma boa função hash deve se esforçar para se aproximar do função ideal de hash .

Answer 6

about8.blogspot.com, você disse

Se iguais () retorna true para dois objetos, em seguida, hashCode () deve retornar o mesmo valor. Se iguais () retorna falso, então hashCode () deve retornar valores diferentes

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

Se A é igual a B, em seguida, A.hashcode deve ser igual a B.hascode

e

Se A.hashcode igual B.hascode isso não significa que uma obrigação é igual a B

Answer 7

Se você usar o eclipse, você pode gerar equals() e hashCode() usando:

Source -> Gerar hashCode () e equals ().

Com esta função você pode decidir que campos que você deseja usar para a igualdade e cálculo código hash, e Eclipse gera os métodos correspondentes.

Answer 8

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

Answer 9

Apenas uma nota rápida para completar outra resposta mais detalhada (em termos de código):

Se eu considerar a questão how-do-i- criar-uma-mistura-mesa-de-Java e especialmente o jGuru FAQ entrada , eu acredito que alguns outros critérios em que um código hash podem ser julgados são:

• sincronização (faz o acesso simultâneo apoio algo ou não)?
• falhar iteração segura (não o algo detectar uma coleção que muda durante a iteração)
• valor nulo (faz o valor nulo apoio código de hash na coleção)

Answer 10

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

Se a sua classe de coleção estende AbstractList, então você não precisa se preocupar com isso, já existe uma implementação de equals () e hashCode () que obras de iteração através de 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ê quer é a melhor maneira de calcular o código hash para uma classe específica, que normalmente usa 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);
}

Answer 11

@ about8: há um erro muito sério lá.

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

mesmo hashcode

você provavelmente vai querer algo como

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

(você pode obter hashCode diretamente de int em Java nos dias de hoje? Acho que faz algum autocasting .. se esse for o caso, ignore a toString, é feio.)

Answer 12

Como você pediu especificamente para coleções, eu gostaria de acrescentar um aspecto que as outras respostas ainda não mencionado: faz um HashMap não esperam que suas teclas para alterar a sua hashcode uma vez que eles são adicionados à coleção. Derrotaria o propósito ...

Answer 13

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

Answer 14

qualquer método de hashing, que distribui uniformemente o valor hash sobre a gama possível é uma boa aplicaçã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 ) , há uma boa dica lá para a implementação hashcode (ponto 9 eu acho ...).

Answer 15

Eu prefiro usar métodos utilitários Fromm Google Collections lib da classe Objetos que me ajuda a manter meu código limpo. Muitas vezes os métodos equals e hashcode são feitas a partir do modelo do IDE, pelo que a sua não estiverem limpos para ler.

Answer 16

Eu uso um pequeno invólucro em torno de Arrays.deepHashCode(...) porque ele lida com matrizes fornecidos como parâmetros corretamente

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

Answer 17

Aqui está outro JDK 1.7+ abordagem demonstração com lógicas superclasse contabilizados. Eu vejo isso como conveniente bonita com hashCode classe Object () representaram, dependência JDK pura e nenhum trabalho manual extra. Por favor, note Objects.hash() é nulo tolerante.

Eu não incluem qualquer implementação equals() mas na realidade você vai de necessidade claro que.

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

}

Answer 18

A implementação padrão é fraco e usá-lo 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))

tem o mesmo hashCode, nomeadamente 31*(a+b) + c como o multiplicador usado para List.hashCode é reutilizada aqui. Obviamente, as colisões são inevitáveis, mas produzir colisões desnecessárias é apenas ... desnecessária.

Não há nada de substancialmente inteligente sobre o uso 31. O multiplicador deve ser ímpar, a fim de evitar a perda de informações (qualquer perde mesmo multiplicador, pelo menos o bit mais significativo, múltiplos de quatro dois lose, etc.). Qualquer multiplicador estranho é utilizável. Pequenas multiplicadores pode levar a computação mais rápida (o JIT pode usar mudanças e adições), mas dado que a multiplicação tem latência de apenas três ciclos no moderno Intel / AMD, isso pouco importa. Pequenas multiplicadores também leva a mais de colisão para pequenas entradas, o que pode ser um problema às vezes.

Usando um nobre é inútil como primos não têm qualquer significado no anel Z / (2 ** 32).

Então, eu recomendo usar um grande número ímpar escolhidos aleatoriamente (sinta-se livre para dar uma prime). Como i86 / amd64 CPUs pode usar uma instrução mais curto para operandos montagem em um único byte assinado, há uma pequena vantagem de velocidade para multiplicadores como 109. Para minimizar colisões, tomar algo como 0x58a54cf5.

Usando diferentes multiplicadores em lugares diferentes é útil, mas provavelmente não o suficiente para justificar o trabalho adicional.

Answer 19

Ao combinar valores de hash, eu costumo usar o método da combinação que é usado no impulso c ++ biblioteca, a saber:

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

Este faz um bom trabalho de garantir uma distribuição uniforme. Por alguma discussão sobre como essa fórmula funciona, veja o post StackOverflow: Magic número em boost :: hash_combine

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

Answer 20

Para uma aula simples muitas vezes é mais fácil de implementar hashCode () com base nos campos de classe que são verificados pelos equals () implementação.

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

A coisa mais importante é manter hashCode () e equals () consistente: Se iguais () retorna true para dois objetos, em seguida, hashCode () deve retornar o mesmo valor. Se iguais () retorna falso, então hashCode () deve retornar valores diferentes.