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