Hash是一種校驗方法，
其中應用最廣為人知的就是 HashMap。
當然Hash算法並不完美，有可能兩個不同的原始值在經過哈希運算後得到同樣的結果，這樣就是哈希碰撞。
哈希碰撞有幾種解決辦法
· 開放定址法
· 鏈地址
鏈地址法
鏈地址法其實就是HashMap中用的策略。
原理是在HashMap中同樣哈希值的位置以一串鏈表存儲起來數據，
把多個原始值不同而哈希結果相同的數據以鏈表存儲起來。
開放定址法
當發生地址衝突時，按照某種方法繼續探測哈希表中的其他存儲單元，直到找到空位置為止。
用方程來表達的話是這樣子，
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… ， k ( k ≤ m – 1))
m 是哈希表的長度。
舉一個實際的例子，
一個哈希函數是 H ( key ) = key mod 7 ，
哈希表長度為 7，
關鍵字序列（ 32 ， 13 ， 49 ， 55 ， 22 ， 38 ， 21 ）
如果以線性探測再散列來生成哈希表的話，
過程是這樣的
32 ％ 7 = 4 ； 13 ％ 7 = 6 ； 49 ％ 7 = 0 ；
55 ％ 7 = 6 發生衝突，下一個存儲地址（ 6 ＋ 1 ）％ 7 ＝ 0 ，仍然發生衝突，再下一個存儲地址：（ 6 ＋ 2 ）％ 7 ＝ 1 未發生衝突，可以存入。
22 ％ 7 ＝ 1 發生衝突，下一個存儲地址是：（ 1 ＋ 1 ）％ 7 ＝ 2 未發生衝突；
38 ％ 7 ＝ 3 ；
21 ％ 7 ＝ 0 發生衝突，按照上面方法繼續探測直至空間 5 ，不發生衝突
所得到的哈希表對應存儲位置：
下標： 0 1 2 3 4 5 6
49 55 22 38 32 21 13
分享到:
閱讀更多 Java高併發框架 的文章
