Java HashMap检测到碰撞

除了密钥的hashCode()之外,您需要知道哈希表的“拖放”(或称为“加扰”,就像我在该项目中称之为)函数.从this list起,HashMap的拖尾功能相当于：

public int scramble(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

因此,为了在HashMap中发生冲突,必要和充分的条件如下：scramble(k1.hashCode())== scramble(k2.hashCode()).如果k1.hashCode()== k2.hashCode()(否则,拖尾/加扰功能不会是一个功能),这一直是真的,所以这是碰撞发生的足够但不是必需的条件.

编辑：实际上,上述必要和充分的条件应该被压缩(scramble(k1.hashCode()))== compress(scramble(k2.hashCode())) – compress函数需要一个整数,并将其映射到{0,…,N-1},其中N是桶的数量,因此它基本上选择一个桶.通常,这简单地被实现为哈希％N,或者当哈希表大小是二的幂时(实际上是具有两个哈希表的幂的大小的动机),作为哈希和N(更快). (“压缩”是古​​德里奇和塔马西亚用来描述这一步的名称,在Data Structures and Algorithms in Java).感谢ILMTitan发现我的肮脏.

其他哈希表实现(ConcurrentHashMap,IdentityHashMap等)还有其他需求,并使用其他拖放/加扰功能,因此您需要知道您正在谈论哪一个.

(例如,HashMap的拖尾功能已经到位了,因为人们使用HashMap,而对于具有最差类型的hashCode()的对象,对于旧的,功能为2的HashMap实现,而不会拖延 – 稍微不同的对象,或而不是在他们用来选择一个存储桶的低位中,例如新的整数(1 * 1024),新的整数(2 * 1024)*等等.正如你所看到的,HashMap的拖尾功能会尝试最好使所有位都影响低位).

所有这些都是在常见情况下工作得很好 – 特定的情况是继承系统的hashCode()的对象.

PS：实际上,提示实现者插入拖放功能的绝对丑陋的情况是Floats / Doubles的hashCode()和值作为键的使用：1.0,2.0,3.0,4.0 …,它们都具有相同(零)低位.这是相关的旧错误报告：http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4669519