Java哈希冲突概率

我在哈希映射（〜280万个对象）中存储了大量对象（在对象中存储在字节数组中的唯一数值组合），并且在检查是否有任何碰撞哈希码（32位哈希），我非常惊讶地发现在统计上没有，我几乎有100％的机会至少有一次碰撞（参见http://preshing.com/20110504/hash-collision-probabilities/）。Java哈希冲突概率

我是这样想，如果我的方法来检测碰撞被窃听或者如果我非常幸运......

这里是我尝试从存储在地图的280万个值检测碰撞：

HashMap<ShowdownFreqKeysVO, Double> values; 
(...fill with 2.8 mlns unique values...) 
HashSet<Integer> hashes = new HashSet<>(); 
for (ShowdownFreqKeysVO key:values.keySet()){ 
    if (hashes.contains(key.hashCode())) throw new RuntimeException("Duplicate hash for:"+key); 
    hashes.add(key.hashCode()); 
}

这里是对象的方法来创建一个散列值：上我做错了什么

public class ShowdownFreqKeysVO { 
    //Values for the different parameters 
    public byte[] values = new byte[12]; 

    @Override 
    public int hashCode() { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + Arrays.hashCode(values); 
     return result; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     ShowdownFreqKeysVO other = (ShowdownFreqKeysVO) obj; 
     if (!Arrays.equals(values, other.values)) 
      return false; 
     return true; 
    } 
}

任何想法/提示将不胜感激！

感谢，托马斯

来源

2013-12-21 Tom

'hashes'在这一行之后包含了什么'HashSet hashes = new HashSet <>（）;'？你如何为'哈希'填充值？ –

他在循环中用'hashes.add（key.hashCode（））;'添加它们。 – meriton

如果在执行'result = prime * result + ...'之前将素数和结果设置为常数，那么在那里看起来错了。 – mprivat

我不相信运气

这是Arrays.hashCode实施您使用

public static int hashCode(int a[]) { 
    if (a == null) 
     return 0; 

    int result = 1; 
    for (int element : a) 
     result = 31 * result + element; 

    return result; 
}

如果值正好是小然后31，他们像对待不同数字在基地31 ，所以每个结果都有不同的数字（如果我们现在忽略溢出）。让我们称之为纯哈希

当然，当然31^11的方式大于Java中的整数，所以我们会得到大量的溢出。但是由于31的幂和最大整数是“非常不同的”，所以你不会得到一个几乎是随机的分布，而是一个非常规则的均匀分布。

让我们考虑一个更小的例子。我假设你的阵列中只有2个元素，每个元素的范围从0到5。我尝试通过采用“纯散列”的模38来创建0到37之间的“hashCode”。结果是我得到5个整数，其间有小间隙，而不是单个碰撞。

val hashes = for { 
    i <- 0 to 4 
    j <- 0 to 4 
} yield (i * 31 + j) % 38 

println(hashes.size) // prints 25 
println(hashes.toSet.size) // prints 25

要验证这是发生了什么你的号码如下您可以创建一个图表：对于每个哈希采取x和第16位和Y，颜色第二个16位点缀黑色。我敢打赌，你会看到一个非常规律的模式。

来源

2013-12-21 15:44:08

谢谢！实际上，存储在字节数组中的所有值都具有低于31的值（它们的范围介于-1和15之间） – Tom

我什么也看不到你的代码错误，但你链接到分析假设哈希码是均匀分布的，而且不同的对象的散列码是独立随机变量。

后者可能不正确：您知道这些对象是唯一的（因此不是独立的）。 hashCode函数可能保留了这个独特的品牌。

来源

2013-12-21 15:03:02 meriton

Java哈希冲突概率

回答

相关问题