1、哈希表與哈希函數 哈希查找因使用哈希 (Hash) 函數而得名，哈希函數又叫散列函數，它是一種能把關鍵字映射成記錄存貯地址的函數。 1.哈希表它是一種能把關鍵字映射成記錄存貯地址的函數。假定數組 HT0 m-1 為存貯記錄的地址空間， m 為表長，哈希函數 H 以記錄的關鍵字 K 為自變量，計算出對應的函數值 H(K) ，并以它作為關鍵字 K 所標識的記錄在表 HT 中的 ( 相對 ) 地址或索引號，這樣產生的記錄表 HT 叫做對應于哈希函數 H 的哈希表。簡言之，在哈希表中，關鍵字為 K 的記錄，存貯在 HTH(K) 位置。哈希函數值 H(K) 稱為 K 的哈希地址或散列地址。 &

2、#160;   3、哈希表的沖突現象（1）沖突    不同的關鍵字值，具有相同的哈希地址，因而被映射到同一表位置上。該現象稱為沖突(Collision)或碰撞。  【例】上圖中的k2k5，但h(k2)=h(k5)，故k2和K5所在的結點的存儲地址相同。（2）安全避免沖突的條件    如何避免沖突發生，則取決于哈希函數的構造。     使散列地址均勻地分布在哈希表的整個地址區間內，這樣可以避免或減少發生沖突。    哈希函數的構造，與關鍵字的長度、

3、哈希表的大小、關鍵字的實際取值狀況等許多因素有關，而且有的因素事前不能確定。所以，避免沖突這并非是件容易做到的事。（3）沖突不可能完全避免    由于關鍵字的值域往往比哈希表的個數大的多，所以哈希函數是一種壓縮映射，碰撞是難免的。   【例】存貯 100 個學生記錄，盡管安排 120 個地址空間，但由于學生名 ( 假設不超過 10 個英文字母 ) 的理論個數超過 2610 ，要找到一個哈希函數把 100 個任意的學生名映射成 0 ， 119 內的不同整數，實際上是不可能的。   注意：問題在于一旦發生了沖

4、突應如何處理。構造哈希表 構造哈希函數的方法很多，這里只介紹一些常用的，計算簡便的方法。1.平方取中法算出關鍵字值的平方，再取其中若干位作為哈希函數值 ( 散列地址 ) ?！纠考俣ū碇懈麝P鍵字是由字母組成的，用二位數字的整數 01 26 表示對應的 26 個英文字母在計算機中的內部編碼，則使用平方取中法計算 KEYA ， KEYB ， AKEY ， BKEY 的散列地址可得：關鍵字 K     K 的內部編碼            K 2 &#

5、160;         H(K)  KEYA         11052501       122157778355001      778 KEYB         11052502   

6、0;   122157800460004      800 AKEY         01110525       001233265775625      265  BKEY         02110525  

7、60;    004454315775625      315 平方之后，取左起第 7 9 位作為散列地址。2.除留余數法    這種方法是用模運算 (%) 得到的。設給出的關鍵字值為 K ，存儲區單元數為 m ，則用一個小于 m 的質數 P 去除 K ，得到的余數為 R ，即： R K % P 。如果 R 落在存儲區地址范圍內，則 R 就取為哈希函數值 ( 散列地址 ) ；否則，再用一個線性數求出哈希函數值?！纠坑幸唤M關鍵字從 000001 到 859999 ，

8、指定的存儲區地址為 1000000 1005999 ，即 m 6000 ，可選 P 599 ，若要轉換關鍵字 K 172148 ，則有：                R 172148 % 599 4176 因 R 不在指定的地址范圍內，所以，取哈希函數為：               &

9、#160;  H(K) 1000000 R故有：                H(K) H(172148) 1004176 這樣就把關鍵字 K 直接轉換成存儲地址了。3.數字分析法對各個關鍵字內部代碼的各個碼位進行分析。假設有 n 個 d 位的關鍵字，使用 s 個不同的符號 ( 如，對于十進制數，每一位可能出現的符號有 10 個，即 0 、 1 、 2 、 9) ，這 s 個不同的符號在各位上出現的頻率不一定相同，

10、它們可能在某些位上分布比較均勻，即每一個符號出現的次數都接近 n/s 次；而在另一些位上分布不均勻。這時，選取其中分布比較均勻的某些位作為哈希函數值 ( 散列地址 ) ，所選取的位數應視存儲區地址范圍而定，這就是數字分析法。注意：這種方法適合于關鍵字值中各位字符分布為已知的情況。例如，給定一組關鍵字：K 1 ： 542482241 K 2 ： 542813678K 3 ： 532228171K 4 ： 542389671 K 5 ： 542541577 K 6 ： 542985376K 7 ： 542193552 這里 n 7 ； d 9 ； s 10 。為了衡量各位上 s 個字符分布的均勻度

11、，可采用度量標準： 式中 a ik 表示第 i 個字符在第 k 位上出現的 (k 1 ， 2 ， d) 次數。 k 值越小，可認為分布越均勻。這里，自左向右，各位上字符的分布均勻度為： (7 7/10) 2 9 × (0 7/10) 2 44.1 44.1 44.1 7 × (1-7/10) 2 3 × (0 7/10) 2 2.1 4 × (1-7/10) 2 (3 7/10) 2 5 × (0-7/10) 2 8.1 5 × (1-7/10) 2 (2 7/10) 2 4 × (0-7/10) 2 4.1 3 ×

12、; (1-7/10) 2 2 × (2 7/10) 2 5 × (0-7/10) 2 6.1 2 × (1-7/10) 2 (5 7/10) 2 7 × (0-7/10) 2 22.1 4 × (1-7/10) 2 (3 7/10) 2 5 × (0-7/10) 2 8.1 假定存儲區地址為 000 999 ，則應取關鍵字的第 4 、 6 、 7 位作為哈希函數值 ( 散列地址 ) ，它們分別為 422 、 836 、 281 、 396 、 515 、 953 和 135 。由于數字分析法需預先知道各位上字符的分布情況，這就大大限制

13、了它的實用性。 構造哈希函數除了上面介紹的幾種常用方法外，還有截段法，即截取關鍵字中的某一段數碼作為哈希函數；分段迭加法，即把關鍵字的機內代碼分成幾段，再進行迭加 ( 可以是算術加，也可以是按位加 ) 得到哈希函數值。對于各種構造哈希函數的方法，很難一概而論地評價其優劣，任何一種哈希函數都應當用實際數據去測試它的均勻性，才能做出正確的判斷和結論。解決沖突的主要方法 雖然我們不希望發生沖突，但實際上發生沖突的可能性仍是存在的。當關鍵字值域遠大于哈希表的長度，而且事先并不知道關鍵字的具體取值時。沖突就難免會發生。另外，當關鍵字的實際取值大于哈希表的長度時，而且表中已裝滿了記錄，如果插入一個新記錄，

14、不僅發生沖突，而且還會發生溢出。因此，處理沖突和溢出是哈希技術中的兩個重要問題。1、開放定址法    用開放定址法解決沖突的做法是：當沖突發生時，使用某種探查(亦稱探測)技術在散列表中形成一個探查(測)序列。沿此序列逐個單元地查找，直到找到給定的關鍵字，或者碰到一個開放的地址(即該地址單元為空)為止（若要插入，在探查到開放的地址，則可將待插入的新結點存人該地址單元）。查找時探查到開放的地址則表明表中無待查的關鍵字，即查找失敗。  注意： 用開放定址法建立散列表時，建表前須將表中所有單元(更嚴格地說，是指單元中存儲的關鍵字)置空。 空單

15、元的表示與具體的應用相關。    按照形成探查序列的方法不同，可將開放定址法區分為線性探查法、線性補償探測法、隨機探測等。（1）線性探查法(Linear Probing)該方法的基本思想是：    將散列表T0.m-1看成是一個循環向量，若初始探查的地址為d(即h(key)=d)，則最長的探查序列為：        d，d+l，d+2，m-1，0，1，d-1    即:探查時從地址d開始，首先探查Td，然后依次探查Td+1，直到Tm-1

16、，此后又循環到T0，T1，直到探查到Td-1為止。探查過程終止于三種情況：    (1)若當前探查的單元為空，則表示查找失?。ㄈ羰遣迦雱t將key寫入其中）；    (2)若當前探查的單元中含有key，則查找成功，但對于插入意味著失??；    (3)若探查到Td-1時仍未發現空單元也未找到key，則無論是查找還是插入均意味著失敗(此時表滿)。利用開放地址法的一般形式，線性探查法的探查序列為：        hi=(h(key)+i)m 0

17、im-1 /即di=i用線性探測法處理沖突，思路清晰，算法簡單，但存在下列缺點： 處理溢出需另編程序。一般可另外設立一個溢出表，專門用來存放上述哈希表中放不下的記錄。此溢出表最簡單的結構是順序表，查找方法可用順序查找。 按上述算法建立起來的哈希表，刪除工作非常困難。假如要從哈希表 HT 中刪除一個記錄，按理應將這個記錄所在位置置為空，但我們不能這樣做，而只能標上已被刪除的標記，否則，將會影響以后的查找。 線性探測法很容易產生堆聚現象。所謂堆聚現象，就是存入哈希表的記錄在表中連成一片。按照線性探測法處理沖突，如果生成哈希地址的連續序列愈長 ( 即不同關鍵字值的哈希地址相鄰在一起愈長 ) ，則當新

18、的記錄加入該表時，與這個序列發生沖突的可能性愈大。因此，哈希地址的較長連續序列比較短連續序列生長得快，這就意味著，一旦出現堆聚 ( 伴隨著沖突 ) ，就將引起進一步的堆聚。（2）線性補償探測法 線性補償探測法的基本思想是：將線性探測的步長從 1 改為 Q ，即將上述算法中的 j (j 1) % m 改為： j (j Q) % m ，而且要求 Q 與 m 是互質的，以便能探測到哈希表中的所有單元?！纠?PDP-11 小型計算機中的匯編程序所用的符合表，就采用此方法來解決沖突，所用表長 m 1321 ，選用 Q 25 。（3）隨機探測 隨機探測的基本思想是：將線性探測的步長從常數改為隨機數，即令

19、： j (j RN) % m ，其中 RN 是一個隨機數。在實際程序中應預先用隨機數發生器產生一個隨機序列，將此序列作為依次探測的步長。這樣就能使不同的關鍵字具有不同的探測次序，從而可以避免或減少堆聚?；谂c線性探測法相同的理由，在線性補償探測法和隨機探測法中，刪除一個記錄后也要打上刪除標記。2、拉鏈法（1）拉鏈法解決沖突的方法    拉鏈法解決沖突的做法是：將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T0.m-1。凡是散列地址為i的結點，均插入到以Ti為頭指針的單鏈表中。T中各分量的初值

20、均應為空指針。在拉鏈法中，裝填因子可以大于1，但一般均取1?！纠吭O有 m 5 ， H(K) K mod 5 ，關鍵字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外鏈地址法所建立的哈希表如下圖所示：           （2）拉鏈法的優點與開放定址法相比，拉鏈法有如下幾個優點：拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；由于拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合于造表前無法確定表長的情況；開放定址法為減少沖

21、突，要求裝填因子較小，故當結點規模較大時會浪費很多空間。而拉鏈法中可取1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；在用拉鏈法構造的散列表中，刪除結點的操作易于實現。只要簡單地刪去鏈表上相應的結點即可。而對開放地址法構造的散列表，刪除結點不能簡單地將被刪結點的空間置為空，否則將截斷在它之后填人散列表的同義詞結點的查找路徑。這是因為各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在用開放地址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。（3）拉鏈法的缺點    拉鏈法的缺點是：指針需要額外的空間

22、，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。已知一個線性表(38，25，74，63，52，48)，采用的散列函數為H(Key)=Key mod 7，將元素散列到表長為7的哈希表中存儲。若采用線性探測的開放定址法解決沖突，則在該散列表上進行等概率成功查找的平均查找長度為  (11)  ；若利用拉鏈法解決沖突，則在該散列表上進行等概率成功查找的平均查找長度為  (12)  。  

23、0; (11)  A、1.5    B、1.7    C、2.0    D、2.3    (12)  A、1.0    B、7/6    C、4/3    D、3/2 0 1 2 3 4 5 6 63 48 38 25 74 520 63123 38 524 25 7456 481+1+2+1+2+1=8 /6 = 4/3+1+2+1+4+3=12 / 6 =2解答：使用開放地址法：1     2     3     4      5      6      7 48      &#