數(shù)據(jù)結構與算法檢索

1、數(shù)據(jù)結構與算法 第10章 檢索,本章由張銘主寫http://db.pku.edu.cn/mzhang/DS/http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 張銘，王騰蛟，趙海燕高等教育出版社，2008. 6?！笆晃濉眹壹壱?guī)劃教材,第十章 檢索,基本概念10.1 線性表的檢索10.2 集合的檢索10.3 散列表的檢索10.4 總結,,,,,,基本概念,檢索檢索的

2、效率非常重要尤其對于大數(shù)據(jù)量需要對數(shù)據(jù)進行特殊的存儲處理,在一組記錄集合中找到關鍵碼值等于給定值的某個記錄，或者找到關鍵碼值符合特定條件的某些記錄的過程,提高檢索效率的方法,預排序建立索引散列技術當散列方法不適合于基于磁盤的應用程序時，我們可以選擇B樹方法,排序算法本身比較費時只是預處理（在檢索之前已經(jīng)完成）,檢索時充分利用輔助索引信息犧牲一定的空間從而提高檢索效率,把數(shù)據(jù)組織到一個表中根據(jù)關鍵碼的值確定表中記錄

3、的位置缺點：不適合進行范圍查詢一般也不允許出現(xiàn)重復關鍵碼,平均檢索長度（ASL）,關鍵碼的比較：檢索運算的主要操作平均檢索長度(Average Search Length)檢索過程中對關鍵碼的平均比較次數(shù)衡量檢索算法優(yōu)劣的時間標準,ASL是存儲結構中對象總數(shù)n的函數(shù),Pi 為檢索第 i 個元素的概率,Ci 為找到第 i 個元素所需的關鍵碼值與給定值的比較次數(shù),平均檢索長度的例子,假設線性表為（a, b, c）檢索a、b、c的

4、概率分別為0.4、0.1、0.5順序檢索算法的平均檢索長度為0.4×1+0.1×2+0.5×3 = 2.1即平均需要2.1次給定值與表中關鍵碼值的比較才能找到待查元素,檢索算法評估的幾個問題,衡量一個檢索算法還需要考慮算法所需的存儲量算法的復雜性...,10.1 基于線性表的檢索,10.1.1 順序檢索10.1.2 二分檢索10.1.3 分塊檢索,,,,10.1.1 順序檢索,針對線性表里的所

5、有記錄，逐個進行關鍵碼和給定值的比較 。若某個記錄的關鍵碼和給定值比較相等，則檢索成功 ；否則檢索失敗(找遍了仍找不到)。存儲：可以順序、鏈接排序要求：無,順序檢索算法,template class Item {private:Type key; //關鍵碼域//… //其它域publ

6、ic: Item(Type value):key(value) {} Type getKey() {return key;} //取關鍵碼值 void setKey(Type k){ key=k;} //置關鍵碼}; vector*> dataList;,“監(jiān)視哨”順序檢索算法,檢索成功返回元素位置，檢索失敗統(tǒng)一返回0;template int SeqSearch(

7、vector*>& dataList, int length, Type k) { int i=length; //將第0個元素設為待檢索值 dataList[0]->setKey (k); //設監(jiān)視哨 while(dataList[i]->getKey()!=k) i--; return i;

8、 //返回元素位置},順序檢索性能分析,檢索成功假設檢索每個關鍵碼是等概率的：Pi = 1/n檢索失敗假設檢索失敗時都需要比較n+1次（設置了一個監(jiān)視哨）,順序檢索平均檢索長度,假設檢索成功的概率為p，檢索失敗的概率為q=(1-p)（n+1)/2 < ASL < (n+1),順序檢索優(yōu)缺點,優(yōu)點：插入元素可以直接加在表尾Θ(1)缺點：檢索時間太

9、長Θ(n),10.1.2 二分檢索法,將任一元素dataList[i] .Key與給定值K比較三種情況： （1）Key = K，檢索成功，返回dataList[i] （2）Key > K，若有則一定排在dataList[i]]前 （3）Key < K，若右則一定排在dataList[i]后縮小進一步檢索的區(qū)間,二分法檢索算法,template int BinSearch (vector

10、*>& dataList, int length, Type k){ int low=1, high=length, mid; while (lowgetKey()) high = mid-1; //右縮檢索區(qū)間 else if (k>dataList[mid]->getKey())

11、 low = mid+1; //左縮檢索區(qū)間 else return mid; //成功返回位置 } return 0; //檢索失敗，返回0},關鍵碼18 low=1 high=9,35,18,17,,第一次：l=1, h=9, mid=5; array[5]=35>18,第二次：l=1, h=4, mid=2; array[2]=1

12、7<18,第三次：l=3, h=4, mid=3; array[3]=18＝18,二分法檢索性能分析,最大檢索長度 失敗的檢索長度是 或在算法復雜性分析中l(wèi)og n是以2為底的對數(shù)其他底，算法量級不變,15,18,22,51,,,,,,,,,,,,7,8,9,2,1,3,4,88,60,93,35,17,5,6,二分法檢索性能分析（續(xù)）,成功的平均檢索長度為：

13、 (n > 50)優(yōu)缺點優(yōu)點：平均與最大檢索長度相近，檢索速度快缺點：要排序、順序存儲，不易更新(插/刪),10.1.3 分塊檢索,順序與二分法的折衷既有較快的檢索又有較靈活的更改,分塊檢索思想,“按塊有序”設線性表中共有n個數(shù)據(jù)元素

14、，將表分成b塊不需要均勻每一塊可能不滿每一塊中的關鍵碼不一定有序但前一塊中的最大關鍵碼必須小于后一塊中的最小關鍵碼,索引表,索引表各塊中的最大關鍵碼及各塊起始位置可能還需要塊中元素個數(shù)（每一塊可能不滿）索引表是一個遞增有序表由于表是分塊有序的,分塊檢索——索引順序結構,,link:,Key:,,,,,,0 1 2 3 4 5 6 7 8 9 10 11

15、 12 13 14 15 16 17,,,,塊內(nèi)最大關鍵碼塊起始位置塊內(nèi)有效元素個數(shù),count:,分塊檢索性能分析,分塊檢索為兩級檢索先在索引表中確定待查元素所在的塊； 設在索引表中確定塊號的時間開銷是ASLb然后在塊內(nèi)檢索待查的元素。 在塊中查找記錄的時間開銷為ASLwASL(n) = ASLb + ASLw,分塊檢索性能分析(續(xù)2),假設在索引表中用順序檢索，在塊內(nèi)也用順序檢索 當s =

16、 時，ASL取最小值， ASL = +1 ≈,分塊檢索性能分析(續(xù)3),當n=10,000時順序檢索5,000次二分法檢索14次分塊檢索100次如果數(shù)據(jù)塊（子表）存放在外存時，還會受到頁塊大小的制約此時往往以外存一個Ｉ/Ｏ讀取的數(shù)據(jù)（一頁）作為一塊,分塊檢索性能分析(續(xù)4),若采用二分法檢索確定記錄所在的子表，則檢索成功時的平均檢索長度為ASL= ASLb + ASLw ? log

17、2 (b+1)-1 + (s+1)/2 ? log2(1+n / s ) + s/2,分塊檢索的優(yōu)缺點,優(yōu)點：插入、刪除相對較易沒有大量記錄移動缺點：增加一個輔助數(shù)組的存儲空間初始線性表分塊排序當大量插入/刪除時，或結點分布不均勻時，速度下降,10.2 集合的檢索,用位向量來表示集合對于密集型集合（數(shù)據(jù)范圍小，而集合中有效元素個數(shù)比較多）,例：計算0到15之間所有的奇素數(shù),奇數(shù)：素數(shù)：奇素數(shù)：,例

18、：集合的無符號數(shù)表示,全集元素個數(shù)N=40的集合，集合{35, 9, 7, 5, 3, 1}表示為,0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0010 1010 1010不夠一個ulong, 左補0,10.3 散列檢索,10.3.0 散列中的基本問題10.3.1 散列函數(shù)碰撞的處理10.3.2 開散

19、列方法10.3.3 閉散列方法10.3.4 閉散列表的算法實現(xiàn)10.3.5 散列方法的效率分析,,,,,,,,10.3.0 散列中的基本問題,基于關鍵碼比較的檢索 順序檢索，==, !=二分法、樹型 >, == , <檢索是直接面向用戶的操作當問題規(guī)模n很大時，上述檢索的時間效率可能使得用戶無法忍受最理想的情況根據(jù)關鍵碼值，直接找到記錄的存儲地址不需要把待查關鍵碼與候選記錄集合的某些記錄進行逐個比較

20、,由數(shù)組的直接尋址想到的,例如，讀取指定下標的數(shù)組元素根據(jù)數(shù)組的起始存儲地址、以及數(shù)組下標值而直接計算出來的，所花費的時間是O(1)與數(shù)組元素個數(shù)的規(guī)模n無關受此啟發(fā)，計算機科學家發(fā)明了散列方法（Hash, 有人稱“哈?！保€有稱“雜湊”）散列是一種重要的存儲方法也是一種常見的檢索方法,散列基本思想,一個確定的函數(shù)關系h以結點的關鍵碼K為自變量函數(shù)值h(K)作為結點的存儲地址檢索時也是根據(jù)這個函數(shù)計算其存儲位置通常散列

21、表的存儲空間是一個一維數(shù)組散列地址是數(shù)組的下標,例子1,例10.1：已知線性表關鍵碼集合為：S = { and, array, begin, do, else, end, for, go, if, repeat, then, until, while, with}可設散列表為：char HT2[26][8];散列函數(shù)H(key)的值，取為關鍵碼key中的第一個字母在字母表{a, b, c, ..., z}中的序號，即：H(

22、key)=key[0] – ‘a(chǎn)’,例子1（續(xù)）,例子2,修改散列函數(shù)：散列函數(shù)的值為key中首尾字母在字母表中序號的平均值，即：int H3(char key[]){ int i = 0; while ((i<8) && (key[i]!=‘\0’)) i++; return((key[0] + key(i-1) – 2*’a’) /2 )},例子2（續(xù)）,幾個重要概念,負載因子 α=

23、n/m散列表的空間大小為m填入表中的結點數(shù)為n沖突某個散列函數(shù)對于不相等的關鍵碼計算出了相同的散列地址在實際應用中，不產(chǎn)生沖突的散列函數(shù)極少存在同義詞發(fā)生沖突的兩個關鍵碼,散列技術的兩個重要問題,采用散列技術時需要考慮的兩個首要問題是：（1）如何構造(選擇)使結點“分布均勻”的散列函數(shù)？（2）一旦發(fā)生沖突，用什么方法來解決？還需考慮散列表本身的組織方法,10.3.1 散列函數(shù),散列函數(shù)：把關鍵碼值映射到存儲位置的函數(shù)

24、，通常用 h 來表示 Address ＝ Hash ( key ),散列函數(shù)的選取原則,運算盡可能簡單函數(shù)的值域必須在表長的范圍內(nèi)盡可能使得關鍵碼不同時，其散列函數(shù)值亦不相同,需要考慮各種因素,關鍵碼長度散列表大小關鍵碼分布情況記錄的檢索頻率…,常用散列函數(shù)選取方法,1. 除余法2. 乘余取整法3. 平方取中法4. 數(shù)字分析法5. 基數(shù)轉換法6. 折疊法7. ELFhash字符串散列函數(shù),,,,,,,,1.

25、 除余法,除余法：用關鍵碼x除以M(往往取散列表長度)，并取余數(shù)作為散列地址。散列函數(shù)為： h(x) ＝ x mod M通常選擇一個質(zhì)數(shù)作為M值函數(shù)值依賴于自變量x的所有位，而不僅僅是最右邊k個低位增大了均勻分布的可能性例如，4093,M為什么不用偶數(shù),若把M設置為偶數(shù)x是偶數(shù)，h(x)也是偶數(shù)x是奇數(shù)，h(x)也是奇數(shù)缺點：分布不均勻如果偶數(shù)關鍵碼比奇數(shù)關鍵碼出現(xiàn)的概率大，那么函數(shù)值就

26、不能均勻分布反之亦然,M不用冪,若把M設置為2的冪那么，h(x)＝x mod 2k 僅僅是x(用二進制表示)最右邊的k個位(bit)若把M設置為10的冪那么，h(x)＝x mod 10k 僅僅是x(用十進制表示)最右邊的k個十進制位(digital)缺點：散列值不依賴于x的全部比特位,0110010111000011010,,x mod 28 選擇最右邊8位,除余法面臨的問題,除余法的潛在缺點連續(xù)的關鍵碼映射成連續(xù)的散列值

27、雖然能保證連續(xù)的關鍵碼不發(fā)生沖突但也意味著要占據(jù)連續(xù)的數(shù)組單元可能導致散列性能的降低,2. 乘余取整法,先讓關鍵碼 key 乘上一個常數(shù)A(0<A<1)，提取乘積的小數(shù)部分然后，再用整數(shù) n 乘以這個值，對結果向下取整，把它作為散列地址散列函數(shù)為： hash ( key ) = ? n * ( A * key % 1 ) ?“A * key % 1”表示取 A * key 小數(shù)部分: A * key %

28、1 = A * key - ? A * key ?,乘余取整法示例,設關鍵碼 key = 123456, n = 10000且取 A = = 0.6180339， 因此有 hash(123456) = = ?10000*(0.6180339*123456 % 1)? = = ?10000 * (76300.0041151… % 1)? =

29、 = ?10000 * 0.0041151…? = 41,乘余取整法參數(shù)取值的考慮,若地址空間為p位，就取n=2p所求出的散列地址正好是計算出來的 A * key % 1 = A * key - ? A * key ? 值的小數(shù)點后最左p位（bit）值此方法的優(yōu)點:對 n 的選擇無關緊要Knuth認為：A可以取任何值，與待排序的數(shù)據(jù)特征有關。一般情況下取黃金分割最理想,3. 平方取中法,此時可采用平方取中法

30、：先通過求關鍵碼的平方來擴大差別，再取其中的幾位或其組合作為散列地址例如，一組二進制關鍵碼：(00000100，00000110，000001010，000001001，000000111)平方結果為：(00010000，00100100，01100010，01010001，00110001) 若表長為4個二進制位，則可取中間四位作為散列地址：(0100，1001，1000，0100，1100),4. 數(shù)字分析法,設有 n 個

31、d 位數(shù)，每一位可能有 r 種不同的符號這 r 種不同的符號在各位上出現(xiàn)的頻率不一定相同可能在某些位上分布均勻些，每種符號出現(xiàn)的幾率均等在某些位上分布不均勻，只有某幾種符號經(jīng)常出現(xiàn)可根據(jù)散列表的大小，選取其中各種符號分布均勻的若干位作為散列地址,數(shù)字分析法（續(xù)1）,計算各位數(shù)字中符號分布的均勻度 ?k 的公式其中， 表示第 i 個符號在第 k 位上出現(xiàn)的次數(shù)，n/r 表示各種符號在 n 個數(shù)中均勻出現(xiàn)的期望值。計

32、算出的 ?k 值越小，表明在該位 (第k 位)各種符號分布得越均勻,數(shù)字分析法（續(xù)2）,若散列表地址范圍有 3 位數(shù)字, 取各關鍵碼的④⑤⑥位做為記錄的散列地址也可以把第①，②，③和第⑤位相加，舍去進位，變成一位數(shù)，與第④，⑥位合起來作為散列地址。還可以用其它方法,9 9 2 1 4 8 ①位， ? 1 = 57.60 9 9 1 2 6 9②位， ?

33、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

34、 0 4 7 9 9 0 0 0 1 ① ② ③ ④ ⑤ ⑥,數(shù)字分析法（續(xù)3）,①位，僅9出現(xiàn)8次，? 1 =(8-8/10)2×1+(0-8/10)2 ×9=57.6②位，僅9出現(xiàn)8次， ? 2 =(8-8/10)2×1+(0-8/10)2 ×9=57.6③ 位，0和2各出現(xiàn)兩次，1出現(xiàn)4次? 3 =(2-8/10)

35、2×2+(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)2×2+(1-8/10)2 ×4+(0-8/10)2 ×4 =5.6,數(shù)字分析法（續(xù)4）,數(shù)字分析法僅

36、適用于事先明確知道表中所有關鍵碼每一位數(shù)值的分布情況它完全依賴于關鍵碼集合如果換一個關鍵碼集合，選擇哪幾位數(shù)據(jù)要重新決定,5. 基數(shù)轉換法,把關鍵碼看成是另一進制上的數(shù)后再把它轉換成原來進制上的數(shù)取其中若干位作為散列地址一般取大于原來基數(shù)的數(shù)作為轉換的基數(shù)，并且兩個基數(shù)要互素,例：基數(shù)轉換法,例如，給定一個十進制數(shù)的關鍵碼是(210485)10，把它看成以13為基數(shù)的十三進制數(shù)(210485)13 ，再把它轉換為十進制

37、 (210485)13 = 2×135 + 1×134 + 4×132 + 8×13 + 5 = (771932)10假設散列表長度是10000，則可取低4位1932作為散列地址,6. 折疊法,關鍵碼所含的位數(shù)很多，采用平方取中法計算太復雜折疊法將關鍵碼分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）然后取這幾部分的疊加和（舍去進位）作為散列

38、地址,兩種折疊方法,兩種疊加方法：移位疊加 — 把各部分的最后一位對齊相加分界疊加 — 各部分不折斷，沿各部分的分界來回折疊，然后對齊相加，將相加的結果當做散列地址,例：折疊法,[例10.6] 如果一本書的編號為04-42-20586-4 5 8 6 4 5 8 6 4 4 2 2 0 0 2

39、2 4 + 0 4 + 0 4[1] 0 0 8 8 6 0 9 2h(key)=0088 h(key)=6092(a)移位疊加 (b)分界疊加,,,,,,,7. ELFhash字符串散列函數(shù),用于UNIX系統(tǒng)V4.0“可執(zhí)

40、行鏈接格式”( Executable and Linking Format，即ELF )int ELFhash(char* key) { unsigned long h = 0; while(*key) { h = (h > 24; h &= ~g; } return h % M;},ELFhash函數(shù)特征,長字符串和短字符串都很有效字符串中每個字符都有同樣的作用對于散列表中的位置

41、不可能產(chǎn)生不平均的分布,散列函數(shù)的應用,在實際應用中應根據(jù)關鍵碼的特點，選用適當?shù)纳⒘泻瘮?shù)有人曾用“輪盤賭”的統(tǒng)計分析方法對它們進行了模擬分析，結論是平方取中法最接近于“隨機化”若關鍵碼不是整數(shù)而是字符串時，可以把每個字符串轉換成整數(shù)，再應用平方取中法,引子：碰撞的處理,開散列方法( open hashing，也稱為拉鏈法，separate chaining )把發(fā)生沖突的關鍵碼存儲在散列表主表之外閉散列方法( closed

42、hashing，也稱為開地址方法，open addressing )把發(fā)生沖突的關鍵碼存儲在表中另一個槽內(nèi),,,10.3.2 開散列方法,1. 拉鏈法2. 桶式散列,當碰撞發(fā)生時就拉出一條鏈，建立一個鏈表方式的同義詞子表 動態(tài)申請同義詞的空間，適合于內(nèi)存操作例：{77、7、110、95、14、75、62 } h(Key) = Key % 11,,,1. 拉鏈法,表中的空單元其實應該有特殊值標記出來 例如-1

43、或INFINITY或者使得散列表中的內(nèi)容就是指針，空單元則內(nèi)容為空指針插入同義詞時，可以對同義詞鏈排序插入,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1. 拉鏈法（續(xù)）,表中的空單元其實應該有特殊值標記出來 例如-1或INFINITY或者使得散列表中的內(nèi)容就是指針，空單元則內(nèi)容為空指針插入同義詞時，可以對同義詞鏈排序插入,拉鏈法性能分析,給定一個大小為M存儲n個記錄的表散列函數(shù)(在理

44、想情況下)將把記錄在表中M個位置平均放置，使得平均每一個鏈表中有n/M個記錄M>n 時，散列方法的平均代價就是Θ(1),拉鏈法不適于外存檢索,如果整個散列表存儲在內(nèi)存中，開散列方法比較容易實現(xiàn)如果散列表存儲在磁盤中，用開散列不太合適一個同義詞表中的元素可能存儲在不同的磁盤頁中這就會導致在檢索一個特定關鍵碼值時引起多次磁盤訪問，從而增加了檢索時間桶式散列,2. 桶式散列,適合存儲于磁盤的散列表基本思想:把一個文件的記錄

45、分為若干存儲桶，每個存儲桶包含一個或多個頁塊一個存儲桶內(nèi)的各頁塊用指針連接起來，每個頁塊包含若干記錄散列函數(shù)h(K)表示具有關鍵碼值K的記錄所在的存儲桶號,桶式散列文件組織,,,,右圖表示了一個具有B個存儲桶的散列文件組織如果B很小，存儲桶目錄表可放在內(nèi)存如果B較大，要存放好多頁塊，則存儲桶目錄表就放到外存上,10.3.3 閉散列方法,d0=h（K）稱為K的基地址地置當沖突發(fā)生時，使用某種方法為關鍵碼K生成一個散列地址序列

46、 d1，d2，... di ，...dm-1所有di(0<i<m)是后繼散列地址形成探查的方法不同，所得到的解決沖突的方法也不同,閉散列表解決沖突的基本思想（續(xù)）,當插入K時，若基地址上的結點已被別的數(shù)據(jù)元素占用則按上述地址序列依次探查，將找到的第一個開放的空閑位置di作為K的存儲位置若所有后繼散列地址都不空閑，說明該閉散列表已滿，報告溢出,檢索過程,檢索時也要像插入時一樣遵循同樣的策略重復沖突解決過程

47、找出在基位置沒有找到的記錄,探查序列,插入和檢索函數(shù)都假定每個關鍵碼的探查序列中至少有一個存儲位置是空的否則可能會進入一個無限循環(huán)中也可以限制探查序列長度,幾種常見的閉散列方法,1. 線性探查2. 二次探查3. 偽隨機數(shù)序列探查4. 雙散列探查法,,,,,1. 線性探查,基本思想：如果記錄的基位置存儲位置被占用，那么就在表中下移，直到找到一個空存儲位置依次探查下述地址單元：d+1，d+2，......，M-1，0，1，..

48、....，d-1 用于簡單線性探查的探查函數(shù)是： p(K，i) = i線性探查的優(yōu)點表中所有的存儲位置都可以作為插入新記錄的候選位置,可能產(chǎn)生的問題——聚集,“聚集”（clustering，或稱為“堆積”）散列地址不同的結點，爭奪同一后繼散列地址小的聚集可能匯合成大的聚集導致很長的探查序列,散列表示例,M = 15, h(key) = key%13在理想情況下，表中的每個空槽都應該有相同的機會接收

49、下一個要插入的記錄。下一條記錄放在第11個槽中的概率是2/15放到第7個槽中的概率是11/15,改進線性探查,每次跳過常數(shù)c個而不是1個槽探查序列中的第i個槽是(h(K) + ic) mod M基位置相鄰的記錄就不會進入同一個探查序列了 探查函數(shù)是p(K，i) = i*c必須使常數(shù)c與M互素,例：改進線性探查,例如，c = 2，要插入關鍵碼k1和k2，h(k1) = 3，h(k2) = 5探查序列k1的探查序列是3、5、

50、7、9、...k2的探查序列就是5、7、9、...k1和k2的探查序列還是糾纏在一起，從而導致了聚集,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,例：二次探查,例：使用一個大小M =

51、 13的表 假定對于關鍵碼k1和k2，h(k1)=3，h(k2)=2探查序列k1的探查序列是3、4、2、7 、...k2的探查序列是2、3、1、6 、...盡管k2會把k1的基位置作為第2個選擇來探查，但是這兩個關鍵碼的探查序列此后就立即分開了,3. 偽隨機數(shù)序列探查,探查函數(shù) p(K，i) = perm[i - 1]這里perm是一個長度為M - 1的數(shù)組包含值從1到M - 1的隨機序列,產(chǎn)生n個數(shù)的偽隨機

52、排列,void permute(int *array, int n) { for (int i = 1; i <= n; i ++) swap(array[i-1], array[Random(i)]);},例：偽隨機數(shù)序列探查,例：考慮一個大小為M = 13的表，perm[0] = 2，perm[1] = 3，perm[2] = 7。假定兩個關鍵碼k1和k2，h(k1)=4，h(k2)=2探查序列k1的探

53、查序列是4、6、7、11 、...k2的探查序列是2、4、5、9 、...盡管k2會把k1的基位置作為第2個選擇來探查，但是這兩個關鍵碼的探查序列此后就立即分開了,適用范圍廣,還有很多散列方法分布散列函數(shù)(DHT),二級聚集,能消除基本聚集基地址不同的關鍵碼，其探查序列的某些段重疊在一起偽隨機探查和二次探查可以消除二級聚集 (secondary clustering)如果兩個關鍵碼散列到同一個基地址，還是得到同樣的探查序

54、列，所產(chǎn)生的聚集原因探查序列只是基地址的函數(shù)，而不是原來關鍵碼值的函數(shù)例子：偽隨機探查和二次探查,4. 雙散列探查法,避免二級聚集探查序列是原來關鍵碼值的函數(shù)而不僅僅是基位置的函數(shù)雙散列探查法利用第二個散列函數(shù)作為常數(shù)每次跳過常數(shù)項，做線性探查,雙散列探查法的基本思想,雙散列探查法使用兩個散列函數(shù)h1和h2若在地址h1(key)=d發(fā)生沖突，則再計算h2(key)，得到的探查序列為： (d+h2(k

55、ey)) % M， (d+2h2 (key)) %M ， (d+3h2 (key)) % M ， ...,明確兩個公式概念,雙散列函數(shù)探查法序列公式： di=(d + i h2 (key)) % M雙散列函數(shù)公式： p(K, i) = i * h2 (key),雙散列函數(shù)法特征,h2 (key) 必須與M互素使發(fā)生沖突的同義詞地址均勻地分布在整個表中

56、否則可能造成同義詞地址的循環(huán)計算雙散列的優(yōu)點: 不易產(chǎn)生“聚集”缺點：計算量增大,M和h2(k)選擇方法,方法1：選擇M為一個素數(shù)，h2返回的值在1≤h2(K)≤M – 1范圍之間方法2：設置M = 2m，讓h2返回一個1到2m之間的奇數(shù)值方法3：若M是素數(shù)，h1(K)=K mod Mh2 (K) = K mod(M-2) + 1或者h2(K) = [K / M] mod(M-2) + 1 方法4：若M是任意數(shù)，h1(K

57、)=K mod p，(p 是小于M的最大素數(shù))h2 (K) = K mod q + 1 (q是小于p的最大素數(shù)),10.3.4 閉散列表的算法實現(xiàn),字典(dictionary)一種特殊的集合，其元素是(關鍵碼，屬性值)二元組。關鍵碼必須是互不相同的(在同一個字典之內(nèi))主要操作是依據(jù)關鍵碼來存儲和析取值insert(key, value)lookup(key),實現(xiàn)方式,實現(xiàn)方式有序線性表字符樹散列方法,散列字典ADT

58、（屬性）,template class hashdict {private: Elem* HT; // 散列表 int M; // 散列表大小 int currcnt; // 現(xiàn)有元素數(shù)目 Elem EMPTY; // 空槽 int p(Key K，int i

59、) // 探查函數(shù) int h(int x) const ; // 散列函數(shù) int h(char* x)const ; // 字符串散列函數(shù),散列字典ADT（方法）,public: hashdict(int sz，Elem e) { // 構造函數(shù) M=sz; EMPTY=e; currcnt=0; HT=new Elem[sz]; for (i

60、nt i=0; i<M; i++) HT[i]=EMPTY; } ~hashdict() { delete [] HT; } bool hashSearch(const Key&，Elem&) const; bool hashInsert(const Elem&); Elem hashDelete(const Key& K); int size() { retu

61、rn currcnt; } // 元素數(shù)目};,插入算法,散列函數(shù)h，假設給定的值為K若表中該地址對應的空間未被占用，則把待插入記錄填入該地址如果該地址中的值與K相等，則報告“散列表中已有此記錄”否則，按設定的處理沖突方法查找探查序列的下一個地址，如此反復下去直到某個地址空間未被占用（可以插入）或者關鍵碼比較相等（不需要插入）為止,散列表插入算法代碼,// 將數(shù)據(jù)元素e插入到散列表 HTtemplate bool has

62、hdict::hashInsert(const Elem& e) { int home= h(getkey(e)); //home存儲基位置 int i=0; int pos = home; // 探查序列的初始位置 while (!EEComp::eq(EMPTY, HT[pos])) { if (EEComp::eq(e, HT[pos])) return false;

63、 i++; pos = (home+p(getkey(e), i)) % M; //探查 } HT[pos] = e; // 插入元素e return true; },散列表的檢索,與插入過程類似采用的探查序列也相同,檢索算法,假設散列函數(shù)h，給定的值為K若表中該地址對應的空間未被占用，則檢索失敗否則將該地址中的值與K比較，若相等則檢索成功否則，按建表

64、時設定的處理沖突方法查找探查序列的下一個地址，如此反復下去關鍵碼比較相等，檢索成功地址空間未被占用，檢索失敗,散列表檢索算法代碼,template bool hashdict::hashSearch(const Key& K, Elem& e) const{ int i=0, pos= home= h(K); // 初始位置 while (!EEComp::eq(EMPTY, HT[pos])) {

65、 if (KEComp::eq(K, HT[pos])) { // 找到 e = HT[pos]; return true; } i++; pos = (home + p(K, i)) % M; }//while return false; },刪除,刪除記錄的時候，有兩點需要重點考慮： (1) 刪除一個記錄一定不能影響后面的檢索(2) 釋

66、放的存儲位置應該能夠為將來插入使用 只有開散列方法（分離的同義詞子表）可以真正刪除閉散列方法都只能作標記（墓碑），不能真正刪除若真正刪除了探查序列將斷掉檢索算法 “直到某個地址空間未被占用（檢索失?。蹦贡畼擞浽黾恿似骄鶛z索長度,刪除帶來的問題,例如，一個長度M = 13的散列表，假定關鍵碼k1和k2，h(k1) = 2，h(k2) = 6。二次探查序列k1的二次探查序列是2、3、1、6、11、11、6、5、12、.

67、..k2的二次探查序列是6、7、5、10、2、2、10、9、3、... k2的同義詞占用刪除位置6，用該序列的最后位置2的元素替換之，位置2設為空檢索k1的同義詞，查不到可事實上它們還存放在位置3和1上!,墓碑,設置一個特殊的標記位，來記錄散列表中的單元狀態(tài)單元被占用空單元已刪除是否可以把空單元、已刪除這兩種狀態(tài)，用特殊的值標記，以區(qū)別于“單元被占用”狀態(tài)？不可以！被刪除標記值稱為墓碑( tombstone )

68、標志一個記錄曾經(jīng)占用這個槽但是現(xiàn)在已經(jīng)不再占用了,帶墓碑的插入操作,在插入時，如果遇到標志為墓碑的槽，可以把新記錄存儲在該槽中嗎?避免插入兩個相同的關鍵碼檢索過程仍然需要沿著探查序列下去，直到找到一個真正的空位置,帶墓碑的刪除算法,template Elem hashdict::hashDelete(const Key& K){ int i=0, pos = home= h(K); //初始位置

69、 while (!EEComp::eq(EMPTY, HT[pos])) { if (KEComp::eq(K, HT[pos])){ temp = HT[pos]; HT[pos] = TOMB; //設置墓碑 return temp; //返回目標} i++; pos = (home + p(K, i))