解释在计算java.util.hash的哈希代码值时使用的常量

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. 他们采用哈希代码的mod（w.r.t.哈希表数组项的数量）来获得哈希表链数组的索引有一种明显的可能性，哈希表数组的大小将相当于2的幂，因此在步骤2中混合比特对于确保它们不会被丢弃非常重要
4. 然后，它们遍历链，直到到达具有相等键的条目（根据equals()方法）

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

实际使用的常数是相当任意的（可能是通过对一些简单的语料库进行实验来选择的，这些语料库包括大量的Integer和String值），但它们的目的不是：将整个值中的信息扩展到值中的大多数低位，以确保尽可能好地使用hashCode()输出中存在的信息。

（使用完美哈希或加密哈希是无法做到这一点的；尽管名称相似，但它们的实现策略却截然不同。前者需要了解密钥空间，以避免/减少冲突，而后者需要信息向各个方向移动，而不仅仅是低位。）

Answer 2

我也对这样的"神奇"数字感到好奇。据我所知，它们是幻数
广泛的测试已经证明，奇数和素数具有有趣的优先级，可以用于哈希（避免主要/次要聚类等）
我相信，大多数数字都是经过研究和测试得出的，这些研究和测试在统计上证明了良好的分布。为什么特别是这些数字会这样做，我不知道，但我有一个印象（希望这里的同事能纠正我，如果我偏离了方向），实施者都不知道为什么这些特定的数字会呈现出这些品质