第9条：覆盖equals时总要覆盖hashCode

一个很常见的错误根源在于没有覆盖hashCode方法。在每个覆盖了equals方法的类中，也必须覆盖hashCode方法。如果不这样做的话，就会违反Object.hashcode的通用约定，从而导致该类无法结合所有基于散列的集合一起正常工作，这样的集合包括HashMap、HashSet和Hashtable。

下面是约定的内容，摘自Object规范[JavaSE6]：

• 在应用程序的执行期间，只要对象的equals方法的比较操作所用到的信息没有被修改，那么对同一个对象调用多次，hashCode方法都必须始终如一地返回同一个整数。在同一个应用程序的多次执行过程中，每次执行所返回的整数可以不一致。
• 如果两个对象根据equals(Object)方法比较是相等的，那么调用这两个对象中任意一个对象的hashCode方法都必须产生同样的整数结果。
• 如果两个对象根据equals(Object)方法比较是不相等的，那么调用这两个对象中任意一个对象的hashCode方法，则不一定要产生不同的整数结果。但是程序员应该知道，给不相等的对象产生截然不同的整数结果，有可能提高散列表（hash table）的性能。

因没有覆盖hashCode而违反的关键约定是第二条：相等的对象必须具有相等的散列码（hash code）。根据类的equals方法，两个截然不同的实例在逻辑上有可能是相等的，但是，根据Object类的hashCode方法，它们仅仅是两个没有任何共同之处的对象。因此，对象的hashCode方法返回两个看起来是随机的整数，而不是根据第二个约定所要求的那样，返回两个相等的整数。

例如，考虑下面这个极为简单的PhoneNumber类，它的equals方法是根据第8条中给出的“诀窍”构造出来的：

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”，但它实际上返回的是null。注意，这里涉及两个PhoneNumber实例：第一个被用于插入到HashMap中，第二个实例与第一个相等，被用于（试图用于）获取。由于PhoneNumber类没有覆盖hashCode方法，从而导致两个相等的实例具有不相等的散列码，违反了hashCode的约定。因此，put方法把电话号码对象存放在一个散列桶（hash bucket）中，get方法却在另一个散列桶中查找这个电话号码。即使这两个实例正好被放在同一个散列桶中，get方法也必定会返回null，因为HashMap有一项优化，可以将每个项相关联的散列码缓存起来，如果散列码不匹配，也不必检验对象的等同性。

修正这个问题非常简单，只需为PhoneNumber类提供一个适当的hashCode方法即可。那么，hashCode方法应该是什么样的呢？编写一个合法但并不好用的hashCode方法没有任何价值。例如，下面这个方法总是合法，但是永远都不应该被正式使用：

// The worst possible legal hash function - never use!
@Override public int hashCode() { return 42; }

上面这个hashCode方法是合法的，因为它确保了相等的对象总是具有同样的散列码。但它也极为恶劣，因为它使得每个对象都具有同样的散列码。因此，每个对象都被映射到同一个散列桶中，使散列表退化为链表（linked list）。它使得本该线性时间运行的程序变成了以平方级时间在运行。对于规模很大的散列表而言，这会关系到散列表能否正常工作。

一个好的散列函数通常倾向于“为不相等的对象产生不相等的散列码”。这正是hashCode约定中第三条的含义。理想情况下，散列函数应该把集合中不相等的实例均匀地分不到所有可能的散列值上。要想完全达到这种理想的情形是非常困难的。幸运的是，相对接近这种理想情形则并不太苦难。下面给出一种简单的解决办法：

1. 把某个非零的常数值，比如说17，保存在一个名为result的int类型的变量中。

2. 对于对象中每个关键域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)，然后按照步骤2.a.iii，为得到的long类型值计算散列值。

   vi. 如果该域是一个对象引用，并且该域的equals方法通过递归地调用equals的方式来比较这个域，则同样为这个域递归地调用hashCode。如果需要更复杂的比较，则为这个域计算一个“范式（canonical representation）”，然后针对这个范式调用hashCode。如果这个域的值为null，则返回0（或者其他某个常数，但通常是0）。

   vii. 如果该域是一个数组，则要把每一个元素当做单独的域来处理。也就是说，递归地应用上述规则，对每个重要的元素计算一个散列码，然后根据步骤2.b中的做法把这些散列值组合起来。如果数组域中的每个元素都很重要，可以利用发行版本1.5中增加的其中一个Arrays.hashCode方法。

   b. 按照下面的公式，把步骤2.a中计算得到的散列码c合并到result中：

   result = 31 * result + c;
   

3. 返回result。

4. 写完了hashCode方法之后，问问自己“相等的实例是否都具有相等的散列码”。要编写单元测试来验证你的推断。如果相等实例有着不相等的散列码，则要找出原因，并修正错误。

在散列码的计算过程中，可以把冗余域（redundant field）排除在外。换句话说，如果一个域的值可以根据参与计算的其他域值计算出来，则可以把这样的域排除在外。必须排除equals比较计算中没有用到的任何域，否则很有可能违反hashCode约定的第二条。

上述步骤1中用到了一个非零的初始值，因此步骤2.a中计算的散列值为0的那些初始域，会影响到散列值。如果步骤1中的初始值为0，则整个散列值将不受这些初始域的影响，因为这些初始域会增加冲突的可能性。值17则是任选的。

步骤2.b中的乘法部分使得散列值依赖于域的顺序，如果一个类包含多个相似的域，这样的乘法运算就会产生一个更好的散列函数。例如，如果String散列函数省略了这个乘法部分，那么只是字母顺序不同的所有字符串都会有相同的散列码。之所以选择31，是因为它是一个奇素数。如果乘数是偶数，并且乘法溢出的话，信息就会丢失，因为与2相乘等价于位移运算。使用素数的好处并不很明显，但是习惯上都使用素数来计算散列结果。31有个很好的特性，即用位移和减法来代替乘法，可以得到更好的性能，31 * i == (i << 5) - i。现代的VM可以自动完成这种优化。

现在我们要把上述的解决办法用到PhoneNumber类中。它有三个关键域，都是short类型：

@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平台类库中的实现。它的做法非常简单，也相当快捷，恰当地把不相等的电话号码分散到不同的散列桶中。

如果一个类是不可变的，并且计算散列码的开销也比较大，就应该考虑把散列码缓存在对象内部，而不是每次请求的时候都重新计算散列码。如果你觉得这种类型的大多数对象会被用作散列键（hash keys），就应该在创建实例的时候计算散列码。否则，可以选择“延迟初始化（lazily initialize）”散列码，一直到hashCode被第一次调用的时候才初始化（见第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;
}

虽然本条目中前面给出的hashCode实现方法能够获得相当好的散列函数，但是它并不能产生最新的散列函数，截止发行版本1.6，Java平台类库也没有提供这样的散列函数。编写这种散列函数是个研究课题，最好留给数学家和理论方面的计算机科学家来完成。也许Java平台的下一个发行版本将会为它的类提供这种最佳的散列函数，并提供一些实用方法来帮助普通的程序员构造出这样的散列函数。与此同时，本条目中介绍的方法对于绝大多数应用程序而言已经足够了。

不要试图从散列码计算中排除掉一个对象的关键部分来提高性能。虽然这样的散列函数运行起来可能更快，但是它的效果不见得会好，可能会导致散列表慢到根本无法使用。特别是在实践中，散列函数可能面临大量的实例，在你选择忽略的区域中，这些实例仍然区别非常大。如果是这样，散列函数就会把所有这些实例映射到极少数的散列码上，基于散列的集合将会显示出平方级的性能指标。这不仅仅是个理论问题。在Java 1.2发行版本之前实现的String散列函数至多只检查16个字符，从第一个字符开始，在整个字符串中均匀选取。对于像URL这种层次状名字的大型集合，该散列函数正好表现出了这里所提到的病态行为。

Java平台类库中的许多类，比如String、Integer和Date，都可以把它们的hashCode方法返回的确切值规定为该实例值的一个函数。一般来说，这并不是个好主意，因为这样做严格地限制了在将来的版本中改进散列函数的能力。如果没有规定散列函数的细节，那么当你发现了它的内部缺陷时，就可以在后面的发行版本中修正它，确信没有任何客户端会依赖于散列函数返回的确切值。