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

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

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


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

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

3.數字分析法
　　對各個關鍵字內部代碼的各個碼位進行分析。假設有 n 個 d 位的關鍵字，使用 s 個不同的符號 ( 如，對于十進制數，每一位可能出現的符號有 10 個，即 0 、 1 、 2 、…、 9) ，這 s 個不同的符號在各位上出現的頻率不一定相同，它們可能在某些位上分布比較均勻，即每一個符號出現的次數都接近 n/s 次；而在另一些位上分布不均勻。這時，選取其中分布比較均勻的某些位作為哈希函數值 ( 散列地址 ) ，所選取的位數應視存儲區地址范圍而定，這就是數字分析法。
注意：
　　這種方法適合于關鍵字值中各位字符分布為已知的情況。
例如，給定一組關鍵字：
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 個字符分布的均勻度，可采用度量標準： 式中 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 × (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 。由于數字分析法需預先知道各位上字符的分布情況，這就大大限制了它的實用性。

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


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