摘要：稱這個對應(yīng)關(guān)系為散列函數(shù)，按這個思想建立的表為散列表。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。此時線性探測的方法是取并假定取關(guān)鍵字除以的余數(shù)為散列函數(shù)法則。

散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計算一個關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

一個通俗的例子是，為了查找電話簿中某人的號碼，可以創(chuàng)建一個按照人名首字母順序排列的表（即建立人名 x 到首字母 F(x) 的一個函數(shù)關(guān)系），在首字母為W的表中查找“王”姓的電話號碼，顯然比直接查找就要快得多。這里使用人名作為關(guān)鍵字，“取首字母”是這個例子中散列函數(shù)的函數(shù)法則F()，存放首字母的表對應(yīng)散列表。關(guān)鍵字和函數(shù)法則理論上可以任意確定。

若關(guān)鍵字為 k，則其值存放在f(k) 的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應(yīng)關(guān)系 f 為散列函數(shù)，按這個思想建立的表為散列表。

對不同的關(guān)鍵字k可能得到同一散列地址，即

$$ k1≠k2 $$

，而

$$ f(k1)=f(k2) $$

，這種現(xiàn)象稱為沖突（或碰撞，英語：Collision）。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。綜上所述，根據(jù)散列函數(shù)f(k) 和處理沖突的方法將一組關(guān)鍵字映射到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址。

若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)（Uniform Hash function），這就使關(guān)鍵字經(jīng)過散列函數(shù)得到一個“隨機的地址”，從而減少沖突。

散列函數(shù)能使對一個數(shù)據(jù)序列的訪問過程更加迅速有效，通過散列函數(shù)，數(shù)據(jù)元素將被更快定位。

直接定址法：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即

$$ hash(k)=k $$

或

$$ hash(k)=a cdot k+b $$

, 其中ab為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）

數(shù)字分析法：假設(shè)關(guān)鍵字是以r為基的數(shù)，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。

平方取中法：取關(guān)鍵字平方后的中間幾位為哈希地址。通常在選定哈希函數(shù)時不一定能知道關(guān)鍵字的全部情況，取其中的哪幾位也不一定合適，而一個數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，由此使隨機分布的關(guān)鍵字得到的哈希地址也是隨機的。取的位數(shù)由表長決定。

折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進位）作為哈希地址。

除留余數(shù)法：取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即

$$ hash(k)=k,{mod {,}}p $$

$$ pleq m $$

不僅可以對關(guān)鍵字直接取模，也可在折疊法、平方取中法等運算之后取模。對p的選擇很重要，一般取素數(shù)或m，若p選擇不好，容易產(chǎn)生沖突。

為了知道沖突產(chǎn)生的相同散列函數(shù)地址所對應(yīng)的關(guān)鍵字，必須選用另外的散列函數(shù)，或者對沖突結(jié)果進行處理，而不發(fā)生沖突的可能性是非常之小的，所以通常對沖突進行處理。常用方法有以下幾種：

開放尋址法(open addressing)。想象一下，有一趟對號入座的火車，假設(shè)它只有一節(jié)車廂，上來一位坐7號座位的旅客。過了一會兒，又上來一位旅客，他買到的是一張假票，也是7號座位，這時怎么辦呢？列車長想了想，讓拿假票的旅客去坐8號座位。過了一會兒，應(yīng)該坐8號座位的旅客上來了，列車長對他說8號座位已經(jīng)有人了，你去坐9號座位吧。哦？9號早就有人了？10號也有人了？那你去坐11號吧?？梢韵胍?，越到后來，當(dāng)空座越來越少時，碰撞的幾率就越大，尋找空座愈發(fā)地費勁。但是，如果是火車的上座率只有50%或者更少的情況呢？也許真正坐8號座位的乘客永遠不會上車，那么讓拿假票的乘客坐8號座位就是一個很好的策略了。所以，這是一個空間換時間的游戲。玩好這個游戲的關(guān)鍵是，讓旅客分散地坐在車廂里。如何才能做到這一點呢？答案是，對于每位不同的旅客使用不同的探查序列。例如，對于旅客 A，探查座位 7，8，23，56……直到找到一個空位；對于旅客B，探查座位 25，66，77，1，3……直到找到一個空位。如果有 m 個座位，每位旅客可以使用 <0, 1, 2, ..., m-1> 的m! 個排列中的一個。

顯而易見，最好減少兩個旅客使用相同的探查序列的情況。也就是說，希望把每位旅客盡量分散地映射到 m! 種探查序列上。換句話說，理想狀態(tài)下，如果能夠讓每個上車的旅客，使用 m! 個探查序列中的任意一個的可能性是相同的，我們就說實現(xiàn)了一致散列。（這里沒有用“隨機”這個詞兒，因為實際是不可能隨機取一個探查序列的，因為在查找這名旅客時還要使用相同的探查序列）。

線性探查：最簡單的方法是，如果發(fā)現(xiàn) values[8] 已經(jīng)被占用了，就看看 values[9] 是否空著，如果 values[9] 也被占用了，就看看 values[0] 是不是還空著。完整的描述是，先使用 H() 函數(shù)獲取 k 的第一個地址，如果這個地址已被占用，就探查下一個緊挨著的地址，如果還是不能用，就探查下一個緊挨著的地址，如果到達了數(shù)組的末尾，就卷繞到數(shù)組的開頭，如果探查了 m 次還是沒有找到空槽，就說明數(shù)組已經(jīng)滿了，這就是線性探查（linear probing）

真正的一致散列是難以實現(xiàn)的，實踐中，常常采用它的一些近似方法。常用的產(chǎn)生探查序列的方法有：線性探查，平方探測，以及雙重散列探查。這些方法都不能實現(xiàn)一致散列，因為它們能產(chǎn)生的不同探查序列數(shù)都不超過

$$ m^2 $$

個（一致散列要求有 m! 個探查序列）。在這三種方法中，雙重散列能產(chǎn)生的探查序列數(shù)最多，因而能給出最好的結(jié)果。

顯示線性探測填裝一個散列表的過程：

關(guān)鍵字為{89,18,49,58,69}插入到一個散列表中的情況。此時線性探測的方法是取

$$ d_{i}=i $$

并假定取關(guān)鍵字除以10的余數(shù)為散列函數(shù)法則。

第一次沖突發(fā)生在填裝49的時候。地址為9的單元已經(jīng)填裝了89這個關(guān)鍵字，所以取 $i=1$，往下查找一個單位，發(fā)現(xiàn)為空，所以將49填裝在地址為0的空單元。

第二次沖突則發(fā)生在58上，取i=3，往下查找3個單位，將58填裝在地址為1的空單元。69同理。
表的大小選取至關(guān)重要，此處選取10作為大小，發(fā)生沖突的幾率就比選擇質(zhì)數(shù)11作為大小的可能性大。越是質(zhì)數(shù)，mod取余就越可能均勻分布在表的各處。

聚集（Cluster，也翻譯做“堆積”）的意思是，在函數(shù)地址的表中，散列函數(shù)的結(jié)果不均勻地占據(jù)表的單元，形成區(qū)塊，造成線性探測產(chǎn)生一次聚集（primary clustering）和平方探測的二次聚集（secondary clustering），散列到區(qū)塊中的任何關(guān)鍵字需要查找多次試選單元才能插入表中，解決沖突，造成時間浪費。對于開放定址法，聚集會造成性能的災(zāi)難性損失，是必須避免的。

轉(zhuǎn)載請注明出處