數(shù)據(jù)結(jié)構(gòu)與算法檢索

1、數(shù)據(jù)結(jié)構(gòu)與算法 第10章 檢索,本章由張銘主寫(xiě)http://db.pku.edu.cn/mzhang/DS/http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 張銘，王騰蛟，趙海燕高等教育出版社，2008. 6。“十一五”國(guó)家級(jí)規(guī)劃教材,第十章 檢索,基本概念10.1 線性表的檢索10.2 集合的檢索10.3 散列表的檢索10.4 總結(jié),,,,,,基本概念,檢索檢索的

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

3、的位置缺點(diǎn)：不適合進(jìn)行范圍查詢一般也不允許出現(xiàn)重復(fù)關(guān)鍵碼,平均檢索長(zhǎng)度（ASL）,關(guān)鍵碼的比較：檢索運(yùn)算的主要操作平均檢索長(zhǎng)度(Average Search Length)檢索過(guò)程中對(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ù),平均檢索長(zhǎng)度的例子,假設(shè)線性表為（a, b, c）檢索a、b、c的

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

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

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

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

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

9、長(zhǎng)Θ(n),10.1.2 二分檢索法,將任一元素dataList[i] .Key與給定值K比較三種情況： （1）Key = K，檢索成功，返回dataList[i] （2）Key > K，若有則一定排在dataList[i]]前 （3）Key < K，若右則一定排在dataList[i]后縮小進(jìn)一步檢索的區(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},關(guān)鍵碼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,二分法檢索性能分析,最大檢索長(zhǎng)度 失敗的檢索長(zhǎng)度是 或在算法復(fù)雜性分析中l(wèi)og n是以2為底的對(duì)數(shù)其他底，算法量級(jí)不變,15,18,22,51,,,,,,,,,,,,7,8,9,2,1,3,4,88,60,93,35,17,5,6,二分法檢索性能分析（續(xù)）,成功的平均檢索長(zhǎng)度為：

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

14、，將表分成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

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

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

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

18、：集合的無(wú)符號(hào)數(shù)表示,全集元素個(gè)數(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不夠一個(gè)ulong, 左補(bǔ)0,10.3 散列檢索,10.3.0 散列中的基本問(wèn)題10.3.1 散列函數(shù)碰撞的處理10.3.2 開(kāi)散

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

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

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

22、key)=key[0] – ‘a(chǎn)’,例子1（續(xù)）,例子2,修改散列函數(shù)：散列函數(shù)的值為key中首尾字母在字母表中序號(hào)的平均值，即：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ù)）,幾個(gè)重要概念,負(fù)載因子 α=

23、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è)重要問(wèn)題,采用散列技術(shù)時(shí)需要考慮的兩個(gè)首要問(wèn)題是：（1）如何構(gòu)造(選擇)使結(jié)點(diǎn)“分布均勻”的散列函數(shù)？（2）一旦發(fā)生沖突，用什么方法來(lái)解決？還需考慮散列表本身的組織方法,10.3.1 散列函數(shù),散列函數(shù)：把關(guān)鍵碼值映射到存儲(chǔ)位置的函數(shù)

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

25、 除余法,除余法：用關(guān)鍵碼x除以M(往往取散列表長(zhǎng)度)，并取余數(shù)作為散列地址。散列函數(shù)為： h(x) ＝ x mod M通常選擇一個(gè)質(zhì)數(shù)作為M值函數(shù)值依賴于自變量x的所有位，而不僅僅是最右邊k個(gè)低位增大了均勻分布的可能性例如，4093,M為什么不用偶數(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ù)值就

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

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

28、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)? =

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

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

31、d 位數(shù)，每一位可能有 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ì)

32、算出的 ?k 值越小，表明在該位 (第k 位)各種符號(hào)分布得越均勻,數(shù)字分析法（續(xù)2）,若散列表地址范圍有 3 位數(shù)字, 取各關(guān)鍵碼的④⑤⑥位做為記錄的散列地址也可以把第①，②，③和第⑤位相加，舍去進(jìn)位，變成一位數(shù)，與第④，⑥位合起來(lái)作為散列地址。還可以用其它方法,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、適用于事先明確知道表中所有關(guān)鍵碼每一位數(shù)值的分布情況它完全依賴于關(guān)鍵碼集合如果換一個(gè)關(guān)鍵碼集合，選擇哪幾位數(shù)據(jù)要重新決定,5. 基數(shù)轉(zhuǎn)換法,把關(guān)鍵碼看成是另一進(jìn)制上的數(shù)后再把它轉(zhuǎn)換成原來(lái)進(jìn)制上的數(shù)取其中若干位作為散列地址一般取大于原來(lái)基數(shù)的數(shù)作為轉(zhuǎn)換的基數(shù)，并且兩個(gè)基數(shù)要互素,例：基數(shù)轉(zhuǎn)換法,例如，給定一個(gè)十進(jìn)制數(shù)的關(guān)鍵碼是(210485)10，把它看成以13為基數(shù)的十三進(jìn)制數(shù)(210485)13 ，再把它轉(zhuǎn)換為十進(jìn)制

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

38、地址,兩種折疊方法,兩種疊加方法：移位疊加 — 把各部分的最后一位對(duì)齊相加分界疊加 — 各部分不折斷，沿各部分的分界來(lái)回折疊，然后對(duì)齊相加，將相加的結(jié)果當(dāng)做散列地址,例：折疊法,[例10.6] 如果一本書(shū)的編號(hào)為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ù)特征,長(zhǎng)字符串和短字符串都很有效字符串中每個(gè)字符都有同樣的作用對(duì)于散列表中的位置

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

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

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

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

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

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

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

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

49、下一個(gè)要插入的記錄。下一條記錄放在第11個(gè)槽中的概率是2/15放到第7個(gè)槽中的概率是11/15,改進(jìn)線性探查,每次跳過(guò)常數(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)線性探查,例如，c = 2，要插入關(guān)鍵碼k1和k2，h(k1) = 3，h(k2) = 5探查序列k1的探查序列是3、5、

50、7、9、...k2的探查序列就是5、7、9、...k1和k2的探查序列還是糾纏在一起，從而導(dǎo)致了聚集,2. 二次探查,探查增量序列依次為：12，-12，22 ，-22，...，即地址公式是 d2i-1 = (d +i2) % M d2i = (d – i2) % M用于簡(jiǎn)單線性探查的探查函數(shù)是 p(K，2i-1) = i*i p(K，2i) = - i*i,例：二次探查,例：使用一個(gè)大小M =

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

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

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

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

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

56、否則可能造成同義詞地址的循環(huán)計(jì)算雙散列的優(yōu)點(diǎn): 不易產(chǎn)生“聚集”缺點(diǎn)：計(jì)算量增大,M和h2(k)選擇方法,方法1：選擇M為一個(gè)素?cái)?shù)，h2返回的值在1≤h2(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

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

58、（屬性）,template class hashdict {private: Elem* HT; // 散列表 int M; // 散列表大小 int currcnt; // 現(xiàn)有元素?cái)?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) { // 構(gòu)造函數(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; } // 元素?cái)?shù)目};,插入算法,散列函數(shù)h，假設(shè)給定的值為K若表中該地址對(duì)應(yīng)的空間未被占用，則把待插入記錄填入該地址如果該地址中的值與K相等，則報(bào)告“散列表中已有此記錄”否則，按設(shè)定的處理沖突方法查找探查序列的下一個(gè)地址，如此反復(fù)下去直到某個(gè)地址空間未被占用（可以插入）或者關(guān)鍵碼比較相等（不需要插入）為止,散列表插入算法代碼,// 將數(shù)據(jù)元素e插入到散列表 HTtemplate bool has

62、hdict::hashInsert(const Elem& e) { int home= h(getkey(e)); //home存儲(chǔ)基位置 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; },散列表的檢索,與插入過(guò)程類似采用的探查序列也相同,檢索算法,假設(shè)散列函數(shù)h，給定的值為K若表中該地址對(duì)應(yīng)的空間未被占用，則檢索失敗否則將該地址中的值與K比較，若相等則檢索成功否則，按建表

64、時(shí)設(shè)定的處理沖突方法查找探查序列的下一個(gè)地址，如此反復(fù)下去關(guān)鍵碼比較相等，檢索成功地址空間未被占用，檢索失敗,散列表檢索算法代碼,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; },刪除,刪除記錄的時(shí)候，有兩點(diǎn)需要重點(diǎn)考慮： (1) 刪除一個(gè)記錄一定不能影響后面的檢索(2) 釋

66、放的存儲(chǔ)位置應(yīng)該能夠?yàn)閷?lái)插入使用 只有開(kāi)散列方法（分離的同義詞子表）可以真正刪除閉散列方法都只能作標(biāo)記（墓碑），不能真正刪除若真正刪除了探查序列將斷掉檢索算法 “直到某個(gè)地址空間未被占用（檢索失?。蹦贡畼?biāo)記增加了平均檢索長(zhǎng)度,刪除帶來(lái)的問(wèn)題,例如，一個(gè)長(zhǎng)度M = 13的散列表，假定關(guān)鍵碼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設(shè)為空檢索k1的同義詞，查不到可事實(shí)上它們還存放在位置3和1上!,墓碑,設(shè)置一個(gè)特殊的標(biāo)記位，來(lái)記錄散列表中的單元狀態(tài)單元被占用空單元已刪除是否可以把空單元、已刪除這兩種狀態(tài)，用特殊的值標(biāo)記，以區(qū)別于“單元被占用”狀態(tài)？不可以！被刪除標(biāo)記值稱為墓碑( tombstone )

68、標(biāo)志一個(gè)記錄曾經(jīng)占用這個(gè)槽但是現(xiàn)在已經(jīng)不再占用了,帶墓碑的插入操作,在插入時(shí)，如果遇到標(biāo)志為墓碑的槽，可以把新記錄存儲(chǔ)在該槽中嗎?避免插入兩個(gè)相同的關(guān)鍵碼檢索過(guò)程仍然需要沿著探查序列下去，直到找到一個(gè)真正的空位置,帶墓碑的刪除算法,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; //設(shè)置墓碑 return temp; //返回目標(biāo)} i++; pos = (home + p(K, i))