1、散列 (Hashing) 在線性表、樹結(jié)構(gòu)中查找紀(jì)錄是通過與關(guān)鍵 字的“比較”完成的。 順序查找，比較的結(jié)果為“=”或“” 非順序查找，比較的結(jié)果為“” 散列的思想： 根據(jù)紀(jì)錄的關(guān)鍵字直接找到記錄的存儲位置， 即為關(guān)鍵字和記錄的存儲位置建立一個對應(yīng)f，使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的 存儲位置相對應(yīng)。 對應(yīng)關(guān)系f為散列函數(shù)，按該思想建立的表 為散列表。1 根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突的方法將一組關(guān)鍵字映像到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為紀(jì)錄在表中的存儲位置，這種表便稱為哈希表，這一影像過程稱為哈希造表或散列，所得存儲位置稱哈希地址或散列地址。哈希表

2、的定義2散列方法在表項的存儲位置與它的關(guān)鍵字之間建立一個確定的對應(yīng)函數(shù)關(guān)系Hash( )，使每個關(guān)鍵字與結(jié)構(gòu)中一個唯一存儲位置相對應(yīng)： Address Hash ( Rec.key )在查找時，首先對表項的關(guān)鍵字進行函數(shù)計算，把函數(shù)值當(dāng)做表項的存儲位置，在結(jié)構(gòu)中按此位置取表項比較。若關(guān)鍵字相等，則查找成功。在存放表項時，依相同函數(shù)計算存儲位置，并按此位置存放。3構(gòu)造散列函數(shù)時的幾點要求： 散列函數(shù)的定義域必須包括需要存儲的全部關(guān) 鍵碼，如果散列表允許有m個地址時,其值域必 須在 0 到 m-1 之間。 散列函數(shù)計算出來的地址應(yīng)能均勻分布在整個 地址空間中：若 key是從關(guān)鍵字集合中隨機抽 取的

3、一個關(guān)鍵字，散列函數(shù)應(yīng)能以同等概率取 0到 m-1 中的每一個值。 散列函數(shù)應(yīng)是簡單的，能在較短的時間內(nèi)計算 出結(jié)果。哈希函數(shù)的構(gòu)造方法41. 直接定址法 此類函數(shù)直接取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值作為散列地址：Hash ( key ) a * key + b a, b為常數(shù) 這類散列函數(shù)是一對一的映射，一般不會產(chǎn)生沖突。 但是，它要求散列地址空間的大小與關(guān)鍵字集合的 大小相同。52. 數(shù)字分析法 設(shè)有n個d位數(shù)，每一位可能有r種不同的符號。這 r 種不同的符號在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布均勻些；在某些位上分布不均勻，只有某幾種符號經(jīng)常出現(xiàn)?？筛鶕?jù)散列表的大小，選取其中各

4、種符號分布均勻的若干位作為散列地址。6 9 4 2 1 4 8 9 4 1 2 6 9 9 4 0 5 2 7 9 4 1 6 3 0 9 4 1 8 0 5 9 4 1 5 5 8 9 4 2 0 4 7 9 4 0 0 0 1 數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵字每一位數(shù)值的分布情況，它完全依賴于關(guān)鍵字集合。如果換一個關(guān)鍵字集合，選擇哪幾位要重新決定。73. 平方取中法此方法在詞典處理中使用十分廣泛。它先計算構(gòu)成關(guān)鍵字 的標(biāo)識符的內(nèi)碼的平方，然后按照散列表的大小取中間 的若干位作為散列地址。設(shè)標(biāo)識符可以用一個計算機字長的內(nèi)碼表示。因為內(nèi) 碼平方數(shù)的中間幾位一般是由標(biāo)識符所有字符決定

5、， 所以對不同的標(biāo)識符計算出的散列地址大多不相同， 即使其中有些字符相同。在平方取中法中，一般取散列地址為2的某次冪。例 如，若散列地址總數(shù)取為m = 2r，則對內(nèi)碼的平方數(shù) 取中間的r位。如果r = 3，所取得的散列地址參看 圖的最右一列。84. 折疊法此方法把關(guān)鍵字自左到右分成位數(shù)相等的幾部分，每一部分的位數(shù)應(yīng)與散列表地址位數(shù)相同，只有最后一部分的位數(shù)可以短一些。把這些部分的數(shù)據(jù)疊加起來，就可以得到具有該關(guān)鍵字的記錄的散列地址。有兩種疊加方法：移位法 把各部分的最后一位對齊相加；分界法 各部分不折斷，沿各部分的分界來回折疊，然后對齊相加，將相加的結(jié)果當(dāng)做散列地址。9示例：設(shè)給定的關(guān)鍵字為

6、key = 23938587841，若存儲空間限定 3 位, 則劃分結(jié)果為每段 3 位. 上述關(guān)鍵字可劃分為 4段： 239 385 878 41把超出地址位數(shù)的最高位刪去, 僅保留最低的3位，做為可用的散列地址。10一般當(dāng)關(guān)鍵字的位數(shù)很多，而且關(guān)鍵字每一位上數(shù)字的分布大致比較均勻時，可用這種方法得到散列地址。115. 除留余數(shù)法設(shè)散列表中允許的地址數(shù)為m,取一個不大于m，但最接近于或等于m的質(zhì)數(shù)p,或選取一個不小于20的質(zhì)因數(shù)的合數(shù)作為除數(shù)，利用以下公式把關(guān)鍵字轉(zhuǎn)換成散列地址。散列函數(shù)為： hash ( key ) = key % pp m其中, “%”是整數(shù)除法取余的運算，要求這時的質(zhì)數(shù)p

7、不是接近2的冪。示例：有一個關(guān)鍵字 key = 962148，散列表大小 m = 25，即 HT25。取質(zhì)數(shù) p= 23。散列函數(shù) hash ( key ) = key % p。則散列地址為：12 hash ( 962148 ) = 962148 % 23 = 12可以按計算出的地址存放記錄。需要注意的是，使用上面的散列函數(shù)計算出來的地址范圍是 0到 22，因此，從23到24這幾個散列地址實際上在一開始是不可能用散列函數(shù)計算出來的，只可能在處理溢出時達(dá)到這些地址。13以上介紹了幾種常用的散列函數(shù)。在實際工作中應(yīng)根據(jù)關(guān)鍵字的特點，選用適當(dāng)?shù)姆椒?。有人曾用“輪盤賭”的統(tǒng)計分析方法對它們進行了模擬分

8、析，結(jié)論是平方取中法最接近于“隨機化”。在應(yīng)用平方取中法時，若關(guān)鍵字不是整數(shù)而是字符串時，可以把每個字符串轉(zhuǎn)換成整數(shù)。14轉(zhuǎn)換的方法：把字符串從右向左，按一個固定長度 (例如 4 ) 進行分段，必要時可在最左端添一些空格。把每一個字符看成為一個數(shù)字，把字符串的每一段看作為一個整數(shù)。如, ASCII碼采用7位字符代碼，因此每一個字符可以看成一個128進制的數(shù)字。字符串a(chǎn)bcd看成整數(shù) a*(128)3 + b*(128)2 + c*(128) + d。把字符串的每一段都轉(zhuǎn)換成一個整數(shù)后，再把各段轉(zhuǎn)換成的整數(shù)加起來。 15如果這個整數(shù)之和太大，再選擇一個適當(dāng)?shù)某?shù)C (大于任一段字符串轉(zhuǎn)換成的整數(shù)

9、)來除這個和并取其余數(shù)，就得到這個字符串所對應(yīng)的整數(shù)了。161. 開放定址法（閉散列）是處理溢出的一種常用的方法Hash函數(shù)： Hi = (H(key)+di) MOD m, i=1,2,k(km-1) 其中：H(key)為哈希函數(shù)，m為哈希表表長，di為增量序列。 di分別有三種取法： (1) di=1,2,3,m-1 線性探測再散列 (2) di=12,-12,22,-22, k2, -k2,(km/2) 二次探測再散列 特別注意：要求表長m為形如4*j+3的素數(shù) (3) di=偽隨機數(shù)序列，偽隨機探測再散列說明：如果Him，則Hi= Hi- m*n; 其中n為整數(shù)如果Hi0, 則Hi= Hi+ m*n; 其中n為整數(shù)處理沖突的方法172. 再哈希法（也稱雙散列法） Hi = R Hi (key)183. 鏈地址法開散列方法 將所有關(guān)鍵字為同義詞的記