/xtzmm1215/article/details/47177701
/afterlife_qiye/article/details/47976917
首先在元素的關鍵字k和元素的存儲位置p之間建立壹個對應關系f，使得p=f(k)，f稱為 哈希函數 。創建哈希表時，把關鍵字為k的元素直接存入地址為f(k)的單元；以後當查找關鍵字為k的元素時，再利用哈希函數計算出該元素的存儲位置p=f(k)，從而達到按關鍵字直接存取元素的目的。
沖突 ：當關鍵字集合很大時，關鍵字值不同的元素可能會映象到哈希表的同壹地址上，即 k1≠k2 ，但 H（k1）=H（k2），這種現象稱為 沖突 ，此時稱k1和k2為同義詞。
哈希法主要包括以下兩方面的內容：
1）如何構造哈希函數
2）如何處理沖突。
本文介紹解決沖突的辦法
這種方法也稱 再散列法 ，其基本思想是：當關鍵字key的哈希地址p=H（key）出現沖突時，以p為基礎，產生另壹個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另壹個哈希地址p2，…，直到找出壹個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有壹個通用的再散列函數形式：
主要有以下三種：
線性探測再散列
這種方法的特點是：沖突發生時，順序查看表中下壹單元，直到找出壹個空單元或查遍全表。
二次探測再散列
偽隨機探測再散列
具體實現時，應建立壹個偽隨機數發生器，（如i=(i+p) % m），並給定壹個隨機數做起點。
從上述例子可以看出，線性探測再散列容易產生“二次聚集”，即在處理同義詞的沖突時又導致非同義詞的沖突。例如，當表中i, i+1 ,i+2三個單元已滿時，下壹個哈希地址為i, 或i+1 ,或i+2，或i+3的元素，都將填入i+3這同壹個單元，而這四個元素並非同義詞。線性探測再散列的優點是：只要哈希表不滿，就壹定能找到壹個不沖突的哈希地址，而二次探測再散列和偽隨機探測再散列則不壹定。
拉鏈法解決沖突的做法是：將所有關鍵字為同義詞的結點鏈接在同壹個單鏈表中。若選定的散列表長度為m，則可將散列表定義為壹個由m個頭指針組成的指針數 組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。
特點
這種方法是同時構造多個不同的哈希函數：
當哈希地址Hi=RH1（key）發生沖突時，再計算Hi=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。
這種方法的基本思想是：將哈希表分為 基本表 和 溢出表 兩部分，凡是和基本表發生沖突的元素，壹律填入溢出表