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

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

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

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

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

$$ k1≠k2 $$

，而

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

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

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

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

直接定址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(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ù)時(shí)不一定能知道關(guān)鍵字的全部情況，取其中的哪幾位也不一定合適，而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，由此使隨機(jī)分布的關(guān)鍵字得到的哈希地址也是隨機(jī)的。取的位數(shù)由表長(zhǎng)決定。

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

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

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

$$ pleq m $$

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

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

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

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

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

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

$$ m^2 $$

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

顯示線性探測(cè)填裝一個(gè)散列表的過(guò)程：

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

$$ d_{i}=i $$

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

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

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

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

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