HashMap哈希函数-二进制运算符

Question

我正在研究HashMap的源代码，但是二进制操作符混淆了很多。

我理解以下的一般目的，公平分配，并使hashCode在桶的限度内。

有人能解释一下这里的评论吗?现在这样做有什么好处呢？

/**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

如果有人能帮我理解它，那将是一个很大的帮助。

这不是重复，因为其他问题与Java 8之前的哈希实现有关。

提前感谢

Answer 1

hashCode()返回一个32位宽的int。

在内部，HashMap将对象保存在pow(2, n)桶或回收箱中。n的值可以改变- the细节在这里并不重要；重要的是n通常比32小得多(哈希中的位数)。

每个对象都被放置在一个桶中。为了获得良好的性能，需要将对象均匀地分布在桶上。这就是对象散列的来源:选择桶的最简单方法是获取对象的哈希代码中最低的n位(使用简单的位数和)。但是，这只会使用最低的n位，而忽略其余的哈希。

在评论中，作者认为这是不可取的。他们列举了已知用例的例子，在这些用例中，对象哈希将系统地与最低的n不同。这将导致系统碰撞，系统碰撞是坏消息。

为了部分解决这一问题，他们实现了当前的启发式：

• 保持散列的前16位；
• 用前16位和下16位的异或替换下16位。