哈希表的定義、查找及分析

1、哈希表的基本思想:“一次”查找成功。關鍵字集合映射函數(shù) H地址空間 H(key)ASL的T(n)=O(1)。通常設定一個一維數(shù)組空間存儲記錄集合，則H(key)指示數(shù)組中的下標。稱這個一維數(shù)組為哈希(Hash)表或散列表。稱映射函數(shù) H 為哈希函數(shù)。 H(key)為哈希地址9.3.1 什么是哈希表9.3 哈希表1第一頁，共二十一頁。一、直接地址法取關鍵字或關鍵字的某個線性函數(shù)值為哈希地址即： H(key) = key 或： H(key) = a* key + b其中，a， b為常數(shù)。常用的構造哈希(散列)函數(shù)的方法： 假設關鍵字集合中的每個關鍵字都是由 s 位數(shù)字組成 (u1, u2, , u

2、s)，分析關鍵字集中的全體， 并從中提取分布均勻的若干位或它們的組合作為地址。二、數(shù)字分析法2第二頁，共二十一頁。四 、折疊法將關鍵字分割成位數(shù)相同的幾部分，然后將這幾部分疊加，舍去進位作為哈希地址。移位疊加：將分割之后的每一部分的最低位對齊，然后相加。間界疊加：從一端向令一端沿分割界來回折疊，然后相加。三、平方取中法將k平方后的中間幾位取為哈希地址。位數(shù)由表長決定3第三頁，共二十一頁。五、 除留余數(shù)法當關鍵字k為整數(shù)時，用關鍵字除以一個整數(shù)p 所得余數(shù)作為哈希的地址。 H(key) = key % p4第四頁，共二十一頁。9.3.3 處理沖突的方法設hash表的長度為m，沖突是指 j=H(K

3、) 的位置已有記錄，(0jm-1)“處理沖突” 為K另找一個“空”的地址。一. 開放地址法：哈希表的存儲結構：typedef struct KeyType key； /關鍵字成員 ； /其它成員 elemtypetypedef elemtype hashtablem ；5第五頁，共二十一頁。利用下面的公式求“下一個”地址。 Hi = (H(key) + di ) % m, di是增量序列， (i=1，2，k，且km-1)根據(jù)d 的取值不同，開放地址法又可分為：()線性探測再散列： di = 1，2，3， ，m-1 ()二次探測再散列： di = 12，-12，22，-22，k2 此時：Hi =

4、 (H(key) +m+ di ) % m,()隨機探測再散列 di = 偽隨機序列6第六頁，共二十一頁。0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 10例如: 關鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 設定哈希函數(shù) ：H(key) = key % 11 (表長=11)191011232141551683191011232141684若采用線性探測再散列處理沖突若采用二次探測再散列處理沖突1168223655511138213627第七頁，共二十一頁。在查找概率相同的情況下，查找成功時的ASLASLsucc =(1

5、*4+2*2+3+5+6)/9 =22/9查找不成功時的ASLASLunsucc=(9+8+7+6+5+4+3+2+1)/11=56/11若采用線性探測再散列處理沖突0 1 2 3 4 5 6 7 8 9 10191011232141551683116822365平均查找長度ASL：8第八頁，共二十一頁。在查找概率相同的情況下,查找成功時的ASLASLsucc =(1*5+2*2+3+4) /9 =16/9查找不成功時的ASLASLunsucc=( )/11= /11若采用二次探測再散列處理沖突0 1 2 3 4 5 6 7 8 9 101910112321416845511138213629

6、第九頁，共二十一頁。線性探測再散列的優(yōu)點：只要哈希表未滿，總能找到一個空地址。缺點：會產(chǎn)生二次聚集。 70 19 33 18 0 1 5 6 7 8 9 1210第十頁，共二十一頁。二、 鏈地址法在哈希表的每一個單元中存放一個指針，將所有的同義詞連成一個鏈表。假設哈希地址在區(qū)間0 . m-1上，則哈希表為一個指針數(shù)組。typedef struct node /定義鏈表中結點 KeyType key； 其它成員 ； struct node *next； Node，*Nodeptr；typedef Nodeptr chainhashm；/ 定義指針數(shù)組11第十一頁，共二十一頁。0123456111

7、982685514013623ASLsucc=(61+22+3)/9=13/9例1: 關鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 哈希函數(shù) H(key) = key % 7 (表長=7)ASLunsucc=(41+12+3)/7=9/712第十二頁，共二十一頁。例2：有一組關鍵字BITE, EACH, BITTER, BROOM, AND, ALSO,HASH, EGGS ，現(xiàn)以關鍵字中第一個字母在字母表中的位置為該關鍵字的哈希函數(shù)值，鏈地址哈希表如下：ASLsucc=(4*1+3*2+1*3)/8=13/8 1 AND ALSO 2 BITE BITTE

8、R BROOM 5 EACH EGGS 8 HASH 2613第十三頁，共二十一頁。四、 建立一個公共溢出區(qū)設向量hashtablem為基本表。另設向量overtableV為溢出表。所有與基本表中關鍵字為同義詞的記錄都填入溢出表例：關鍵字表 (a，d，e，f，d1，d2，f1，g)， 表長 m=11，H(key)= i1 % 11； i1為首字母在字母表中的位置。0 1 2 3 4 5 6 7 8 9 10 基本表ad0 1 2 3 4 5 6 7 8 9 10 溢出表efd1d2f1g14第十四頁，共二十一頁。9.3.4 哈希表的查找及分析一.哈希表的查找查找過程和建立哈希表的過程基本一致。

9、(1) 計算哈希地址。(2) 相應地址上沒有記錄，則查找不成功。(3) 相應地址上有記錄，則比較關鍵字， 若和給定值相等，則查找成功。 不相等，則根據(jù)造表時設定的處理沖突的方法找“下一地址”，直到哈希表中某個位置為空或者表中的關鍵字與給定值相同為止。15第十五頁，共二十一頁。int hashsrch(hashtable shtable，KeyType k) /已知hash函數(shù)為hash(key), 散列表的表長為m，地址序列/ Hi=(hash(key)+di)% m, di=1,2, ,m-1 j=hash(k)； if(shtablej=nullrecd) return(0)； else

10、if(shtablej.key=k)return(j)； else do j=(j+1) % m； /線性探測再散列while(shtablej.keyk & shtablejnullrecd) if (shtablej=nullrecd) return(0)； else return(j)； / hashsrch 16第十六頁，共二十一頁。二. 分析比較次數(shù)取決于三個因素：哈希函數(shù)、處理沖突的方法、哈希表的裝填因子 在一般情況下，處理沖突方法相同的哈希表，其平均查找長度依賴于哈希表的裝填因子。(1)查找成功時的平均查找長度線性探測 ASLl 隨機探測、二次探測 ASLr 鏈地址法 ASLc

11、17第十七頁，共二十一頁。例：已知一個含有100個記錄的表，關鍵字為中國人姓氏的拼音，請給出此表的一個哈希表設計方案，要求它在等概率情況下查找成功的平均查找長度不超過3。 ASLl = 3，(1) 用線性探測再散列處理沖突建立散列表存儲則由 ： ASLl 3，可求出 求得 4/518第十八頁，共二十一頁。(3) 關鍵字分析：開頭a-z，最長6位。 選擇hash函數(shù)： hash(key) = 5*(i-1) + L 其中，i為第一個字母在字母表中的序號，L為關鍵字的長度。(2) 設表長：由 =記錄長度n/表長m , 表長 m = n/ (100*5)/4=125 取表長 m = 13319第十九頁，共二十一頁。9.3 、9.9 、 9.13、9.14 、 9.19、9.21作業(yè)20第二十頁，共二十一頁。內容總結哈希表的基本思想:。通常設定一個一維數(shù)組空間存儲記錄集合，則H(key)指示數(shù)組中的下標。取關鍵字或關鍵字的某個線性函數(shù)值為哈希地址。其中，a， b為常數(shù)。常用的構造哈希(散列)函數(shù)的方法：。將關鍵字分割成位數(shù)相同的幾部分，然后將這幾部分疊加，舍去進位作為哈希地址。移位疊