查找與散列（Hash）

1.查找的一些概念

查找——在給定集合中查找特定的元素。

在查找的過程中，查找的長度是指關鍵字間的比較次數，而平均查找長度則是數學上的期望：ASL=P1*C1+P2*C2+...+Pn*Cn。 Pi為查找第i個元素的概率，Ci為查找第i個元素所需的查找長度。一般認為每個元素查找概率相同。平均查找長度分為查找成功和查找不成功長度兩種。

對於順序查找來說。ASL（成功）=(1+2+...+n)*1/n=(n+1)/2；ASL(不成功)=n。

折半查找的查找過程可以用判定樹來描述。

ASL(成功)=int[log(2)(n)]+1。

例題：【2010研招】已知一個長度為16的順序表L，其元素有序，若采用折半查找去查找一個不存在的元素，則關鍵字的比較次數最多是（5次）

答：具有n個結點的判定樹高度為int[log(2)(n)]+1。所以最多比較5次。

2.散列表(Hash)

散列：把元素的內容與元素的存儲地址關聯起來，提高查找效率。

散列函數：實現從元素值到存儲地址的映射。

散列表：記錄元素值到存儲地址的映射。

常用散列函數：

1.直接定址法:H(key)=a*key+b。

2.除留餘數法：H(key)=key mod b。

處理衝突的方法：

1.拉鏈法——把所有同義詞存儲在一個鏈表中。

2.線性探測法——衝突發生時，查找該衝突位置後麵的單元，遇到空單元時把地址填進去。

散列表的查找效率取決於三個因素：散列函、衝突處理方法和填裝因子。

填裝因子=元素數目/散列表長度。填裝因子越大，散列表越滿，發生衝突的可能性就大。

例題：【2010研招】將關鍵字序列(7,8,30,11,18,9,14)7個元素散列存儲到散列表中。散列表的存儲空間是下標從0開始的一維數組，散列函數為H(key)=key*3 mod 7。處理衝突的方法為線性探測再散列法，填充因子為0.7。

1）請畫出散列表；

2）分別計算等概率情況下，查找成功和查找不成功的平均查找長度。

引申：

他人blog——從頭到尾徹底解析Hash 表算法

最後更新：2017-04-03 12:56:01