hash位址_Hash算法基礎

​1.Hash介紹

Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入，通過雜湊演算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，是以不可能從散列值來唯一的确定輸入值。簡單的說就是一種将任意長度的消息壓縮到某一固定長度的消息摘要的函數。

所有散列函數都有如下一個基本特性：根據同一散列函數計算出的散列值如果不同，那麼輸入值肯定也不同。但是，根據同一散列函數計算出的散列值如果相同，輸入值不一定相同。

碰撞

兩個不同的輸入值，根據同一散列函數計算出的散列值相同的現象叫做碰撞。

壓縮映射

設(X, ρ)為距離空間，T是X到X中的映射，如果存在數a(0<a<1)，使得對所有的x,y∈X都有ρ(Tx, Ty)≤a*ρ(x, y)，則稱T是壓縮映射，壓縮映射也稱為利普希茨映射。

例子

舉個簡單的例子，新華字典，我們查字典的時候，如果按照拼音去查找（當然按照偏旁部首去查找也是一樣），比如查找“位”，按照拼音表，W開頭的拼音

按照步驟來，應該首先去查W開頭的拼音，然後去查找wei的位置，然後在找到“位”，這個過程就是鍵碼映射，在wei鍵值下有很多字，這些字存儲的時候産生了“碰撞”， 在公式裡面，就是通過key去查找f(key)。其中，wei就是關鍵字（key），f（）就是字典索引，也就是哈希函數，查到的頁碼就是哈希值。

2.Hash沖突

剛剛查字的時候，發現wei下有很多字，問題就來了，我們要查的是“位”，而不是“未“，但是他們的拼音是一樣的。也就是通過關鍵字”位“和關鍵字”未“可以映射到一樣的字典頁碼的位置，這就是哈希沖突（也叫哈希碰撞），在公式上表達就是key1≠key2，但f(key1)=f(key2)。沖突會給查找帶來麻煩，你想想，你本來查找的是“位”，但是卻找到“未”字，你又得向後翻一兩頁，在計算機裡面也是一樣道理的。

但哈希沖突是無可避免的，為什麼這麼說呢，因為你如果要完全避開這種情況，你隻能每個字典去新開一個頁，然後每個字在索引裡面都有對應的頁碼，這就可以避免沖突。但是會導緻空間增大（每個字都有一頁）。

既然無法避免，就隻能盡量減少沖突帶來的損失，而一個好的哈希函數需要有以下特點：

1. 盡量使關鍵字對應的記錄均勻配置設定在哈希表裡面（比如說某廠商賣30棟房子，均勻劃分ABC3個區域，如果你劃分A區域1個房子，B區域1個房子，C區域28個房子，有人來查找C區域的某個房子最壞的情況就是要找28次）。
2. 關鍵字極小的變化可以引起哈希值極大的變化。

Hash函數

此條來自于百度，Hash函數的建立有很多學問，這裡隻是幫大家了解一下，這些均來自資料結構中的知識！

散列函數能使對一個資料序列的通路過程更加迅速有效，通過散列函數，資料元素将被更快地定位。常用Hash函數有：

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選的不好，容易産生碰撞。

Time33算法

這是一個對字元串進行哈希的函數，現在幾乎所有流行的HashMap都采用了DJB Hash Function，俗稱“Times33”算法。Times33的算法很簡單，就是對字元串進行逐個字元周遊，不斷的乘33，然後把數值相加即可。

核心的算法就是如下：

unsigned long hash(const char* key){
    unsigned long hash=0;
    for(int i=0;i<strlen(key);i++){
        hash = hash*33+str[i];
    }  
    return hash;
}
           

3.Hash沖突解決

處理沖突方法

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=12,-12,22,-22,32,…，±k2,(k<=m/2)稱二次探測再散列；
   3. di=僞随機數序列，稱僞随機探測再散列。
2. 再散列法：Hi=RHi(key),i=1,2,…，k RHi均是不同的散列函數，即在同義詞産生位址沖突時計算另一個散列函數位址，直到沖突不再發生，這種方法不易産生“聚集”，但增加了計算時間。
3. 鍊位址法(拉鍊法)
4. 建立一個公共溢出區

最常用的就是開發定址法和鍊位址法。

開放定址法

為了使用開放定址法插入一個元素，需要連續的檢查散清單，直到找到一個新的空槽來放置帶插入的元素為止。檢查的順序不一定是0,1,2,…,m-1的這種順序，而是要依賴待插入的關鍵字key,為了确定探查哪些槽，我們将散列函數加以擴充，使之包含探查号作為第二個輸入參數，

下圖示範的是線性探測解決沖突的方法：

二次探測和僞随機數法和線性探測的模式相同，隻是在沖突後，選取平方數和随機數進行探測

鍊位址法

上面所說的開發定址法的原理是遇到沖突的時候查找順着原來哈希位址查找下一個空閑位址然後插入，但是也有一個問題就是如果空間不足，那他無法處理沖突也無法插入資料，是以需要裝填因子(插入資料/空間)<=1。

那有沒有一種方法可以解決這種問題呢？鍊位址法可以，鍊位址法的原理時如果遇到沖突，他就會在原位址建立一個空間，然後以連結清單結點的形式插入到該空間。我感覺業界上用的最多的就是鍊位址法。下面從百度上截取來一張圖檔，可以很清晰明了反應下面的結構。比如說我有一堆資料{1,12,26,337,353…}，而我的雜湊演算法是H(key)=key mod 16，第一個資料1的哈希值f(1)=1，插入到1結點的後面，第二個資料12的哈希值f(12)=12，插入到12結點，第三個資料26的哈希值f(26)=10，插入到10結點後面，第4個資料337，計算得到哈希值是1，遇到沖突，但是依然隻需要找到該1結點的最後鍊結點插入即可，同理353。

開放定址法的所有元素都存在于散清單之内，每一個表項要麼存在元素，要麼就為空，當發生映射值沖突的時候我們可以探查新的位置。最好的探查方法是雙重散列，因為雙重散列産生的探查序列足夠随機，不像線性探查和二次探查哪樣存在較為嚴重的群集現象。

開放定址法相對于連結法來說，可以将存儲連結清單指針的記憶體空出來存儲更多的資料，直接跳過了指針的操作，而是用數組的直接通路來通路元素，但是如果探查散列函數設計差勁的話，将會嚴重拖慢散清單的速度！

4.Hash查找性能

散清單的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數轉換的位址直接找到，另一些關鍵碼在散列函數得到的位址上産生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，産生沖突後的查找仍然是給定值與關鍵碼進行比較的過程。是以，對散清單查找效率的量度，依然用平均查找長度來衡量。

查找過程中，關鍵碼的比較次數，取決于産生沖突的多少，産生的沖突少，查找效率就高，産生的沖突多，查找效率就低。是以，影響産生沖突多少的因素，也就是影響查找效率的因素。影響産生沖突多少有以下三個因素：

1. 散列函數是否均勻；
2. 處理沖突的方法；

3. 散清單的裝填因子。

   散清單的裝填因子定義為：α= 填入表中的元素個數/散清單的長度

   α是散清單裝滿程度的标志因子。由于表長是定值，α與“填入表中的元素個數”成正比，是以，α越大，填入表中的元素較多，産生沖突的可能性就越大；α越小，填入表中的元素較少，産生沖突的可能性就越小。

   實際上，散清單的平均查找長度是裝填因子α的函數，隻是不同處理沖突的方法有不同的函數。

由于哈希表高效的特性，查找或者插入的情況在大多數情況下可以達到O(1)，時間主要花在計算hash上，當然也有最壞的情況就是hash值全都映射到同一個位址上，這樣哈希表就會退化成連結清單，查找的時間複雜度變成O(n)，但是這種情況比較少，隻要不要把hash計算的公式外漏出去并且有人故意攻擊（用興趣的人可以搜一下基于哈希沖突的拒絕服務攻擊），一般也不會出現這種情況。

如圖所示，哈希沖突攻擊導緻退化成連結清單