转载

Java 基础：解析 hashCode

Java 中所有的类都继承自 Object 类，Object 类中有个返回 hashCode 的本地方法。

public native int hashCode();
复制代码

在文档的注释中很清楚的说明了 hashCode 的作用，和它应该满足的一些要求。

作用：给一个对象返回一个 hashCode 值，这个值在 hash table 的数据结构中有重要的作用。例如，确定放置在 hash table 哪个索引位置，hash 冲突的频率。

要求：

同一个 Java 对象，在程序运行的整个生命周期中。该对象返回的 hashCode 应该相同。
使用 equals 方法，判断为两个相等的对象，其返回的 hashCode 应该相同。
使用 equals 方法，判断为两个不相同的对象，其返回的 hashCode 应该不相同。

通常的 hashCode 生成方法是将对象的内存地址转换成一个整型数，这样就能为不同的对象返回一个不一样的 hashCode。但是这种方法不能满足上面的第二个条件，所以这种实现也不是 Java 语言所必须的实现方法。

在 String 中的实现

String 类也是继承自 Object 类，它重写了 hashCode() 方法。

/** Cache the hash code for the string */
private int hash; // Default to 0

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}
复制代码

在 String 中计算的 hashCode 会存储在 hash 变量中，并且只会计算一次。因为 String 是 final 的，并且一个 String 对象被初始化后无法修改，所以它的 hashCode 不会变化。

for 循环计算 hashCode 的方法是根据以下式子：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]。

使用 31 的原因

31 是一个质数（Prime number），质数也称为素数。质数是大于 1 的自然数，且只能被 1 和其本身整除。

选择 31 的原因大概有以下几点：

一个数乘质数后的结果，只能被 1 、质数、乘数还有结果本身整除。计算 hashCode 选择一个优质质数可以降低 hash 的冲突率。
31 （2 << 5 - 1），在计算的过程中可以被 JVM 优化。

相信第二点很多同学都能够理解，现在解释一下第一点。

我们列举一下 100 以内左右的质数：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97。

从上面的质数中选择三个小中大质数：2，31，97。分析公式 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 中的每一项，都是一个数乘质数的平方项。所以我们计算一下每个质数的 n 次方，我们选择 n = 5。那么结果如下：

质数	结果
2	2^5 = 32
31	31^5 = 28,629,151
97	97^5 = 8,587,340,257

可以看到通过质数 2 计算后的 hashCode 值是一个比较小的值，而通过质数 97 计算后的 hashCode 是一个比较大的值，而 31 比较适中。

我们可以认为 hashCode 的范围若太小，可能会增加 hash 冲突的概率。而计算 hashCode 的计算乘子太大容易导致整型数的溢出（这里并不是说选择 31 不会导致溢出，是指一个导致溢出的速率），从而也会导致 hash 冲突的概率。31 可以有效的减轻这两点。

更详细的内容可以看一下 stackoverflow 上面的这个问题： Why does Java's hashCode() in String use 31 as a multiplier?

设计 hashCode 算法

根据《Effective Java》第二版中的第 9 条，对于我们自己编写的类，覆盖 equals 方法时需要覆盖 hashCode 方法。原因在前面说过。

那么如何设计一个 hashCode 算法，书中设计了一个算法：

把某个非 0 的常数值，比如 17，保存在一个名为 result 的 int 类型的变量中。
对于对象中的每个域，做如下操作：
- 为该域计算 int 类型的哈希值 c ：
  - 如果该域是 boolean 类型，则计算 (f?1:0)
  - 如果该域是 byte、char、short 或者 int 类型，则计算 (int)f
  - 如果该域是 long 类型，则计算 (int)(f^(f>>>32))
  - 如果该域是 float 类型，则计算 Float.floatToIntBits(f)
  - 如果该域是 double 类型，则计算 Double.doubleToLongBits(f)，然后重复第三个步骤。
  - 如果该域是一个对象引用，并且该类的 equals 方法通过递归调用 equals 方法来比较这个域，同样为这个域递归的调用 hashCode，如果这个域为 null，则返回0。
  - 如果该域是数组，则要把每一个元素当作单独的域来处理，递归的运用上述规则，如果数组域中的每个元素都很重要，那么可以使用 Arrays.hashCode 方法。
- 按照公式 result = 31 * result + c，把上面步骤 2.1 中计算得到的散列码 c 合并到 result 中。
返回 result