構(gòu)造哈希表的幾種方法
直接定址法
f(key) = a × key + b
除留余數(shù)法
f( key ) = key mod p ( p ≤ m )
mod是取模（求余數(shù)）的意思。事實(shí)上，這方法不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方取中后再取模。
1. 平方取中法
2. 折疊法
3. 隨機(jī)數(shù)法
4. 數(shù)學(xué)分析法
哈希沖突（碰撞）以及處理
開(kāi)發(fā)定址法
所謂的開(kāi)放定址法就是一旦發(fā)生了沖突，就去尋找下一個(gè)空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。
- 線(xiàn)性探測(cè)法
f(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1)
用開(kāi)放定址法解決沖突的做法是：當(dāng)沖突發(fā)生時(shí)，使用某種探測(cè)技術(shù)在散列表中形成一個(gè)探測(cè)序列。沿此序列逐個(gè)單元地查找，直到找到給定的關(guān)鍵字，或者碰到一個(gè)開(kāi)放的地址（即該地址單元為空）為止（若要插入，在探查到開(kāi)放的地址，則可將待插入的新結(jié)點(diǎn)存人該地址單元）。查找時(shí)探測(cè)到開(kāi)放的地址則表明表中無(wú)待查的關(guān)鍵字，即查找失敗。
- 二次探測(cè)法
f(key) = (f(key)+di) MOD m (di = 1^2, -1^2, 2^2, -2^2,……, q^2, -q^2, q <= m/2)
注：1^2 表示是 1的平方
設(shè)哈希表長(zhǎng)m＝14，哈希函數(shù)H（key）＝key％11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址為空。如果用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是？
因?yàn)?f(49) = 5 與 f(38) 沖突
所以需要采用二次探測(cè)再散列來(lái)處理沖突
(f(49) + di) MOD 14(哈希表長(zhǎng)m＝14)
第一次 di = 1^2
（5 + 1）MOD 14 = 6 與addr(61)=6沖突
第二次 di = -1^2
（5 - 1）MOD 14 = 4 與addr(15)=4 沖突
第三次 di = 2^2
（5 + 4）MOD 14 = 9 沒(méi)有沖突
所以 addr(49)=9
- 鏈地址法
前面我們談到了散列沖突處理的開(kāi)放定址法，它的思路就是一旦發(fā)生了沖突，就去尋找下一個(gè)空的散列地址。那么，有沖突就非要換地方呢，我們直接就在原地處理行不行呢？
答案是可以的，就是鏈地址法，就好比Java里的HashMap的數(shù)據(jù)結(jié)構(gòu)一樣。
