七、哈希表（Hash Table）及散列法（Hashing）
數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；而鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實(shí)現(xiàn)方法，我接下來解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數(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é)過匯編的都知道，求模數(shù)其實(shí)是通過一個(gè)除法運(yùn)算得到的，所以叫“除法散列法”。
2，平方散列法
求index是非常頻繁的操作，而乘法的運(yùn)算要比除法來得省時(shí)（對(duì)現(xiàn)在的CPU來說，估計(jì)我們感覺不出來），所以我們考慮把除法換成乘法和一個(gè)位移操作。公式：
index = (value * value) >> 28
如果數(shù)值分配比較均勻的話這種方法能得到不錯(cuò)的結(jié)果，但我上面畫的那個(gè)圖的各個(gè)元素的值算出來的index都是0——非常失敗。也許你還有個(gè)問題，value如果很大，value * value不會(huì)溢出嗎？答案是會(huì)的，但我們這個(gè)乘法不關(guān)心溢出，因?yàn)槲覀兏静皇菫榱双@取相乘結(jié)果，而是為了獲取index。
3，斐波那契（Fibonacci）散列法
平方散列法的缺點(diǎ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ù)”是如何得出來的呢？這跟一個(gè)法則有關(guān)，叫黃金分割法則，而描述黃金分割法則的最經(jīng)典表達(dá)式無疑就是著名的斐波那契數(shù)列，如果你還有興趣，就到網(wǎng)上查找一下“斐波那契數(shù)列”等關(guān)鍵字，我數(shù)學(xué)水平有限，不知道怎么描述清楚為什么，另外斐波那契數(shù)列的值居然和太陽(yáng)系八大行星的軌道半徑的比例出奇吻合，很神奇，對(duì)么？
對(duì)我們常見的32位整數(shù)而言，公式：
index = (value * 2654435769) >> 28
如果用這種斐波那契散列法的話，那我上面的圖就變成這樣了：
看起來不錯(cuò)，以后就用斐波那契散列法吧。
不過我們要注意了，前面提到的都是針對(duì)整數(shù)的散列法，那如果不是整數(shù)呢？下面給出一些參考算法，我把其它類型的數(shù)據(jù)轉(zhuǎn)變?yōu)?2位整數(shù)，之后的處理前面已經(jīng)說了。
1，浮點(diǎn)數(shù)的散列法
unsigned int HashingDouble(double d)
{
if (d==0)
return 0;
else
{
int exponent;
double mantissa = frexp(d, &exponent);
return (unsigned int)((2*mantissa-1) * (~0U));
}
}
2，字符串的散列法
unsigned int HashingString(char *str, int iLen)
{
unsigned int hsval = 2654435769;
int i;
int iShift = 0;
for(i=0; i<iLen; i++)
{
hsval ^= (str[i]<<iShift);
iShift+=3;
if(iShift>24)
iShift=0;
}
return hsval;
}
方法就提供那么多，遇到別的情況，比如說Unicode字符串，隨機(jī)應(yīng)變吧！