七、哈希表（Hash Table）及散列法（Hashing）

數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；而鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實(shí)現(xiàn)方法，我接下來(lái)解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數(shù)組”，如圖：

左邊很明顯是個(gè)數(shù)組，數(shù)組的每個(gè)成員包括一個(gè)指針，指向一個(gè)鏈表的頭，當(dāng)然這個(gè)鏈表可能為空，也可能元素很多。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征，找到正確的鏈表，再?gòu)逆湵碇姓页鲞@個(gè)元素。

元素特征轉(zhuǎn)變?yōu)閿?shù)組下標(biāo)的方法就是散列法。散列法當(dāng)然不止一種，我下面列出三種比較常用的。

1，除法散列法
最直觀的一種，上圖使用的就是這種散列法，公式：
index = value % 16
學(xué)過(guò)匯編的都知道，求模數(shù)其實(shí)是通過(guò)一個(gè)除法運(yùn)算得到的，所以叫“除法散列法”。

2，平方散列法
求index是非常頻繁的操作，而乘法的運(yùn)算要比除法來(lái)得省時(shí)（對(duì)現(xiàn)在的CPU來(lái)說(shuō)，估計(jì)我們感覺(jué)不出來(lái)），所以我們考慮把除法換成乘法和一個(gè)位移操作。公式：
index = (value * value) >> 28
如果數(shù)值分配比較均勻的話這種方法能得到不錯(cuò)的結(jié)果，但我上面畫的那個(gè)圖的各個(gè)元素的值算出來(lái)的index都是0——非常失敗。也許你還有個(gè)問(wèn)題，value如果很大，value * value不會(huì)溢出嗎？答案是會(huì)的，但我們這個(gè)乘法不關(guān)心溢出，因?yàn)槲覀兏静皇菫榱双@取相乘結(jié)果，而是為了獲取index。

3，斐波那契（Fibonacci）散列法

平方散列法的缺點(diǎn)是顯而易見(jiàn)的，所以我們能不能找出一個(gè)理想的乘數(shù)，而不是拿value本身當(dāng)作乘數(shù)呢？答案是肯定的。

1，對(duì)于16位整數(shù)而言，這個(gè)乘數(shù)是40503
2，對(duì)于32位整數(shù)而言，這個(gè)乘數(shù)是2654435769
3，對(duì)于64位整數(shù)而言，這個(gè)乘數(shù)是11400714819323198485

這幾個(gè)“理想乘數(shù)”是如何得出來(lái)的呢？這跟一個(gè)法則有關(guān)，叫黃金分割法則，而描述黃金分割法則的最經(jīng)典表達(dá)式無(wú)疑就是著名的斐波那契數(shù)列，如果你還有興趣，就到網(wǎng)上查找一下“斐波那契數(shù)列”等關(guān)鍵字，我數(shù)學(xué)水平有限，不知道怎么描述清楚為什么，另外斐波那契數(shù)列的值居然和太陽(yáng)系八大行星的軌道半徑的比例出奇吻合，很神奇，對(duì)么？

對(duì)我們常見(jiàn)的32位整數(shù)而言，公式：
index = (value * 2654435769) >> 28

如果用這種斐波那契散列法的話，那我上面的圖就變成這樣了：

看起來(lái)不錯(cuò)，以后就用斐波那契散列法吧。

不過(guò)我們要注意了，前面提到的都是針對(duì)整數(shù)的散列法，那如果不是整數(shù)呢？下面給出一些參考算法，我把其它類型的數(shù)據(jù)轉(zhuǎn)變?yōu)?2位整數(shù)，之后的處理前面已經(jīng)說(shuō)了。

1，浮點(diǎn)數(shù)的散列法

2，字符串的散列法

方法就提供那么多，遇到別的情況，比如說(shuō)Unicode字符串，隨機(jī)應(yīng)變吧！