哈希表與哈希函數(shù)
　　哈希查找因使用哈希 (Hash) 函數(shù)而得名，哈希函數(shù)又叫散列函數(shù)，它是一種能把關(guān)鍵字映射成記錄存貯地址的函數(shù)。
1.哈希表
①它是一種能把關(guān)鍵字映射成記錄存貯地址的函數(shù)。
②假定數(shù)組 HT[0 ～ m-1] 為存貯記錄的地址空間， m 為表長，哈希函數(shù) H 以記錄的關(guān)鍵字 K 為自變量，計算出對應(yīng)的函數(shù)值 H(K) ，并以它作為關(guān)鍵字 K 所標(biāo)識的記錄在表 HT 中的 ( 相對 ) 地址或索引號，這樣產(chǎn)生的記錄表 HT 叫做對應(yīng)于哈希函數(shù) H 的哈希表。
③簡言之，在哈希表中，關(guān)鍵字為 K 的記錄，存貯在 HT[H(K)] 位置。
④哈希函數(shù)值 H(K) 稱為 K 的哈希地址或散列地址。
    
3、哈希表的沖突現(xiàn)象
（1）沖突
    　不同的關(guān)鍵字值，具有相同的哈希地址，因而被映射到同一表位置上。該現(xiàn)象稱為沖突(Collision)或碰撞。
  　【例】上圖中的k₂≠k₅，但h(k₂)=h(k₅)，故k₂和K₅所在的結(jié)點的存儲地址相同。

（2）安全避免沖突的條件
    如何避免沖突發(fā)生，則取決于哈希函數(shù)的構(gòu)造。
    使散列地址均勻地分布在哈希表的整個地址區(qū)間內(nèi)，這樣可以避免或減少發(fā)生沖突。
    哈希函數(shù)的構(gòu)造，與關(guān)鍵字的長度、哈希表的大小、關(guān)鍵字的實際取值狀況等許多因素有關(guān)，而且有的因素事前不能確定。所以，避免沖突這并非是件容易做到的事。

（3）沖突不可能完全避免
    　由于關(guān)鍵字的值域往往比哈希表的個數(shù)大的多，所以哈希函數(shù)是一種壓縮映射，碰撞是難免的。
   【例】存貯 100 個學(xué)生記錄，盡管安排 120 個地址空間，但由于學(xué)生名 ( 假設(shè)不超過 10 個英文字母 ) 的理論個數(shù)超過 2610 ，要找到一個哈希函數(shù)把 100 個任意的學(xué)生名映射成 [0 ， 119] 內(nèi)的不同整數(shù)，實際上是不可能的。
   注意：問題在于一旦發(fā)生了沖突應(yīng)如何處理。


構(gòu)造哈希表
　　構(gòu)造哈希函數(shù)的方法很多，這里只介紹一些常用的，計算簡便的方法。
1.平方取中法
　　算出關(guān)鍵字值的平方，再取其中若干位作為哈希函數(shù)值 ( 散列地址 ) 。
【例】假定表中各關(guān)鍵字是由字母組成的，用二位數(shù)字的整數(shù) 01 ～ 26 表示對應(yīng)的 26 個英文字母在計算機中的內(nèi)部編碼，則使用平方取中法計算 KEYA ， KEYB ， AKEY ， BKEY 的散列地址可得：
關(guān)鍵字 K     K 的內(nèi)部編碼            K ²           H(K)
 KEYA         11052501       122157778355001      778
 KEYB         11052502       122157800460004      800
 AKEY         01110525       001233265775625      265
 BKEY         02110525       004454315775625      315
平方之后，取左起第 7 ～ 9 位作為散列地址。

2.除留余數(shù)法
    這種方法是用模運算 (%) 得到的。設(shè)給出的關(guān)鍵字值為 K ，存儲區(qū)單元數(shù)為 m ，則用一個小于 m 的質(zhì)數(shù) P 去除 K ，得到的余數(shù)為 R ，即： R ＝ K % P 。如果 R 落在存儲區(qū)地址范圍內(nèi)，則 R 就取為哈希函數(shù)值 ( 散列地址 ) ；否則，再用一個線性數(shù)求出哈希函數(shù)值。
【例】有一組關(guān)鍵字從 000001 到 859999 ，指定的存儲區(qū)地址為 1000000 ～ 1005999 ，即 m ＝ 6000 ，可選 P ＝ 599 ，若要轉(zhuǎn)換關(guān)鍵字 K ＝ 172148 ，則有：
                R ＝ 172148 % 599 ＝ 4176
因 R 不在指定的地址范圍內(nèi)，所以，取哈希函數(shù)為：
                  H(K) ＝ 1000000 ＋ R
故有：
                H(K) ＝ H(172148) ＝ 1004176
這樣就把關(guān)鍵字 K 直接轉(zhuǎn)換成存儲地址了。

3.數(shù)字分析法
　　對各個關(guān)鍵字內(nèi)部代碼的各個碼位進行分析。假設(shè)有 n 個 d 位的關(guān)鍵字，使用 s 個不同的符號 ( 如，對于十進制數(shù)，每一位可能出現(xiàn)的符號有 10 個，即 0 、 1 、 2 、…、 9) ，這 s 個不同的符號在各位上出現(xiàn)的頻率不一定相同，它們可能在某些位上分布比較均勻，即每一個符號出現(xiàn)的次數(shù)都接近 n/s 次；而在另一些位上分布不均勻。這時，選取其中分布比較均勻的某些位作為哈希函數(shù)值 ( 散列地址 ) ，所選取的位數(shù)應(yīng)視存儲區(qū)地址范圍而定，這就是數(shù)字分析法。
注意：
　　這種方法適合于關(guān)鍵字值中各位字符分布為已知的情況。
例如，給定一組關(guān)鍵字：
K 1 ： 542482241
K 2 ： 542813678
K 3 ： 532228171
K 4 ： 542389671
K 5 ： 542541577
K 6 ： 542985376
K 7 ： 542193552

　　這里 n ＝ 7 ； d ＝ 9 ； s ＝ 10 。為了衡量各位上 s 個字符分布的均勻度，可采用度量標(biāo)準(zhǔn)： 式中 a ik 表示第 i 個字符在第 k 位上出現(xiàn)的 (k ＝ 1 ， 2 ，…， d) 次數(shù)。λ 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 × (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
　　假定存儲區(qū)地址為 000 ～ 999 ，則應(yīng)取關(guān)鍵字的第 4 、 6 、 7 位作為哈希函數(shù)值 ( 散列地址 ) ，它們分別為 422 、 836 、 281 、 396 、 515 、 953 和 135 。由于數(shù)字分析法需預(yù)先知道各位上字符的分布情況，這就大大限制了它的實用性。

　 　構(gòu)造哈希函數(shù)除了上面介紹的幾種常用方法外，還有截段法，即截取關(guān)鍵字中的某一段數(shù)碼作為哈希函數(shù)；分段迭加法，即把關(guān)鍵字的機內(nèi)代碼分成幾段，再進行迭加 ( 可以是算術(shù)加，也可以是按位加 ) 得到哈希函數(shù)值。對于各種構(gòu)造哈希函數(shù)的方法，很難一概而論地評價其優(yōu)劣，任何一種哈希函數(shù)都應(yīng)當(dāng)用實際數(shù)據(jù)去測試它的均勻性，才能做出正確的判斷和結(jié)論。


解決沖突的主要方法
　　雖然我們不希望發(fā)生沖突，但實際上發(fā)生沖突的可能性仍是存在的。當(dāng)關(guān)鍵字值域遠大于哈希表的長度，而且事先并不知道關(guān)鍵字的具體取值時。沖突就難免會發(fā)生。另外，當(dāng)關(guān)鍵字的實際取值大于哈希表的長度時，而且表中已裝滿了記錄，如果插入一個新記錄，不僅發(fā)生沖突，而且還會發(fā)生溢出。因此，處理沖突和溢出是哈希技術(shù)中的兩個重要問題。
1、開放定址法
    　用開放定址法解決沖突的做法是：當(dāng)沖突發(fā)生時，使用某種探查(亦稱探測)技術(shù)在散列表中形成一個探查(測)序列。沿此序列逐個單元地查找，直到找到給定的關(guān)鍵字，或者碰到一個開放的地址(即該地址單元為空)為止（若要插入，在探查到開放的地址，則可將待插入的新結(jié)點存人該地址單元）。查找時探查到開放的地址則表明表中無待查的關(guān)鍵字，即查找失敗。
  注意：
 ①用開放定址法建立散列表時，建表前須將表中所有單元(更嚴(yán)格地說，是指單元中存儲的關(guān)鍵字)置空。
 ②空單元的表示與具體的應(yīng)用相關(guān)。
    　按照形成探查序列的方法不同，可將開放定址法區(qū)分為線性探查法、線性補償探測法、隨機探測等。
（1）線性探查法(Linear Probing)
該方法的基本思想是：
　    將散列表T[0..m-1]看成是一個循環(huán)向量，若初始探查的地址為d(即h(key)=d)，則最長的探查序列為：
        d，d+l，d+2，…，m-1，0，1，…，d-1
    　即:探查時從地址d開始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循環(huán)到T[0]，T[1]，…，直到探查到T[d-1]為止。
探查過程終止于三種情況：
    　(1)若當(dāng)前探查的單元為空，則表示查找失敗（若是插入則將key寫入其中）；
　    (2)若當(dāng)前探查的單元中含有key，則查找成功，但對于插入意味著失敗；
    　(3)若探查到T[d-1]時仍未發(fā)現(xiàn)空單元也未找到key，則無論是查找還是插入均意味著失敗(此時表滿)。
利用開放地址法的一般形式，線性探查法的探查序列為：
        h_i=(h(key)+i)％m 0≤i≤m-1 //即d_i=i
用線性探測法處理沖突，思路清晰，算法簡單，但存在下列缺點：
　　① 處理溢出需另編程序。一般可另外設(shè)立一個溢出表，專門用來存放上述哈希表中放不下的記錄。此溢出表最簡單的結(jié)構(gòu)是順序表，查找方法可用順序查找。
　　② 按上述算法建立起來的哈希表，刪除工作非常困難。假如要從哈希表 HT 中刪除一個記錄，按理應(yīng)將這個記錄所在位置置為空，但我們不能這樣做，而只能標(biāo)上已被刪除的標(biāo)記，否則，將會影響以后的查找。
　　③ 線性探測法很容易產(chǎn)生堆聚現(xiàn)象。所謂堆聚現(xiàn)象，就是存入哈希表的記錄在表中連成一片。按照線性探測法處理沖突，如果生成哈希地址的連續(xù)序列愈長 ( 即不同關(guān)鍵字值的哈希地址相鄰在一起愈長 ) ，則當(dāng)新的記錄加入該表時，與這個序列發(fā)生沖突的可能性愈大。因此，哈希地址的較長連續(xù)序列比較短連續(xù)序列生長得快，這就意味著，一旦出現(xiàn)堆聚 ( 伴隨著沖突 ) ，就將引起進一步的堆聚。