散列函數(shù)一般設(shè)想：

首先，我們討論什么是散列函數(shù)？

函數(shù)，就是映射，對應(yīng)關(guān)系，對吧。散列函數(shù)也一樣。我們設(shè)一個(gè)關(guān)鍵詞為key，再設(shè)一個(gè)正整數(shù)素?cái)?shù)m，讓m去與key做模運(yùn)算然后將他定義為散列函數(shù)h(key)，函數(shù)表達(dá)式為：h(key) ≡key(mod m)，他的含義是，函數(shù)h的值為key和m做取模運(yùn)算，結(jié)果是key模m的最小正剩余。那么我們一開始說，函數(shù)就是映射，所以散列函數(shù)也不例外，這就是映射。我們把這種思想搬到程序設(shè)計(jì)上去，此時(shí)m是一個(gè)數(shù)組的容量，key模m的最小剩余為關(guān)鍵詞key在m數(shù)組中的位置

例如m是111，key為64848212，那么h(64848212) ≡ 64848212 ≡ 1124 ≡ 14(mod 111)我們檢測一下正確性：(64848212 - 14) 能夠整除111，所以是對的。那么這個(gè)時(shí)候m數(shù)組中的第14的位置就存放著64848212這個(gè)數(shù)據(jù)。所以14對應(yīng)著64848212所以是映射。（事實(shí)上這樣算是錯(cuò)誤的，我只是舉個(gè)例子說明是什么樣子的，下面會(huì)說明為什么錯(cuò)誤）

另外，m不能是一個(gè)關(guān)鍵詞key的基數(shù)低b的方冪。例如當(dāng)關(guān)鍵詞是十進(jìn)制的時(shí)候，m不能是10的3次方。這是因?yàn)榇藭r(shí)再做模運(yùn)算，散列函數(shù)會(huì)簡單的變成關(guān)鍵詞的后幾位數(shù)字，并且這可能導(dǎo)致關(guān)鍵詞不會(huì)在數(shù)組中分布均勻，例如這樣會(huì)讓最后三位數(shù)字在000到099之間，很少會(huì)在900到999之間。類似的利用一個(gè)可以整除b^key ± a的數(shù)也是不明智的，其中key和a模m來說是較小的整數(shù)，在這種情況下，h(key)會(huì)強(qiáng)烈的依賴關(guān)鍵詞的某幾位數(shù)，并且相似的卻重排了數(shù)字順序的不同關(guān)鍵詞可能會(huì)被發(fā)送到一個(gè)存儲單元中。拿上個(gè)例子來說，若m = 111， 因?yàn)?11整除(10^3 - 1) = 999，即10^3 ≡ 1(mod 111)所以64212848和64848212會(huì)被發(fā)送到一個(gè)存儲地址，因?yàn)?/p>

h(64848212) ≡ 64848212 ≡ 1124 ≡ 14(mod 111)

h(648212848) ≡ 64212848 ≡ 1124 ≡ 14(mod 111)

所以他們兩個(gè)都會(huì)存儲在14這個(gè)位置。為了避免這種麻煩，應(yīng)該找一個(gè)接近m的素?cái)?shù)。像上面這種情況叫做沖突。下面是對于散列函數(shù)實(shí)現(xiàn)的代碼演示

我們再談?wù)摚鉀Q沖突的方法

分離鏈接：

散列表，也可以看作一個(gè)線性表，借助線性表的思想，我們進(jìn)行改進(jìn)

其思想是，將散列沖突的元素保留在一個(gè)單鏈表中，這些表都有表頭

舉例說明：假設(shè)關(guān)鍵字是前10個(gè)完全平方數(shù)并設(shè)散列函數(shù)就是h(X) = X(mod 10)(表的大小不是素?cái)?shù)是為了簡單起見)如下圖所示

?以下是表的類型聲明代碼：

散列表初始化：

?散列表查找Find函數(shù)

插入操作

刪除是鏈表中的刪除操作直接實(shí)現(xiàn)，就不多贅述?

總結(jié)：分離鏈表的操作很像鏈表和棧的結(jié)合，另外這個(gè)insert函數(shù)計(jì)算了兩次散列函數(shù)，多余的計(jì)算其實(shí)是沒必要的。

當(dāng)然，還有開放定址法，線性探測法（需要微積分知識），平方探測法等等