java - 集合的 hashCode 方法的最佳实现

Question

我们如何决定hashCode()集合方法的最佳实现（假设 equals 方法已被正确覆盖）？

Answer 1

最好的实现？这是一个难题，因为它取决于使用模式。

在Josh Bloch的 Effective Java的第 8 条（第二版）中，几乎所有情况下都提出了合理的良好实现。最好的办法是在那里查找，因为作者在那里解释了为什么这种方法很好。

一个简短的版本

1. 创建一个int result并分配一个非零值。

2. 对于方法中测试的每个字段 ，通过以下方式计算哈希码：fequals()c

   • 如果字段 f 是 a boolean：计算(f ? 0 : 1)；
   • 如果字段 f 是 a byte, char,short或int: 计算(int)f;
   • 如果字段 f 是 a long：计算(int)(f ^ (f >>> 32))；
   • 如果字段 f 是 a float：计算Float.floatToIntBits(f)；
   • 如果字段 f 是 a double：像每个 long 值一样计算Double.doubleToLongBits(f)和处理返回值；
   • 如果字段 f 是一个对象：使用hashCode()方法的结果或 0 if f == null;
   • 如果字段 f 是一个数组：将每个字段视为单独的元素，并以递归方式计算散列值，然后将这些值组合起来，如下所述。

3. 将哈希值c与result：

   result = 37 * result + c
   

4. 返回result

对于大多数使用情况，这应该会导致哈希值的正确分布。

Answer 2

如果您对 dmeister 推荐的 Effective Java 实现感到满意，您可以使用库调用而不是自己滚动：

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

这需要 Guava ( com.google.common.base.Objects.hashCode) 或 Java 7 ( ) 中的标准库，java.util.Objects.hash但工作方式相同。

Answer 3

尽管这与Github上的Android文档（Wayback Machine）和我自己的代码相关联，但它通常适用于 Java。我的答案是dmeister 的答案的扩展，代码更易于阅读和理解。

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

}

编辑

通常，当您覆盖 时hashcode(...)，您还希望覆盖equals(...)。所以对于那些将要或已经实施的人equals，这里是我的 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 4

最好使用Eclipse提供的功能，它做得很好，你可以把你的精力和精力放在开发业务逻辑上。

Answer 5

首先确保equals正确实现。来自IBM DeveloperWorks 文章：

• 对称性：对于两个引用，a 和 b，a.equals(b) 当且仅当 b.equals(a)
• 自反性：对于所有非空引用，a.equals(a)
• 传递性：如果 a.equals(b) 和 b.equals(c)，那么 a.equals(c)

然后确保他们与 hashCode 的关系尊重联系人（来自同一篇文章）：

• 与 hashCode() 的一致性：两个相等的对象必须具有相同的 hashCode() 值

最后，一个好的散列函数应该努力接近理想的散列函数。

Answer 6

about8.blogspot.com，你说

如果 equals() 对两个对象返回 true，则 hashCode() 应该返回相同的值。如果 equals() 返回 false，则 hashCode() 应该返回不同的值

我不能同意你的看法。如果两个对象具有相同的哈希码，则不一定意味着它们相等。

如果 A 等于 B 则 A.hashcode 必须等于 B.hascode

但

如果 A.hashcode 等于 B.hascode 这并不意味着 A 必须等于 B

Answer 7

在Apache Commons Lang中有一个有效的 Javahashcode()和equals()逻辑的良好实现。结帐HashCodeBuilder和EqualsBuilder。

Answer 8

如果你使用eclipse，你可以生成equals()和hashCode()使用：

源 -> 生成 hashCode() 和 equals()。

使用此功能，您可以决定要使用哪些字段进行相等和哈希码计算，Eclipse 会生成相应的方法。

Answer 9

只是一个快速说明完成其他更详细的答案（在代码方面）：

如果我考虑how-do-i-create-a-hash-table-in-java这个问题，尤其是jGuru FAQ entry，我相信可以判断哈希码的其他一些标准是：

• 同步（算法是否支持并发访问）？
• 失败安全迭代（算法是否检测到在迭代期间发生变化的集合）
• 空值（哈希码是否支持集合中的空值）

Answer 10

如果我正确理解了您的问题，那么您有一个自定义集合类（即从 Collection 接口扩展的新类）并且您想要实现 hashCode() 方法。

如果您的集合类扩展了 AbstractList，那么您不必担心它，已经有一个 equals() 和 hashCode() 的实现，它通过遍历所有对象并将它们的 hashCodes() 添加在一起来工作。

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

现在，如果您想要的是计算特定类的哈希码的最佳方法，我通常使用 ^（按位异或）运算符来处理我在 equals 方法中使用的所有字段：

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

Answer 11

@about8：那里有一个非常严重的错误。

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

相同的哈希码

你可能想要类似的东西

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

（这些天你可以直接从 Java 中的 int 获取 hashCode 吗？我认为它会进行一些自动转换。如果是这种情况，请跳过 toString，它很难看。）

Answer 12

正如您特别要求收集的那样，我想添加其他答案尚未提及的一个方面： HashMap 不希望它们的键在添加到集合后更改其哈希码。会破坏整个目的......

Answer 13

在 Apache Commons EqualsBuilder和HashCodeBuilder上使用反射方法。

Answer 14

我使用了一个很小的包装器，Arrays.deepHashCode(...)因为它可以正确处理作为参数提供的数组

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

Answer 15

任何在可能范围内均匀分布散列值的散列方法都是一个很好的实现。查看有效的java（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），有一个很好的提示在那里用于实现哈希码（我认为是第 9 项......）。

Answer 16

我更喜欢使用来自类 Objects 的 Google Collections lib中的实用方法，这有助于我保持代码整洁。很多时候equals，hashcode方法是由 IDE 的模板制作的，所以它们读起来不干净。

Answer 17

这是另一个包含超类逻辑的 JDK 1.7+ 方法演示。我认为它非常方便使用 Object class hashCode() 计算，纯 JDK 依赖并且没有额外的手动工作。请注意Objects.hash()是零容忍的。

我没有包括任何equals()实现，但实际上你当然会需要它。

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

标准实现很弱，使用它会导致不必要的冲突。想象一个

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

    ...
}

现在，

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

和

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

具有相同的hashCode，即31*(a+b) + c用于List.hashCode在这里重用的乘数。显然，碰撞是不可避免的，但产生不必要的碰撞只是......不必要的。

使用31. 乘数必须为奇数以避免丢失信息（任何偶数乘数至少会丢失最高有效位，四的倍数会丢失二，等等）。任何奇数乘数都是可用的。小的乘法器可能会导致更快的计算（JIT 可以使用移位和加法），但考虑到乘法在现代 Intel/AMD 上只有三个周期的延迟，这无关紧要。小的乘数也会导致小输入的更多冲突，这有时可能是一个问题。

使用素数是没有意义的，因为素数在环 Z/(2**32) 中没有意义。

所以，我建议使用随机选择的大奇数（随意取质数）。由于 i86/amd64 CPU 可以对适合单个有符号字节的操作数使用更短的指令，因此对于像 109 这样的乘法器有微小的速度优势。为了最大限度地减少冲突，请使用 0x58a54cf5 之类的东西。

在不同的地方使用不同的乘数是有帮助的，但可能不足以证明额外的工作是合理的。

Answer 19

在组合哈希值时，我通常使用 boost c++ 库中使用的组合方法，即：

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

这在确保均匀分布方面做得相当好。有关此公式如何工作的一些讨论，请参阅 StackOverflow 帖子：Boost::hash_combine 中的魔数

在以下位置对不同的哈希函数进行了很好的讨论：http: //burtleburtle.net/bob/hash/doobs.html

Answer 20

对于一个简单的类，通常最容易实现 hashCode() 基于由 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;
    }
}

最重要的是保持 hashCode() 和 equals() 一致：如果 equals() 对两个对象返回 true，则 hashCode() 应该返回相同的值。如果 equals() 返回 false，则 hashCode() 应该返回不同的值。