文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
Item 9: 重写equals时必须重写hashCode
一个常见的错误来源是没有重写hashCode方。在每个重写equals方法的类中，你必须重写hashCode方法。不这样做会违反Object.hashCode的通用约定，这会使你的类不能在功能上与所有基于哈希的集合进行恰当的结合，包括HashMap，HashSet和Hashtable。
下面是这些约定，从Object规范中拷贝的[JavaSE6]：
-
假设同一个对象在进行
equals比较时没有修改信息，那么在一个应用执行期间，无论什么时候对同一个对象调用多次hashCode方法，它的hashCode方法都必须返回一个一致的整数。这个整数在应用多次执行期间不必保持一致。 -
如果两个对象根据
equals(Object)方法是相等的，那么调用每一个对象的hashCode方法必须产生同样的整数结果。 -
如果两个对象根据
equals(Object)方法不相等，不要求调用每一个对象的hashCode方法必须产生同样的整数结果。然而，程序员应该意识到对于不等的对象产生不同的整数结果可能改善哈希表的性能。
当不重写hashCode时，违反的第二条是关键约定：相等对象必须具有相等的哈希值。两个不同的对象根据类的equals方法可能在逻辑上是相等的，但对于Object的hashCode方法，它们是两个对象，没有共同的东西，因此Object的hashCode方法返回两个看似随机的数字来代替约定要求的相等数字。
public final class PhoneNumber {
private final short areaCode;
private final short prefix;
private final short lineNumber;
public PhoneNumber(int areaCode, int prefix, int lineNumber) {
rangeCheck(areaCode, 999, "area code");
rangeCheck(prefix, 999, "prefix");
rangeCheck(lineNumber, 9999, "line number");
this.areaCode = (short) areaCode;
this.prefix = (short) prefix;
this.lineNumber = (short) lineNumber;
}
private static void rangeCheck(int arg, int max, String name) {
if (arg < 0 || arg > max)
throw new IllegalArgumentException(name + ": " + arg);
}
@Override
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof PhoneNumber))
return false;
PhoneNumber pn = (PhoneNumber) o;
return pn.lineNumber == lineNumber && pn.prefix == prefix
&& pn.areaCode == areaCode;
}
// Broken - no hashCode method!
... // Remainder omitted
}
假设你试图在HashMap中使用这个类：
Map<PhoneNumber, String> m = new HashMap<PhoneNumber, String>();
m.put(new PhoneNumber(707, 867, 5309), "Jenny");
这时候，你可能期待m.get(new PhoneNumber(707, 867, 5309))返回Jenny，但它返回空。注意涉及到两个PhoneNumber实例：一个用来插入到HashMap，第二个相等的实例用来（试图）检索。PhoneNumber类没有重写hashCode方法引起两个相等的实例有不等的哈希值，违反了hashCode约定。因此get方法可能在一个与put方法储存的哈希桶不同的哈希桶中查找电话号码。即使两个实例碰到哈希到同一个桶中，get几乎必定返回空，因为HashMap缓存了每个输入相关的哈希吗，如果哈希码不匹配，不会检查对象的相等性。
修正这个问题很简单，为PhoneNumber类提供一个合适的hashCode方法。因此hashCode方法应该看起来是什么样的？编写一个合法但不好的方法是没意义的。例如，下面的方法合法但从未被用到：
// The worst possible legal hash function - never use!
@Override
public int hashCode() {
return 42;
}
它是合法的因为它保证了相等的对象有同样的哈希值。它是极差的因为它保证了每个对象都有同样的哈希值。因此，每个对象哈希到相同的桶中，哈希表退化成链表。程序从应该运行在线性时间内变成运行在平方时间内。对于打的哈希表，这是工作和不工作的区别。
一个好的哈希函数对于不等的对象趋向于产生不等的哈希值。这与hashCode约定中的第三条是一个意思。理想情况下，一个哈希函数应该将任何合理的不等的实例集合，统一散列在所有可能的哈希值上。要取得这样的目标是非常困难的。幸运的是不难取得一个公平的近似。下面是简单的流程：
-
存储一些非零常量值，例如17，存储在变量名为
result的int变量中。 -
对于对象中每一个有意义的字段
f（每一个equals方法考虑的字段），按以下做法去做：
a. 为这个字段计算一个int型的哈希码c：
i. 如果这个字段是一个boolean，计算(f ? 1 : 0)。
ii. 如果这个字段是一个byte，char，short或int，计算(int) f。
iii. 如果这个字段是一个long，计算(int)(f^(f>>>32))。
iv. 如果这个字段是一个float，计算Float.floatToIntBits(f)。
v. 如果这个字段是一个double，计算Double.doubleToLongBits(f)，然后对结果long进行2.a.iii处理。
vi. 如果这个字段是一个对象引用并且这个类的equals方法通过递归调用equals方法来比较这个字段，那么对这个字段递归的调用hashCode方法。如果需要更复杂的比较，为这个字段计算一个“标准表示”然后在标准表示上调用hashCode方法。如果字段值为null，返回0(或一些其它常量，但0是传统表示).
vii. 如果字段是一个数组，将它每一个元素看做是一个单独的字段。也就是说，通过递归的应用这些规则为每一个有效元素计算一个哈希值，并结合这些值对每一个用步骤2.b处理。如果数组的每个元素都是有意义的，你可以用JDK 1.5中的Arrays.hashCode方法。
b. 结合步骤2.a计算的哈希码c得到结果如下：result = 31 * result + c；
-
返回结果。
-
当你完成了
hashCode方法的编写后，问一下自己相等的对象是否有相同的哈希码。写单元测试来验证你的直觉！如果相等的实例有不等的哈希码弄明白为什么并修正这个问题。
你可以从哈希码计算中排除冗余字段。换句话说，你可以忽略那些可以从根据计算中的字段计算出值的字段。你必须排除那些equals比较没有使用的字段，或者你冒险违反hashCode约定中的第二条。
步骤1中使用了一个非零初始值，因此哈希值会受到哈希值为0的最初字段的影响，最初字段的哈希值是在步骤2.a中计算的。如果0作为初始值在步骤1中使用，全部的哈希值将不受任何这样的最初字段的影响，这将会增加哈希碰撞。
步骤2.b中的乘积使结果依赖于字段的顺序，如果这个类有多个相似的字段会取得一个更好的哈希函数。例如，String哈希函数忽略了乘积，所有的字母顺序将有相同的哈希码。选择值31是因为它是一个奇素数。如果它是偶数并且乘积溢出，会损失信息，因为与2想乘等价于位移运算。使用一个素数的优势不是那么明显，但习惯上都使用素数。31的一个很好的特性是乘积可以用位移和减法运算替换从而取得更好的性能：31 * i == (i << 5) - i。现代的虚拟机能自动进行排序的优化。让我们对PhoneNumber类应用上面的步骤。这儿有三个字段，所有的类型缩写：
@Override public int hashCode() {
int result = 17;
result = 31 * result + areaCode;
result = 31 * result + prefix;
result = 31 * result + lineNumber;
return result;
}
因为这个方法返回一个简单的确定性运算的结果，唯一的输入是PhoneNumber实例中的三个有效字段，很明显相等的PhoneNumber有相等的哈希值。事实上，这个方法对于PhoneNumber来说是一个完美的很好的hashCode实现，与Java平台库的实现是等价的。它是简单的，相当的快，做者合理的工作——将不等的电话号码分散到不同的哈希桶里。
如果一个类是不可变的，计算哈希码的代价是很明显的，你可能想缓存对象中的哈希码而不是每次请求时重新计算它。如果你认为这种类型的大多数对象将作为哈希键使用，那当实例创建时你应该计算哈希码。此外，当第一次调用hashCode时(Item 71)，你可以选择延迟初始化。我们的PhoneNumber类进行这样处理的优点不是很明显，但可以显示一下它是怎么做的：
// Lazily initialized, cached hashCode
private volatile int hashCode; // (See Item 71)
@Override
public int hashCode() {
int result = hashCode;
if (result == 0) {
result = 17;
result = 31 * result + areaCode;
result = 31 * result + prefix;
result = 31 * result + lineNumber;
hashCode = result;
}
return result;
}
不要试图将对象的有效部分排除在哈希码计算之外来提高性能。虽然最终结果的哈希函数可能运行更快，但它的质量很差可能会降低哈希表的性能，使哈希表变成慢的不可用的状态。尤其是在实践中，哈希函数可能面临在你选择忽略的区域中存在很大不同的实例集合。如果这种情况发生了，哈希函数会映射所有的实例到一个非常小的哈希码上，基于哈希的集合的性能将会变成平方级的。这不仅仅是一个理论问题。String哈希函数在1.2之前的实现中，最多检查16个字符，整个字符串等间距，从第一个字符开始。对于名字分层的大集合，例如URLs，哈希函数正好展现了这里提到的病态行为。
Java平台库中的许多类，例如String，Integer和Date，包含了类规范中它们的hashCode方法返回的确定值。这通常不是一个好注意，因为它严重限制了你在将来版本中改进哈希函数的能力。如果没有指定哈希函数的细节，当发现有缺陷或一个更好的哈希函数时，你可以在接下来的版本中改变哈希函数，确信没有用户依赖哈希函数返回的确定值。
网友评论