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

哈希表的基本思想:“一次”查找成功。關(guān)鍵字集合映射函數(shù)H地址空間H(key)ASL的T(n)=O(1)。通常設(shè)定一個一維數(shù)組空間存儲記錄集合，則H(key)指示數(shù)組中的下標。稱這個一維數(shù)組為哈希(Hash)表或散列表。稱映射函數(shù)H為哈希函數(shù)。H(key)為哈希地址9.3.1什么是哈希表9.3哈希表1哈希表的基本思想:關(guān)鍵字集合映射函數(shù)H地址空間H(key一、直接地址法取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址即：H(key)=key或：H(key)=a*key+b其中，a，b為常數(shù)。常用的構(gòu)造哈希(散列)函數(shù)的方法：假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。二、數(shù)字分析法2一、直接地址法常用的構(gòu)造哈希(散列)函數(shù)的方法：假設(shè)四、折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分，然后將這幾部分疊加，舍去進位作為哈希地址。移位疊加：將分割之后的每一部分的最低位對齊，然后相加。間界疊加：從一端向令一端沿分割界來回折疊，然后相加。三、平方取中法將k平方后的中間幾位取為哈希地址。位數(shù)由表長決定3四、折疊法三、平方取中法3五、除留余數(shù)法當(dāng)關(guān)鍵字k為整數(shù)時，用關(guān)鍵字除以一個整數(shù)p所得余數(shù)作為哈希的地址。

H(key)=key%p4五、除留余數(shù)法49.3.3處理沖突的方法設(shè)hash表的長度為m，沖突是指j=H(K)的位置已有記錄，(0≤j≤m-1)“處理沖突”——為K另找一個“空”的地址。一.開放地址法：哈希表的存儲結(jié)構(gòu)：typedefstruct{KeyType

key；

//關(guān)鍵字成員

…；

//其它成員

}elemtypetypedef

elemtype

hashtable[m]

；59.3.3處理沖突的方法設(shè)hash表的長度為m，沖突是利用下面的公式求“下一個”地址。

Hi=(H(key)+di)%m,

di是增量序列，

(i=1，2，…，k，且k≤m-1)根據(jù)d

的取值不同，開放地址法又可分為：(Ⅰ)線性探測再散列：

di=1，2，3，…，m-1(Ⅱ)二次探測再散列：

di=12，-12，22，-22，…，k2此時：Hi=(H(key)+m+di)%m,(Ⅲ)隨機探測再散列

di=偽隨機序列6利用下面的公式求“下一個”地址。6012345678910012345678910例如:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)

：H(key)=key%11

(表長=11)191011232141551683191011232141684若采用線性探測再散列處理沖突若采用二次探測再散列處理沖突11682236555111382136270123在查找概率相同的情況下，查找成功時的ASLASLsucc

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

=(1*5+2*2+3+4)/9=16/9查找不成功時的ASLASLunsucc=()/11=/11若采用二次探測再散列處理沖突0123456789101910112321416845511138213629在查找概率相同的情況下,若采用二次探測再散列處理沖突0線性探測再散列的優(yōu)點：只要哈希表未滿，總能找到一個空地址。缺點：會產(chǎn)生二次聚集。

7019331801…56789…1210線性探測再散列的優(yōu)點：二、鏈地址法在哈希表的每一個單元中存放一個指針，將所有的同義詞連成一個鏈表。假設(shè)哈希地址在區(qū)間[0..m-1]上，則哈希表為一個指針數(shù)組。typedefstructnode{//定義鏈表中結(jié)點

KeyTypekey；

其它成員；

structnode*next；

}Node，*Nodeptr； typedefNodeptr

chainhash[m]；//定義指針數(shù)組11二、鏈地址法110123456111982685514013623ASLsucc=(6×1+2×2+3)/9=13/9例1:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}哈希函數(shù)H(key)=key%7

(表長=7)ASLunsucc=(4×1+1×2+3)/7=9/7120111982685514013623ASLs例2：有一組關(guān)鍵字{BITE,EACH,BITTER,BROOM,AND,ALSO,HASH,EGGS}，現(xiàn)以關(guān)鍵字中第一個字母在字母表中的位置為該關(guān)鍵字的哈希函數(shù)值，鏈地址哈希表如下：ASLsucc=(4*1+3*2+1*3)/8=13/8

1

ANDALSO2BITEBITTERBROOM┇5EACHEGGS┇8HASH┇2613例2：有一組關(guān)鍵字{BITE,EACH,BITTER,四、建立一個公共溢出區(qū)設(shè)向量hashtable[m]為基本表。另設(shè)向量overtable[V]為溢出表。所有與基本表中關(guān)鍵字為同義詞的記錄都填入溢出表例：關(guān)鍵字表(a，d，e，f，d1，d2，f1，g)，表長m=11，H(key)=i1%11；i1為首字母在字母表中的位置。012345678910基本表ad012345678910溢出表efd1d2f1g14四、建立一個公共溢出區(qū)例：關(guān)鍵字表(a，d，e，f，d19.3.4哈希表的查找及分析一.哈希表的查找查找過程和建立哈希表的過程基本一致。(1)計算哈希地址。(2)相應(yīng)地址上沒有記錄，則查找不成功。(3)相應(yīng)地址上有記錄，則比較關(guān)鍵字，①若和給定值相等，則查找成功。②不相等，則根據(jù)造表時設(shè)定的處理沖突的方法找“下一地址”，直到哈希表中某個位置為空或者表中的關(guān)鍵字與給定值相同為止。159.3.4哈希表的查找及分析一.哈希表的查找15inthashsrch(hashtable

shtable，KeyTypek){//已知hash函數(shù)為hash(key),散列表的表長為m，地址序列//Hi=(hash(key)+di)%m,di=1,2,…,m-1

j=hash(k)；if(shtable[j]==nullrecd)return(0)；elseif(shtable[j].key==k)return(j)；

else

do{

j=(j+1)%m；}

//線性探測再散列while(shtable[j].key≠k

&&

shtable[j]≠nullrecd)if(shtable[j]==nullrecd)return(0)；elsereturn(j)；}}

//hashsrch

16inthashsrch(hashtableshtable二.分析比較次數(shù)取決于三個因素：哈希函數(shù)、處理沖突的方法、哈希表的裝填因子

在一般情況下，處理沖突方法相同的哈希表，其平均查找長度依賴于哈希表的裝填因子。(1)查找成功時的平均查找長度①線性探測ASLl≈②隨機探測、二次探測ASLr≈③鏈地址法ASLc≈

17二.分析(1)查找成功時的平均查找長度17例：已知一個含有100個記錄的表，關(guān)鍵字為中國人姓氏的拼音，請給出此表的一個哈希表設(shè)計方案，要求它在等概率情況下查找成功的平均查找長度不超過3。

ASLl=≤3，(1)用線性探測再散列處理沖突建立散列表存儲則由：ASLl

≤3，可求出求得≤4/518例：已知一個含有100個記錄的表，關(guān)鍵字為中國人姓氏的拼音，(3)關(guān)鍵字分析：開頭a-z，最長6位。選擇hash函數(shù)：

hash(key)=5*(i-1)+L其中，i為第一個字母在字母表中的序號，L為關(guān)鍵字的長度。(2)設(shè)表長：由=記錄長度n/表長m,表長m=n/≥(100*5)/4=125取表長m=13319(3)關(guān)鍵字分析：開頭a-z，最長6位。(2)設(shè)表長：由9.3、9.9、9.13、9.14、9.19、9.21作業(yè)209.3、9.9、9.13、9.14、9.19、哈希表的基本思想:“一次”查找成功。關(guān)鍵字集合映射函數(shù)H地址空間H(key)ASL的T(n)=O(1)。通常設(shè)定一個一維數(shù)組空間存儲記錄集合，則H(key)指示數(shù)組中的下標。稱這個一維數(shù)組為哈希(Hash)表或散列表。稱映射函數(shù)H為哈希函數(shù)。H(key)為哈希地址9.3.1什么是哈希表9.3哈希表21哈希表的基本思想:關(guān)鍵字集合映射函數(shù)H地址空間H(key一、直接地址法取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址即：H(key)=key或：H(key)=a*key+b其中，a，b為常數(shù)。常用的構(gòu)造哈希(散列)函數(shù)的方法：假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。二、數(shù)字分析法22一、直接地址法常用的構(gòu)造哈希(散列)函數(shù)的方法：假設(shè)四、折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分，然后將這幾部分疊加，舍去進位作為哈希地址。移位疊加：將分割之后的每一部分的最低位對齊，然后相加。間界疊加：從一端向令一端沿分割界來回折疊，然后相加。三、平方取中法將k平方后的中間幾位取為哈希地址。位數(shù)由表長決定23四、折疊法三、平方取中法3五、除留余數(shù)法當(dāng)關(guān)鍵字k為整數(shù)時，用關(guān)鍵字除以一個整數(shù)p所得余數(shù)作為哈希的地址。

H(key)=key%p24五、除留余數(shù)法49.3.3處理沖突的方法設(shè)hash表的長度為m，沖突是指j=H(K)的位置已有記錄，(0≤j≤m-1)“處理沖突”——為K另找一個“空”的地址。一.開放地址法：哈希表的存儲結(jié)構(gòu)：typedefstruct{KeyType

key；

//關(guān)鍵字成員

…；

//其它成員

}elemtypetypedef

elemtype

hashtable[m]

；259.3.3處理沖突的方法設(shè)hash表的長度為m，沖突是利用下面的公式求“下一個”地址。

Hi=(H(key)+di)%m,

di是增量序列，

(i=1，2，…，k，且k≤m-1)根據(jù)d

的取值不同，開放地址法又可分為：(Ⅰ)線性探測再散列：

di=1，2，3，…，m-1(Ⅱ)二次探測再散列：

di=12，-12，22，-22，…，k2此時：Hi=(H(key)+m+di)%m,(Ⅲ)隨機探測再散列

di=偽隨機序列26利用下面的公式求“下一個”地址。6012345678910012345678910例如:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)

：H(key)=key%11

(表長=11)191011232141551683191011232141684若采用線性探測再散列處理沖突若采用二次探測再散列處理沖突116822365551113821362270123在查找概率相同的情況下，查找成功時的ASLASLsucc

=(1*4+2*2+3+5+6)/9=22/9查找不成功時的ASLASLunsucc=(9+8+7+6+5+4+3+2+1)/11=56/11若采用線性探測再散列處理沖突012345678910191011232141551683116822365平均查找長度ASL：28在查找概率相同的情況下，若采用線性探測再散列處理沖突0在查找概率相同的情況下,查找成功時的ASLASLsucc

=(1*5+2*2+3+4)/9=16/9查找不成功時的ASLASLunsucc=()/11=/11若采用二次探測再散列處理沖突01234567891019101123214168455111382136229在查找概率相同的情況下,若采用二次探測再散列處理沖突0線性探測再散列的優(yōu)點：只要哈希表未滿，總能找到一個空地址。缺點：會產(chǎn)生二次聚集。

7019331801…56789…1230線性探測再散列的優(yōu)點：二、鏈地址法在哈希表的每一個單元中存放一個指針，將所有的同義詞連成一個鏈表。假設(shè)哈希地址在區(qū)間[0..m-1]上，則哈希表為一個指針數(shù)組。typedefstructnode{//定義鏈表中結(jié)點

KeyTypekey；

其它成員；

structnode*next；

}Node，*Nodeptr； typedefNodeptr

chainhash[m]；//定義指針數(shù)組31二、鏈地址法110123456111982685514013623ASLsucc=(6×1+2×2+3)/9=13/9例1:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}哈希函數(shù)H(key)=key%7

(表長=7)ASLunsucc=(4×1+1×2+3)/7=9/7320111982685514013623ASLs例2：有一組關(guān)鍵字{BITE,EACH,BITTER,BROOM,AND,ALSO,HASH,EGGS}，現(xiàn)以關(guān)鍵字中第一個字母在字母表中的位置為該關(guān)鍵字的哈希函數(shù)值，鏈地址哈希表如下：ASLsucc=(4*1+3*2+1*3)/8=13/8

1

ANDALSO2BITEBITTERBROOM┇5EACHEGGS┇8HASH┇2633例2：有一組關(guān)鍵字{BITE,EACH,BITTER,四、建立一個公共溢出區(qū)設(shè)向量hashtable[m]為基本表。另設(shè)向量overtable[V]為溢出表。所有與基本表中關(guān)鍵字為同義詞的記錄都填入溢出表例：關(guān)鍵字表(a，d，e，f，d1，d2，f1，g)，表長m=11，H(key)=i1%11；i1為首字母在字母表中的位置。012345678910基本表ad012345678910溢出表efd1d2f1g34四、建立一個公共溢出區(qū)例：關(guān)鍵字表(a，d，e，f，d19.3.4哈希表的查找及分析一.哈希表的查找查找過程和建立哈希表的過程基本一致。(1)計算哈希地址。(2)相應(yīng)地址上沒有記錄，則查找不成功。(3)相應(yīng)地址上有記錄，則比較關(guān)鍵字，①若和給定值相等，則查找成功。②不相等，則根據(jù)造表時設(shè)定的處理沖突的方法找“下一地址”，直到哈希表中某個位置為空或者表中的關(guān)鍵字與給定值相同為止。359.3.4哈希表的查找及分析一.哈希表的查找15inthashsrch(hashtable

shtable，KeyTypek){//已知hash函數(shù)為hash(key),散列表的表長為m，地址序列//Hi=(hash(key