Java HashMap 哈希函数

Question

很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它， visit the help center 。

已关闭 10 年前。

我正在研究 Java 的 HashMap hash() 实现，如下所示

final int hash(Object k) {
            // some checks
            h ^= k.hashCode();
            // 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);
                   // >>> is Unsigned right shift
    }

我不知道为什么添加下面的代码，以及这样做有什么好处？

        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);

或者让我重新构建我的问题，如果我从实现中删除上面的代码有什么缺点？我了解一些如何避免碰撞的机会，但不确定“到底”如何？

有人可以通过举一个例子来帮助我理解，并解释使用和不使用上述代码时它将如何工作吗？

Answer 1

Java 哈希表实现的大小不是素数大小，而是 2 的幂大小。这使得它可以使用快速位掩码而不是昂贵的余数操作，这通常是一件好事，但缺点是特别糟糕的哈希函数可能会比平常有更多的冲突。您引用的代码以最小化额外冲突的方式混合散列的位。