Hash（哈希）相關知識（哈希函數、哈希查找）

Hash（哈希）相關知識

• 前言
• 一. 哈希函數
• • 1. 函數特性
  • • 1.1 基本的哈希函數
    • 1.2 加密的哈希函數
  • 2. 常見的哈希函數構造法
  • • 2.1 直接尋址法
    • 2.2 數字分析法
    • 2.3 平方取中法
    • 2.4 折疊法
    • 2.5 随機數法
    • 2.6 除留餘數法
    • 2.7 加密哈希函數
  • 3. 哈希函數總結
• 二. 哈希查找
• • 1. 操作步驟
  • 2.哈希表的查找
  • • 2.1 哈希沖突
    • • 2.1.1 開放尋址法
      • 2.1.2 鍊位址法
      • 2.1.3 再散列法
      • 2.1.4 建立公共溢出區
    • 2.2 裝填因子
• 三. 總結

前言

• 因為本人是小白(小菜雞)，是以有些地方說的可能不是很準确，大家可以參考一些很厲害的部落客，在評論區指出我寫的不對的地方。
• 本來是想要單獨寫一下Hash(哈希)查找算法，但後來想到Java和區塊鍊的入門裡面都涉及到Hash，是以就說一下自己對Hash的了解。
• 在寫的過程中，有涉及到密碼學的相關概念，我盡力用舉例子的方式讓讀者明白，如果覺得我有哪裡說的不準确，可以查找相關文獻進行更深層次的了解，以免我誤人子弟，順便謝謝大家啦！

一. 哈希函數

1. 函數特性

1.1 基本的哈希函數

• 哈希函數是一個數學函數，特性有下面三點：
• 其輸入可為任意大小的字元串。
• 它産生固定大小的輸出。
• 它能進行有效的計算，就是說對于特定的輸入字元串，在合理時間内，能夠計算出哈希函數的輸出，對n位的字元串，哈希值計算的複雜度是O(n)。

1.2 加密的哈希函數

• 主要有附加的三個特性(相關文字說明源于BITCOIN AND CRYPTOCURRENCY TECHNOLOGIES 區塊鍊技術驅動金融-數字貨币與智能合約技術)：
• 碰撞阻力：對于兩個不同的輸入，能夠産生相同的輸出，就像y=x2，key1≠key2，但是産生了H(key1)=H(key2)。實際上世界上根本不存在具有防碰撞特性的哈希函數，現在技術上所用的加密哈希函數隻不過是還沒有找到碰撞的函數，就像之前人們都用的MD5，在前幾年找到了碰撞後就逐漸淡出市場。
• 隐秘性：如果我們無法通過輸出y=H(x)來找到輸入x，那麼就保證了隐秘性。但要滿足這樣條件的x必須取自一個非常大的集合，否則x将很容易就被擷取。例如，我們抛硬币，隻需要知道結果就很容易窮舉出x的确定值。
• 謎題友好：這個特性聽起來是人畜無害的，其實用我的話來解釋就是盲目的窮舉一個巨大無比的資料集，而要求是要找到一個小區域内的值。用人話來說就是，給你一個地球這麼大的區域，讓你通過窮舉來尋找你家小區或者一個超市或者一個城市的區域，這個所要尋找的區域往往越小，難度越高(正常人都能看出來)。而這個謎題取自哪裡也非常重要，謎題往往取自高階最小熵分布，這樣就保證了沒有捷徑能走。

2. 常見的哈希函數構造法

• 相信大家都接觸過資料結構，在那裡面講到過很多種建構哈希函數的方法和存儲方式，咱也列舉一下(有的是複制粘貼的，因為在資料結構中都有講到)。
• 百度詞條：哈希表和相應問題處理方法

2.1 直接尋址法

• 取關鍵字或關鍵字的某個線性函數值為散列位址。即hash(k) = k 或 hash(k) = a · k + b，其中a、b為常數(這種散列函數叫做自身函數)。

2.2 數字分析法

• 這種方法是對重複性比較高的位進行查找，然後多選幾位組成哈希位址，避免沖突增加。

2.3 平方取中法

• 取關鍵字平方後的中間幾位為哈希位址。通常在標明哈希函數時不一定能知道關鍵字的全部情況，取其中的哪幾位也不一定合适，而一個數平方後的中間幾位數和數的每一位都相關，由此使随機分布的關鍵字得到的哈希位址也是随機的。取的位數由表長決定。

2.4 折疊法

• 将關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（舍去進位）作為哈希位址。

2.5 随機數法

• 選擇一個随機函數，取關鍵字的随機函數值作為它的哈希位址，即H(key)=random(key)，其中random為随機函數。通常用于關鍵字長度不等時的場合。

2.6 除留餘數法

• 取關鍵字被某個不大于哈希表表長m的數p除後所得餘數為哈希位址。即H(key)=key MOD p(p<=m)。
• 不僅可以對關鍵字直接取模，也可在折疊法、平方取中法等運算之後取模。對p的選擇很重要，一般取素數或m，若p選擇不好，容易産生沖突。

2.7 加密哈希函數

• 這裡介紹安全雜湊演算法(SHA - 256),主要是被比特币采用的哈希函數。
• 與它相關的概念叫壓縮函數(compression function)。在通用術語中，将接受固定長度的哈希函數轉化為可接受任意長度輸入的哈希函數，這種轉換過程叫MD(Merkle-Damgard)變換。一般來說這種基礎型，可用于固定長度，并且具備碰撞阻力的哈希函數就是壓縮函數。
• SHA - 256就是利用了壓縮函數将一個768位的輸入壓縮成256位的輸出，每一個區塊的大小是512位。
• 對于以上所說的知識，可以在百度上搜，或者看區塊鍊的書。

3. 哈希函數總結

• 哈希函數并不是越複雜越好，而是根據需求進行設計和使用，因為哈希函數越複雜，時間消耗越長，對性能也有一定的影響。

二. 哈希查找

1. 操作步驟

• 用給定的哈希函數構造哈希表。
• 根據選擇的沖突處理方法解決位址沖突。
• 在哈希表的基礎上執行哈希查找。

2.哈希表的查找

• 哈希表的查找效率主要取決于哈希函數的構造方式、處理沖突的方式和裝填因子。

2.1 哈希沖突

• 其實原理就是上面講的碰撞，為了處理沖突，有這幾種處理方法：
• 百度詞條：哈希查找，這裡面講的還可以，有資源的可以在網上找具體操作，當然資料結構中的hash也講過這幾個方法，可以去找課件和書。

• 

2.1.1 開放尋址法

• 如果産生沖突，就找個空位址塞進去，當然要保證散列位址足夠大。
• 這種方法細分為3種，分别是線性探測再散列、二次探測再散列、僞随機探測再散列，詳細的設計方法和原理在上面的連結裡也有。

2.1.2 鍊位址法

• 将所有同關鍵字的記錄存儲在一個單連結清單中，稱這種表為同義詞子表，在散清單中隻存儲所有同義詞子表的頭指針。
• 這種方法有點像用連結清單構成樹。

2.1.3 再散列法

• 提前準備多個散列函數，如果其中一個找不到合适的位置，那就換一個散列函數。

2.1.4 建立公共溢出區

• 粗暴方式，隻要發生沖突就填進公共溢出區。

2.2 裝填因子

• 散清單的裝填因子定義為：α= 填入表中的元素個數 / 散清單的長度
• α是散清單裝滿程度的标志因子。
• 由于表長是定值，α與填入表中的元素個數成正比，是以，α越大，填入表中的元素較多，産生沖突的可能性就越大；α越小，填入表中的元素較少，産生沖突的可能性就越小。
• 實際上，散清單的平均查找長度是裝填因子α的函數，隻是不同處理沖突的方法有不同的函數。

三. 總結

• HashMap就是由數組+連結清單組合成的，也就是鍊位址法，在這篇裡主要講的就是哈希相關的東西，HashMap改天再說。
• 哈希函數的構造不是越複雜越好，合适就行了，因為不同的應用由不同的需求，根據需求選擇合适的結構就行了，性能方面也要考慮，例如HashMap隻要盡量的減少它的連結清單就能提高它執行的性能。