2數(shù)據(jù)結(jié)構(gòu)與算法北大彩色講義

1、數(shù)據(jù)結(jié)構(gòu)與算法第九章檢索任課教員：張銘mzhang信息科學(xué)與技術(shù)學(xué)院網(wǎng)絡(luò)與信息系統(tǒng)Ó所有，或第九章檢索n 基本概念n 9.1n 9.2n 9.3n 9.4線性表的檢索集合的檢索 散列表的檢索總結(jié)張銘ÓPage 2信息學(xué)院編寫所有，或基本概念n 檢索：在一組集合中找到關(guān)鍵碼值等于給定值的某個(gè)，或者找到關(guān)鍵碼值符合特定條件的某些過程的n 檢索的效率非常重要n 尤其對(duì)于大數(shù)據(jù)量n 需要對(duì)數(shù)據(jù)進(jìn)行特殊的處理張銘ÓPage 3信息學(xué)院編寫所有，或基本概念（續(xù)）n 預(yù)排序n 排序算法本身比較費(fèi)時(shí)n 只是預(yù)處理（在檢索之前已經(jīng)完成）n 建立索引n 檢索時(shí)充分利用輔助索引信息n

2、犧牲一定的空間n 從而提高檢索效率張銘ÓPage 4信息學(xué)院編寫所有，或基本概念（續(xù)）n 散列技術(shù)n 把數(shù)據(jù)組織到一個(gè)表中n 根據(jù)關(guān)鍵碼的值來確定表中每個(gè)n 缺點(diǎn)：n 不適合進(jìn)行范圍的位置n 一般也不出現(xiàn)重復(fù)關(guān)鍵碼n 當(dāng)散列方法不適合于基于磁盤的應(yīng)用程序時(shí)，我們可以選擇B樹方法張銘ÓPage 5信息學(xué)院編寫所有，或平均檢索長度（ASL）n 關(guān)鍵碼的比較：檢索運(yùn)算的主要操作n 平均檢索長度(Average Search Length)n 檢索過程中對(duì)關(guān)鍵碼的平均比較次數(shù)n 衡量檢索算法優(yōu)劣的時(shí)間標(biāo)準(zhǔn)nå=A S LPi Cii = 1Pi 為檢索第i個(gè)元素的概率Ci

3、 為找到第i個(gè)元素所需的關(guān)鍵碼值與給定值的比較次數(shù)張銘ÓPage6信息學(xué)院編寫所有，或平均檢索長度的例子n 假設(shè)線性表為（a, b, c）檢索a、b、c的概率分別為0.4、0.1、0.5n 順序檢索算法的平均檢索長度為0.4×1+0.1×2+0.5×3 = 2.1n 即平均需要2.1次給定值與表中關(guān)鍵碼值的比較才能找到待查元素張銘ÓPage 7信息學(xué)院編寫所有，或檢索算法評(píng)估的幾個(gè)問題n 衡量一個(gè)檢索算法還需要考慮n 算法所需的n 算法的復(fù)雜性n .量張銘ÓPage8信息學(xué)院編寫所有，或9.1基于線性表的檢索n 9.1.1n 9.1.

4、2n 9.1.3順序檢索二分檢索分塊檢索張銘ÓPage 9信息學(xué)院編寫所有，或9.1.1順序檢索線性表里的所有，逐個(gè)進(jìn)行關(guān)鍵碼和給定值的比較 。n 若某個(gè)的關(guān)鍵碼和給定值比較相等，則檢索；n 否則檢索失敗(找遍了仍找不到)。：可以順序、n 排序要求：無張銘ÓPage10信息學(xué)院編寫所有，或順序檢索算法template<class Type>class Item public:Item(Type value):key(value) Type getKey() return key; /取關(guān)鍵碼值; void setKey(Type k) key=k; /置關(guān)鍵碼p

5、rivate:Typekey;/關(guān)鍵碼域/其它域string other;vector<Item<Type>*>dataList;張銘ÓPage11信息學(xué)院編寫所有，或“監(jiān)視哨”順序檢索算法返回元素位置，檢索失敗統(tǒng)一返回0;n 檢索template <class Type> intSeqSearch(vector<Item<Type>*>& dataList,int length, Type k) int i=length;/將第0個(gè)元素設(shè)為待檢索值dataList0->setKey (k); /設(shè)監(jiān)視哨whi

6、le(dataListi->getKey()!=k) i-;return i;/返回元素位置張銘ÓPage 12信息學(xué)院編寫所有，或順序檢索性能分析n 檢索假設(shè)檢索每個(gè)關(guān)鍵碼是等概率的，Pin - 1=1/n1 n - 1å Pi·(n - i) =i = 0=å(n - i)ni = 0ni = n + 1å2i = 1n 檢索失敗假設(shè)檢索失敗時(shí)都需要比較n+1次（設(shè)置了一個(gè)監(jiān)視哨）張銘ÓPage 13信息學(xué)院編寫所有，或順序檢索平均檢索長度n 假設(shè)檢索為q=(1-p)AS L的概率為p，檢索失敗的概率n + 1=p 

7、5;+ q × ( n + 1)2p × n + 1 + (1 -=p )( n + 1)2( n + 1)(1 -p / 2 )n （n+1)/2<ASL< (n+1)張銘ÓPage14信息學(xué)院編寫所有，或順序檢索優(yōu)缺點(diǎn)n 優(yōu)點(diǎn)：元素可以直接加在表尾(1)n 缺點(diǎn)：檢索時(shí)間太長(n)張銘ÓPage 15信息學(xué)院編寫所有，或9.1.2二分檢索法n 將任一元素dataListi .Key與給定值K比較n 三種情況：（1）Key = K，檢索，返回dataListi（2） Key > K，若有則一定排在dataListi前（3） Key &

8、lt; K，若右則一定排在dataListi后n 縮小進(jìn)一步檢索的區(qū)間張銘ÓPage16信息學(xué)院編寫所有，或二分法檢索算法template <class Type> int BinSearch(vector<Item<Type>*>& dataList,int length,Type k) int low=1, high=length, mid;while (low<=high) mid=(low+high)/2;if (k<dataListmid->getKey()high = mid-1;/右縮檢索區(qū)間else if

9、(k>dataListmid->getKey()low = mid+1; else return mid; /左縮檢索區(qū)間返回位置return 0; /檢索失敗，返回0張銘ÓPage 17信息學(xué)院編寫所有，或二分法檢索圖示lowmidhigh=9high檢索關(guān)鍵碼18low=1K=18第一次：mid=5;array5=35>18high=4; (low=1)第二次：mid=2; array2=17<18low=3;(high=4)第三次：mid=3;array3=18=18mid=3；return 8張銘ÓPage 18信息學(xué)院編寫所有，或12345

10、6789151718223551608893二分法檢索性能分析n 最大檢索長度為5léo（gn +ù 1）2217n 失敗的檢索長度是n 停止在內(nèi)部葉結(jié)點(diǎn)léog（2lëog（2n +n +ù1）û1）或n 停止在外部空結(jié)點(diǎn)，則加1張銘Ó9ge 1Pa信息學(xué)院編寫所有，或二分法檢索性能分析（續(xù)）的平均檢索長度為：j1 (i × 2 i - 1 )=åi = 1AS Lnn + 1 lo g=»( n + 1) - 12nlo g 2 ( n + 1) - 1(n > 50)n 優(yōu)缺點(diǎn)n 優(yōu)

11、點(diǎn)：平均與最大檢索長度相近，檢索速度快n 缺點(diǎn)：要排序、順序，不易更新(插/刪)張銘ÓPage 20信息學(xué)院編寫所有，或9.1.3 分塊檢索n 順序與二分法的折衷n 既有較快的檢索n 又有較靈活的更改張銘ÓPage 21信息學(xué)院編寫所有，或分塊檢索思想n “按塊有序”n 設(shè)線性表中共有n個(gè)數(shù)據(jù)元素，將表分成b塊n 不需要均勻n 每一塊可能不滿n 每一塊中的關(guān)鍵碼不一定有序n 但前一塊中的最大關(guān)鍵碼必須小于后一塊中的最小關(guān)鍵碼張銘ÓPage 22信息學(xué)院編寫所有，或索引表n 索引表n 各塊中的最大關(guān)鍵碼n 及各塊起始位置n 可能還需要塊中元素個(gè)數(shù)（每一塊可能不滿）n

12、 索引表是一個(gè)遞增有序表n 由于表是分塊有序的張銘ÓPage 23信息學(xué)院編寫所有，或分塊檢索分兩個(gè)階段n （1）確定待查元素所在的塊n （2）在塊內(nèi)檢索待查的元素分塊檢索索引順序結(jié)構(gòu)張銘ÓPage 24信息學(xué)院編寫所有，或分塊檢索索引順序結(jié)構(gòu)01234567891011121314151617link:Key:Size:塊內(nèi)最大關(guān)鍵碼塊起始位置塊內(nèi)有效元素個(gè)數(shù)張銘ÓPage 25信息學(xué)院編寫所有，或06122248863652212133342443824486080744986分塊檢索性能分析n 分塊檢索為兩級(jí)檢索n 先在索引表中確定待查元素所在的塊；n 設(shè)在

13、索引表中確定塊號(hào)的時(shí)間開銷是ASLbn 然后在塊內(nèi)檢索待查的元素。n 在塊中查找的時(shí)間開銷為ASLwn ASL(n)信息學(xué)院=張銘ASLb編寫+ÓASLw所有，Page 26或分塊檢索性能分析(續(xù)1)n 索引表是按塊內(nèi)最大關(guān)鍵碼有序的， 且長度也不大， 可以二分檢索，也可以順序檢索n 各子表內(nèi)各個(gè)不是按關(guān)鍵碼有序，只能順序檢索張銘ÓPage 27信息學(xué)院編寫所有，或分塊檢索性能分析(續(xù)2)n 假設(shè)在索引表中用順序檢索，在塊內(nèi)也用順序檢索b + 1s + 1ASL=ASL bw22ASL = b + 1 + s + 1 = b + s + 12n + s 22+ 12=2 s

14、n 時(shí)，ASL取最小值，n 當(dāng)s=ASLn +1 =nÓ張銘Page28信息學(xué)院編寫所有，或分塊檢索性能分析(續(xù)3)n 當(dāng)n=10,000時(shí)n 順序檢索5,000次n 二分法檢索14次n 分塊檢索100次n 如果數(shù)據(jù)塊（子表）存放在外存時(shí)，還會(huì)受到頁塊大小的制約n 此時(shí)往往以外存一個(gè)/ 頁）作為一塊的數(shù)據(jù)（一張銘ÓPage 29信息學(xué)院編寫所有，或分塊檢索性能分析(續(xù)4)n 若采用二分法檢索確定所在的子表，則檢索索長度為ASL= ASLb + ASLw時(shí)的平均檢» log2 (b+1)-1 + (s+1)/2» log2(1+n / s ) + s/2張

15、銘ÓPage 30信息學(xué)院編寫所有，或分塊檢索的優(yōu)缺點(diǎn)n 優(yōu)點(diǎn)：、刪除相對(duì)較易n 沒有大量n 缺點(diǎn)：移動(dòng)n 增加一個(gè)輔助數(shù)組的n 初始線性表分塊排序空間n 當(dāng)大量/刪除時(shí)，或結(jié)點(diǎn)分布不均勻時(shí)，速度下降張銘ÓPage31信息學(xué)院編寫所有，或9.2集合的檢索用位向量來表示集合對(duì)于密集型集合（數(shù)據(jù)范圍小，而集合中有效元素個(gè)數(shù)比較多）01234567815張銘ÓPage32信息學(xué)院編寫所有，或0011010100010100例：計(jì)算0到15之間所有的奇素?cái)?shù)奇數(shù)：05素?cái)?shù)：15奇素?cái)?shù)：張銘ÓPage 33信息學(xué)院編寫所有，或00010101000101000101

16、01010101010101234567&89 1011121314 150011010100010100=實(shí)際實(shí)現(xiàn)用無符合長整數(shù)數(shù)組n 全集元素個(gè)數(shù)N=40的集合，集合35, 9, 7, 5, 3, 1表示為0000000000000000000000000000000000000000000000100000101010001010不夠一個(gè)usigned long,左補(bǔ)0張銘ÓPage 34信息學(xué)院編寫所有，或9.3散列檢索n 9.3.0n 9.3.1散列中的基本問題散列函數(shù)n 碰撞的處理n 9.3.2n 9.3.3n 9.3.4n 9.3.5開散列方法閉散列方法閉散列表

17、的算法實(shí)現(xiàn)散列方法的效率分析張銘ÓPage 35信息學(xué)院編寫所有，或9.3.0散列中的基本問題基于關(guān)鍵碼比較的檢索n 順序檢索，=, !=n 二分法、樹型 >, = , <檢索是直接面向用戶的操作當(dāng)問題規(guī)模n很大時(shí)，上述檢索的時(shí)間效率可能使得用戶最理想的情況受n 根據(jù)關(guān)鍵碼值，直接找到n 不需要把待查關(guān)鍵碼與候選行逐個(gè)比較的地址集合的某些進(jìn)張銘ÓPage 36信息學(xué)院編寫所有，或由數(shù)組的直接尋址想到的例如， 素指定下標(biāo)的數(shù)組元n 根據(jù)數(shù)組的起始地址、以及數(shù)組下標(biāo)值而直接計(jì)算出來的，所花費(fèi)的時(shí)間是O(1)n 與數(shù)組元素個(gè)數(shù)的規(guī)模n無關(guān)受此啟發(fā)，計(jì)算機(jī)科學(xué)家發(fā)明了散

18、列方法（Hash, 有人稱“哈?！?，還有稱“雜湊”）散列是一種重要的方法也是一種常見的檢索方法張銘ÓPage 37信息學(xué)院編寫所有，或散列基本思想n 一個(gè)確定的函數(shù)關(guān)系hn 以結(jié)點(diǎn)的關(guān)鍵碼K為自變量n 函數(shù)值h(K)作為結(jié)點(diǎn)的地址n 檢索時(shí)也是根據(jù)這個(gè)函數(shù)計(jì)算其置位n 通常散列表的空間是一個(gè)一維數(shù)組n 散列地址是數(shù)組的下標(biāo)張銘ÓPage38信息學(xué)院編寫所有，或例子1例9.1：已知線性表關(guān)鍵碼集合為：S = and, begin, do, end, for, go, if, repeat, then, until, while可設(shè)散列表為：charHT2268;散列函數(shù)H(k

19、ey)的值，取為關(guān)鍵碼key中的第一個(gè)字母在字母表a, b, c, ., z中的序號(hào)，即：H(key)=key0 a張銘ÓPage 39信息學(xué)院編寫所有，或例子1表張銘ÓPage 40信息學(xué)院編寫所有，或散 列 地 址關(guān) 鍵 碼13 14 15 16 17 r e p e at 18 19 t h e n2 0un t i l21 22 w h i le(w i t h )23 24 25 散 列 地 址關(guān) 鍵 碼0an d( ar r ay) 1be g in23d o4e nd (e l s e )5f or 6go 78i f910 11 12 例子2例9.2：在集合

20、S中增加4個(gè)關(guān)鍵碼，集合S1 = S + else, array, with, up要修改散列函數(shù)：散列函數(shù)的值為key中首尾字母在字母表中序號(hào)的平均值，即：int H3(key)char key; int i; i = 0;while (i<8) && (keyi!=0)i+;return(key0 + key(i-1) 2*a) /2 )張銘ÓPage 41信息學(xué)院編寫所有，或例子2表張銘ÓPage 42信息學(xué)院編寫所有，或散 列 地 址關(guān) 鍵 碼13 w h ile14 w ith15 u n til16 th en17 18 rep eat 1

21、9 20 21 22 23 24 25 散 列 地 址關(guān) 鍵 碼01an d23en d4e lse56if7beg in8d o910 go 11fo r12 arra y幾個(gè)重要概念n 負(fù)載因子=n/mn 散列表的空間大小為mn 填入表中的結(jié)點(diǎn)數(shù)為nn 某個(gè)散列函數(shù)對(duì)于不相等的關(guān)鍵碼計(jì)算出了相同的散列地址n 在實(shí)際應(yīng)用中，不產(chǎn)生n 同義詞的散列函數(shù)極少存在n 發(fā)生的兩個(gè)關(guān)鍵碼張銘ÓPage 43信息學(xué)院編寫所有，或散列技術(shù)的兩個(gè)重要問題n 采用散列技術(shù)時(shí)需要考慮的兩個(gè)首要問題是：n （1）如何構(gòu)造(選擇)使結(jié)點(diǎn)“分布均勻”的散列函數(shù)？n （2）一旦發(fā)生決？n 還需考慮散列表本身的

22、組織方法，用什么方法來解張銘ÓPage 44信息學(xué)院編寫所有，或9.3.1散列函數(shù)n 散列函數(shù)：把關(guān)鍵碼值到位置的函數(shù)，通常用h來表示Address Hash ( key )張銘ÓPage45信息學(xué)院編寫所有，或散列函數(shù)的選取原則n 運(yùn)算盡可能簡單n 函數(shù)的值域必須在表長的范圍內(nèi)n 盡可能使得關(guān)鍵碼不同時(shí)，其散列函數(shù)值亦不相同張銘ÓPage 46信息學(xué)院編寫所有，或需要考慮各種因素n 關(guān)鍵碼長度n 散列表大小n 關(guān)鍵碼分布情況的檢索頻率n 張銘ÓPage 47信息學(xué)院編寫所有，或常用散列函數(shù)除余法乘余取整法平方取中法數(shù)字分析法基數(shù)轉(zhuǎn)換法折疊法ELFhas

23、h字符串散列函數(shù)n 1.n 2.n 3.n 4.n 5.n 6.n 7.張銘ÓPage 48信息學(xué)院編寫所有，或1.除余法n 除余法：用關(guān)鍵碼x除以M(往往取散列表長度)，并取余數(shù)作為散列地址。散列函數(shù)為：h(x) x mod Mn 通常選擇一個(gè)質(zhì)數(shù)作為M值函數(shù)值依賴于自變量x的所有位，而不僅僅是最右邊k個(gè)低位增大了均勻分布的可能性例如，4093張銘ÓPage 49信息學(xué)院編寫所有，或M為什么不用偶數(shù)n 若把M設(shè)置為偶數(shù)n x是偶數(shù)，h(x)也是偶數(shù)n x是奇數(shù)，h(x)也是奇數(shù)n 缺點(diǎn)：分布不均勻n 如果偶數(shù)關(guān)鍵碼比奇數(shù)關(guān)鍵碼出現(xiàn)的概率大，那么函數(shù)值就不能均勻分布n 反之

24、亦然張銘ÓPage50信息學(xué)院編寫所有，或x mod 28 選擇最右邊8位M不用冪n 若把M設(shè)置為2的冪n 那么，h(x)x mod 2k 僅僅是x(用二進(jìn)制表示)最右邊的k個(gè)位(bit)n 若把M設(shè)置為10的冪n 那么，h(x)x mod 10k 僅僅是x(用十進(jìn)制表示)最右邊的k個(gè)十進(jìn)制位(digital)n 缺點(diǎn)：散列值不依賴于x的全部比特位張銘ÓPage51信息學(xué)院編寫所有，或0除余法的問題n 除余法的潛在缺點(diǎn)n 連續(xù)的關(guān)鍵碼成連續(xù)的散列值n 雖然能保證連續(xù)的關(guān)鍵碼不發(fā)生n 但也意味著要占據(jù)連續(xù)的數(shù)組單元n 可能導(dǎo)致散列性能的降低張銘ÓPage 52信息學(xué)

25、院編寫所有，或2.乘余取整法n 先讓關(guān)鍵碼 key乘上一個(gè)常數(shù)A(0<A<1)，提取乘積的小數(shù)部分n 然后，再用整數(shù)n乘以這個(gè)值，對(duì)結(jié)果向下取整，把它作為散列地址n 散列函數(shù)為：hash ( key ) = ë n * ( A * key % 1 ) ûn “A* key% 1”表示取 A* key小數(shù)部分:A * key % 1 = A * key - ë A * key û張銘ÓPage53信息學(xué)院編寫所有，或乘余取整法示例n 設(shè)關(guān)鍵碼 key = 123456, n = 10000且取 A = (5 -1) / 2 = 0.6

26、180339，n 因此有hash(123456) = ë10000*(0.6180339*123456 % 1)û = ë10000 * (76300.0041151 % 1)û = ë10000 * 0.0041151û = 41張銘ÓPage 54信息學(xué)院編寫所有，或乘余取整法參數(shù)取值的考慮n 若地址空間為p位，就取n=2p所求出的散列地址正好是計(jì)算出來的A * key % 1 = A * key - ë A * key û值的小數(shù)點(diǎn)后最左p位（bit）值n 此方法的優(yōu)點(diǎn):對(duì) n的選擇無關(guān)緊要認(rèn)為：A

27、可以取任何值，與待排序的數(shù)據(jù)特征有關(guān)。一般情況下( 5 - 1) 2取黃金分割最理想張銘ÓPage 55信息學(xué)院編寫所有，或3.平方取中法n 此時(shí)可采用平方取中法：先通過求關(guān)鍵碼的平方來擴(kuò)大差別，再取其中的幾位或其組合作為散列地址n 例如，n 一組二進(jìn)制關(guān)鍵碼：(00000100，00000110， 000001010，000001001，000000111)n 平方結(jié)果為：(00010000，00100100，01100010， 01010001，00110001)n 若表長為4個(gè)二進(jìn)制位，則可取中間四位作為散列地址：(0100，1001，1000，0100，1100)張銘

28、1;Page 56信息學(xué)院編寫所有，或4.數(shù)字分析法n 設(shè)有 n 個(gè) d 位數(shù)，每一位可能有 r 種不同的符號(hào)n 這 r 種不同的符號(hào)在各位上出現(xiàn)的頻率不一定相同n 可能在某些位上分布均勻些，每種符號(hào)出現(xiàn)的幾率 均等n 在某些位上分布不均勻，只有某幾種符號(hào)經(jīng)常出現(xiàn)n 可根據(jù)散列表的大小，選取其中各種符號(hào)分布均勻的若干位作為散列地址張銘ÓPage 57信息學(xué)院編寫所有，或數(shù)字分析法（續(xù)1）lk 的公n 計(jì)算各位數(shù)字中符號(hào)分布的均勻度r式：åk=- n / r)k2(ii =1kikn 其中，表示第個(gè)符號(hào)在第位上出i現(xiàn)的次數(shù)，n n/rn表示各種符號(hào)在個(gè)數(shù)中均勻出現(xiàn)的期望值。n

29、 計(jì)算出的 lk(第k值越小，表明在該位位)各種符號(hào)分布得越均勻張銘ÓPage 58信息學(xué)院編寫所有，或數(shù)字分析法（續(xù)2）位， l 1 = 57.60位， l 2 = 57.60位， l 3 = 17.60位， l 4 = 5.60位， l 5 = 5.60位， l 6 = 5.60992148999999999999991011120256850062305409705871 n 若散列表地址范圍有 3 位數(shù)字, 的散列地址取各關(guān)鍵碼的位做為n 也可以把第，和第位相加，舍去進(jìn)位，變成一位 數(shù)，與第，位合起來作為散列地址。還可以用其它方法張銘ÓPage 59信息學(xué)院編寫所有

30、，或數(shù)字分析法（續(xù)3）n 位，僅9出現(xiàn)8次，n l=（8-8/10）2×1+（0-8/10）×9=57.621n 位，僅9出現(xiàn)8次，n l=（8-8/10）2×1+（0-8/10）×9=57.622n 位，0和2各出現(xiàn)兩次，1出現(xiàn)4次n l=（2-8/10）2×2+（4-8/10）×1+ （0-8/10）223×7 =17.6n 位，0和5各出現(xiàn)兩次，1、2、6、8各出現(xiàn)1次n 位，0和4各出現(xiàn)兩次，2、3、5、6各出現(xiàn)1次n 位，7和8各出現(xiàn)兩次，0、1、5、9各出現(xiàn)1次l 4 = l= l= （2-8/10）2×

31、;2+（1-8/10）×4+256（0-8/10）×4 =5.62張銘ÓPage 60信息學(xué)院編寫所有，或數(shù)字分析法（續(xù)4）n 數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵碼每一位數(shù)值的分布情況n 它完全依賴于關(guān)鍵碼集合n 如果換一個(gè)關(guān)鍵碼集合，選擇哪幾張銘ÓPage 61信息學(xué)院編寫所有，或5.基數(shù)轉(zhuǎn)換法n 把關(guān)鍵碼看成是另一進(jìn)制上的數(shù)后n 再把它轉(zhuǎn)換成原來進(jìn)制上的數(shù)n 取其中若干位作為散列地址n 一般取大于原來基數(shù)的數(shù)作為轉(zhuǎn)換的基數(shù)，并且兩個(gè)基數(shù)要互素張銘ÓPage 62信息學(xué)院編寫所有，或例：基數(shù)轉(zhuǎn)換法n 例如，給定一個(gè)十進(jìn)制數(shù)的關(guān)鍵碼是(

32、210485)10，把它看成以13為基數(shù)的十三進(jìn)制數(shù)(210485)13，再把它轉(zhuǎn)換為十進(jìn)制(210485)13 = 2×135 + 1×134 + 4×132 + 8×13 + 5= (771932)10n 假設(shè)散列表長度是10000，則可取低4位1932作為散列地址張銘ÓPage63信息學(xué)院編寫所有，或6.折疊法n 關(guān)鍵碼所含的位數(shù)很多，采用平方取中法計(jì)算太復(fù)雜n 折疊法n 將關(guān)鍵碼分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）n 然后取這幾部分的疊加和（舍去進(jìn)位）作為散列地址張銘ÓPage64信息學(xué)院編寫所有，或兩種折疊方法

33、n 兩種疊加方法：n 移位疊加 位對(duì)齊相加n 分界疊加 把各部分的最后一各部分不折斷，沿各部分的分界來回折疊，然后對(duì)齊相加，將相加的結(jié)果當(dāng)做散列地址張銘ÓPage65信息學(xué)院編寫所有，或例：折疊法n 例9.6 如果一本書的編號(hào)為04-42-20586-45 8 6 45 8 6 44 2 2 00 2 2 4n +0 4n 1 0 0 8 8+0 46 0 9 2n h(key)=0088n (a)移位疊加h(key)=6092 (b)分界疊加張銘ÓPage 66信息學(xué)院編寫所有，或7.ELFhash字符串散列函數(shù)n 用于UNIX系統(tǒng)V4.0“可執(zhí)行Linking Form

34、at，即ELF ) int ELFhash(char* key)unsigned long h = 0;格式”( Executable andwhile(*key) h = (h <<4)+*key+;unsigned long g = h & 0xF0000000L;if (g) h h &= g;= g>> 24;returnh%M;張銘ÓPage 67信息學(xué)院編寫所有，或ELFhash函數(shù)特征n 長字符串和短字符串都很有效n 字符串中每個(gè)字符都有同樣的作用n 對(duì)于散列表中的位置不可能產(chǎn)生不平均的分布張銘ÓPage 68信息學(xué)院編

35、寫所有，或散列函數(shù)的應(yīng)用n 在實(shí)際應(yīng)用中應(yīng)根據(jù)關(guān)鍵碼的特點(diǎn)，選用適當(dāng)?shù)纳⒘泻瘮?shù)n 有人曾用“賭”的統(tǒng)計(jì)分析方法對(duì)它們進(jìn)行了模擬分析，結(jié)論是平方取中法最接近于“隨機(jī)化”n 若關(guān)鍵碼不是整數(shù)而是字符串時(shí)，可以把每個(gè)字符串轉(zhuǎn)換成整數(shù)，再應(yīng)用平方取中法張銘ÓPage 69信息學(xué)院編寫所有，或：碰撞的處理n 開散列方法( open hashing，也稱為拉鏈法，separate chaining )n 把發(fā)生的關(guān)鍵碼在散列表主表之外n 閉散列方法( closed hashing，也稱為開地址方法，open addressing )n 把發(fā)生的關(guān)鍵碼在表中另一個(gè)槽內(nèi)張銘ÓPage 70

36、信息學(xué)院編寫所有，或9.3.2開散列方法n 當(dāng)碰撞發(fā)生時(shí)就拉出一條鏈，建立一個(gè)鏈表方式的同義詞子表動(dòng)態(tài)申請同義詞的空間，適合于內(nèi)存操作例：77、7、110、95、14、75、62 h(Key) = Key % 11n 1.n 2.拉鏈法桶式散列張銘ÓPage71信息學(xué)院編寫所有，或1.拉鏈法345678910 n 表中的空單元其實(shí)應(yīng)該有特殊值標(biāo)記出來，例如-1或INFIn 或者使得散列表中的內(nèi)容就是指針，空單元?jiǎng)t內(nèi)容為空指針。同義詞時(shí)，可以對(duì)同義詞鏈排序張銘ÓPage72信息學(xué)院編寫所有，或201277 拉鏈法性能分析n 給定一個(gè)大小為Mn個(gè)的表n 散列函數(shù)(在理想情況下)

37、將把在表中M個(gè)位置平均放置，使得平均每一個(gè)鏈表中有n/M個(gè)n M>n時(shí)，散列方法的平均代價(jià)就是(1)張銘ÓPage73信息學(xué)院編寫所有，或拉鏈法不適于外存檢索n 如果整個(gè)散列表 方法比較容易實(shí)現(xiàn)在內(nèi)存中，開散列n 如果散列表太合適在磁盤中，用開散列不n 一個(gè)同義詞表中的元素可能盤頁中在不同的磁n 這就會(huì)導(dǎo)致在檢索一個(gè)特定關(guān)鍵碼值時(shí)引起多次磁盤n 桶式散列，從而增加了檢索時(shí)間張銘ÓPage 74信息學(xué)院編寫所有，或溢出區(qū)靜態(tài)鏈張銘ÓPage 75信息學(xué)院編寫所有，或2.桶式散列n 適合于磁盤的散列表n 基本思想:n 把一個(gè)文件的分為若干桶，每個(gè)n 一個(gè)桶包含一

38、個(gè)或多個(gè)頁塊桶內(nèi)的各頁塊用指針連接起來，每個(gè)頁塊包含若干n 散列函數(shù)h(K)表示具有關(guān)鍵碼值K的所在的桶號(hào)張銘ÓPage 76信息學(xué)院編寫所有，或桶式散列文件組織n 右圖表示了一個(gè)具有B0個(gè)組織桶的散列文件b1b21n 如果B很小， 錄表可放在內(nèi)存n 如果B較大，要存放好桶目b3B-1多頁塊，則桶目b4b5b6錄表就放到外存上桶目錄表張銘ÓPage 77信息學(xué)院編寫所有，或桶式散列的磁盤性能分析一個(gè)查找平均訪外次數(shù)等于桶內(nèi)頁塊數(shù)k 的一半桶目錄表進(jìn)入內(nèi)存(假定目錄表不在n 調(diào) 內(nèi)存)n 為了尋找要求的各頁塊n 實(shí)際上是(k+1)/2必須逐個(gè)檢查一個(gè)桶內(nèi)對(duì)于修改、刪除等運(yùn)算尚

39、需另一次訪外，用于重新寫回外存張銘ÓPage78信息學(xué)院編寫所有，或性能分析(續(xù))桶式散列的磁盤n 最理想狀況:n 每個(gè)桶僅由一個(gè)頁塊組成，假設(shè)目錄在外存n 這樣只需訪外二次(對(duì)檢索)或三次(對(duì)其他運(yùn)算)n 要求桶的個(gè)數(shù)大致等于存放所需的頁塊數(shù)n 散列函數(shù)值分布均勻張銘ÓPage 79信息學(xué)院編寫所有，或桶式散列的問題n 理想狀況很難實(shí)現(xiàn)n 尤其當(dāng)文件不斷增長時(shí)，桶內(nèi)的頁塊數(shù)也隨之增多n 由于分布不均勻，有些桶內(nèi)頁塊數(shù)可能過多，嚴(yán)重影響檢索效率n 必要時(shí)需對(duì)文件進(jìn)行重新組織n 改變散列函數(shù)n 增加桶目錄表的大小張銘ÓPage80信息學(xué)院編寫所有，或9.3.3直接閉

40、散列方法在散列表中。n 把所有n 每個(gè)關(guān)鍵碼有一個(gè)基位置即h(key)，即由散列函數(shù)計(jì)算出來的地址n 如果要一個(gè)關(guān)鍵碼，而另一個(gè)記錄已經(jīng)占據(jù)了R的基位置(發(fā)生碰撞)，n 那么就把R在表中的其它地址內(nèi)，由解決策略確定是哪個(gè)地址張銘ÓPage 81信息學(xué)院編寫所有，或閉散列表解決的基本思想n 當(dāng)發(fā)生時(shí)，使用某種方法為關(guān)鍵碼K生成一個(gè)散列地址序列d0，d1，d2，. di ，.dm-1n 其中d0=h（K）稱為K的基地址地置n 所有di(0<i<m)是后繼散列地址n 形成探查的方法不同，所得到的解決沖突的方法也不同張銘ÓPage 82信息學(xué)院編寫所有，或閉散列表解決的

41、基本思想（續(xù)）K時(shí)，若基地址上的結(jié)點(diǎn)n 當(dāng)已被別的數(shù)據(jù)元素占用n 則按上述地址序列依次探查，將找到的第一個(gè)開放的空閑位置di作為K的位置n 若所有后繼散列地址都不空閑， 說明該閉散列表已滿，報(bào)告溢出張銘ÓPage 83信息學(xué)院編寫所有，或檢索過程n 檢索時(shí)也要像的策略時(shí)一樣遵循同樣n 重復(fù)解決過程n 找出在基位置沒有找到的張銘ÓPage 84信息學(xué)院編寫所有，或探查序列和檢索函數(shù)都假定每個(gè)關(guān)鍵碼的探查序列中至少有一個(gè)是空的位置n 否則可能會(huì)進(jìn)入一個(gè)無限循環(huán)中n 也可以限制探查序列長度張銘ÓPage85信息學(xué)院編寫所有，或幾種常見的閉散列方法線性探查二次探查偽隨機(jī)數(shù)

42、序列探查雙散列探查法n 1.n 2.n 3.n 4.張銘ÓPage 86信息學(xué)院編寫所有，或1.線性探查n 基本思想：n 如果的基位置位置被占用，那么就在表中下移，直到找到一個(gè)空位置。n 依次探查下述地址單元：d+1，d+2，M-1，0，1，.，d-1n 用于簡單線性探查的探查函數(shù)是：p(K，i) = in 線性探查的優(yōu)點(diǎn)n 表中所有的的候選位置位置都可以作為新張銘ÓPage 87信息學(xué)院編寫所有，或可能產(chǎn)生的問題”（clustering，或稱為n “堆積”）n 散列地址不同的結(jié)點(diǎn)，爭奪同一后繼散列地址n 小的可能匯大的n 導(dǎo)致很長的探查序列張銘ÓPage88信息

43、學(xué)院編寫所有，或散列表示例n M = 15,h(key) = key%13n 在理想情況下，表中的每個(gè)空槽都應(yīng)該有相同的機(jī)會(huì)接收下一個(gè)要的放在第11個(gè)槽中的概率是2/15n 下一條n 放到第7個(gè)槽中的概率是11/張銘ÓPage 89信息學(xué)院編寫所有，或改進(jìn)線性探查n 每次跳過常數(shù)c個(gè)而不是1個(gè)槽n 探查序列中的第i個(gè)槽是(h(K) +ic) mod Mn 基位置相鄰的 一個(gè)探查序列了就進(jìn)入同n 探查函數(shù)是p(K，i) = i*cn 必須使常數(shù)c與M互素張銘ÓPage90信息學(xué)院編寫所有，或例：改進(jìn)線性探查n 例如，c = 2，要關(guān)鍵碼k1和k2，h(k1) = 3，h(k2) = 5n 探查序列n k1的探查序列是3、5、7、9、.n k2的探查序列就是5、7、9、.n k1和k2的探查序列還是