字典的散列表示

1、1 1 第十講字典的散列表示第十講字典的散列表示 12 2n普通高等教育普通高等教育“十一五十一五”國家級規(guī)劃教材國家級規(guī)劃教材普通高等教育精品教材普通高等教育精品教材算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu) C語言描述語言描述（第（第2版）版） 張乃孝張乃孝 編著編著, , 高等教育出版社高等教育出版社 2008.2008.第第6 6章章 集合與字典（集合與字典（6.56.5）參考.（外存數(shù)據(jù)的組織）n普通高等教育普通高等教育“十一五十一五”國家級規(guī)劃教材配套參考書國家級規(guī)劃教材配套參考書算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)（第（第2 2版）學(xué)習(xí)指導(dǎo)與習(xí)題解析版）學(xué)習(xí)指導(dǎo)與習(xí)題解析 張乃孝張乃孝 編著編著, ,

2、 高等教育出版社高等教育出版社 2009.2009.36.5 字典的散列表示n動機:n如果關(guān)鍵碼是存儲字典元素的數(shù)組下標(biāo), 則可以直接找到字典元素!n關(guān)鍵碼未必總是整數(shù)!nWindows 序列號n關(guān)鍵碼即使是整數(shù),也未必適合做數(shù)組下標(biāo)!n北大學(xué)生學(xué)號n如何建立從關(guān)鍵碼集合到適當(dāng)整數(shù)集合的映射, 把數(shù)據(jù)存放在映射值對應(yīng)的位置.散列表示!46.5.1基本概念n散列法散列法(Hashing), 也稱為雜湊法雜湊法或關(guān)鍵碼關(guān)鍵碼- -地址轉(zhuǎn)換法地址轉(zhuǎn)換法.關(guān)鍵碼 key 散列地址 h(key) 散列函數(shù) h碰撞碰撞: 如果 key1key2, 而h(key1)=h(key2).發(fā)生碰撞的關(guān)鍵碼稱為同義

3、詞同義詞.散列函數(shù)h的值域應(yīng)該是可以使用的整個地址空間,稱為基本區(qū)域基本區(qū)域.負載因子負載因子:字典中結(jié)點數(shù)目基本區(qū)域能容納的結(jié)點數(shù)目散列表散列表: 采用散列法表示的字典.5設(shè)計散列表示n主要關(guān)注兩個問題:n散列函數(shù)的選擇n使得散列地址的分布盡可能均勻.n理想的負載因子0.5.n碰撞的處理n依據(jù)存儲條件, 同義詞可以存放在基本區(qū)域中未被占用的單元;n也可以在基本區(qū)域以外另開辟區(qū)域,例如1時. 66.5.2 散列函數(shù)n不存在一種普遍適用的最佳的散列函數(shù)!n具體問題具體設(shè)計!n常用設(shè)計方法n數(shù)字分析法n折疊法n中平方法n基數(shù)轉(zhuǎn)換法n除余法對于非整數(shù)關(guān)鍵碼,常見的方式是先設(shè)計一種方式把它轉(zhuǎn)換到整數(shù),

4、而后再用整數(shù)散列的方法.7數(shù)字分析法n如果關(guān)鍵碼位數(shù)比基本區(qū)的地址碼位數(shù)多,丟掉分布不均勻的位留下均勻的位作為地址.n例如: key h(key) 000319426 326326 000718309 709709 000629443 643643 000758615 715715n過分依賴于關(guān)鍵碼集合,通常適合靜態(tài)的字典.8折疊法n如果關(guān)鍵碼位數(shù)比地址碼位數(shù)多,且分布比較均勻,則將關(guān)鍵碼從某些地方斷開,分為幾部分,以幾部分的疊加和(舍棄進位)作為地址.n例如: key =58242224158|2422|24158|2422|241移位折疊相加移位相加85142242210641064158

5、2412422272127219中平方法n先求出關(guān)鍵碼的平方, 然后取中間幾位作為地址.n例如: key = 4731, 47312=22382361, h(4731)=382382.10基數(shù)轉(zhuǎn)換法n把關(guān)鍵碼看成基數(shù)為r1的數(shù),將它轉(zhuǎn)換成基數(shù)為r2的數(shù), 用數(shù)字分析法取中間幾位作為散列地址.nr1和r2互素.n例 key =236075, r1=13, r2=10, (236075)1313= 2135+3134+6133+713+5 = (841547)1010 h(key) = 4154415411除余法n關(guān)鍵碼除以某個不大于基本區(qū)域大小(m)的數(shù)p后的余數(shù)為散列地址, 即 h(key)=

6、(int)key%p;n數(shù) p 一般選素數(shù).n 常用素數(shù):nm = 128, 256, 512, 1024, np選擇 127, 251, 503, 1019.n除余法使用最廣,常用于動態(tài)字典和關(guān)鍵碼沒有規(guī)律出現(xiàn)的情況.n也可以用于將其他散列函數(shù)得到值歸縮到所需基本區(qū)域.12散列函數(shù)選取的原則n一般而言，散列函數(shù)的選取應(yīng)根據(jù)具體問題具體分析的原則，針對具體字典元素關(guān)鍵碼集合的特性，加上空間、時間的條件，去構(gòu)造相對理想的散列函數(shù)。n散列函數(shù)計算出的地址應(yīng)該盡可能均勻地分布在希望的地址空間中。n散列函數(shù)應(yīng)該盡可能簡單,以提高關(guān)鍵碼到地址的轉(zhuǎn)換速度 。136.5.3 碰撞的處理n散列表的插入和檢索都

7、要考慮對碰撞的處理.n如果以h(key)為地址的空間未被占用:n執(zhí)行檢索, 檢索失敗;n執(zhí)行插入, 將元素存入該存儲空間.n如果以h(key)為地址的空間已被占用:n執(zhí)行檢索,則需要檢查已經(jīng)存放的元素(甚至同義詞)是否是需要檢索的元素;n檢查同義詞需要知道處理碰撞的方法n如果執(zhí)行插入, 發(fā)生碰撞.n涉及對同義詞的處理.n碰撞處理方法:n開地址法n拉鏈法14開地址法n基本想法：n出現(xiàn)沖突時元素?zé)o法保存在散列函數(shù)確定的位置,需設(shè)法為它在基本區(qū)域內(nèi)基本區(qū)域內(nèi)另外安排一個位置.n采用探查方式探查方式作為系統(tǒng)化的位置安排方式.l 開地址法解決碰撞：在基本區(qū)域內(nèi)形成一個同義詞的探測序列,沿著探測序列逐個查

8、找,直到滿足下列條件為止:l找到查找的元素(檢索成功), 后者l碰到一個未被占用的地址(可以插入同義詞或者檢索失敗).顯然基本區(qū)域的負載因子必須小于1.15線性探查與雙散列探查n基本區(qū)域內(nèi)的一個探查序列探查序列:Hi= (h(key)+di)%m, 其中:m為表長, di為增量序列, i=1,2, ,k (km-1).n如果增量序列滿足:di=i, 則為線性探查序列線性探查序列.n如果增量序列滿足:di=i h2 (key) 則為雙散列探查序列雙散列探查序列.16n對關(guān)鍵碼集合 K=18,73,10,5,68,99,22,32,46,58,25, n我們?nèi)(key)=key%13, 則 h(

9、18)=5(18)=5, h(73)=8(73)=8, h(10)=10, h(5)=5(5)=5, h(68)=3, h(99)=8(99)=8, h(22)=9, h(32)=6(32)=6, h(46)=7, h(58)=6(58)=6, h(25)=12.散列地址關(guān)鍵碼01234567891012115825681853273991046225992232465825l 從例子中看到線性探測容易出現(xiàn)堆積堆積現(xiàn)象,即在處理同義詞的過程中又添加了非同義詞沖突(其他探查法也可能有類似情況)線性探查序列17雙散列函數(shù)探查序列n對關(guān)鍵碼集合 K=18,10,73,7, n我們?nèi)(key)=ke

10、y%5, h2 (key) =key%3+1,則 h(18)=3, h(10)=0, h(73)=3, h(7)=2; h2 (18)=1, h2 (10)=2, h2 (73)=2, h2 (7)=2.散列地址關(guān)鍵碼0123410731877373718開地址法散列表上的檢索n對給定key值： (1)根據(jù)散列函數(shù)求出散列地址; (2)若該位置無記錄,則檢索失敗結(jié)束; (3)否則比較元素關(guān)鍵碼,若與 key 相等則檢索成功結(jié)束; (4)否則根據(jù)本散列表設(shè)計的沖突處理方法找出“下一地址”, 回到步驟(2) 用這個位置檢查.散列地址關(guān)鍵碼012341073187l 對關(guān)鍵碼集合K=18,10,73

11、,7, l 我們?nèi)(key)=key%5, h2 (key) =key%3+1,則 h(18)=3, h(10)=0, h(73)=3, h(7)=2; h2 (18)=1, h2 (10)=2, h2 (73)=2, h2 (7)=2.l 檢索關(guān)鍵碼73.19開地址法散列表的實現(xiàn)n存儲結(jié)構(gòu)n實現(xiàn)算法n算法 6.13 創(chuàng)建空散列表n與算法2.1類似, 用m(基本區(qū)域長度)代替MAXNUM;n假定有效的關(guān)鍵碼值都大于0, 因此創(chuàng)建空字典的時候都用0初始化關(guān)鍵碼.n算法6.14 散列表的檢索算法用線性探查法解決碰撞;n算法6.15 散列表的插入算法用線性探查法解決碰撞.20存儲結(jié)構(gòu)typedef

12、 int KeyType;typedef int DataType;typedef struct KeyType key; /* 字典元素的關(guān)鍵碼字段*/ DataType value; /* 字典元素的屬性字段*/ DicElement;typedef struct int m; /* m為基本區(qū)域長度 */ DicElement *elements; HashDictionary;typedef HashDictionary *PHashDictionary; 21算法6.14 散列表的檢索算法intint linearSearchlinearSearch( (HashDictionary

13、HashDictionary * *phashphash, , KeyTypeKeyType key, key, intint * *position) position) intint d = h(key), inc; / d = h(key), inc; /* * 設(shè)設(shè) h h 為散列函數(shù)為散列函數(shù) * */ / for (inc = 0; inc for (inc = 0; inc m; inc+) -m; inc+) if ( if (phashphash-elementsd.key = key) -elementsd.key = key) * *position = d; retur

14、n 1; /position = d; return 1; /* * 檢索成功檢索成功 * */ / else if ( else if (phashphash-elementsd.key = null) -elementsd.key = null) * *position = d; return 0; /position = d; return 0; /* * 檢索失敗，找到空位置檢索失敗，找到空位置 * */ / d = (d+1) % d = (d+1) % phashphash-m;-m; * *position = -1; /position = -1; /* * 散列表溢出散列表溢

15、出 * */ / return 0; return 0; 22算法6.15 散列表的插入算法n首先調(diào)用檢索算法, 如果檢索失敗, 再根據(jù)提供的位置信息將元素ele插入.int linearInsert(HashDictionary int linearInsert(HashDictionary * *phash, DicElement ele) phash, DicElement ele) int position; if (linearSearch(phash, key, &position) =1) printf(Key exists n); /* 已有關(guān)鍵碼為key的結(jié)點*/ else

16、if (position != -1) /*插入結(jié)點*/ phash-elementsposition =ele ; else return 0; /* 散列表溢出 */ return 1;23關(guān)于開地址法的討論n對于用開地址法構(gòu)造的散列表, 刪除結(jié)點時不能簡單地將要刪除的結(jié)點空間置為0;n這會引起檢索方面的問題.n怎么處理?!散列地址關(guān)鍵碼012341073187散列地址關(guān)鍵碼01234073187檢索檢索7373失敗失敗24拉鏈法n基本思想：n元素存在基本區(qū)域之外;n為每個關(guān)鍵碼建立一個鏈接表,所有關(guān)鍵字為同義詞的記錄存儲在同一個鏈表中.n所有元素可以統(tǒng)一處理(無論是否沖突).n允許任意的

17、負載因子.n最簡單的方法是把新元素插在鏈接表頭.n如果要防止出現(xiàn)重復(fù)關(guān)鍵碼，就需要檢查整個鏈表拉鏈法舉例25對關(guān)鍵碼集合對關(guān)鍵碼集合K=18,10,73,7, K=18,10,73,7, 取取h(key)=key%5,(key)=key%5,則則 h(18)=3, (18)=3, h(10)=0, (10)=0, h(73)=3, (73)=3, h(7)=2.(7)=2.用拉鏈法解決碰撞用拉鏈法解決碰撞26關(guān)于拉鏈法討論n拉鏈法的實現(xiàn)比較清楚：在單鏈表上檢索、插入、刪除。n每個同義詞子表的平均長度為n/m, 其中n為關(guān)鍵碼個數(shù), m為基本區(qū)域長度.nnm, 則一定存在若干空表;n一般設(shè)計為

18、1n/m10 .n各鏈接表上的結(jié)點動態(tài)申請, 適合構(gòu)造散列表前無法確定表長的情況;n不會造成堆積現(xiàn)象, 結(jié)點的刪除比較方便.276.5.4 散列文件n散列文件散列文件是存在外存的大型字典結(jié)構(gòu),把散列的思想用于文件:n將散列函數(shù)作用到記錄的關(guān)鍵碼,確定記錄在外存的存儲地址n處理沖突常用適合外存分塊存取的拉鏈法拉鏈法28補充介紹補充介紹與大型字典相關(guān)的概念與大型字典相關(guān)的概念外存與文件外存與文件 外存儲器磁盤結(jié)構(gòu) n磁盤類似于多碟的磁盤類似于多碟的CD，若干盤片（比如，若干盤片（比如4片）串在一根主軸片）串在一根主軸上形成一個盤組，當(dāng)主軸旋轉(zhuǎn)時帶動各個盤片旋轉(zhuǎn)。每個盤上形成一個盤組，當(dāng)主軸旋轉(zhuǎn)時帶

19、動各個盤片旋轉(zhuǎn)。每個盤面上包含大小不同的許多同心圓。面上包含大小不同的許多同心圓。n每個圓圈稱為一個每個圓圈稱為一個磁道磁道，各個盤面的半徑相同的磁道合在一，各個盤面的半徑相同的磁道合在一起構(gòu)成一個起構(gòu)成一個柱面柱面。n一個磁道又可分為若干段，每段是一個一個磁道又可分為若干段，每段是一個頁塊頁塊（物理記錄）。（物理記錄）。n一個盤組上從大到小的一個盤組上從大到小的存儲地址為：柱面、磁道和頁塊存儲地址為：柱面、磁道和頁塊。29在磁盤上讀寫信息在磁盤上讀寫信息選定柱面，這是機械動作，所以比較慢。選定柱面，這是機械動作，所以比較慢。選定磁道，由電子線路實現(xiàn)，所以比較快。選定磁道，由電子線路實現(xiàn)，所以

20、比較快。找物理記錄，這是機械動作，較慢。找物理記錄，這是機械動作，較慢。n實際讀寫信息的時間比定位時間少得多，訪問磁盤中的數(shù)據(jù)實際讀寫信息的時間比定位時間少得多，訪問磁盤中的數(shù)據(jù)比訪問內(nèi)存慢比訪問內(nèi)存慢56個數(shù)量級。個數(shù)量級。主機對外存儲器上的數(shù)據(jù)主機對外存儲器上的數(shù)據(jù)必須按頁塊頁塊存?。ú荒苤苯影醋只蛘撸ú荒苤苯影醋只蛘咦止?jié)存?。┳止?jié)存?。?。n頁塊頁塊是內(nèi)存與外存進行交換的物理單位物理單位30緩沖區(qū)與訪外緩沖區(qū)與訪外讀外存上的數(shù)據(jù)讀外存上的數(shù)據(jù):1,把外存上一個或者多個物理記錄讀到內(nèi)存的指定的區(qū)域（緩沖區(qū)）緩沖區(qū)）。2,在緩沖區(qū)中找到需要的邏輯記錄進行處理。n寫的過程則相反寫的過程則相反，先

21、寫到緩沖區(qū)中，然后通過主機與外存的接口，把緩沖區(qū)中的數(shù)據(jù)寫到外存儲器的物理記錄中。一次讀寫過程，通常稱為一次一次讀寫過程，通常稱為一次訪外訪外。提高外存的存取時間的關(guān)鍵在于減少訪外的次數(shù)。提高外存的存取時間的關(guān)鍵在于減少訪外的次數(shù)。31文件與邏輯記錄文件與邏輯記錄n文件文件通常指存儲在外存的數(shù)據(jù)，是邏輯記錄的集合。通常指存儲在外存的數(shù)據(jù)，是邏輯記錄的集合。n邏輯記錄（邏輯記錄（簡稱記錄）記錄）是應(yīng)用程序需要進行內(nèi)外存交換的邏輯單位。n每個記錄可以包含若干數(shù)據(jù)項數(shù)據(jù)項，n其中能夠唯一標(biāo)識該記錄的數(shù)據(jù)項稱為關(guān)鍵碼關(guān)鍵碼。n邏輯記錄在外存儲器上的地址由兩部分組成：邏輯記錄在外存儲器上的地址由兩部分組

22、成： 邏輯記錄所在物理記錄的地址；邏輯記錄所在物理記錄的地址； 邏輯記錄在物理記錄內(nèi)的相對位置。邏輯記錄在物理記錄內(nèi)的相對位置。 由于緩沖區(qū)的大小受到內(nèi)存容量的限制，所以減少訪外次數(shù)由于緩沖區(qū)的大小受到內(nèi)存容量的限制，所以減少訪外次數(shù)的有效方法是精心設(shè)計文件的結(jié)構(gòu)，使外存中存放的記錄，的有效方法是精心設(shè)計文件的結(jié)構(gòu)，使外存中存放的記錄，相互關(guān)聯(lián)，以便于成批處理。相互關(guān)聯(lián)，以便于成批處理。3233按桶散列的文件n桶桶: 拉鏈法中存放同義詞的表. n這里桶是由0個或多個外存的頁塊通過指針的鏈接而構(gòu)成.n實現(xiàn)散列文件的常見方法就是按桶散列按桶散列: :n只是這里存儲桶里的一個鏈表結(jié)點對應(yīng)于外存的一個

23、頁塊,各種鏈接都直接采用外存的頁塊地址.n檢索和插入、刪除操作中涉及到訪問外存.n桶目錄表是一些指針的序列, 通常存儲在內(nèi)存中,每個指針指向一個桶的首頁塊. 桶目錄表桶的頁塊按桶散列的文件34首先計算（首先計算（key）；）；設(shè)（設(shè)（key），查閱桶目錄表的第項，得到第），查閱桶目錄表的第項，得到第個桶的首頁塊地址，讀入首頁塊，在塊上進行順個桶的首頁塊地址，讀入首頁塊，在塊上進行順序查找；序查找；找到關(guān)鍵碼為找到關(guān)鍵碼為key的記錄則結(jié)束，否則根據(jù)塊之間的的記錄則結(jié)束，否則根據(jù)塊之間的鏈指針讀入下一塊，繼續(xù)查找；鏈指針讀入下一塊，繼續(xù)查找；直到找到或者找遍全桶時結(jié)束。直到找到或者找遍全桶時結(jié)束。 檢索檢索：查找關(guān)鍵碼值為key的記錄35 先按上述方法進行查找；先按上述方法進行查找；找到時，說明本次插入是錯誤的或多余的；找到時，說明本次插入是錯誤的或多余的；若找不到若找不到(則此時讀到內(nèi)存中的頁塊恰好是新記錄應(yīng)插入的則此時讀到內(nèi)存中的頁塊恰好是新記錄應(yīng)插入的桶的最后一塊桶的最后一塊),在這個頁塊的空位置上填入新記錄，并寫在這個頁塊的空位置上填入新記錄，并寫回外存；回外存；如果此頁塊已滿，則申請一個新頁塊，其地址填入前一塊如果此頁塊已滿，則申請一個新頁塊，其地址填入前一塊的指針位置的指針