java - 计算 java.util.hash 的 hashcode 值时使用的常量说明

Question

谁能解释这些常量的意义以及选择它们的原因？

static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

来源:java-se6库

Answer 1

理解什么是好的哈希函数是很棘手的，因为实际上有很多不同的函数被使用并且目的略有不同。

Java 的哈希表的工作方式如下:

1. 他们要求关键对象产生它的散列码。 hashCode() 方法的实现可能具有明显可变的质量(在最坏的情况下，返回一个常量值!)并且绝对不会适应您正在使用的特定哈希表与。
2. 然后他们使用上面的函数将位混合一点，这样高位中的信息也被向下移动到低位。这很重要，因为接下来……
3. 他们采用哈希码的模数(w.r.t. 哈希表数组条目的数量)来获取哈希表链数组的索引。 哈希表数组的大小很可能等于 2 的幂，因此在第 2 步中混合位非常重要，以确保它们不会被丢弃。
4. 然后他们遍历链，直到他们到达具有相等键的条目(根据 equals() 方法)。

完成图片，哈希表数组中的条目数是非常量；如果链条太长，数组将被替换为一个新的更大的数组，并且所有内容都会重新散列。这相对较快，并且对正常使用模式具有良好的性能影响(例如，大量 put() 后跟大量 get())。

实际使用的常量是相当随意的(并且可能是通过一些简单的语料库进行实验选择的，包括大量的 Integer 和 String 值)但它们的目的是不是:将整个值中的信息传播到值中的大部分低位可确保尽可能使用 hashCode() 输出中存在的信息。

(您不会使用完美哈希或加密哈希来执行此操作；尽管名称相似，但它们的实现策略却截然不同。前者需要知道 key 空间，以便避免/减少冲突，后者需要信息向各个方向移动，而不仅仅是低位。)