一个好的哈希函数会为不等的对象产生不等的哈希码。理想情况下,哈希函数能够将不相等的实例均匀分不到所有可能的哈希值上。达到这个理想情况是很难的。幸运的是,达到近似理想情况并不十分困难,下面 是简单的秘诀:
1、用一个int类型的变量result 保存一个非零的常数,例如17。
2、针对对象中的每个关键字段f (即equals方法中涉及的每个字段),执行以下操作:
a. 计算该字段的哈希码:
如果字段是boolean类型,计算 (f 1 : 0)
如果字段是byte, char, short, int,计算 (int) f
如果字段是long,计算 (int) ( f ^ (f >>> 32))
如果字段是float,计算Float.floatToIntBits(f)
如果字段是double,计算Double.doubleToLongBits(f),然后对返回的long值进行上一步操作
如果字段是对象引用,并且该类的equals通过递归调用该对象引用的equals来比较这个字段,则递归调用该字段的hashCode;如果需要更复杂的比较,则为该字段计算一个范式(canonical representation),在该范式上调用hashCode;如果该字段为null,则返回0(也可以返回其他常数,但一般用0)
如果字段是数组,则将其每个元素当成一个单独字段来处理。如果数组中的每个元素都很重要,可以用Arrays.hashCode来处理。
b. 将Step2.a中得到的值c,合并到result中
result = 31 * result + c;
3、返回result
4、当你写完hashCode方法后,问问自己相同的实例是否返回相同的哈希码。编写单元测试来验证你的推论。
在哈希码的计算过程中,你可以排除掉冗余字段。换言之,如果一个字段的值 可以通过hashCode计算过程中的其他字段计算出来,则可以忽略掉这个字段。你必须排除掉在equals比较中没有用到的字段,否则就有可能违反hashCode约定的第二条。
在Step1中用了一个非零的初始值,所以Step2.a中计算得到哈希码为0的那些初始字段会影响到哈希值。如果Step1中的初始值为0,则最终的哈希值不会被这些初始字段影响,这样会增加冲突。值17是任选的。
Step2.b中的乘积使得计算结果依赖于字段顺序,如果类包含多个相似的字段,这样就会产生更好的哈希函数。【例】如果String类的hash函数忽略了乘积,则所有字符都具有相同的哈希码。
其中乘数选择31,是因为它是一个奇素数。如果选用偶数,并且乘法溢出,则信息会丢失,因为与2相乘等价于移位操作。使用素数的好处并不明显,不过习惯上这么用。31的一个很好的特性是,乘积可以用移位和减法来替代,以达到更好的性能:
[java]
31 * i == (i << 5) - i
31 * i == (i << 5) - i 现代VM会自动进行这种优化。
我们将上述诀窍应用于PhoneNumber类,它有三个重要字段,都是short类型:
[java]
@Override
public int hashCode() {
int result = 17;
result = 31 * result + areaCode;
result = 31 * result + prefix;
result = 31 * result + lineNumver;
return result;
}
@Override
public int hashCode() {
int result = 17;
result = 31 * result + areaCode;
result = 31 * result + prefix;
result = 31 * result + lineNumver;
return result;
}
如果想哈希函数达到艺术级别,最好留给科学家去研究……
不要试图在哈希码计算过程中排除掉任何重要字段以便提高性能。虽然这样哈希函数可能跑得更快,但是由于其质量不好,可能会降低哈希表的性能,以致哈希表慢到无法使用。特别是在实践中,哈希函数会面对大量的实例集合,这些实例恰恰在被你忽略的字段上有很大差异。如果是这样,那么哈希函数将把所有实例映射到少数几个哈希码上,以致基于哈希的集合显示出平方级的性能指标。
这可不仅仅是理论问题,JDK1.2之前版本中String类的哈希函数最多只检查16个字符,从第一个字符开始在整个字符串中均匀选取。对于像URL这种层级结构的字符串集合来说,这种哈希函数正好体现了这种病态行为。
Java平台包中的许多类,例如String、Integer、Date,都指定将其hashCode()方法返回的确切值作为实例值得一个函数。这通常不是个好主意,因为这限制了在后续版本中对哈希函数做改进的能力。而如果不指定hashCode()方法的细节,则如果以后发现了缺陷,或者找到了更好的哈希函数,那么就可以在后续版本中更改哈希函数,并确信没有客户端依赖于哈希函数返回的确切值。