大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第八章：查找-第四節(jié)-散列表查找

第四節(jié)散列表查找一、散列表的概念1、散列的概念"散列"既是一種存儲方式，又是一種查找方法。這種查找方法稱為散列查找。散列的基本思想是通過由散列函數(shù)決定的鍵值與散列地址之間的對應(yīng)關(guān)系來實現(xiàn)存儲組織和查找運(yùn)算。2、實例分析【例】有個線性表A=（3l，62，74，36，49，77），散列函數(shù)為H(key)=key％m即用元素的關(guān)鍵字key整除m，取其余數(shù)作為存儲該元素的散列地址，m一般取小于或等于散列表長的最大素數(shù)，在這里取m=1l，表長也為ll，因此可得到每個元素的的散列地址：H(31)=31％11=9；H(62)=62％ll=7；H(74)=74％ll=8；H(36)=36％11=3；H(49)=49％11=5；H(77)=77％11=0；散列表若在上面散列表中插入元素88、7等會出現(xiàn)沖突。采用散列技術(shù)時需要考慮的兩個主要問題是：①如何構(gòu)造（選擇）"均勻的"散列函數(shù)？②用什么方法解決沖突？二、散列函數(shù)的構(gòu)造方法1、直接地址法直接地址法是以關(guān)鍵字key本身或關(guān)鍵字加上某個常量C作為散列地址的方法。對應(yīng)的散列函數(shù)H(key)為：H(key)=key+C特點：方法計算簡單，并且沒有沖突。它適合于關(guān)鍵字的分布基本連續(xù)的情況，若關(guān)鍵字分布不連續(xù)，空號較多，將會造成較大的空間浪費(fèi)。2、數(shù)字分析法數(shù)字分析法是假設(shè)有一組關(guān)鍵字，每個關(guān)鍵字由n位數(shù)字組成，數(shù)字分析法是從中提取數(shù)字分布比較均勻的若干位作為散列地址。3、除余數(shù)法除余數(shù)法是一種最簡單也最常用的一種散列函數(shù)構(gòu)造方法。散列函數(shù)：H(k)=k％p其中，p最好選取小于或等于表長m的最大素數(shù)。4、平方取中法平方取中法是取關(guān)鍵字平方的中間幾位作為散列地址的方法5、折疊法折疊法是首先把關(guān)鍵字分割成位數(shù)相同的幾段(最后一段的位數(shù)可少一些)，段的位數(shù)取決于散列地址的位數(shù)，由實際情況而定，然后將它們的疊加和(舍去最高進(jìn)位)作為散列地址的方法?！纠筷P(guān)鍵字k=98123658，散列地址為3位，則將關(guān)鍵字從左到右每三位一段進(jìn)行劃分，得到的三個段為981、236和58，疊加后值為1275，取低3位275作為關(guān)鍵字98123658的元素的散列地址三、處理沖突的方法1、開放定址法開放定址法的思想：使用某種方法在散列表中形成一個探查序列，沿著此序列逐個單元進(jìn)行查找，直到找到一個空閑的單元時將新結(jié)點存入其中。開放定址法又分為線性探插法、二次探查法和雙重散列法。（1）線性探插法探查序列可以由下述公式得到：di=(d+i)%m其中：di表示第i次探查的地址，m表示散列表的長度?！纠吭O(shè)散列函數(shù)為h（key）=key％1l；散列地址表空間為0～l0，對關(guān)鍵字序列{27，13，55，32，18，49，24，38，43），利用線性探測法解決沖突，構(gòu)造散列表。并計算查找成功時的平均查找長度?！窘獯稹渴紫雀鶕?jù)散列函數(shù)計算散列地址h（27）=5；h（13）=2；h（55）=0；h（32）=10；h（18）=7；h（49）=5；h（24）=2；h（38）=5；h（43）=10；散列表查找成功時的平均查找長度ASL=（1×5＋2×2＋3×1＋4×1）/9≈1.78（2）二次探查法二次探查法的探查序列為：d0=H（K），d1=（d0+12）%md2=（d0

-12）%m，d3=（d0+22）%m，d4=（d0

-22）%m，……（3）雙重散列法雙重散列法是幾種方法中最好的方法，它的探查序列為：hi=（H（key）+i*H1（key））％m（0≤i≤m-1）即探查序列為：d=H（key），（d+l*H1（key））％m，（d+2*H1（key））％m，…等。2、拉鏈法(鏈地址法)用拉鏈法處理沖突的辦法是：把具有相同散列地址的關(guān)鍵字（同義詞）值放在同一個單鏈表中，稱為同義詞鏈表。【例】設(shè)散列函數(shù)為h（key）=key％1l；，對關(guān)鍵字序列{27，13，55，32，18，49，24，38，43），用拉鏈法構(gòu)造散列表，并計算查找成功時的平均查找長度。【解答】首先根據(jù)散列函數(shù)計算散列地址h（27）=5；h（13）=2；h（55）=0；h（32）=10；h（18）=7；h（49）=5；h（24）=2；h（38）=5；h（43）=10；查找成功時的平均查找長度=（1×5＋2×3＋3×1）/9≈1.55四、散列表的查找1、線性探查法解決沖突的查找和插入算法采用開放定值法構(gòu)造散列表的類型定義：#defineM997//M定義為表長，一般M為一個素數(shù)typedefstruct//定義散列表結(jié)點類型{KeyTypekey；DataTypedata；}NodeType；typedefNodeTypeHashTable[M]；//散列表類型（1）采用線性探查法的散列表查找算法intHashSearchl(HashTableHT，KeyTypeK，intm){//在長度為m的散列表HT中查找關(guān)鍵字值為K的元素位置intd，temp；d=K％m；//計算散列地址temp=d；//temp作為哨卡，防止進(jìn)入重復(fù)循環(huán)while(HT[d].key!=-32768)//當(dāng)散列地址中的key域不為空，則循環(huán){if(HT[d].key==K)returnd；//查找成功返回其下標(biāo)delsed=(d+1)％m；//計算下一個地址if(d==temp)return-l；//查找一周仍無空位置，返回-1表示失敗}returnd；//遇到空單元，查找失敗}（2）在散列表上插入一個結(jié)點的算法intHashInsertl(HashTableHT，NodeTypes，intm){//在HT表上插入一個新結(jié)點sintd；d=HashSearchl(HT，s.key，m)；//查找插入位置if(d==-1)return-1；//表滿，不能插入else{if(HT[d].key==s.key)return0；//表中已有該結(jié)點!else//找到一個開放的地址{HT[d]=s；//插入新結(jié)點Sreturn1；//插入成功｝}｝2、拉鏈法建立散列表上的查找和插入運(yùn)算采用拉鏈法的散列表類定義：typedefstructnode{//定義結(jié)點類型KeyTypekey；DataTypedata；structnode*next；｝HTNode；typedefHTNode*HT[M]；//定義散列表類型（1）查找算法HTNode*HashSearch2(HTT，KeyTypeK，intm){//在長度為m的散列表T中查找關(guān)鍵字值為K的元素位置HTNode*p=T[K％m]；//取K所在鏈表的頭指針while(p!=NULL&&p->key!=K)p=p->next；//順鏈查找returnp；//查找成功p指向K結(jié)點的位置，不成功返回NULL（2）插入算法intHashInsert2(HTT，HTNode*s，intm){//采用頭插法在T表上插入一個新結(jié)點intd；HTNode*p=HashSearch2(T，s->key，m)；//查找表中有無待插結(jié)點if(P!=NULL)return0；//說明表中已有該結(jié)點else//將*s插入在相應(yīng)鏈表的表頭上{d=s->key%m；s->next=T[d]；T[d]=s；return1；//說明插入成功}｝3、幾種處理沖突方法的散列表的平均查找長度比較【例】設(shè)散列函數(shù)h(k)=k％13，散列表地址空間為0～12，對給定的關(guān)鍵字序列（19，14,01，68，20，84，27，26，50，36）分別以拉鏈法和線性探查法解決沖突構(gòu)造散列表，畫出所構(gòu)造的散列表，指出在這兩個散列表中查找每一個關(guān)鍵字時進(jìn)行比較的次數(shù)，并分析在等概率情況下查找成功和不成功時的平均查找長度以及當(dāng)結(jié)點數(shù)為n=10時的順序查找和二分查找成功與不成功的情況?！窘獯稹渴紫雀鶕?jù)散列函數(shù)計算散列地址h（19）=6；h（14）=1；h（01）=1；h（68）=3；h（20）=7；h（84）=6；h（27）=1；h（26）=0；h（50）=11；h（36）=10；（1）線性探查法解決沖突構(gòu)造散列表：查找成功的平均查找長度=（1×7＋2×1＋3×1＋4×1）/10=1.6查找不成功的平均查找長度=（6＋5＋4＋3＋2＋1＋4＋3＋2＋1＋3＋2＋1）/13≈2.85（2）拉鏈法解決沖突構(gòu)造散列表查找成功的平均查找長度=（1×7＋2×2＋3×1）/10=1.4查找不成功的平均查找長度（不包括空指針的比較）=（1＋3＋0＋1＋0＋0＋2＋1＋0＋0＋1＋1＋0）/13≈0.7當(dāng)n=10時，順序查找成功的平均查找長度=（10＋1）/2=5.5順序查找不成功的平均查找長度=10＋1=11n=10的有序表的判定樹：當(dāng)n=10時，二分查找成功的平均查找長度=（1×1＋2×2＋3×3＋4×3）/10≈3二分查找不成功的平均查找長度=（3×2＋3×1＋4×2＋3×1＋4×23×1＋4×2）/11≈3.2注意：結(jié)點個數(shù)n，散列表長度為m，散列表的平均查找長度不是n的函數(shù)，而是裝填因子的函數(shù)，采用四種不同方法處理沖突時得出的散列表