Effective.Java 读书笔记（9）关于HashCode

9.Always override hashCode when you override equals

大意为 在你重写equals方法的时候要经常重写hashCode

有很多程序会错误的原因之一，就是当你重写一个类的equals方法的时候忘记重写它的hashCode了

请记住当你重写一个类的equals方法的时候，一定要重写hashCode，如果你不这样做的话，就会违反了Object.hashCode的 通用规范，这通常会导致一些hash类的问题，比如HashMap,HashSet以及HashTable

以下有一些来自于Object类的规范 [JavaSE6]:

• 当你不断在一个程序里面调用一个对象的hashCode方法，它总应该返回一个相同的整形数值

需要注意的是，这个和重写equals方法的规范中的一致性不大一样，不要求在反复执行相同的程序的情况下，返回一样的值

• 如果两个对象使用equals方法比较然后返回true的话，那么这两个对象的hashCode应该返回相同的数值
• 对于两个对象使用equals方法比较返回false的情况，并不强制要求hashCode也不一样

当然，对两个不同的对象返回不同的hashCode值会提高hashTable的表现

在这里指出最为关键的部分,即第二个条件是最容易犯错的，两个对象用equals比较，一定要返回一样的hashCode 两个不一样的实例可能由于修改了equals方法，可能逻辑上是相等的，但是Object的hashCode并不会去在意这些，只会简单地返回不一样的数值，并不会根据规范而返回相同值

举一个简单的例子来说，我们来看一个PhoneNumber的类，我们已经重写了它的构造方法：

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")

这个时候，你可能会认为以下这条语句会返回Jenny

m.get(new PhoneNumber(707 , 867 , 5309))

事实却是它返回了一个null，明显存在的问题就是没有重写hashCode方法导致这样，修复这问题只需要重写一个合适的hashCode方法即可

在这里要说一点，即使两个实例运气足够好，散列到同一个bucket里面，HashMap的get方法也会返回null，只要hashCode不一样HashMap就不会去检查逻辑上的相等

下面给出一个无脑的解决的方法：

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

这样看上去好像合法，但是你千万别这样用，它合法是由于它保证了相等的对象一定会有相同的hash code，但是这样的做法太过于粗暴以至于让所有的对象的hash code都一样，所有的对象都散列到相同的bucket里面，HashTable就退化成链表了

一个好的hashCode方法对于不同的对象应该返回不同的值，理想情况下，hashCode方法应该均匀地分配数值给那些不相等的对象，但是实现起来好像比较困难，不过接近这样的方案还是有的：

1. 存一些连续的非零整形数值，比如说17，把它记为result
2. 对于每一个重要的域，做下列的事情：
   1. 对这个域计算int类型的hash code，我们把这个hash code叫做c：
      1. 如果这个域是布尔变量，返回（f？1：0）
      2. 如果是byte，char，short或者是int，返回（int）f
      3. 如果是long类型，返回 (int) (f ^ (f >>> 32))
      4. 如果是float类型，返回 Float.floatToIntBits(f)
      5. 如果是double类型，先使用 Double.doubleToLongBits(f) 转变为long类型，再按long类型来计算
      6. 如果这个域是对象的引用，而且这个类在使用equals方法的时候会递归地来调用这个引用，那就直接递归地调用这个引用的hashCode方法，当然如果是需要更加复杂的比较，可以先计算出一个规范的表示，然后在这个规范的表示中去调用hashCode方法，如果该域是null，就直接返回0

      返回0是比较传统的做法，你也可以返回其他的

      1. 如果域是一个数组，你可以把元素看成是分离的域的组合，对于那些重要的域使用上述的原则进行计算，当然如果整个数组的元素都是重要的，必须要比较的，那你可以直接使用Arrays.hashCode方法
   2. 通过计算得到的result和c我们可以来更新result，公式为：$$ result=result*31+c$$
3. 返回result
4. 结束对hashCode方法的编写，并且检查有没有符合上文所说的那几条规范

在对hash code进行计算的时候，你可能不会把一些“冗余的”域也计算进去，需要注意的是，那些可以由其他域计算而来的域称为冗余的域，计算hash code的时候把它们忽略不理可能不是一件正确的事，很有可能就会导致对于第二个规范的违反

回看一下计算的过程，我们初始化了一个非零的值，这个值对于hash code的最后生成有着极大的影响，但是这个值不能是0，如果是0的话，那么初始化的域的影响就没了，这样就可能产生冲突，故17这个值是合适的

多维的对于不同类型的不同操作表现出了不错的hash特性，另外选择31作为因子是由于它是一个奇素数，而且利用位运算很容易计算，只要右移5位减去1即可

目前使用素数还是不大明确其优点，但传统上是这么用的，在溢出的情况下能够在一定意义上保留信息

我们使用PhoneNumber类来实际操作一次

@Override public int hashCode() {
    int result = 17;
    result = 31 * result + areaCode;
    result = 31 * result + prefix;
    result = 31 * result + lineNumber;
    return result;
}

这样的方法实现保证了逻辑相同的实例有着相同的hashCode，这个方法看似简单，它的性能却和Java平台库的函数性能上不相上下，十分简单而且高效，将逻辑不同的实例散列到不同的bucket中

需要说明的是，如果计算hash code的代价开销不小，你必须考虑把hash code缓存起来而不是每一次都重新计算

我们在PhoneNumber类上简单实现一下

// Lazily initialized, cached hashCode
private volatile int hashCode; 
@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;
}

这里所提及的hash函数并不是最先进的，你可以利用数学和计算机科学理论的知识结合最前沿的论文探讨一下这个函数的更好的实现方案，但是将一个对象重要的域在hash code的计算中忽略以试图提高性能的做法绝对是完全错误的，最多加快了方法的速度，但对于整个hash集合的性能来说是得不偿失的

目前Integer类的hashCode方法都是返回实确的值，这并不是一个好的办法，希望有一天可以被修改成更为高效的方法