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