一、什麼是哈希沖突？
當資料插入到哈希表時，不同key值産生的h(key)卻是相等的，這個時候就産生了沖突。
二、怎麼解決哈希沖突？
常用的幾種方法有：開放定址法、拉鍊法、再哈希法、建立公共溢出區。
1、開放定址法
所謂的開放定址法就是一旦發生了沖突，就去尋找下一個空的散列位址，隻要散清單足夠大，空的散列位址總能找到，并将記錄存入
公式為：fi(key) = (f(key)+di) MOD m (di=1,2,3,……,m-1)
詳解：當沖突發生時，使用某種探測技術在散清單中形成一個探測序列（根據生成序列的規則不同，可以有線性探查法、僞随機探查法、二次探查法、雙散列法等）。沿此序列逐個單元地查找，直到找到給定的關鍵字，或者碰到一個開放的位址（即該位址單元為空）為止。
比如說（借用例子），我們的關鍵字集合為{12,67,56,16,25,37,22,29,15,47,48,34},表長為12。 我們用散列函數f(key) = key mod l2
當計算前S個數{12,67,56,16,25}時，都是沒有沖突的散列位址，直接存入：
計算key = 37時，發現f(37) = 1，此時就與25所在的位置沖突。
于是我們應用上面的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存入下标為2的位置：
2、拉鍊法
拉鍊法是解決哈希沖突的一種行之有效的方法（比如php、java就是使用該方法解決哈希沖突），某些哈希位址可以被多個關鍵字值共享，這樣可以針對每個哈希位址建立一個單連結清單。
原理：每個哈希表節點都有一個next指針，多個哈希表節點可以用next指針構成一個單向連結清單，被配置設定到同一個索引上的多個節點可以用這個單向連結清單連接配接起來。
如（借用例子）： 鍵值對k2, v2與鍵值對k1, v1通過計算後的索引值都為2，這時及産生沖突，但是可以通道next指針将k2, k1所在的節點連接配接起來，這樣就解決了哈希的沖突問題
3、再哈希法
再哈希法了解起來比較簡單，再哈希法又叫雙哈希法，有多個不同的Hash函數，當發生沖突時，就可以使用第二個函數、如果在發生沖突繼續使用第三個函數、以此類推，一直到無沖突為止，再哈希法雖然不容易發生聚集，但是大大增加了計算時間。
4、建立公共溢出區
原理：将哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表。
三、利用哈希沖突來進行攻擊
上面我提到，php和java之類的語言用的就是拉鍊法解決哈希沖突的。
其攻擊原理就是：構造惡意的資料使hash表退化為連結清單，每次插入資料都會周遊連結清單，消耗大量伺服器資源，進而達到攻擊目的。
例如：php的數組就是利用hash表實作的，下面用例子看看惡意構造的資料和普通資料的差別
<?php
$size = pow(2, 16);
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 個惡意的元素需要 ', $endTime - $startTime, ' 秒', "\n";
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 個普通元素需要 ', $endTime - $startTime, ' 秒', "\n";
上面的例子, 就是惡意構造資料，導緻每次資料的寫入都産生了哈希沖突，導緻每一次存入就會周遊整個連結清單，在我的機器上的執行結果如下:
（這是我機器配置高一些，還有就是php7優化了hash表的結構和算法，如果用的php5.6，時間會更久）
插入 65536 個惡意的元素需要 7.9304070472717 秒
插入 65536 個普通元素需要 0.0048370361328125 秒
可參考鳥哥部落格位址：PHP數組的Hash沖突執行個體 - 風雪之隅