Java HashMap检测冲突

Question

有没有办法在Java哈希映射中检测冲突？任何人都可以指出可能发生大量碰撞的情况.当然,如果你覆盖一个对象的哈希码并简单地返回一个常量值,肯定会发生冲突.我不是在谈论那个.我想知道前面提到的其他所有情况都会发生大量的碰撞无需修改默认的哈希码实现.

Answer 1

我创建了一个项目,这些基准样的事情:http://code.google.com/p/hashingbench/(对于哈希表与链接,开放寻址和布隆过滤器).

除了hashCode()方法的关键,你需要知道的"拖尾"(或"扰",我把它在该项目)的哈希表的功能.从这个列表中,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()(否则,涂抹/加扰功能将不会是一个功能),所以这是一个足够的,但不是必要的,以发生冲突的条件.

编辑:实际上,上述的充分必要条件应该是compress(scramble(k1.hashCode())) == compress(scramble(k2.hashCode()))-的compress函数需要一个整数,并将其映射到{0, ..., N-1},这里N是桶的数量,因此,它基本上选择一个桶.通常情况下,这根本是实现为hash % N,或当哈希表大小为二的幂(这实际上是对具有电源的两散列表的大小动机),因为hash & N(快).("compress"是Goodrich和Tamassia用于描述此步骤的名称,在Java中的数据结构和算法中).感谢ILMTitan发现我的邋..

其他散列表实现(ConcurrentHashMap中,IdentityHashMap等)有其他需求,并使用另一涂抹/加扰功能,所以你需要知道你在谈论哪一个.

(例如,HashMap的拖尾函数已经到位,因为人们使用HashMap和具有最差类型hashCode()的对象,用于HashMap的旧的,两个表的实现,而不会出现拖尾 - 对象稍有不同,或者完全没有,在用于选择存储桶的低位中 - 例如new Integer(1 * 1024),new Integer(2 * 1024)*等等.正如您所看到的,HashMap的拖尾函数尽力使所有位影响低位.

但是,所有这些都适用于常见情况 - 特殊情况是继承系统的hashCode()的对象.

PS:实际上,提示实现者插入拖尾函数的绝对丑陋的案例是Floats/Doubles的hashCode(),以及作为值的键的用法:1.0,2.0,3.0,4.0 ......,所有这些都有相同(零)低位.这是相关的旧错误报告:http://bugs.sun.com/bugdatabase/view_bug.do？video_id = 46669519