.NET 中 GetHashCode 的哈希值有多大概率會相同（哈希碰撞）
- 2020 年 2 月 10 日
- 筆記
如果你試圖通過 GetHashCode 得到的一個哈希值來避免衝突，你可能要失望了。因為實際上 GetHashCode 得到的只是一個 Int32 的結果，而 Int32 只有 32 個 bit。
32 個 bit 的哈希，有多大概率是相同的呢？本文將計算其概率值。
對於 GetHashCode 得到的哈希值，
- 9292 個對象的哈希值衝突概率為 1%；
- 77163 個對象的哈希值衝突概率為 50%。
計算方法
計算哈希碰撞概率的問題可以簡化為這樣：
- 有 1, 2, 3, … n 這些數字；
- 現在，隨機從這些數字中取出 k 個；
- 計算這 k 個數字裡面出現重複數字的概率。
例如：
- 有 1, 2, 3, 4 這四個不同的數字；
- 現在從中隨機抽取 2 個。
那麼抽取出來的可能的情況總數為：
4^2
一定不會重複的可能的情況總數為：
4times3
意思是，第一次抽取的時候有 4 個數字可以選，而第二次抽取的時候就只有 3 個數字可以選了。
那麼，會出現重複的概率就是：
1-frac{4times3}{4^2}
也就是 25% 的概率會出現重複。
那麼現在，我們隨機抽取 3 個會怎樣呢？
- 有 1, 2, 3, 4 這四個不同的數字；
- 現在從中隨機抽取 3 個。
那麼，會出現重複的概率就是：
1-frac{4times3times2}{4^3}
也就是 37.5%，64 種可能裡面，有 24 種是有重複的。
現在，我們推及到 GetHashCode 函數的重複情況。
GetHashCode 實際上返回的是一個 Int32 值，占 32 bit。也就是說，我們有 2^{32} 個數字可以選。
現在問題是：
- 有 1, 2, 3, … 2^{32} 這些數字，我們把 2^{32} 記為 n；
- 現在從中隨機抽取 k 個。
那麼會出現重複的概率為：
1-frac{ntimes(n-1)times(n-2)times…(n-k+1)}{n^k}
當然，分子分母都有的 n 可以約去：
1-frac{(n-1)times(n-2)times…(n-k+1)}{n^{k-1}}
計算的簡化
而 k 很大的時候，此概率的計算非常複雜。然而我們可以取近似值簡化成如下形式 [1]：
1-e^{frac{-k(k-1)}{2n}}
當然，實際上此計算在 k 取值較小的時候還可以進一步簡化成：
frac{k(k-1)}{2n}
於是，在日常估算的時候，你甚至可以使用計算器估算出哈希值碰撞的概率。
你可以閱讀 Hash Collision Probabilities 了解更多關於計算簡化的內容。
概率圖
為了直觀感受到 32 bit 的哈希值的碰撞概率與對象數量之間的關係，我從 Socks, birthdays and hash collisions 和 Hash Collision Probabilities 找到了計算好的概率數據，並繪製成一張圖：
- c# – Probability of getting a duplicate value when calling GetHashCode() on strings – Stack Overflow
- Socks, birthdays and hash collisions – Fabulous Adventures In Coding
- Hash Collision Probabilities
本作品採用 知識共享署名-非商業性使用-相同方式共享 4.0 國際許可協議 進行許可。歡迎轉載、使用、重新發布，但務必保留文章署名 呂毅 （包含鏈接： https://blog.walterlv.com ），不得用於商業目的，基於本文修改後的作品務必以相同的許可發布。如有任何疑問，請 與我聯繫 ([email protected]) 。
