集合的hashCode方法的最佳实现

我们如何决定一个集合的hashCode()方法的最佳实现(假设equals方法已被正确重写)?

268651 次浏览
小开

对于简单类，通常最容易基于equals()实现检查的类字段实现hashCode()。

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()应该返回不同的值。

小开

这里有一个非常严重的bug。

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

同样的hashcode

你可能想要

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

(现在你能在Java中直接从int获取hashCode吗?我认为它做了一些自动铸造。如果是这种情况，跳过toString，它很难看。)

小开

首先确保equals被正确实现。从一篇IBM DeveloperWorks文章:

  • 对称性:对于两个参考，a和b，当且仅当b等于(a)时，a等于(b)
  • 自反性:对于所有非空引用，a.equals(a)
  • 及物性:如果a等于(b) b等于(c)，那么a等于(c)

然后确保它们与hashCode的关系尊重联系人(来自同一篇文章):

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

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

小开

只是一个快速的注释，以完成其他更详细的答案(在代码方面):

如果我考虑问题how-do-i-create-a-hash-table-in-java，特别是jGuru常见问题，我相信可以判断哈希码的其他一些标准是:

  • 同步(算法是否支持并发访问)?
  • 失败安全迭代(算法是否检测到迭代过程中发生变化的集合)
  • 空值(哈希码是否支持集合中的空值)
小开

由于您特别要求集合，我想添加一个其他答案还没有提到的方面:HashMap不期望它们的键在添加到集合后改变它们的hashcode。会破坏整个目的…

小开

如果我正确理解你的问题，你有一个自定义的集合类(即一个从集合接口扩展的新类)，你想实现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);
}
小开

任何在可能的范围内均匀分布哈希值的哈希方法都是一个很好的实现。参见effective 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)，这里有一个关于hashcode实现的好提示(第9项我认为…)

小开
最佳答案

最好的实现?这是一个很难回答的问题，因为这取决于使用模式。

在Item 8(第二版)中的乔什•布洛赫的Java < / em > < em >有效中提出了几乎所有情况下的合理良好实现。最好的办法是去查一下，因为作者在那里解释了为什么这种方法是好的。

简短的版本

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

  2. 对于equals()方法中测试的每一个领域 f，通过以下方法计算哈希代码c:

    • 如果字段f是boolean: 李计算(f ? 0 : 1); < / >
    • 如果字段f是byte， char， short或int:计算(int)f;
    • 如果字段f是long:计算(int)(f ^ (f >>> 32));
    • 如果字段f是float:计算Float.floatToIntBits(f);
    • 如果字段f是double:计算Double.doubleToLongBits(f)并像处理每个长值一样处理返回值;
    • 如果字段f是对象:使用hashCode()方法的结果，如果f == null;
    • 如果字段f是数组:将每个字段视为单独的元素，并计算递归的方式中的哈希值，并将下面描述的值组合在一起。
      • 李< / ul > < / >
    • 将哈希值c与result组合:

      result = 37 * result + c

    • Return result

This should result in a proper distribution of hash values for most use situations.

小开

在Apache Commons Lang中有有效的Java的hashcode()和equals()逻辑的良好实现。签出HashCodeBuilder和EqualsBuilder。

小开

关于8.blogspot.com，你说过

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

我不同意你的看法。如果两个对象具有相同的hashcode，并不意味着它们是相等的。

如果A等于B，那么A.hashcode必须等于B.hascode

但

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

小开

我更喜欢使用来自谷歌类对象的集合库的实用程序方法，这有助于我保持代码干净。equals和hashcode方法通常是由IDE的模板创建的，所以它们的读取不干净。

小开

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

小开

如果你使用eclipse，你可以使用以下方法生成equals()和hashCode():

生成hashCode()和equals()。

使用这个函数，你可以决定要使用哪些字段来进行等式和哈希码计算，Eclipse会生成相应的方法。

小开

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

小开

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

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

这在确保平均分配方面做得相当好。有关这个公式如何工作的讨论，请参阅StackOverflow的帖子:boost::hash_combine中的魔法数字

http://burtleburtle.net/bob/hash/doobs.html中有关于不同哈希函数的很好的讨论

小开

如果你对dmeister推荐的Effective Java实现感到满意，你可以使用一个库调用来代替自己的调用:

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

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

小开

虽然这与Android文档(Wayback Machine)和我自己在Github上的代码相关联，但它一般适用于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));
}
小开

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

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

下面是另一个考虑超类逻辑的JDK 1.7+方法演示。我认为它对对象类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());
}


}
小开

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

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并没有什么实质上的聪明之处。乘数必须是奇数，以避免丢失信息(任何偶数乘数都会丢失至少最有效的位，4的倍数会丢失2位，等等)。任何奇数乘数都可用。小型乘法器可能会导致更快的计算(JIT可以使用移位和加法)，但考虑到乘法在现代英特尔/AMD上只有三个周期的延迟，这几乎无关紧要。小的乘法器也会导致小输入的碰撞更多，这有时可能是一个问题。

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

因此，我建议使用随机选择的大奇数(可以选择质数)。由于i86/amd64 cpu可以使用更短的指令来匹配一个有符号字节的操作数，因此对于像109这样的乘法器来说，速度优势很小。为了最小化冲突，可以使用类似0x58a54cf5的值。

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


提交答案