散列表的基本概念
- 散列函數(shù)：一個把查找表中的關鍵字映射成該關鍵字對應的地址的函數(shù)，記為Hash(key) = Addr
- 沖突：散列函數(shù)可能會把兩個或兩個以上的不同關鍵字映射到統(tǒng)一地址
- 同義詞：這些發(fā)生碰撞的不用關鍵字
- 散列函數(shù)的兩點要求：1.散列函數(shù)應盡量減少這樣的沖突 2.設計好處理沖突的方法
- 散列表：根據(jù)關鍵字而直接進行訪問的數(shù)據(jù)結構，建立了關鍵字和存儲地址之間的中直接映射關系
散列函數(shù)的構造方法
在構造散列函數(shù)時，必須注意以下幾點：
1）散列函數(shù)的定義域必須包含全部需要存儲的關鍵字，而值域的范圍則依賴于散列表的大小或地址范圍
2）散列函數(shù)計算出來的地址應該能等概率、均勻地分布在整個空間中，從而減少沖突的發(fā)生
3）散列函數(shù)因盡量簡單，能夠在較多的時間內計算出任意關鍵字對應的散列地址
常見的散列函數(shù)
| 方法名 | 函數(shù) | 優(yōu)點 | 缺點 |
|---|---|---|---|
| 直接定址法 | H（key） = a x key + b | 不會產(chǎn)生沖突 | 關鍵字分布不均，造成空間浪費 |
| 除留余數(shù)法 | H（key）= key %p | 關鍵字分布較均勻 | 會產(chǎn)生沖突 |
| 數(shù)學分析法 | 分析關鍵字集合選取重復概率較小的數(shù)位作關鍵字 | 更換關鍵字集合需重新構造散列函數(shù) | |
| 平方取中法 | 取關鍵字平方值的中間幾位作為關鍵地址 | 散列地址分布較均勻 | |
| 折疊法 | 將關鍵字分割成位數(shù)相同的幾個部分然后取這幾個部分的疊加個作為散列地址 |
處理沖突的方法
1.開放地址法
Hi = (H(key)+di)%m
1)線性探測法：di = 0,1,2,3,...,m-1,沖突法發(fā)生時，順序查看表中下一個單元，直到找到一個空閑單元或 查遍全表
2）平方探測法：di = 0*0,1*1，-1*1,2*2，-2*2，...,k*k,-k*k 是一種比較好的處理宏圖的方法，可以避免癡線“堆積”問題，它的缺點是不能探測到散列表上的所有大院，但至少能探測到一半單元
3）再散列法：di = Hash2(key)
4) 偽隨機序列法：當di = 為隨機數(shù)序列時
2.拉鏈法
適合經(jīng)常進行插入和刪除操作
