一、哈希表了解：
哈希表，别名散清單，是根據關鍵碼值直接進行通路的資料結構，也就是說，它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散清單。
資料結構中，有個時間算法複雜度O(n)的概念來衡量某種算法在時間效率上的優劣。哈希表的理想算法複雜度為O(1)，也就是說利用哈希表查找某個值，系統所使用的時間在理想情況下為定值，這就是它的優勢。那麼哈希表是如何做到這一點的呢？
我們定義一個很大的有序數組，想要得到位于該數組第n個位置的值，它的算法複雜度為O(1)。哈希表利用哈希函數将需要存儲的内容的關鍵值轉換為這個有序數組中的某個值（實作方法：哈希表做法其實很簡單，就是把Key通過一個固定的算法函數既所謂的哈希函數轉換成一個整型數字，然後就将該數字對數組長度進行取餘，取餘結果就當作數組的下标，将value存儲在以該數字為下标的數組空間裡；而當使用哈希表進行查詢的時候，就是再次使用哈希函數将key轉換為對應的數組下标，并定位到該空間擷取value，如此一來，就可以充分利用到數組的定位性能進行資料定位。），在被存儲内容和有序數組之間建立了映射關系。這樣，下次我們對這個值進行查找時隻要使用同一個哈希函數對關鍵值進行轉換，找到這個數組值 就可以了。
如果還沒有明白是怎麼回事的話，那我們來舉個例子。假設我們要做個存儲結構，需要存儲下來三國中的人物，以及他們的詳細資訊。我們用他們的名字來作為存儲 的關鍵值，例如：劉備，曹操，孫權，關羽，張飛……等等。這個時候我們如果想用一般的方法來查找這些英雄豪傑，需要周遊整個存儲空間，如果這些英雄豪傑一 共有n個，那麼這時候的時間算法複雜度為O(n)。顯然如果n值很大，每次想要找到某個英雄就需要比較長的時間。
此時我們先定義一個大的有序結構數組HashValue[m]，用來存放各位英雄豪傑的資訊。然後編寫一個哈希函數ChangeToHashValue (name)，函數的具體内容就不細說了，反正這個函數會将這些做為關鍵值的名字轉換為HashValue[m]中的某個下标值x。然後可以将英雄的資訊 放進HashValue[x]中去。這樣，可以将所有英雄的資訊存儲起來。當查詢的時候再使用哈希函數ChangeToHashValue(name)得 到這個下标值，這樣就很容易得到了這個英雄的資訊。例如：ChangeToHashValue(劉備)為10，那麼就将劉備存儲到HashValue [10]裡面。當查詢的時候再次使用ChangeToHashValue(劉備)得到10，這個時候我們就可以很容易找到劉備的所有資訊。在實際應用中如 果我們想把所有的英雄豪傑都存儲進系統時，需要定義m>n。就是數組的大小要大于需要存儲的資訊量，是以說哈希表是一個以空間換取時間的資料結構。
這個時候問題來了，出現了這種情況ChangeToHashValue(關羽)和ChangeToHashValue(張飛)得到的值是一樣的，都是 250，我們豈不是在存儲過程中會遇到麻煩，怎麼安排他們二位的地方呢（總不能讓二位打一架，誰赢了誰呆在那吧），這就需要一個解決沖突的方法。當遇到這 種情況時我們可以這樣處理，先存儲好了關羽，當張飛進入系統時會發現關羽已經是250了，那咱就加一位，251得了，這不就解決了。我們查找張飛的時候也 是，一看250不是張飛，那就加個1，就找到了。這時還存在一個問題。直接用ChangeToHashValue(趙雲)為251，張飛已經早早占了他的 地方，那就再加1存到252呗。呵呵，這時我們會發現，當哈希函數沖突發生的機率很高時，可能會有一群英雄豪傑在250這個值後面紮堆排隊。要命的是查找 的時候，時間算法複雜度早已不是O(1)了（是以我們說理想情況下哈希表的時間算法複雜度為O(1)）。 這就是說哈希函數的編寫是哈希表的一個關鍵問題，會涉及到一個存儲值在哈希表中的統計分布。如果哈希函數已經定義好了，沖突的解決就成為了改變系統性能的 關鍵因素。其實還有很多種方法來解決沖突情況下的存儲和查找問題，不一定非要線性向後排隊，如果有好的哈希表沖突的解決方法也能很大程度上提高系統的效率。
二、雜湊演算法：
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
如果用這種斐波那契散列法的話，那上面的圖就變成這樣了：
注：用斐波那契散列法調整之後會比原來的取摸散列法好很多。
适用範圍
快速查找，删除的基本資料結構，通常需要總資料量可以放入記憶體。