Java HashMap检测冲突
有没有办法在Java哈希映射中检测冲突？ 任何人都可以指出可能发生大量碰撞的情况。 当然，如果你覆盖一个对象的哈希码并简单地返回一个常量值，肯定会发生冲突。我不是在谈论那个。我想知道前面提到的其他所有情况都发生了大量的碰撞无需修改默认的哈希码实现。
我创建了一个项目来对这些事情进行基准测试： http ： //code.google.com/p/hashingbench/ （对于带有链接，开放寻址和布隆filter的哈希表）。
除了密钥的hashCode（）之外 ，您还需要知道哈希表的“拖尾” （或“加扰”，就像我在该项目中所称的那样）function。 从这个列表中 ，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 ，或者当散列表大小是2的幂（并且实际上是具有2个幂散列表大小的动机）时，作为hash & N （更快）。 （“compress”是Goodrich和Tamassia用于描述此步骤的名称， 在Java中的数据结构和算法中 ）。 感谢ILMTitan发现我的邋。。
其他哈希表实现（ConcurrentHashMap，IdentityHashMap等）有其他需求并使用另一个拖尾/加扰函数，因此您需要知道您正在谈论哪一个。
（例如，HashMap的拖尾函数已经到位，因为人们使用具有最差类型hashCode（）的HashMap用于HashMap的旧的，两个表的实现而没有拖尾 – 对象稍有不同，或者根本没有，用于选择存储桶的低位 – 例如new Integer(1 * 1024) ， new Integer(2 * 1024) *等等。正如您所看到的，HashMap的拖尾函数尽力而为让所有位影响低位）。
但是，所有这些都适用于常见情况 – 特殊情况是inheritance系统的hashCode（）的对象。
PS：实际上，提示实现者插入拖尾函数的绝对丑陋的案例是Floats / Doubles的hashCode（），以及作为值的键的用法：1.0,2.0,3.0,4.0 ……，所有这些都有相同（零）低位。 这是相关的旧错误报告： http ： //bugs.sun.com/bugdatabase/view_bug.do？video_id = 46669519
简单的例子：哈希Long 。 显然，有64位输入，只有32位输出。 Long的哈希记录为：
(int)(this.longValue()^(this.longValue()>>>32))
也就是说，想象它是彼此相邻的两个int值，并将它们异或。
因此所有这些都将具有0的哈希码：
0 1L | (1L << 32) 2L | (2L << 32) 3L | (3L << 32)
等等
我不知道这是否算是“大量的碰撞”，但它是易于制造碰撞的一个例子。
显然， 任何有超过2 32个可能值的哈希都会发生冲突，但在很多情况下它们更难产生。 例如，虽然我确实只使用ASCII值看到了String上的哈希冲突，但它们的生成比上面的更难。
另外两个答案我看到一个很好的IMO，但我只是想分享一下，测试你的hashCode()在HashMap表现有多好的最好方法是从你的类中实际生成大量对象，将它们放在特定的HashMap实现为关键并测试CPU和内存负载。 一百万或两百万个条目是一个很好的数字，但如果您使用预期的地图大小进行测试，您将获得最佳结果。
我只是看了一堂课，我怀疑它的散列函数。 所以我决定使用该类型的随机对象和测试碰撞数来填充HashMap。 我测试了两个正在调查的类的hashCode（）实现。 所以我在groovy中编写了你在底部看到的类，扩展了HashMap的openjdk实现，以计算HashMap中的冲突数（参见countCollidingEntries() ）。 请注意，这些不是整个哈希的真实冲突，而是包含条目的数组中的冲突。 数组索引计算为hash & (length-1) ，这意味着，如果此数组的大小较短，则获得的冲突越多。 并且此数组的大小取决于HashMap initialCapacity和loadFactor （当put()更多数据时它可以增加）。
最后虽然我认为看这些数字没什么意义。 事实上，HashMap使用错误的hashCode()方法较慢，这意味着只需通过对Map中数据的插入和检索进行基准测试，您就可以有效地了解哪个hashCode()实现更好。
public class TestHashMap extends HashMap { public TestHashMap(int size) { super(size); } public TestHashMap() { super(); } public int countCollidingEntries() { def fs = this.getClass().getSuperclass().getDeclaredFields(); def table; def count =0 ; for ( java.lang.reflect.Field field: fs ) { if (field.getName() == "table") { field.setAccessible(true); table = field.get(super); break; } } for(Object e: table) { if (e != null) { while (e.next != null) { count++ e = e.next; } } } return count; } }