哈希表的定義查找及

哈希表的基本思想:“一次”查找成功。關(guān)鍵字集合映射函數(shù)H地址空間H(key)ASL的T(n)=O(1)。通常設(shè)定一個一維數(shù)組空間存儲記錄集合，則H(key)指示數(shù)組中的下標(biāo)。稱這個一維數(shù)組為哈希(Hash)表或散列表。稱映射函數(shù)H為哈希函數(shù)。H(key)為哈希地址9.3.1什么是哈希表9.3哈希表1一、直接地址法取關(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四、折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分，然后將這幾部分疊加，舍去進(jìn)位作為哈希地址。移位疊加：將分割之后的每一部分的最低位對齊，然后相加。間界疊加：從一端向令一端沿分割界來回折疊，然后相加。三、平方取中法將k平方后的中間幾位取為哈希地址。位數(shù)由表長決定3五、除留余數(shù)法當(dāng)關(guān)鍵字k為整數(shù)時，用關(guān)鍵字除以一個整數(shù)p所得余數(shù)作為哈希的地址。

H(key)=key%p49.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]

；5利用下面的公式求“下一個”地址。

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,(Ⅲ)隨機(jī)探測再散列

di=偽隨機(jī)序列6012345678910012345678910例如:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)

：H(key)=key%11

(表長=11)191011232141551683191011232141684若采用線性探測再散列處理沖突若采用二次探測再散列處理沖突1168223655511138213627在查找概率相同的情況下，查找成功時的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在查找概率相同的情況下,查找成功時的ASLASLsucc

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

7019331801…56789…1210二、鏈鏈地地址法法在哈希表表的每每一個個單元元中存放一一個指指針，將所有有的同同義詞詞連成成一個個鏈表表。假設(shè)哈哈希地地址在在區(qū)間間[0..m-1]上，則哈希希表為為一個個指針數(shù)數(shù)組。typedefstructnode{//定定義鏈鏈表中中結(jié)點(diǎn)點(diǎn)KeyTypekey；其它成成員；；structnode*next；}Node，，*Nodeptr；typedefNodeptrchainhash[m]；//定定義義指針針數(shù)組組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/712例2：有一一組關(guān)關(guān)鍵字字{BITE,EACH,BITTER,BROOM,AND,ALSO,HASH,EGGS}，現(xiàn)以以關(guān)鍵鍵字中中第一一個字字母在在字母母表中中的位位置為為該關(guān)關(guān)鍵字字的哈希函函數(shù)值，鏈地址址哈希希表如下：：ASLsucc=(4*1+3*2+1*3)/8=13/81ANDALSO2BITEBITTERBROOM┇5EACHEGGS┇8HASH┇2613四、建建立立一個個公共共溢出出區(qū)設(shè)向量量hashtable[m]為為基本本表。。另設(shè)向向量overtable[V]為為溢出出表。。所有與與基本本表中中關(guān)鍵鍵字為為同義義詞的的記錄錄都填填入溢溢出表表例：關(guān)關(guān)鍵字字表(a，d，e，f，d1，，d2，f1，，g)，表長m=11，H(key)=i1%11；；i1為首字字母在在字母母表中中的位位置。。012345678910基本表ad012345678910溢出表efd1d2f1g14哈哈希表表的查查找及及分析析一.哈哈希表表的查查找查找過過程和和建立立哈希希表的的過程程基本本一致致。(1)計計算哈哈希地地址。。(2)相相應(yīng)地地址上上沒有有記錄錄，則則查找找不成成功。。(3)相相應(yīng)地地址上上有記記錄，，則比比較關(guān)關(guān)鍵字字，①若和和給定定值相相等，，則查查找成成功。。②不相相等，，則根根據(jù)造造表時時設(shè)定定的處處理沖沖突的的方法找找“下下一地地址””，直直到哈哈希表表中某某個位位置為空或或者表表中的的關(guān)鍵鍵字與與給定定值相相同為為止。。15inthashsrch(hashtableshtable，KeyTypek){//已已知hash函函數(shù)為為hash(key),散散列表表的表表長為為m，，地址址序列列//Hi=(hash(key)+di)%m,di=1,2,…,m-1j=hash(k)；if(shtable[j]==nullrecd)return(0)；；elseif(shtable[j].key==k)return(j)；elsedo{j=(j+1)%m；}//線性探探測再再散列列while(shtable[j].key≠≠k&&shtable[j]≠≠nullrecd)if(shtable[j]==nullrecd)return(0)；；elsereturn(j)；；}}//hashsrch16二.分析析比較次數(shù)取取決于三個因素：哈希函數(shù)、、處理沖突突的方法、、哈希表的的裝填因子子在一般情況況下，處理理沖突方法法相同的哈哈希表，其其平均查找找長度依賴賴于哈希表表的裝填因因子。(1)查找成功時的平均查找長度①線性探測ASLl≈②隨機(jī)探測、二次探測ASLr≈③鏈地址法ASLc≈

17例：已知一一個含有100個記記錄的表，，關(guān)鍵字為為中國人姓姓氏的拼音音，請給出出此表的一一個哈希表表設(shè)計方案案，要求它它在等概率率情況下查查找成功的的平均查找找長度不超超過3。ASLl=≤3，(1)用用線性探測測再散列處處理沖突建建立散列表表存儲則由：ASL