Java的HashMap的碰撞检测

有没有一种方法来检测Java的哈希地图碰撞？任何人都可以指出某种情况下可能发生很多碰撞事件。当然，如果你重写一个对象的哈希码，并简单地返回一个常数值，肯定会发生冲突。我不是在谈论那个。我想知道在前面提到的其他情况下会发生大量碰撞的情况而无需修改默认的哈希码实现。Java的HashMap的碰撞检测

来源

2010-08-11 Emil

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

除的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()（否则，涂抹/加扰功能不会是功能），所以这是一个足够，但不是必要条件为发生碰撞。

编辑：实际上，上述的充分必要条件应该已经compress(scramble(k1.hashCode())) == compress(scramble(k2.hashCode())) - 的compress函数取的整数，并将其映射到{0, ..., N-1}，其中N是桶的数量，因此，它基本上选择一个桶。通常情况下，这根本是实现为hash % N，或者在哈希表大小为二的幂（这实际上是对具有电源的两散列表的大小动机），为hash & N（快）。（“压缩”是Goodrich和Tamassia用于描述这一步骤的名称，在Data Structures and Algorithms in Java中）。感谢ILMTitan发现我的sl iness。其他散列表实现（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 ...，它们都具有相同的（零）低位。这是有关老的bug报告：http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4669519

来源

2010-08-11 07:33:08

不应必要而充分的条件是'加扰（k1.hashCode（））％C ==加扰（k2.hashCode（））％C'其中c是在容量，或料斗数量哈希表？ – ILMTitan 2010-08-11 16:06:27

@ILMTitan，是的，谢谢，修正 – 2010-08-11 17:02:22

简单的例子：一个散列Long。显然，有64位输入，只有32位输出。的Long哈希值记录为：

(int)(this.longValue()^(this.longValue()>>>32))

即想象它的下坚持两个彼此int值和XOR他们。

因此，所有的这些都将有0的散列码：

0 
1L | (1L << 32) 
2L | (2L << 32) 
3L | (3L << 32)

等

我不知道这是否算作是“冲突的数量庞大”，但它是一个例子，其中碰撞是容易制造。

显然任何散列结果，其中有超过2 可能值会有冲突，但在许多情况下，他们难以产生。例如，尽管我只使用ASCII值在String上看到了散列冲突，但它们的生产难度要高于上述。

来源

2010-08-11 05:37:16

另外两个答案，我看到一个很好的IMO，但我只是想和大家分享，最好的方式来测试你的hashCode()的行为在HashMap是如何实际生成的一个大数目来自你班级的对象，将它们放在特定的HashMap实现中作为密钥并测试CPU和内存负载。 1或200万个条目是一个很好的数字，但如果您使用预期的地图大小进行测试，则可以获得最佳结果。

我只是看着一个我怀疑它的哈希函数的类。所以我决定用这种类型的随机对象和测试碰撞次数填充一个HashMap。我测试了正在调查的类的两个hashCode（）实现。所以我在groovy中写下了你在底部看到的扩展了HashMap的openjdk实现的类来计算进入HashMap的冲突数量（见countCollidingEntries()）。请注意，这些不是整个散列的实际冲突，而是包含条目的数组中的冲突。数组索引计算为hash & (length-1)，这意味着此数组的大小越短，您获得的冲突就越多。这个数组的大小取决于initialCapacity和loadFactor的HashMap（它可以增加当put()更多的数据）。

尽管我认为看着这些数字没什么意义。由于HashMap速度较慢，而且方法较差，这意味着只需通过对来自Map的数据的插入和检索进行基准测试，就可以有效地了解哪个实施更好。

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; 
    } 
}

来源

2013-03-24 19:55:57 akostadinov

Java的HashMap的碰撞检测

回答

相关问题