0

我正在通过 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);

或者,如果我从实现中删除上述代码,让我重新提出我的问题,有什么缺点?我了解它如何避免碰撞的机会,但不确定“确切”如何?

有人可以通过举个例子来帮助我理解,并解释它在使用和不使用上述代码的情况下如何工作?

4

1 回答 1

5

Java 哈希表实现不是将表的大小调整为素数大小,而是两倍的大小。这允许它使用快速位掩码而不是昂贵的余数运算,这通常是一件好事,但缺点是特别糟糕的散列函数可能比平时有更多的冲突。您引用的代码以最小化额外冲突的方式混合了哈希的位。

于 2013-03-19T03:09:31.930 回答