在看哈希之前還是來看看“散列函數（哈希函數）”吧，后面會用到的。

解決沖突的方法。

      開放定址法。如果h(k)已經被占用，按如下序列探查：

      (h(k)+p(1))%TSize, (h(k)+p(2))%TSize, …,(h(k)+p(i))%TSize,…　

　　其中，h(k)為哈希函數，TSize為哈希表長，p(i)為探查函數。

      在 h(k)+p(i-1))%TSize的基礎上，若發現沖突，

　　則使用增量 p(i) 進行新的探測，直至無沖突出現為止。

　　其中，根據探查函數p(i)的不同，開放定址法又分為

      (1)線性探查法（p(i) = i : 1 , 2 , 3 , …），

　　 (2)二次探查法（p(i)=(-1)i-1((i+1)/2)2: 12 , -12 , 22 , -22 …），

      (3)隨機探查法（p(i): 隨機數 ），

　　 (4)雙散列函數法（雙散列函數h(key) ，

       hp (key)若h(key)出現沖突，則再使用hp (key)求取散列地址。

　 　探查序列為：h(k), h(k)+ hp(k),…, h(k)+ i*hp(k)）。

 

基本知識

　　Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，

     就是把任意長度的輸入（又叫做預映射， pre-image），

　　通過散列算法，變換成固定長度的輸出，該輸出就是散列值。

     這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，

　　不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。

　　簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

　　HASH主要用于信息安全領域中加密算法，

     它把一些不同長度的信息轉化成雜亂的128位的編碼，

　　這些編碼值叫做HASH值. 也可以說，

     hash就是找到一種數據內容和數據存放地址之間的映射關系

基本概念

　　　* 若結構中存在和關鍵字K相等的記錄，則必定在f(K)的存儲位置上。

           由此，不需比較便可直接取得所查記錄。

　　　　稱這個對應關系f為散列函數(Hash function)，

           按這個思想建立的表為散列表。

　　* 對不同的關鍵字可能得到同一散列地址，即key1≠key2，

        而f(key1)=f(key2)，這種現象稱沖突。

　　　具有相同函數值的關鍵字對該散列函數來說稱做同義詞。

　　　綜上所述，根據散列函數H(key)和處理沖突的方法將一組關鍵字

        映象到一個有限的連續的地址集（區間）上，

　　  并以關鍵字在地址集中的“象” 作為記錄在表中的存儲位置，

       這種表便稱為散列表，這一映象過程稱為散列造表或散列，

　　  所得的存儲位置稱散列地址。

 

　　* 若對于關鍵字集合中的任一個關鍵字，

        經散列函數映象到地址集合中任何一個地址的概率是相等的，

　　   則稱此類散列函數為均勻散列函數(Uniform Hash function)，

        這就是使關鍵字經過散列函數得到一個“隨機的地址”，從而減少沖突。

　　   常用的構造散列函數的方法

　　   散列函數能使對一個數據序列的訪問過程更加迅速有效，

        通過散列函數，數據元素將被更快地定位ǐ

　　1． 直接尋址法：取關鍵字或關鍵字的某個線性函數值為散列地址。

           即H(key)=key或H(key) = a·key + b，

　　　　其中a和b為常數（這種散列函數叫做自身函數）

　　2． 數字分析法

　　3． 平方取中法

　　4． 折疊法

　　5． 隨機數法

　　6． 除留余數法：取關鍵字被某個不大于散列表表長m的數p除后所得的余數為散列地址。

　　　　即 H(key) = key MOD p,p<=m。不僅可以對關鍵字直接取模，

          也可在折疊、平方取中等運算之后取模。

　　　　對p的選擇很重要，一般取素數或m，若p選的不好，容易產生同義詞。

處理沖突的方法

      1． 開放尋址法；Hi=(H(key) + di) MOD m,i=1,2,…，k(k<=m-1)，

          其中H(key)為散列函數，m為散列表長，di為增量序列，

　　    可有下列三種取法：

　    　1． di=1,2,3,…，m-1，稱線性探測再散列；

　       2． di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…，±(k)^2,(k<=m/2)稱二次探測再散列；

　       3． di=偽隨機數序列，稱偽隨機探測再散列。==

　　2． 再散列法：Hi=RHi(key),i=1,2,…，k RHi均是不同的散列函數，

            即在同義詞產生地址沖突時計算另一個散列函數地址，

　　　　直到沖突不再發生，這種方法不易產生“聚集”，但增加了計算時間。

　　3． 鏈地址法(拉鏈法)

　   4． 建立一個公共溢出區