哈希函數和哈希表

2021-02-23 算法工程師之路

筆者在讀研剛開始的時候，偶爾看面經，有這樣一個問題：只用2GB內存在20億個整數中找到出現次數最多的數，當時的我一臉懵逼，怎麼去思考，20億個數？What The Fuck! 但是，看完今天的文章，你或許就會覺得原來也不過如此啊！其核心就是哈希函數和哈希表的應用！

哈希函數

哈希函數又稱為散列函數，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。假設輸出值域為S，哈希函數的性質如下：

典型的哈希函數都有無限的輸入值域

當哈希函數輸入一致時，輸出必相同

當哈希函數傳入不同的輸入值時，返回值可能一樣，也可能不一樣，由於輸入域遠大於值域

（重要）很多的不同輸入所得的輸出值會均勻的分布在S上（但不是絕對均勻）

最後一個性質對於一個優秀的哈希函數是非常重要的，並且這種均勻與數據的輸入規律無關。比如「aa1」、"aa2"經過hash後可能結果會相差很多，當一個哈希函數的輸出在S中是均勻的，那麼我們將輸出值對m取餘（%m），就會將不定長輸入映射到0～m-1空間中，並且在這個空間也保持均勻分布！哈希表就是這麼做的，一會再說！哈希函數還有以下特點：

免碰撞：即不會出現輸入 x≠y ，但是H(x)=H(y) 的情況，其實這個特點在理論上並不成立，比如目前比特幣使用的 SHA256 算法，會有2^256種輸出，如果我們進行2^256 + 1 次輸入，那麼必然會產生一次碰撞，事實上，通過 理論證明 ，通過2^130次輸入就會有99%的可能性發生一次碰撞，不過即使如此，即便是人類製造的所有計算機自宇宙誕生開始一直運算到今天，發生一次碰撞的機率也是極其微小的。

隱匿性：也就是說，對於一個給定的輸出結果 H(x) ，想要逆推出輸入 x ，在計算上是不可能的。如果想要得到 H(x) 的可能的原輸入，不存在比窮舉更好的方法。

常見的哈希函數有：SHA1、MD5、SHA2等

哈希函數映射哈希表

哈希表就是利用哈希函數，可以根據關鍵碼而直接進行訪問的數據結構，也就是將關鍵碼（Key value）通過哈希函數映射到表中的一個位置來進行訪問。由於是直接訪問，所以對於哈希表的元素理論上的增刪改查時間複雜度都是O(1)。


而計算散列地址的方法有很多種，通常我們使用的是除留餘數法，也就是說使用哈希函數對關鍵字得到的輸出值對散列表長度取餘得到的餘數即為散列地址。哈希衝突

由於我們的輸入長度和範圍是任意的，但是經過哈希函數後的輸出值域是固定的，所以必然會產生衝突。如上圖的buckets152（紅色區域）就相當於發生衝突！處理衝突的方法有：

我們來說下拉鏈法，也如上圖所示，拉鏈法的思路很簡單，就是當發生哈希衝突後，會在當前地址區域建立一個鍊表，將衝突目標添加到鍊表中去。這種方式也不太好，當衝突發生過多時，鍊表的查找方式效率也就不是很高了！
因此對於JAVA中（C++標準中沒有hashmap，只有第三方的），hashmap的實現也是類似，但是有一點改進，也就是如果發生衝突，將衝突對象添加到鍊表，假設衝突個數達到了8次，那麼就會使用紅黑樹來代替鍊表，以加快查找速度。衝突個數少時，沒有必要使用紅黑樹。

C++中的hash_map

c++的hash_map和map的用法很類似，但一定要區別，map和hash_map雖然都是key-value形式，但是map的底層是紅黑樹，而hash_map的底層是hash表！
如果在Linux下使用hash_map，一定要加上一個__gnu_cxx的命名空間聲明！

#include<iostream>
#include<hash_map>

using namespace __gnu_cxx;    

using namespace std;

int main(int args, char** argv){
    hash_map<int, string>* has = new hash_map<int, string>;
    has->insert(make_pair(32, "zhang"));
    has->insert({0, "teddy"});     

    auto res = has->find(0);
    auto res2 = has->find(32);
    cout << res->second << endl;
    cout << res2->second << endl;

    return 0;
}

題目：2G內存下在20億數據中找到出現次數最多的數

首先我們確定value的範圍，如果一個數出現了20億次，那麼value就為20億次。因此我們使用32位的正整型，也就是4B的空間，同理key也是4B的空間，因此一條記錄（Entry）需要8B的空間，當記錄為20億個時，需要至少16GB的內存。
在極端最差的狀態，20億個數都不相同，那麼哈希表中可能會有20億條記錄，這樣的話顯然內存不足，因此一次性統計20個數風險很大。
解決方案：將包含有20億個數的大文件分成16個小文件，利用哈希函數，這樣的話，同一個重複的數肯定不會分到不同的文件中去，並且，如果哈希函數足夠好，那麼這16個文件中不同的數也不會大於2億（20 / 16）。然後我們在這16個文件中依次統計就可以了，最後進行匯總得到重複數最多的數。當然如果使用分布式系統，那麼可以利用哈希函數將這些數據分配到不同的電腦上去！
資源連結
如果想要看更多精彩內容，請關注我的個人公眾號 （算法工程師之路）希望大家多多支持哦~

公眾號簡介：分享算法工程師必備技能，談談那些有深度有意思的算法，主要範圍：C++數據結構與算法/深度學習（CV），立志成為Offer收割機！堅持分享算法題目和解題思路（Day By Day)

相關焦點

  • 哈希函數
    接下來，理解哈希函數的根本含義￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣前面講的查找方法，不管是靜態查找還是動態查找，其根本思想是將待查的關鍵字key與表中元素的關鍵字相比較，根據比較的結果得出查找成功或不成功
  • 哈希表(散列表)詳解(包含哈希表處理衝突的方法)
    對於哈希表而言，衝突只能儘可能地少，無法完全避免。哈希函數的構造常用的哈希函數的構造方法有 6 種：直接定址法、數字分析法、平方取中法、摺疊法、除留餘數法和隨機數法。直接定址法：其哈希函數為一次函數，即以下兩種形式：H（key）= key 或者 H（key）=a * key + b其中 H（key）表示關鍵字為 key 對應的哈希地址，a 和 b 都為常數。
  • 深入理解哈希表
    有些計算機常識的讀者都會立刻回答: 「一樣快，底層都用了哈希表，查找的時間複雜度為 O(1)」。然而實際情況真的是這樣麼？答案是否定的，存在少部分情況兩者速度不一致，本文首先對哈希表做一個簡短的總結，然後思考 Java 和 Redis 中對哈希表的實現，最後再得出結論，如果對某個話題已經很熟悉，可以直接跳到文章末尾的對比和總結部分。
  • 詳解哈希表的查找
    哈希表和哈希函數在記錄的存儲位置和它的關鍵字之間是建立一個確定的對應關係（映射函數），使每個關鍵字和一個存儲位置能唯一對應。這個映射函數稱為哈希函數，根據這個原則建立的表稱為哈希表(Hash Table)，也叫散列表。以上描述，如果通過數學形式來描述就是：若查找關鍵字為 key，則其值存放在 f(key) 的存儲位置上。由此，不需比較便可直接取得所查記錄。註：哈希查找與線性表查找和樹表查找最大的區別在於，不用數值比較。
  • 哈希表的使用指南
    本文約7600字+，閱讀（觀看）需要43分鐘在記錄的存儲位置和它的關鍵字之間是建立一個確定的對應關係（映射函數），使每個關鍵字和一個存儲位置能唯一對應。這個映射函數稱為哈希函數，根據這個原則建立的表稱為哈希表(Hash Table)，也叫散列表。
  • 數據結構 | 哈希表
    本文為數據結構系列第 11 篇，介紹哈希表的實現。哈希表（也叫散列表）是數據結構課程中都會介紹的概念，一般出現在「散列與查找」相關章節。哈希表的核心思想是構造一個散列函數，鍵值作為散列函數輸入，將元素映射到哈希表某一位置存儲。這樣，在進行查找時就可以根據散列函數快速找到元素所在位置。常見散列函數有：直接定址法、平方取中法、除留餘數法、數字分析法等。
  • Python | Leetcode哈希表系列
    哈希表哈希表（散列表）的思想是將關鍵字 Key 映射到存放記錄的散列表中從而進行快速訪問，其中映射函數 f(key) 稱為哈希函數（散列函數），依據哈希函數建立的查找表稱為哈希表。假如班級裡面有50個學生，都有各自的名字，我們想把學生的名字放在一個表上，同時便於很快的查找，你會毫無想到數組，但是查找的複雜度是O(n),所以哈希表就是為了解決這問題，將查找的複雜度達到 O(1)假如有個學生的名字叫做lies,通過hash函數，得到下標9 ，將lies的ASCII碼加起來
  • 理解 Golang 哈希表 Map 的原理
    在上一節中我們介紹了 數組和切片的實現原理，這一節會介紹 Golang 中的另一個集合元素 — 哈希，也就是 Map 的實現原理；哈希表是除了數組之外，最常見的數據結構，幾乎所有的語言都會有數組和哈希表這兩種集合元素，有的語言將數組實現成列表，有的語言將哈希表稱作結構體或者字典，但是它們其實就是兩種設計集合元素的思路，數組用於表示一個元素的序列，而哈希表示的是鍵值對之間映射關係，只是不同語言的叫法和實現稍微有些不同
  • 一文讀懂哈希函數
    哈希函數哈希函數（Hash）：h=H（Data）定義哈希函數H，將可變大小的數據Data作為輸入，產生固定長度的h值。
  • 和你聊聊哈希算法
    和你聊聊哈希算法1.1 引言哈希算法又稱散列函數算法，是一種查找算法，應該說哈希算法是最快的查找算法，沒有之一。對於查找問題，哈希算法一直是首選算法。那麼，為什麼名字起的這麼「嘻哈」的算法會如此強大，本文將為你揭開謎底。
  • 一看就懂的數據結構基礎「哈希表」
    通過把鍵映射到表中的一個位置來訪問數據，以提高查找速度。而這個映射關係就是哈希函數。哈希函數因為哈希表的數據映射關係以哈希函數為體現，為了避免小夥伴對哈希函數不夠了解，此處先介紹哈希函數。哈希函數可以把給定的數據轉換成固定長度的無規律數值，可以把它想像成一臺處理器，如下圖所示：輸入的數據經過加工後，會輸出對應的「哈希值」。哈希值多用十六進位表示（十六進位數範圍是，數字0~9和字母a~f）。而計算機中則使用0和1表示的二進位來管理這些數據，實際上，哈希函數就是計算機內部進行的某種運算。
  • 圖解:什麼是哈希?
    哈希是對直接訪問表的改進。使用哈希函數將給定的電話號碼或任何其他鍵轉換為較小的數字，將該較小的數字稱為哈希表的索引（哈希值）什麼是哈希表？哈希表和直接訪問表很類似，同樣是一個用於存儲指向給定電話號碼對應記錄的指針的數組，只不過，此時的數組下標不再是電話號碼，而是經過哈希函數映射後的輸出值。什麼是哈希函數？
  • 數據結構-PHP 哈希表(Hash Table)的實現
    這篇文章主要介紹一下哈希表（Hash Table）的實現原理，哈希表(Hash Table) 也叫
  • 哈希函數的特點及應用介紹
    原本呢，我是計劃在第二篇就開始進入程序開發的部分，只是我發現到，不先了解哈希函數的原理功能、或是留給讀者自行google，會破壞這個系列文章的完整性，尤其是在實作內存塊鏈的不可逆性、或是Key創建等功能，讀者的感受與理解會有差異，所以還是決定，在進入開發區塊鏈之前，寫一篇文章來專門介紹哈希函數，尤其是其在密碼學方面的應用 哈希函數應用在區塊鏈的哪些地方？
  • 比特幣的加密本質: 哈希函數是什麼?
    什麼是哈希?　　加密哈希函數是在數字數據上運行的數學運算。在比特幣中，所有操作都使用SHA256作為底層加密哈希函數。　　安全哈希算法是由美國國家安全局(NSA)設計的一套加密哈希函數。　　1)毫不含糊:哈希 (輸出)就像輸入數據的指紋。
  • 7000字哈希表總結,圖文講解!
    首先我們可以對哈希函數下手，我們可以精心設計哈希函數，讓其儘可能少的產生衝突，所以我們創建哈希函數時應遵循以下規則（1）必須是一致的，假設你輸入辣子雞丁時得到的是在看，那麼每次輸入辣子雞丁時，得到的也必須為在看。如果不是這樣，散列表將毫無用處。
  • 圖文詳解:7000 字哈希表總結
    首先我們可以對哈希函數下手，我們可以精心設計哈希函數，讓其儘可能少的產生衝突，所以我們創建哈希函數時應遵循以下規則（1）必須是一致的，假設你輸入辣子雞丁時得到的是在看，那麼每次輸入辣子雞丁時，得到的也必須為在看。如果不是這樣，散列表將毫無用處。
  • 簡單易懂的哈希表總結
    散列技術是在通過記錄的存儲位置和它的關鍵字之間建立一個確定的對應關係 f ，使得每個關鍵字 key 都對應一個存儲位置 f(key)。見下圖這裡的 f 就是我們所說的散列函數（哈希）函數。我們利用散列技術將記錄存儲在一塊連續的存儲空間中，這塊連續存儲空間就是我們本文的主人公-散列(哈希)但是大家有沒有考慮到這種情況，那就是將關鍵字映射到同一個槽中的情況，即 f(k4) = f(k3) 時。
  • PHP哈希表碰撞攻擊原理
    哈希表碰撞攻擊的基本原理哈希表是一種查找效率極高的數據結構，很多語言都在內部實現了哈希表。PHP中的哈希表是一種極為重要的數據結構，不但用於表示Array數據類型，還在Zend虛擬機內部用於存儲上下文環境信息（執行上下文的變量及函數均使用哈希表結構存儲）。
  • 哈希函數--區塊鏈的back bone
    哈希函數不管是在數據結構還是在分布式共識方面都是非常重要的，那麼什麼是哈希函數呢？一般來說哈希函數是一類可以把任何數據轉換成固定長度輸出（也就是我們說的哈希值）的數學函數，而且可以被高效的計算， 所以我們一般會用來構建哈希表等。在此基礎上密碼學哈希還多了3個特性。