在HASHMAP中计算密钥的哈希码两次

Question

我一直在研究Hashmap实现的内部.

为了根据密钥从map添加或获取值,它将计算哈希码,然后它找到桶位置(或表位置/索引,如果我错了,请纠正我).
但它正在计算两次哈希码.

在下面的代码片段中,key.hashcode()是对象类中的本机方法,然后哈希方法在同一个类中实现.
它在哈希方法的注释中给出了为什么它被计算两次,这是我无法理解的.

任何人都可以用一个场景简要解释一下吗？

int hash = hash(key.hashCode());

/ * Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions.  This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.           
*/
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);
}

谢谢.

Answer 1

http://tekmarathon.com/2012/12/04/hashmap-internal-implementation-analysis-in-java/

这意味着如果我们为哈希码生成编写的算法不能均匀地分配/混合较低位,则会导致更多冲突.例如,我们有哈希码逻辑"empId*deptId",如果deptId是偶数,它将始终生成偶数哈希码,因为任何乘以偶数的数字总是偶数.如果我们直接依赖这些哈希码来计算索引并将我们的对象存储到hashmap中,那么1. hashmap中的奇数位置总是空的.因为#1,它会让我们只使用偶数位置,因此加倍碰撞

它防止写得不好的哈希函数.另外,类似值的对象即使不一定相同也会引起冲突.冲突不好,它们增加了查找与密钥相关联的值的时间,因为每个哈希都指向一个链接的值列表,必须在检索时迭代这些值才能匹配正确的密钥.即使具有良好的散列函数,您仍然需要"混合较低位"以确保均匀的两次分配功能.

也可以看看:

• 提高大型HashMaps的性能:Java HashMap性能优化/替代方案

• 可能的重复:

  • HashMap#hash(int)方法的说明
  • Java HashMap Hashing函数
  • HashMap中的哈希方法
  • (Java 8)在Java 8中更改为HashMap哈希函数
  • 为什么在HashMap中使用hash方法

免责声明:我与HashMaps一起工作了一年多,这是所有研究的来源