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哈希衝突概率

回答

相關問題