【文章內(nèi)容簡介】 25 26 27 … … 人數(shù) 300 2022 5000 … 1050 … … … … 表 直接定址哈希函數(shù)例子一 其中，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身。若要詢問 25歲的人有 多少，則只要查表的第 25項(xiàng)即可。 例二：有一個解放后出生的人口調(diào)查表。 地址 01 02 03 … 22 … 年份 1949 1950 1951 … 1970 … 人數(shù) … … … … 15000 … 其中，關(guān)鍵字是年份，哈希函數(shù)取關(guān)鍵字加一常數(shù)： H(key) = key + (－ 1948)。 若要查 1970年出生的人，則只要查第 (1970－ 1948)＝ 22項(xiàng)即可。 表 直接定址哈希函數(shù)例子二 （ 2）數(shù)字分析法 主要思想 ：假設(shè)關(guān)鍵字是以 r為基的數(shù)（如：以10為基的十進(jìn)制數(shù)），并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干位組成哈希地址。 例如，有 80個記錄，其關(guān)鍵字為 8位十進(jìn)制數(shù)。假設(shè)哈希表的表長為 10010，則 可取兩位十進(jìn)制數(shù)組成哈希地址。這兩位的取法，原則是使得到的哈希地址盡量避免產(chǎn)生沖突 。假設(shè)這 80個關(guān)鍵字中的一部分如下所列： 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 5 4 1 5 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 對關(guān)鍵字全體的分析：第 ①② 位都是“ 8 1”，第 ③ 位只可能取 3或 4，第 ⑧ 位只可能取 5或 7，因此這 4位都不可取。由于中間 4位可看成是近乎隨機(jī)的，因此可取其中任意兩位，或取其中兩位與另兩位的疊加求和后舍去進(jìn)位作為哈希地址。 2．例子 假設(shè) BASIC語言中允許的標(biāo)識符為一個字母，或一個字母和一個數(shù)字。在計算機(jī)內(nèi)可用兩位八進(jìn)制數(shù)表示字母和數(shù)字 . 如圖 (a)所示。取表示符在計算機(jī)中的八進(jìn)制數(shù)為它的關(guān)鍵字。 A B C … Z 0 1 2 … 9 01 02 03 … 32 60 61 62 … 71 （ 3）平方取中法 1．定義 取關(guān)鍵字平方后的中間幾位為哈希地址 。取的位數(shù)由表長決定。 (a) 字符的八進(jìn)制表示對照表 2．例子 假設(shè)表長為 512＝ 29，則 可取關(guān)鍵字平方后的中間 9位二進(jìn)制數(shù)為哈希地址 。例如，圖 (b)列出了一些標(biāo)識符及它們的哈希地址。 A 0100 0 010000 000 I 1100 1 210000 210 J 1200 1 440000 440 I0 1160 1 370400 370 P1 2061 4 310541 310 P2 2062 4 314704 314 Q1 2161 4 734741 734 Q2 2162 4 741304 741 Q3 2163 4 745651 745 記錄 關(guān)鍵字 (關(guān)鍵字 )2 哈希地址 (217~29) (b) 標(biāo)識符及其哈希地址 圖 （ 4）折疊法 折疊法 （ folding）：將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址。 移位疊加 ：將分割后的每一部分的最低位對齊，然后相加。 間界疊加 ：從一端向另一端沿分割界來回折疊，然后對齊相加。 使用前提 : 關(guān)鍵字位數(shù)很多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻時。 （ 4）折疊法 3．例子 例如，每一種西文圖書館都有一個國際標(biāo)準(zhǔn)圖書編號（ ISBN）， 如國際標(biāo)準(zhǔn)圖書館圖書編號 0442205864的哈希地址分別如圖 (a)和 (b)所示。 5864 5864 4220 0224 ＋ ) 04 ＋ ) 04 10088 6092 H(key) = 0088 H(key) = 6092 (a) 移位疊加 (b) 間界疊加 圖 由折疊法求得哈希地址 ? (5)除留余數(shù)法 ? 構(gòu)造：取關(guān)鍵字被某個不大于哈希表表長 m的數(shù) p除后所得余數(shù)作哈希地址，即H(key)=key MOD p， p?m ? 特點(diǎn) ? 簡單、常用，可與上述幾種方法結(jié)合使用 ? p的選取很重要； p選的不好，容易產(chǎn)生同義詞 ? (6)隨機(jī)數(shù)法 ? 構(gòu)造：取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址，即 H(key)=random(key) ? 適于關(guān)鍵字長度不等的情況 ￡ 處理沖突的方法 沖突 ：指由關(guān)鍵字得到的哈希地址的位置上已存在記錄。 處理沖突 ：為產(chǎn)生沖突的關(guān)鍵字的記錄找到另一個“空”的哈希地址。 ? 開放定址法 ? 方法： 當(dāng)沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即 Hi=(H(key)+di)MOD m，i=1,2,……k(k ?m1) 其中： H(key)—— 哈希函數(shù) m—— 哈希表表長 di—— 增量序列 ? 分類 ? 線性探測再散列： di=1,2,3,……m 1 ? 二次探測再散列： di=1178。,1178。,2178。,2178。,3178。,…… 177。 k178。(k?m/2) ? 偽隨機(jī)探測再散列： di=偽隨機(jī)數(shù)序列 例 表長為 11的哈希表中已填有關(guān)鍵字為 17， 60， 29的記錄， H(key)=key MOD 11,現(xiàn)有第 4個記錄，其關(guān)鍵字為 38， 按三種處理沖突的方法，將它填入表中 0 1 2 3 4 5 6 7 8 9 10 60 17 29 (1) H(38)=38 MOD 11=5 沖突 H1=(5+1) MOD 11=6 沖突 H2=(5+2) MOD 11=7 沖突 H3=(5+3) MOD 11=8 不沖突 38 (2) H(38)=38 MOD 11=5 沖突 H1=(5+1178。) MOD 11=6 沖突 H2=(51178。) MOD 11=4 不沖突 38 (3) H(38)=38 MOD 11=5 沖突 設(shè)偽隨機(jī)數(shù)序列為 9，則： H1=(5+9) MOD 11=3 不沖突 38 ? 再哈希法 ? 方法：構(gòu)造若干個哈希函數(shù)，當(dāng)發(fā)生沖突時，計算下一個哈希地址，即： Hi=Rhi(key) i=1,2,……k 其中： Rhi—— 不同的哈希函數(shù) ? 特點(diǎn)：計算時間增加 ? 鏈地址法 ? 方法：將所有關(guān)鍵字為同義詞的記錄存儲在一個單鏈表中，并用一維數(shù)組存放頭指針 建立一個公共溢出區(qū) 另設(shè)立向量為 溢出表 。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。 例 已知一組關(guān)鍵字 (19,14,23,1,68,20,84,27,55,11,10,79) 哈希函數(shù)為： H(key)=key MOD 13, 用鏈地址法處理沖突 0 1 2 3 4 5 6 7 8 9 10 11 12 14 ^ 1 27 79 68 55 19 84 20 23 10 11 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ￡ 哈希表的查找及其分析 （ 1）相關(guān)術(shù)語 查找過程 ： (1) 給定 K值，根據(jù)造表時設(shè)定的哈希函數(shù)求得哈希地址， 若表中此位置上沒有記錄，則查找不成功 ； (2) 否則比較關(guān)鍵字，若和給定值相等，則查找成功； (3) 否則根據(jù)造表時設(shè)定的處理沖突的方法找“下 一地址”，直至哈希表中某個位置為“空”或者表中所填記錄的關(guān)鍵字等于給定值為止。 ￡ 哈希表的查找及其分析 （ 1）相關(guān)術(shù)語 影響查找過程中需和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)的因素 (p260)： 1．哈希函數(shù) 2．沖突處理方法 3．哈希表的裝填因子 裝填因子 ： 哈希表的長度表中填入的記錄數(shù)??其中， α標(biāo)志哈希表的裝滿程度。 直觀的看， α越小，發(fā)生沖突的可能性就越??；反之， α越大，表中已填入的記錄越多，再填記錄時，發(fā)生沖突的可能性就越大，則查找時，給定值需與之進(jìn)行比較的關(guān)鍵字的個數(shù)也就越多。 例 已知一組關(guān)鍵字 (19,14,23,1,68,20,84,27,55,11,10,79) 哈希函數(shù)為： H(key)=key MOD 13, 哈希表長為 m=16， 設(shè)每個記錄的查找概率相等 (1) 用線性探測再散列處理沖突，即 Hi=(H(key)+di) MOD m H(55)=3 沖突， H1=(3+1)MOD16=4 沖突， H2=(3+2)MOD16=5 H(79)=1 沖突， H1=(1+1)MOD16=2 沖突， H2=(1+2)MOD16=3 沖突， H3=(1+3)MOD16=4 沖突， H4=(1+4)MOD16=5 沖突， H5=(1+5)MOD16=6 沖突， H6=(1+6)MOD16=7 沖突， H7=(1+7)MOD16=8 沖突， H8=(1+8)MOD16=9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ASL=(1*6+2+3*3+4+9)/12= 14 1 68 27 55 19 20 84 79 23 11 10 H(19)=6 H(14)=1 H(23)=10 H(1)=1 沖突， H1=(1+1) MOD16=2 H(68)=3 H(20)=7 H(84)=6 沖突， H1=(6+1)MOD16=7 沖突， H2=(6+2)MOD16=8 H(27)=1 沖突， H1=(1+1)MOD16=2 沖突， H2=(1+2)MOD16=3 沖突， H3=(1+3)MOD16=4 H(11)=11 H(10)=10 沖突， H1=(10+1)MOD16=11 沖突， H2=(10+2)MO