牛小飛《數(shù)據(jù)結(jié)構(gòu)》5散列表

1、散列表 散列函數(shù)的構(gòu)造方法 處理沖突的方法 散列表的查找算法 散列表的查找分析 小結(jié)和作業(yè) 課堂練習(xí) 散列的基本思想 散列的基本思想 已講查找表的共同特點(diǎn)：記錄在表中的位置和它 的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系； 查找的過(guò)程為給定值依次和關(guān)鍵字集合中各個(gè)關(guān) 鍵字進(jìn)行比較； 查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè) 數(shù)。 用這類(lèi)方法表示的查找表，其平均查找長(zhǎng)度都 不為零 不同的表示方法，其差別僅在于： 關(guān)鍵字和給定值進(jìn)行比較的順序不同。 散列的基本思想 如果預(yù)先知道所查關(guān)鍵字在表中的位置， 就可以實(shí)現(xiàn)。 對(duì)于頻繁使用的查找表，希望ASL = 0。 只要記錄在表中位置和其關(guān)鍵字之間存在 一種確定

2、的關(guān)系。 散列的基本思想 若以下標(biāo)為000 999 的順序表來(lái)表示。 例如：為每年招收的1000名新生建立一張查找表， 其關(guān)鍵字為學(xué)號(hào)，其值的范圍為xx000 xx999 (前 兩位為年份)。 則查找過(guò)程可以簡(jiǎn)單進(jìn)行：取給定值（學(xué)號(hào)）的 后三位，不需要經(jīng)過(guò)比較便可直接從順序表中找 到待查關(guān)鍵字。 散列的基本思想 散列的基本思想 因此在一般情況下，需在關(guān)鍵字與記錄在表中的 存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)系，以 f(key) 作 為關(guān)鍵字為 key 的記錄在表中的位置，通常稱(chēng) 這個(gè)函數(shù) f(key) 為哈希函數(shù)。 Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei

3、例：對(duì)于如下9個(gè)關(guān)鍵字 設(shè) 散列函數(shù) f(key) = (Ord(第一個(gè)字母)/2 散列的基本思想舉例 字 母 ABCDEFGHIJKLM 序 號(hào) 12345678910111213 字 母 NOPQRSTUVWXYZ 序 號(hào) 14151617181920212223242526 ChenZhaoQian SunLiWuHanYeDei 序號(hào) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 問(wèn)題: 若添加關(guān)鍵字Zhou , 怎么辦？ Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei 由此可見(jiàn)， 1) 散列(Hash)函數(shù)是一個(gè)將關(guān)鍵字的集合

4、映射 到某個(gè)地址集合上，它的設(shè)置很靈活，只要這個(gè) 地址集合的大小不超出允許范圍即可； 2) 對(duì)不同的關(guān)鍵字可能得到同一散列地址，即： key1 key2，而 f(key1) = f(key2),因此，很 容易產(chǎn)生“沖突”現(xiàn)象； 散列的基本思想結(jié)論 3) 很難找到一個(gè)不產(chǎn)生沖突的散列函數(shù)。一般 情況下，只能選擇恰當(dāng)?shù)纳⒘泻瘮?shù)，使沖突盡可 能少地產(chǎn)生。 因此，在構(gòu)造這種特殊的“查找表” 時(shí)，除 了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的散 列函數(shù)之外；還需要找到一種“處理沖突” 的方 法。 散列的基本思想結(jié)論 根據(jù)設(shè)定的散列函數(shù) H(key) 和所選中的處理沖突的 方法，將一組關(guān)鍵字映象到一個(gè)有限

5、的、地址連續(xù)的 地址集 (區(qū)間) 上，并以關(guān)鍵字在地址集中的“象” 作為相應(yīng)記錄在表中的存儲(chǔ)位置，如此構(gòu)造所得的查 找表稱(chēng)之為“散列表”。 這一過(guò)程稱(chēng)為散列造表或者散列，所得的存儲(chǔ)位置成 為散列地址或者哈希地址。 散列的基本思想定義 散列函數(shù)的構(gòu)造方法 對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法: 若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。 1. 直接定址法 3. 平方取中法 5. 除留余數(shù)法 4. 折疊法 6. 隨機(jī)數(shù)法 2. 數(shù)字分析法 散列函數(shù)為關(guān)鍵字的線性函數(shù) H(key) = key 或者 H(key) = a key + b 1. 直接定址法 散列函數(shù)的構(gòu)造方法 散列函數(shù)的構(gòu)造方法 2. 數(shù)

6、字分析法 假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由 s 位數(shù)字組 成 (u1, u2, , us)，分析關(guān)鍵字集中的全體， 并從 中提取分布均勻的若干位或它們的組合作為地址。 此方法僅適合于： 能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字 出現(xiàn)的頻度。 散列函數(shù)的構(gòu)造方法 有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，散列地址為 2位十進(jìn)制數(shù) 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 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 6 8 5 3 7 8 1 4 1 9 3 5 5 . . 分析： 只

7、取8 只取1 只取3、4 只取2、7、5 數(shù)字分布近乎隨機(jī) 所以：取任意兩位或兩位 與另兩位的疊加作散列地址 散列函數(shù)的構(gòu)造方法 以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān) 鍵字的平方值”的目的是“擴(kuò)大差別”，同時(shí)平方值 的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。 3. 平方取中法 此方法適合于: 關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度 很高的現(xiàn)象。 散列函數(shù)的構(gòu)造方法 4. 折疊法 將關(guān)鍵字分割成若干部分，然后取它們的疊加和為散列 地址。有兩種疊加處理的方法：移位疊加和間界疊加。 此方法適合于: 關(guān)鍵字的數(shù)字位數(shù)特別多，而且關(guān)鍵字在每一位上 的數(shù)字分布大致均勻的情況。 散列函數(shù)的構(gòu)造方

8、法 例 關(guān)鍵字為 ：0442205864，散列地址位數(shù)為4 5 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088 移位疊加 5 8 6 4 0 2 2 4 0 4 6 0 9 2 H(key)=6092 間界疊加 4. 折疊法 散列函數(shù)的構(gòu)造方法 5. 除留余數(shù)法 設(shè)定散列函數(shù)為: H(key) = key MOD p 其中， pm (表長(zhǎng)) 并且 p 應(yīng)為不大于 m 的素?cái)?shù) 或是 不含 20 以下的質(zhì)因子 散列函數(shù)的構(gòu)造方法 給定一組關(guān)鍵字為: 12, 39, 18, 24, 33, 21 若取 p=9, 則它們對(duì)應(yīng)的散列函數(shù)值將為: 3, 3, 0, 6, 6

9、, 3 為什么要對(duì)p加限制？ 可見(jiàn)，若p中含質(zhì)因子3, 則所有含質(zhì)因子3的關(guān) 鍵字均映射到“3的倍數(shù)”的地址上，從而增加 了“沖突”的可能。 散列函數(shù)的構(gòu)造方法 6. 隨機(jī)數(shù)法 設(shè)定散列函數(shù)為: H(key) = Random(key) 其中Random 為隨機(jī)函數(shù) 此方法通常用于對(duì)長(zhǎng)度不等的關(guān)鍵字構(gòu)造散 列函數(shù)。 散列函數(shù)的構(gòu)造方法 實(shí)際構(gòu)造散列表時(shí) 1.采用哪種構(gòu)造散列函數(shù)的方法取決于建表的關(guān)鍵字 集合的情況(包括關(guān)鍵字的范圍和形態(tài)) 2.總的原則是使產(chǎn)生沖突的可能性盡可能的小。 3.如果散列造表過(guò)程中產(chǎn)生沖突，應(yīng)當(dāng)如何處理這些 沖突呢？ 處理沖突的方法 沖突：由關(guān)鍵字得到的散列地址為j（

10、0jn-1）的位置上 已存有記錄 處理沖突：為產(chǎn)生沖突的地址尋找下一個(gè)空的散列地址 2. 不用鏈表的散列表開(kāi)放定址法5.4 3. 再散列法5.5 1. 分離鏈接法5.3 4. 建立一個(gè)公共溢出區(qū) 處理沖突的方法1 1. 分離鏈接法(separate chaining) 將散列到同一個(gè)值的所有元素保留到同一線 性鏈表中。 處理沖突的方法1 例如: 關(guān)鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 采用鏈地址法來(lái)構(gòu)造的 散列表： 散列函數(shù)為 H(key)=key MOD 7 11 198268 55 14 0136 23 19012314 55681182 36 0

11、 1 2 3 4 5 6 處理沖突的方法1 執(zhí)行一次查找：首 先使用散列函數(shù)來(lái) 確定需要遍歷的鏈 表；然后再在被確 定的鏈表中執(zhí)行一 次查找。 11 198268 55 14 0136 23 0 1 2 3 4 5 6 ASL=(61+22+ 31)/9=13/9 處理沖突的方法1 執(zhí)行插入操作：首 先檢查相應(yīng)的鏈表 中該元素是否已處 在適當(dāng)?shù)奈恢茫?則被插入到鏈表的 前端。 11 198268 55 14 0136 23 0 1 2 3 4 5 6 處理沖突的方法2 2. 開(kāi)放定址法 為產(chǎn)生沖突的地址 H(key) 求得一個(gè)地址序列： H0, H1, H2, , Hs 1 sm-1 其中：

12、H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s m 為散列表表長(zhǎng) 處理沖突的方法2 1. 線性探測(cè)再散列法 2. 平方探測(cè)再散列法 3. 雙散列法 增量 di的 三種 取法 處理沖突的方法2 1. 開(kāi)放定址法 對(duì)增量 di 的三種取法-： 1) 線性探測(cè)再散列 di = c i 最簡(jiǎn)單的情況 c=1 , 即di=f(i)=i; 即 di= 1,2,3,m-1 處理沖突的方法2 例如: 關(guān)鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 設(shè)定散列函數(shù) H(key) = key MOD 11 ( 表長(zhǎng)=11 ) 采

13、用線性探測(cè)再散列法來(lái)構(gòu)造散列表。 19 0 1 2 3 4 5 6 7 8 9 10 1901 012323 2314 14 55 5568 68 6811821136 118236 1 1 2 1 3 6 2 5 1 處理沖突的方法2 1. 開(kāi)放定址法 對(duì)增量 di 有三種取法-： 2) 平方（二次）探測(cè)再散列 di =f(i)= 12, -12, 22, -22, , 處理沖突的方法2 例如: 關(guān)鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 19 0 1 2 3 4 5 6 7 8 9 10 1901 012323 23 14 14 55 5568 68

14、6811 821136 118236 36 設(shè)定散列函數(shù) H(key) = key MOD 11 ( 表長(zhǎng)=11 ) 采用二次探測(cè)再散列法來(lái)構(gòu)造散列表。 1 1 2 1 2 1 4 1 3 處理沖突的方法2 1. 開(kāi)放定址法 對(duì)增量 di 有三種取法-： 3) 雙散列法 di即f(i)是一組隨機(jī)數(shù)列 或者 di=f(i)=iH2(key) (又稱(chēng)隨機(jī)探測(cè)再散列) 處理沖突的方法2 H2(key) 是另設(shè)定的一個(gè)散列函數(shù)，它的函數(shù) 值應(yīng)和 TableSize 互為素?cái)?shù)。 若 TableSize 為素?cái)?shù)，則 H2(key) 可以是 1 至 TableSize-1 之間的任意數(shù); 若 TableSi

15、ze 為 2 的冪次，則 H2(key) 應(yīng)是 1 至 TableSize-1 之間的任意奇數(shù)。 處理沖突的方法 例如，當(dāng) m=11時(shí)， 可設(shè) H2(key)=(3 key) MOD 10+1 190123145568118236 2 1 1 1 2 1 2 1 3 設(shè)定哈希函數(shù) H(key) = key MOD 11 ( 表長(zhǎng)=11 ) 例如: 關(guān)鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 處理沖突的方法2 即：產(chǎn)生的 Hi 均不相同，且所產(chǎn)生的TableSize-1 個(gè) Hi 值能覆蓋散列表中所有地址。 則要求： 注意：增量 di 應(yīng)具有“完備性” 雙散

16、列時(shí)TableSize和 di 沒(méi)有公因子。 平方探測(cè)時(shí)的表長(zhǎng) TableSize 必為形如 4j+3 的素?cái)?shù)（如: 7, 11, 19, 23, 等）； 處理沖突的方法3 3. 再散列法 Hi=RHi(key) i=1,2,3,，k RHi均是不同的散列函數(shù)，在同義詞產(chǎn)生地址 沖突時(shí)計(jì)算另一個(gè)散列函數(shù)地址，直到?jīng)_突 不再發(fā)生。 缺點(diǎn)：增加了計(jì)算時(shí)間。 處理沖突的方法4 4. 建立一個(gè)公共溢出區(qū) 散列函數(shù)的值域0,m-1 向量HashTable0.m-1為基本表，每個(gè)分量存放 一個(gè)記錄 向量OverTable0.v為溢出表 對(duì)于關(guān)鍵字和基本表HashTable中關(guān)鍵字為同義 詞的記錄，只要發(fā)生

17、沖突，都填入溢出表。 課堂練習(xí) 設(shè)有一組關(guān)鍵字11，54，36，89，51，47，38， 59，63，94，15，采用哈希函數(shù)：H(key) = key % 13。采用開(kāi)放地址法的線性探測(cè)再散列方法解決沖 突，試在015的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造 哈希表。 散列表的查找算法 查找過(guò)程和造表過(guò)程一致。假設(shè)采用開(kāi)放定址 處理沖突，則查找過(guò)程為: 1.對(duì)于給定值 K, 計(jì)算散列地址 i = H(K) 2.若 ri = NULL 則查找不成功 3.若 ri.key = K 則查找成功 4.否則 “求下一地址 Hi” ，直至 rHi = NULL (查 找不成功)或 rHi.key = K (查找成功) 為止。 哈希表的查找分析 從查找過(guò)程得知： 由于沖突的產(chǎn)生，哈希表的查找過(guò)程仍然是一個(gè) 給定值和關(guān)鍵字進(jìn)行比較的過(guò)程。 哈希表查找的平均查找長(zhǎng)度實(shí)際上并不等于零。 哈希表的查找分析 1) 選用的哈希函數(shù); 2) 選用的處理沖突的方法; 3）哈希表飽和的程度，裝載因子 =n/m 值的大小 （n記錄數(shù)，m表的長(zhǎng)度，即TableSize） 決定哈希表查找的ASL的因素： 哈希表的查找分析 一般情況下，可以認(rèn)為選用的哈希函數(shù)是“均勻”的， 則在討論ASL時(shí)，可以不考慮它的因素。 因此，哈希表的ASL是處理沖突方法和裝載因子的函 數(shù)。 例如：前述例子 線性探測(cè)處理沖