聲明：版權所有，歡迎轉載。 聯系信箱：[email protected]】
在數據查找中我們會想到很多不錯的、行之有效的方法，大體分為以下幾種，1、對於空間連續的數據采用二分查找法等是比較不錯的。2、對於空間不連續的采用排序二叉樹也是不錯的方法。3、但是對於空間不連續的而且數據量相當大時，如果依然采用上述兩種方法顯然就有點力不從心了，當然了我們可以采用哈希表查詢的方式。哈希表及繼承了數組易於定位查找的有點又兼顧了鏈表易於增刪等優點。
什麼是Hash：
Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
HASH主要用於信息安全領域中加密算法，它把一些不同長度的信息轉化成雜亂的128位的編碼,這些編碼值叫做HASH值. 也可以說，hash就是找到一種數據內容和數據存放地址之間的映射關系。
數組的特點是：尋址容易，插入和刪除困難；而鏈表的特點是：尋址困難，插入和刪除容易。那麼我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數據結構？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實現方法，我接下來解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數組”，如圖：
左邊很明顯是個數組，數組的每個成員包括一個指針，指向一個鏈表的頭，當然這個鏈表可能為空，也可能元素很多。我們根據元素的一些特征把元素分配到不同的鏈表中去，也是根據這些特征，找到正確的鏈表，再從鏈表中找出這個元素。
元素特征轉變為數組下標的方法就是散列法。散列法當然不止一種，下面列出三種
比較常用的：
1，除法散列法
最直觀的一種，上圖使用的就是這種散列法，公式：
index = value % 16
學過匯編的都知道，求模數其實是通過一個除法運算得到的，所以叫“除法散列法”。
2，平方散列法
求index是非常頻繁的操作，而乘法的運算要比除法來得省時對現在的CPU來說，估計我們感覺不出來），所以我們考慮把除法換成乘法和一個位移操作。公式： index = (value * value) >> 28 右移，除以2^28。記法：左移變大，是乘。右移變小，是除。）如果數值分配比較均勻的話這種方法能得到不錯的結果，但我上面畫的那個圖的各個元素的值算出來的index都是0——非常失敗。也許你還有個問題，value如果很大，value * value不會溢出嗎？答案是會的，但我們這個乘法不關心溢出，因為我們根本不是為了獲取相乘結果，而是為了獲取index。
3，斐波那契Fibonacci）散列法
平方散列法的缺點是顯而易見的，所以我們能不能找出一個理想的乘數，而不是拿value本身當作乘數呢？答案是肯定的。
1，對於16位整數而言，這個乘數是40503
2，對於32位整數而言，這個乘數是2654435769
3，對於64位整數而言，這個乘數是11400714819323198485
這幾個“理想乘數”是如何得出來的呢？這跟一個法則有關，叫黃金分割法則，而描述黃金分割法則的最經典表達式無疑就是著名的斐波那契數列，即如此形式的序列：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610， 987, 1597,
2584, 4181, 6765, 10946，…。另外，斐波那契數列的值和太陽系八大行星的軌道半
徑的比例出奇吻合。
對我們常見的32位整數而言，公式：
index = (value * 2654435769) >> 28
如果用這種斐波那契散列法的話，那上面的圖就變成這樣了：
很明顯，用斐波那契散列法調整之後要比原來的取摸散列法好很多。
適用范圍：
快速查找，刪除的基本數據結構，通常需要總數據量可以放入內存。
基本原理及要點：
hash函數選擇，針對字符串，整數，排列，具體相應的hash方法。碰撞處理，一種是open hashing，也稱為拉鏈法；另一種就是closed hashing，也稱開地址法，opened addressing。
擴展 ：
d-left hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數，h1和h2。在存儲一個新的key時，同 時用兩個哈希函數進行計算，得出兩個地址h1[key]和h2[key]。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個 位置已經存儲的有碰撞的）key比較多，然後將新key存儲在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key 存儲在左邊的T1子表中，2-left也由此而來。在查找一個key時，必須進行兩次hash，同時查找兩個位置。
本文出自 “驿落黃昏” 博客，請務必保留此出處http://yiluohuanghun.blog.51cto.com/3407300/1258577
