集合的hashCode方法的最佳实现
我们如何决定集合的hashCode()
方法的最佳实现(假设equals方法已被正确覆盖)?
最好的实施? 这是一个难题,因为它取决于使用模式。
对于几乎所有情况,在Josh Bloch的第8版(第二版)的Effective Java中提出了合理的良好实现。 最好的事情是在那里查找,因为作者解释了为什么这种方法是好的。
一个简短的版本
-
创建一个
int result
并指定一个非零值。 -
对于在
equals()
方法中测试的每个字段f
,通过以下方式计算哈希码c
:- 如果字段f是
boolean
:calculate(f ? 0 : 1)
; - 如果字段f是
byte
,char
,short
或int
:calculate(int)f
; - 如果字段f是
long
:calculate(int)(f ^ (f >>> 32))
; - 如果字段f是
float
:计算Float.floatToIntBits(f)
; - 如果字段f是
double
:计算Double.doubleToLongBits(f)
并像每个long值一样处理返回值; - 如果字段f是一个对象 :使用
hashCode()
方法的结果,如果f == null
,则使用0; - 如果字段f是一个数组 :将每个字段视为单独的元素,并以递归方式计算散列值,并按照下面的描述组合这些值。
- 如果字段f是
-
将哈希值
c
与result
:result = 37 * result + c
-
返回
result
这应该导致大多数使用情况的哈希值的正确分布。
如果您对dmeister推荐的Effective Java实现感到满意,可以使用库调用而不是自己编译:
@Override public int hashCode(){ return Objects.hashCode(this.firstName, this.lastName); }
这需要guava( com.google.common.base.Objects.hashCode(...)
)或JDK7( java.util.Objects.hash(...)
),但工作方式相同。
最好使用Eclipse提供的function,它可以很好地完成工作,您可以将您的精力和精力投入到开发业务逻辑中。
虽然这与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)); }
首先确保正确实现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()值
最后,一个好的哈希函数应该努力接近理想的哈希函数 。
你说的是about8.blogspot.com
如果equals()为两个对象返回true,则hashCode()应该返回相同的值。 如果equals()返回false,则hashCode()应返回不同的值
我不能同意你的看法。 如果两个对象具有相同的哈希码,则不一定意味着它们是相等的。
如果A等于B,那么A.hashcode必须等于B.hascode
但
如果A.hashcode等于B.hascode,那并不意味着A必须等于B
在Apache Commons Lang中 有效实现了Effective Java的hashcode()
和equals()
逻辑。 Checkout HashCodeBuilder和EqualsBuilder 。
如果使用eclipse,则可以使用以下命令生成equals()
和hashCode()
:
Source – >生成hashCode()和equals()。
使用此函数,您可以决定要用于相等和散列码计算的字段 ,Eclipse会生成相应的方法。
只需快速填写其他更详细的答案(代码方面):
如果我考虑如何创建一个哈希表在java中的问题 ,特别是jGuru FAQ条目 ,我相信可以判断哈希码的其他一些标准是:
- 同步(算法是否支持并发访问)?
- 失败安全迭代(算法是否检测到在迭代期间发生变化的集合)
- null值(哈希代码是否支持集合中的空值)
如果我正确理解你的问题,你有一个自定义集合类(即从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); }
@ 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吗?我认为它会进行一些autocasting ..如果是这种情况,请跳过toString,这很难看。)
正如您特别要求收集的那样,我想添加一个其他答案尚未提及的方面:HashMap不希望他们的密钥在添加到集合后更改其哈希码。 会打败整个目的……
在Apache Commons EqualsBuilder和HashCodeBuilder上使用reflection方法。
在可能的范围内均匀分布哈希值的任何哈希方法都是一个很好的实现。 查看有效的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项,我认为……)。
我更喜欢使用来自对象类的Google Collections lib中的实用程序方法来帮助我保持代码清洁。 通常equals
和hashcode
方法是从IDE的模板制作的,因此它们不易读取。
我在Arrays.deepHashCode(...)
周围使用一个小包装器,因为它正确处理作为参数提供的数组
public static int hash(final Object... objects) { return Arrays.deepHashCode(objects); }
这是另一个JDK 1.7+方法演示,其中包含超类逻辑。 我认为它非常方便Object类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 first; List second; ListPair(List first, List 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。
在不同的地方使用不同的乘数是有帮助的,但可能不足以certificate额外的工作是正确的。
组合哈希值时,我通常使用boost c ++库中使用的组合方法,即:
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
这在确保均匀分布方面做得相当不错。 有关此公式如何工作的一些讨论,请参阅StackOverflowpost: boost :: hash_combine中的幻数
有关不同哈希函数的讨论很好: http : //burtleburtle.net/bob/hash/doobs.html
对于一个简单的类,通常最容易基于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()应返回不同的值。