國家級(jí)精品課程-《數(shù)據(jù)結(jié)構(gòu)與算法》

1、國家級(jí)精品課程數(shù)據(jù)結(jié)構(gòu)與算法張銘、趙海燕、王騰蛟、宋國杰、高軍http:/pkujpk/course/sjjg/北京大學(xué)信息科學(xué)與技術(shù)學(xué)院“數(shù)據(jù)結(jié)構(gòu)與算法”教學(xué)小組本章主筆：張銘版權(quán)所有，轉(zhuǎn)載或翻印必究第10章 檢索2 基本概念10.1 線性表的檢索10.2 集合的檢索10.3 散列表的檢索小結(jié)主要內(nèi)容3基本概念檢索檢索的效率非常重要尤其對(duì)于大數(shù)據(jù)量需要對(duì)數(shù)據(jù)進(jìn)行特殊的存儲(chǔ)處理在一組記錄集合中找到關(guān)鍵碼值等于給定值的某個(gè)記錄，或者找到關(guān)鍵碼值符合特定條件的某些記錄的過程4提高檢索效率的方法預(yù)排序建立索引散列技術(shù)當(dāng)散列方法不適合于基于磁盤的應(yīng)用程序時(shí)，我們可以選擇B樹方法排序算法本身比較費(fèi)時(shí)只是

2、預(yù)處理（在檢索之前已經(jīng)完成）檢索時(shí)充分利用輔助索引信息犧牲一定的空間從而提高檢索效率把數(shù)據(jù)組織到一個(gè)表中根據(jù)關(guān)鍵碼的值確定表中記錄的位置缺點(diǎn)：不適合進(jìn)行范圍查詢一般也不允許出現(xiàn)重復(fù)關(guān)鍵碼5平均檢索長度（ASL）關(guān)鍵碼的比較：檢索運(yùn)算的主要操作平均檢索長度(Average Search Length)檢索過程中對(duì)關(guān)鍵碼的平均比較次數(shù)衡量檢索算法優(yōu)劣的時(shí)間標(biāo)準(zhǔn)ASL是存儲(chǔ)結(jié)構(gòu)中對(duì)象總數(shù)n的函數(shù)Pi 為檢索第 i 個(gè)元素的概率Ci 為找到第 i 個(gè)元素所需的關(guān)鍵碼值與給定值的比較次數(shù)6平均檢索長度的例子假設(shè)線性表為（a, b, c）檢索a、b、c的概率分別為0.4、0.1、0.5順序檢索算法的平均檢

3、索長度為0.41+0.12+0.53 = 2.1即平均需要2.1次給定值與表中關(guān)鍵碼值的比較才能找到待查元素7檢索算法評(píng)估的幾個(gè)問題衡量一個(gè)檢索算法還需要考慮算法所需的存儲(chǔ)量算法的復(fù)雜性.10.1 基于線性表的檢索10.1.1 順序檢索10.1.2 二分檢索10.1.3 分塊檢索10.1.1 順序檢索針對(duì)線性表里的所有記錄，逐個(gè)進(jìn)行關(guān)鍵碼和給定值的比較 。若某個(gè)記錄的關(guān)鍵碼和給定值比較相等，則檢索成功 ；否則檢索失敗(找遍了仍找不到)。存儲(chǔ)：可以順序、鏈接排序要求：無順序檢索算法template class Item private:Type key; /關(guān)鍵碼域/ /其它域public: I

4、tem(Type value):key(value) Type getKey() return key; /取關(guān)鍵碼值 void setKey(Type k) key=k; /置關(guān)鍵碼; vectorItem* dataList;“監(jiān)視哨”順序檢索算法檢索成功返回元素位置，檢索失敗統(tǒng)一返回0;template int SeqSearch(vectorItem*& dataList, int length, Type k) int i=length; /將第0個(gè)元素設(shè)為待檢索值 dataList0-setKey (k); /設(shè)監(jiān)視哨 while(dataListi-getKey()!=k) i-

5、; return i; /返回元素位置順序檢索性能分析檢索成功假設(shè)檢索每個(gè)關(guān)鍵碼是等概率的：Pi = 1/n檢索失敗假設(shè)檢索失敗時(shí)都需要比較n+1次（設(shè)置了一個(gè)監(jiān)視哨）順序檢索平均檢索長度假設(shè)檢索成功的概率為p，檢索失敗的概率為q=(1-p)（n+1)/2 ASL K，若有則一定排在dataListi前 （3）Key K，若右則一定排在dataListi后縮小進(jìn)一步檢索的區(qū)間二分法檢索算法template int BinSearch (vectorItem*& dataList, int length, Type k) int low=1, high=length, mid; while (l

6、ow=high) mid=(low+high)/2; if (kgetKey() high = mid-1; /右縮檢索區(qū)間 else if (kdataListmid-getKey() low = mid+1; /左縮檢索區(qū)間 else return mid; /成功返回位置 return 0; /檢索失敗，返回0關(guān)鍵碼18 low=1 high=9 351 2 3 4 5 6 7 8 9 15 22 51 60 88 93 lowmidhigh1817第一次：l=1, h=9, mid=5; array5=3518第二次：l=1, h=4, mid=2; array2=17 50)優(yōu)缺點(diǎn)優(yōu)

7、點(diǎn)：平均與最大檢索長度相近，檢索速度快缺點(diǎn)：要排序、順序存儲(chǔ)，不易更新(插/刪)10.1.3 分塊檢索順序與二分法的折衷既有較快的檢索又有較靈活的更改分塊檢索思想“按塊有序”設(shè)線性表中共有n個(gè)數(shù)據(jù)元素，將表分成b塊不需要均勻每一塊可能不滿每一塊中的關(guān)鍵碼不一定有序但前一塊中的最大關(guān)鍵碼必須小于后一塊中的最小關(guān)鍵碼索引表索引表各塊中的最大關(guān)鍵碼及各塊起始位置可能還需要塊中元素個(gè)數(shù)（每一塊可能不滿）索引表是一個(gè)遞增有序表由于表是分塊有序的分塊檢索索引順序結(jié)構(gòu)link:Key:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 221398334244244860

8、8074498653 006 12- 224886 0 556塊內(nèi)最大關(guān)鍵碼塊起始位置塊內(nèi)有效元素個(gè)數(shù)count:typedef struct int maxkey, firstloc, count; Index; typedef struct int *elem, length, blknum; / 塊的數(shù)目Index idxMAXBLOCK; / 塊起始位置/ 和最大元素，其中idx0不利用 IdxSqList; / 索引順序表類型 int Search_IdxSeq(IdxSqList L,int key) if (keyL.idxL.blknum.maxkey) return ERRO

9、R; int i, j, temp, mid, low, high, found; low=1; high=L.blknum; found=false; while (low=high & !found) mid = (low+high)/2 if (key L.idxmid-1.maxkey) found = true; / 就在第mid塊中 else if (key L.idxmid.maxkey) low = mid+1; / 向右找 else high = mid-1; / 向左找 i = L.idxmid.firstloc; / 塊的下界 j = i+ L.idxmid.count-

10、1; / 塊的上界 temp = L.elemi-1; / 保存左鄰元素 L.elemi-1 = key; / 設(shè)置監(jiān)視哨 for (k=j; L.elemk!=key; k-); / 順序查找 L.elemi-1=temp; / 放回左鄰元素 if (k, = , 檢索是直接面向用戶的操作當(dāng)問題規(guī)模n很大時(shí)，上述檢索的時(shí)間效率可能使得用戶無法忍受最理想的情況根據(jù)關(guān)鍵碼值，直接找到記錄的存儲(chǔ)地址不需要把待查關(guān)鍵碼與候選記錄集合的某些記錄進(jìn)行逐個(gè)比較由數(shù)組的直接尋址想到的例如，讀取指定下標(biāo)的數(shù)組元素根據(jù)數(shù)組的起始存儲(chǔ)地址、以及數(shù)組下標(biāo)值而直接計(jì)算出來的，所花費(fèi)的時(shí)間是O(1)與數(shù)組元素個(gè)數(shù)的規(guī)模

11、n無關(guān)受此啟發(fā)，計(jì)算機(jī)科學(xué)家發(fā)明了散列方法（Hash, 有人稱“哈希”，還有稱“雜湊”）散列是一種重要的存儲(chǔ)方法也是一種常見的檢索方法散列基本思想一個(gè)確定的函數(shù)關(guān)系h以結(jié)點(diǎn)的關(guān)鍵碼K為自變量函數(shù)值h(K)作為結(jié)點(diǎn)的存儲(chǔ)地址檢索時(shí)也是根據(jù)這個(gè)函數(shù)計(jì)算其存儲(chǔ)位置通常散列表的存儲(chǔ)空間是一個(gè)一維數(shù)組散列地址是數(shù)組的下標(biāo)例子1已知線性表關(guān)鍵碼集合為：S = and, array, begin, do, else, end, for, go, if, repeat, then, until, while, with可設(shè)散列表為：char HT2268;散列函數(shù)H(key)的值，取為關(guān)鍵碼key中的第一個(gè)字

12、母在字母表a, b, c, ., z中的序號(hào)，即：H(key)=key0 a例子1（續(xù)）例子2修改散列函數(shù)：散列函數(shù)的值為key中首尾字母在字母表中序號(hào)的平均值，即：int H3(char key) int i = 0; while (i8) & (keyi!=0) i+; return(key0 + key(i-1) 2*a) /2 )例子2（續(xù)）幾個(gè)重要概念負(fù)載因子 =n/m散列表的空間大小為m填入表中的結(jié)點(diǎn)數(shù)為n沖突某個(gè)散列函數(shù)對(duì)于不相等的關(guān)鍵碼計(jì)算出了相同的散列地址在實(shí)際應(yīng)用中，不產(chǎn)生沖突的散列函數(shù)極少存在同義詞發(fā)生沖突的兩個(gè)關(guān)鍵碼散列技術(shù)的兩個(gè)重要問題采用散列技術(shù)時(shí)需要考慮的兩個(gè)首要

13、問題是：（1）如何構(gòu)造(選擇)使結(jié)點(diǎn)“分布均勻”的散列函數(shù)？（2）一旦發(fā)生沖突，用什么方法來解決？還需考慮散列表本身的組織方法 10.3.1 散列函數(shù)散列函數(shù)：把關(guān)鍵碼值映射到存儲(chǔ)位置的函數(shù)，通常用 h 來表示 Address Hash ( key )散列函數(shù)的選取原則運(yùn)算盡可能簡單函數(shù)的值域必須在表長的范圍內(nèi)盡可能使得關(guān)鍵碼不同時(shí)，其散列函數(shù)值亦不相同需要考慮各種因素關(guān)鍵碼長度散列表大小關(guān)鍵碼分布情況記錄的檢索頻率 48 基本概念10.1 線性表的檢索10.2 集合的檢索10.3 散列表的檢索小結(jié)主要內(nèi)容常用散列函數(shù)選取方法1. 除余法2. 乘余取整法3. 平方取中法4. 數(shù)字分析法5. 基

14、數(shù)轉(zhuǎn)換法6. 折疊法7. ELFhash字符串散列函數(shù)1. 除余法除余法：用關(guān)鍵碼x除以M(往往取散列表長度)，并取余數(shù)作為散列地址。散列函數(shù)為： h(x) x mod M通常選擇一個(gè)質(zhì)數(shù)作為M值函數(shù)值依賴于自變量x的所有位，而不僅僅是最右邊k個(gè)低位增大了均勻分布的可能性例如，4093M為什么不用偶數(shù)若把M設(shè)置為偶數(shù)x是偶數(shù)，h(x)也是偶數(shù)x是奇數(shù)，h(x)也是奇數(shù)缺點(diǎn)：分布不均勻如果偶數(shù)關(guān)鍵碼比奇數(shù)關(guān)鍵碼出現(xiàn)的概率大，那么函數(shù)值就不能均勻分布反之亦然M不用冪若把M設(shè)置為2的冪那么，h(x)x mod 2k 僅僅是x(用二進(jìn)制表示)最右邊的k個(gè)位(bit)若把M設(shè)置為10的冪那么，h(x)x

15、 mod 10k 僅僅是x(用十進(jìn)制表示)最右邊的k個(gè)十進(jìn)制位(digital)缺點(diǎn)：散列值不依賴于x的全部比特位0110010111000011010 x mod 28 選擇最右邊8位 除余法面臨的問題除余法的潛在缺點(diǎn)連續(xù)的關(guān)鍵碼映射成連續(xù)的散列值雖然能保證連續(xù)的關(guān)鍵碼不發(fā)生沖突但也意味著要占據(jù)連續(xù)的數(shù)組單元可能導(dǎo)致散列性能的降低2. 乘余取整法先讓關(guān)鍵碼 key 乘上一個(gè)常數(shù)A(0A1)，提取乘積的小數(shù)部分然后，再用整數(shù) n 乘以這個(gè)值，對(duì)結(jié)果向下取整，把它作為散列地址散列函數(shù)為： hash ( key ) = n * ( A * key % 1 ) “A * key % 1”表示取 A

16、* key 小數(shù)部分: A * key % 1 = A * key - A * key 乘余取整法示例設(shè)關(guān)鍵碼 key = 123456, n = 10000且取 A = = 0.6180339， 因此有 hash(123456) = = 10000*(0.6180339*123456 % 1) = = 10000 * (76300.0041151 % 1) = = 10000 * 0.0041151 = 41乘余取整法參數(shù)取值的考慮若地址空間為p位，就取n=2p所求出的散列地址正好是計(jì)算出來的 A * key % 1 = A * key - A * key 值的小數(shù)點(diǎn)后最左p位（bit）值此

17、方法的優(yōu)點(diǎn):對(duì) n 的選擇無關(guān)緊要Knuth認(rèn)為：A可以取任何值，與待排序的數(shù)據(jù)特征有關(guān)。一般情況下取黃金分割最理想3. 平方取中法此時(shí)可采用平方取中法：先通過求關(guān)鍵碼的平方來擴(kuò)大差別，再取其中的幾位或其組合作為散列地址例如，一組二進(jìn)制關(guān)鍵碼：(00000100，00000110，000001010，000001001，000000111)平方結(jié)果為：(00010000，00100100，01100010，01010001，00110001) 若表長為4個(gè)二進(jìn)制位，則可取中間四位作為散列地址：(0100，1001，1000，0100，1100)4. 數(shù)字分析法設(shè)有 n 個(gè) d 位數(shù)，每一位可能

18、有 r 種不同的符號(hào)這 r 種不同的符號(hào)在各位上出現(xiàn)的頻率不一定相同可能在某些位上分布均勻些，每種符號(hào)出現(xiàn)的幾率均等在某些位上分布不均勻，只有某幾種符號(hào)經(jīng)常出現(xiàn)可根據(jù)散列表的大小，選取其中各種符號(hào)分布均勻的若干位作為散列地址數(shù)字分析法（續(xù)1）計(jì)算各位數(shù)字中符號(hào)分布的均勻度 k 的公式其中， 表示第 i 個(gè)符號(hào)在第 k 位上出現(xiàn)的次數(shù)n/r 表示各種符號(hào)在 n 個(gè)數(shù)中均勻出現(xiàn)的期望值計(jì)算出的 k 值越小，表明在該位 (第k 位)各種符號(hào)分布得越均勻數(shù)字分析法（續(xù)2）位，僅9出現(xiàn)8次， 1 =(8-8/10)21+(0-8/10)2 9=57.6位，僅9出現(xiàn)8次， 2 =(8-8/10)21+(0

19、-8/10)2 9=57.6 位，0和2各出現(xiàn)兩次，1出現(xiàn)4次 3 =(2-8/10)22+(4-8/10)2 1+ (0-8/10)2 7 =17.6位，0和5各出現(xiàn)兩次，1、2、6、8各出現(xiàn)1次位，0和4各出現(xiàn)兩次，2、3、5、6各出現(xiàn)1次位，7和8各出現(xiàn)兩次，0、1、5、9各出現(xiàn)1次 4 = 5 = 6 = (2-8/10)22+(1-8/10)2 4+(0-8/10)2 4 =5.6數(shù)字分析法（續(xù)3）若散列表地址范圍有 3 位數(shù)字, 取各關(guān)鍵碼的位做為記錄的散列地址也可以把第，和第位相加，舍去進(jìn)位，變成一位數(shù)，與第，位合起來作為散列地址。還可以用其它方法 9 9 2 1 4 8 位，

20、1 = 57.60 9 9 1 2 6 9位， 2 = 57.60 9 9 0 5 2 7位， 3 = 17.60 9 9 1 6 3 0位， 4 = 5.60 9 9 1 8 0 5位， 5 = 5.60 9 9 1 5 5 8位， 6 = 5.60 9 9 2 0 4 7 9 9 0 0 0 1 數(shù)字分析法（續(xù)4）數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵碼每一位數(shù)值的分布情況它完全依賴于關(guān)鍵碼集合如果換一個(gè)關(guān)鍵碼集合，選擇哪幾位數(shù)據(jù)要重新決定5. 基數(shù)轉(zhuǎn)換法把關(guān)鍵碼看成是另一進(jìn)制上的數(shù)后再把它轉(zhuǎn)換成原來進(jìn)制上的數(shù)取其中若干位作為散列地址一般取大于原來基數(shù)的數(shù)作為轉(zhuǎn)換的基數(shù)，并且兩個(gè)基數(shù)要

21、互素例：基數(shù)轉(zhuǎn)換法例如，給定一個(gè)十進(jìn)制數(shù)的關(guān)鍵碼是(210485)10，把它看成以13為基數(shù)的十三進(jìn)制數(shù)(210485)13 ，再把它轉(zhuǎn)換為十進(jìn)制 (210485)13 = 2135 + 1134 + 4132 + 813 + 5 = (771932)10假設(shè)散列表長度是10000，則可取低4位1932作為散列地址6. 折疊法關(guān)鍵碼所含的位數(shù)很多，采用平方取中法計(jì)算太復(fù)雜折疊法將關(guān)鍵碼分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）然后取這幾部分的疊加和（舍去進(jìn)位）作為散列地址兩種折疊方法兩種疊加方法：移位疊加 把各部分的最后一位對(duì)齊相加分界疊加 各部分不折斷，沿各部分的分界來回折疊，然后對(duì)

22、齊相加，將相加的結(jié)果當(dāng)做散列地址例：折疊法如果一本書的編號(hào)為04-42-20586-4 5 8 6 4 5 8 6 4 4 2 2 0 0 2 2 4 + 0 4 + 0 41 0 0 8 8 6 0 9 2h(key)=0088 h(key)=6092(a)移位疊加 (b)分界疊加 7. ELFhash字符串散列函數(shù)用于UNIX系統(tǒng)V4.0“可執(zhí)行鏈接格式”( Executable and Linking Format，即ELF )int ELFhash(char* key) unsigned long h = 0; while(*key) h = (h 24; h &= g; return

23、 h % M;ELFhash函數(shù)特征長字符串和短字符串都很有效字符串中每個(gè)字符都有同樣的作用對(duì)于散列表中的位置不可能產(chǎn)生不平均的分布散列函數(shù)的應(yīng)用在實(shí)際應(yīng)用中應(yīng)根據(jù)關(guān)鍵碼的特點(diǎn)，選用適當(dāng)?shù)纳⒘泻瘮?shù)有人曾用“輪盤賭”的統(tǒng)計(jì)分析方法對(duì)它們進(jìn)行了模擬分析，結(jié)論是平方取中法最接近于“隨機(jī)化”若關(guān)鍵碼不是整數(shù)而是字符串時(shí)，可以把每個(gè)字符串轉(zhuǎn)換成整數(shù)，再應(yīng)用平方取中法引子：碰撞的處理開散列方法( open hashing，也稱為拉鏈法，separate chaining )把發(fā)生沖突的關(guān)鍵碼存儲(chǔ)在散列表主表之外閉散列方法( closed hashing，也稱為開地址方法，open addressing )

24、把發(fā)生沖突的關(guān)鍵碼存儲(chǔ)在表中另一個(gè)槽內(nèi)10.3.2 開散列方法1. 拉鏈法2. 桶式散列碰撞發(fā)生時(shí)建立一個(gè)同義詞子鏈表 動(dòng)態(tài)申請同義詞的空間，適合于內(nèi)存操作例：77、7、110、95、14、75、62 h(Key) = Key % 111. 拉鏈法表中的空單元其實(shí)應(yīng)該有特殊值標(biāo)記出來 例如-1或INFINITY或者使得散列表中的內(nèi)容就是指針，空單元?jiǎng)t內(nèi)容為空指針插入同義詞時(shí)，可以對(duì)同義詞鏈排序插入 0 1 2 3 4 5 6 7 8 9 10 77 14 7 75 1106295拉鏈法性能分析給定一個(gè)大小為M存儲(chǔ)n個(gè)記錄的表散列函數(shù)(在理想情況下)將把記錄在表中M個(gè)位置平均放置，使得平均每一個(gè)

25、鏈表中有n/M個(gè)記錄Mn 時(shí)，散列方法的平均代價(jià)就是(1)拉鏈法不適于外存檢索如果整個(gè)散列表存儲(chǔ)在內(nèi)存中，開散列方法比較容易實(shí)現(xiàn)如果散列表存儲(chǔ)在磁盤中，用開散列不太合適一個(gè)同義詞表中的元素可能存儲(chǔ)在不同的磁盤頁中這就會(huì)導(dǎo)致在檢索一個(gè)特定關(guān)鍵碼值時(shí)引起多次磁盤訪問，從而增加了檢索時(shí)間桶式散列2. 桶式散列 適合存儲(chǔ)于磁盤的散列表基本思想:把一個(gè)文件的記錄分為若干存儲(chǔ)桶，每個(gè)存儲(chǔ)桶包含一個(gè)或多個(gè)頁塊一個(gè)存儲(chǔ)桶內(nèi)的各頁塊用指針連接起來，每個(gè)頁塊包含若干記錄散列函數(shù)h(K)表示具有關(guān)鍵碼值K的記錄所在的存儲(chǔ)桶號(hào)桶式散列文件組織右圖表示了一個(gè)具有B個(gè)存儲(chǔ)桶的散列文件組織如果B很小，存儲(chǔ)桶目錄表可放在內(nèi)存

26、如果B較大，要存放好多頁塊，則存儲(chǔ)桶目錄表就放到外存上10.3.3 閉散列方法d0=h（K）稱為K的基地址地置當(dāng)沖突發(fā)生時(shí)，使用某種方法為關(guān)鍵碼K生成一個(gè)散列地址序列 d1，d2，. di ，.dm-1所有di(0im)是后繼散列地址形成探查的方法不同，所得到的解決沖突的方法也不同閉散列表解決沖突的基本思想（續(xù)）當(dāng)插入K時(shí)，若基地址上的結(jié)點(diǎn)已被別的數(shù)據(jù)元素占用則按上述地址序列依次探查，將找到的第一個(gè)開放的空閑位置di作為K的存儲(chǔ)位置若所有后繼散列地址都不空閑，說明該閉散列表已滿，報(bào)告溢出檢索過程檢索時(shí)也要像插入時(shí)一樣遵循同樣的策略重復(fù)沖突解決過程找出在基位置沒有找到的記錄探查序列插入和檢索函數(shù)

27、都假定每個(gè)關(guān)鍵碼的探查序列中至少有一個(gè)存儲(chǔ)位置是空的否則可能會(huì)進(jìn)入一個(gè)無限循環(huán)中也可以限制探查序列長度幾種常見的閉散列方法1. 線性探查2. 二次探查3. 偽隨機(jī)數(shù)序列探查4. 雙散列探查法1. 線性探查基本思想：如果記錄的基位置存儲(chǔ)位置被占用，那么就在表中下移，直到找到一個(gè)空存儲(chǔ)位置依次探查下述地址單元：d+1，d+2，.，M-1，0，1，.，d-1 用于簡單線性探查的探查函數(shù)是： p(K，i) = i線性探查的優(yōu)點(diǎn)表中所有的存儲(chǔ)位置都可以作為插入新記錄的候選位置可能產(chǎn)生的問題聚集“聚集”（clustering，或稱為“堆積”）散列地址不同的結(jié)點(diǎn)，爭奪同一后繼散列地址小的聚集可能匯合成大的聚

28、集導(dǎo)致很長的探查序列散列表示例 30, 40, 47, 42, 50, 17, 63, 12, 6, 62, 27 M = 15, h(key) = key % 15在理想情況下，表中的每個(gè)空槽都應(yīng)該有相同的機(jī)會(huì)接收下一個(gè)要插入的記錄。下一條記錄放在第11個(gè)槽中的概率是2/15放到第7個(gè)槽中的概率是11/150123456789101112131430475040421763126622727改進(jìn)線性探查每次跳過常數(shù)c個(gè)而不是1個(gè)槽探查序列中的第i個(gè)槽是(h(K) + ic) mod M基位置相鄰的記錄就不會(huì)進(jìn)入同一個(gè)探查序列了 探查函數(shù)是p(K，i) = i*c必須使常數(shù)c與M互素例：改進(jìn)線

29、性探查例如，c = 2，要插入關(guān)鍵碼k1和k2，h(k1) = 3，h(k2) = 5探查序列k1的探查序列是3、5、7、9、.k2的探查序列就是5、7、9、.k1和k2的探查序列還是糾纏在一起，從而導(dǎo)致了聚集2. 二次探查探查增量序列依次為：12，-12，22 ，-22，.，即地址公式是 d2i-1 = (d +i2) % M d2i = (d i2) % M用于簡單線性探查的探查函數(shù)是 p(K，2i-1) = i*i p(K，2i) = - i*i例：二次探查使用一個(gè)大小M = 13的表 假定對(duì)于關(guān)鍵碼k1和k2，h(k1)=3，h(k2)=2探查序列k1的探查序列是3、4、2、7 、.k

30、2的探查序列是2、3、1、6 、.盡管k2會(huì)把k1的基位置作為第2個(gè)選擇來探查，但是這兩個(gè)關(guān)鍵碼的探查序列此后就立即分開了3. 偽隨機(jī)數(shù)序列探查探查函數(shù) p(K，i) = permi - 1這里perm是一個(gè)長度為M - 1的數(shù)組包含值從1到M - 1的隨機(jī)序列產(chǎn)生n個(gè)數(shù)的偽隨機(jī)排列void permute(int *array, int n) for (int i = 1; i = n; i +) swap(arrayi-1, arrayRandom(i); 例：偽隨機(jī)數(shù)序列探查考慮一個(gè)大小為M = 13的表，perm0 = 2，perm1 = 3，perm2 = 7。假定兩個(gè)關(guān)鍵碼k1和k

31、2，h(k1)=4，h(k2)=2探查序列k1的探查序列是4、6、7、11 、.k2的探查序列是2、4、5、9 、.盡管k2會(huì)把k1的基位置作為第2個(gè)選擇來探查，但是這兩個(gè)關(guān)鍵碼的探查序列此后就立即分開了適用范圍廣還有很多散列方法分布散列函數(shù)(DHT)二級(jí)聚集消除基本聚集基地址不同的關(guān)鍵碼，其探查序列的某些段重疊在一起偽隨機(jī)探查和二次探查可以消除二級(jí)聚集 (secondary clustering)如果兩個(gè)關(guān)鍵碼散列到同一個(gè)基地址，還是得到同樣的探查序列，所產(chǎn)生的聚集原因：探查序列只是基地址的函數(shù)，而不是原來關(guān)鍵碼值的函數(shù)例子：偽隨機(jī)探查和二次探查4. 雙散列探查法避免二級(jí)聚集探查序列是原來關(guān)

32、鍵碼值的函數(shù)而不僅僅是基位置的函數(shù)雙散列探查法利用第二個(gè)散列函數(shù)作為常數(shù)每次跳過常數(shù)項(xiàng)，做線性探查雙散列探查法的基本思想雙散列探查法使用兩個(gè)散列函數(shù)h1和h2若在地址h1(key)=d發(fā)生沖突，則再計(jì)算h2(key)，得到的探查序列為： (d+h2(key) % M， (d+2h2 (key) %M ， (d+3h2 (key) % M ， .明確兩個(gè)公式概念雙散列函數(shù)探查法序列公式： di=(d + i h2 (K) % M雙散列函數(shù)公式： p(K, i) = i * h2 (K)雙散列函數(shù)法特征h2 (key) 必須與M互素使發(fā)生沖突的同義詞地址均勻地分布在整個(gè)表中否則可能造成同義詞地址的

33、循環(huán)計(jì)算雙散列的優(yōu)點(diǎn): 不易產(chǎn)生“聚集”缺點(diǎn)：計(jì)算量增大M和h2(k)選擇方法方法1：選擇M為一個(gè)素?cái)?shù)，h2返回的值在1h2(K)M 1范圍之間方法2：設(shè)置M = 2m，讓h2返回一個(gè)1到2m之間的奇數(shù)值方法3：若M是素?cái)?shù)，h1(K)=K mod Mh2 (K) = K mod(M-2) + 1或者h(yuǎn)2(K) = K / M mod (M-2) + 1 方法4：若M是任意數(shù)，h1(K)=K mod p，(p 是小于M的最大素?cái)?shù))h2 (K) = K mod q + 1 (q是小于p的最大素?cái)?shù))國家級(jí)精品課程數(shù)據(jù)結(jié)構(gòu)與算法張銘、趙海燕、王騰蛟、宋國杰、高軍http:/pkujpk/course/

34、sjjg/北京大學(xué)信息科學(xué)與技術(shù)學(xué)院“數(shù)據(jù)結(jié)構(gòu)與算法”教學(xué)小組本章主筆：張銘版權(quán)所有，轉(zhuǎn)載或翻印必究第10章 檢索101 基本概念10.1 線性表的檢索10.2 集合的檢索10.3 散列表的檢索小結(jié)主要內(nèi)容引子：碰撞的處理開散列方法( open hashing，也稱為拉鏈法，separate chaining )把發(fā)生沖突的關(guān)鍵碼存儲(chǔ)在散列表主表之外閉散列方法( closed hashing，也稱為開地址方法，open addressing )把發(fā)生沖突的關(guān)鍵碼存儲(chǔ)在表中另一個(gè)槽內(nèi)3. 偽隨機(jī)數(shù)序列探查探查函數(shù) p(K，i) = permi - 1這里perm是一個(gè)長度為M - 1的數(shù)組包含值

35、從1到M - 1的隨機(jī)序列10.3.4 閉散列表的算法實(shí)現(xiàn)字典(dictionary)一種特殊的集合，其元素是(關(guān)鍵碼，屬性值)二元組。關(guān)鍵碼必須是互不相同的(在同一個(gè)字典之內(nèi))主要操作是依據(jù)關(guān)鍵碼來存儲(chǔ)和析取值bool hashSearch(const Key&，T&) const; / lookup(key)bool hashInsert(const T&); / insert(key, value)實(shí)現(xiàn)方式有序線性表字符樹散列方法散列字典ADT（屬性）template class hashdict private: T* HT; / 散列表 int M; / 散列表大小 int curr

36、cnt; / 現(xiàn)有元素?cái)?shù)目 T EMPTY; / 空槽 int p(Key K，int i) / 探查函數(shù) int h(int x) const ; / 散列函數(shù) int h(char* x)const ; / 字符串散列函數(shù)散列字典ADT（方法）public: hashdict(int sz，T e) / 構(gòu)造函數(shù) M=sz; EMPTY=e; currcnt=0; HT=new Tsz; for (int i=0; iM; i+) HTi=EMPTY; hashdict() delete HT; bool hashSearch(const Key&，T&) const; bool hash

37、Insert(const T&); T hashDelete(const Key& K); int size() return currcnt; / 元素?cái)?shù)目;插入算法散列函數(shù)h，假設(shè)給定的值為K若表中該地址對(duì)應(yīng)的空間未被占用，則把待插入記錄填入該地址如果該地址中的值與K相等，則報(bào)告“散列表中已有此記錄”否則，按設(shè)定的處理沖突方法查找探查序列的下一個(gè)地址，如此反復(fù)下去直到某個(gè)地址空間未被占用（可以插入）或者關(guān)鍵碼比較相等（不需要插入）為止散列表插入算法代碼/ 將數(shù)據(jù)元素e插入到散列表 HTtemplate bool hashdict:hashInsert(const T& e) int hom

38、e= h(getkey(e); /home存儲(chǔ)基位置 int i=0; int pos = home; / 探查序列的初始位置 散列表插入算法代碼 while (!EEComp:eq(EMPTY, HTpos) if (EEComp:eq(e, HTpos) return false; i+; pos = (home+p(getkey(e), i) % M; /探查 HTpos = e; / 插入元素e return true; 散列表的檢索 與插入過程類似采用的探查序列也相同檢索算法假設(shè)散列函數(shù)h，給定的值為K若表中該地址對(duì)應(yīng)的空間未被占用，則檢索失敗否則將該地址中的值與K比較，若相等則檢索

39、成功否則，按建表時(shí)設(shè)定的處理沖突方法查找探查序列的下一個(gè)地址，如此反復(fù)下去關(guān)鍵碼比較相等，檢索成功地址空間未被占用，檢索失敗散列表檢索算法代碼template bool hashdict:hashSearch(const Key& K, T& e) const int i=0, pos= home= h(K); / 初始位置 while (!EEComp:eq(EMPTY, HTpos) if (KEComp:eq(K, HTpos) / 找到 e = HTpos; return true; 散列表檢索算法代碼 i+; pos = (home + p(K, i) % M; /while ret

40、urn false; 刪除刪除記錄的時(shí)候，有兩點(diǎn)需要重點(diǎn)考慮： (1) 刪除一個(gè)記錄一定不能影響后面的檢索(2) 釋放的存儲(chǔ)位置應(yīng)該能夠?yàn)閷聿迦胧褂?只有開散列方法（分離的同義詞子表）可以真正刪除閉散列方法都只能作標(biāo)記（墓碑），不能真正刪除若真正刪除了探查序列將斷掉檢索算法 “直到某個(gè)地址空間未被占用（檢索失敗）”墓碑標(biāo)記增加了平均檢索長度 刪除帶來的問題例如，一個(gè)長度M = 13的散列表，假定關(guān)鍵碼k1和k2，h(k1) = 2，h(k2) = 6。二次探查序列k1的二次探查序列是2、3、1、6、11、11、6、5、12、.k2的二次探查序列是6、7、5、10、2、2、10、9、3、. 刪

41、除位置6，用該序列的最后位置2的元素替換之，位置2設(shè)為空檢索k1的同義詞，查不到可事實(shí)上它們還存放在位置3和1上!墓碑設(shè)置一個(gè)特殊的標(biāo)記位，來記錄散列表中的單元狀態(tài)單元被占用空單元已刪除是否可以把空單元、已刪除這兩種狀態(tài)，用特殊的值標(biāo)記，以區(qū)別于“單元被占用”狀態(tài)？不可以！被刪除標(biāo)記值稱為墓碑( tombstone )標(biāo)志一個(gè)記錄曾經(jīng)占用這個(gè)槽但是現(xiàn)在已經(jīng)不再占用了帶墓碑的插入操作在插入時(shí)，如果遇到標(biāo)志為墓碑的槽，可以把新記錄存儲(chǔ)在該槽中嗎?避免插入兩個(gè)相同的關(guān)鍵碼檢索過程仍然需要沿著探查序列下去，直到找到一個(gè)真正的空位置帶墓碑的刪除算法template T hashdict:hashDele

42、te(const Key& K) int i=0, pos = home= h(K); / 初始位置 while (!EEComp:eq(EMPTY, HTpos) if (KEComp:eq(K, HTpos) temp = HTpos; HTpos = TOMB; / 設(shè)置墓碑 return temp; / 返回目標(biāo) i+; pos = (home + p(K, i) % M; return EMPTY; 帶墓碑的插入操作改進(jìn)template bool hashdict:hashInsert(const T &e) int insplace, i = 0, pos = home = h(getkey(e); bool tomb_pos = false; 帶墓碑的插入操作改進(jìn) while (HTpos) != EMPTY ) if (g