「數據結構」Hash表

數據結構】Hash表

Hash表也叫散列表，是一種線性數據結構。在一般情況下，可以用o(1)的時間複雜度進行數據的增刪改查。在Java開發語言中，HashMap的底層就是一個散列表。

1. 什麼是Hash表

Hash表是一種線性數據結構，這種數據結構的底層一般是通過數組來實現的。在進行數據增刪改查的時候，Hash表首先通過Hash函數對某個鍵值進行Hash操作，這個Hash操作會將這個鍵映射到數組的某個下標，獲得下標以後就可以直接對數組中的數據進行操作了。理論上講，Hash表數據操作的時間複雜度都是O(1)。

Hash表的底層是通過數組實現的。數據有個特點就是：必須在初始化的時候指定其長度。所以當Hash表中的數據填滿之後想繼續向裡面放數據的話就必須再創建一個容量更大的數組，然後將之前數組中的數組copy到這個新數組中。這個過程是一個耗費性能的操作，因此我們在使用Hash表之前最好估算下數據的容量，儘量避免擴容操作。

2. Hash函數

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

• 典型的哈希函數都有無限的輸入值域；
• 當哈希函數輸入一致時，輸出必相同；
• 當哈希函數傳入不同的輸入值時，返回值可能一樣，也可能不一樣；
• 對於不同的輸入所得的輸出值會均勻的分佈；

另外，Hash函數還具有如下兩個性質：

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

常用的Hash函數有：SHA1、MD5、SHA2等

3. Hash衝突

對於不同的輸入值，Hash函數可能會給出相同的輸出，這種情況就叫做Hash衝突。

哈希衝突是不可避免的，我們常用解決哈希衝突的方法有 開放地址法 和** 拉鍊法**。

3.1 拉鍊法

拉鍊法的核心思想是：如果Hash表的某個位置上發生了Hash衝突（也就是說在將一個元素放置到數組中某個位置的時候，這個位置上已經有其他元素佔據了），那麼將這些元素以鏈表的形式存放。

鏈表的查詢效率是比較低的，所以如果在Hash表的某個位置上發生衝突的次數太多的話，那麼這個位置就是一個很長的鏈表。查詢速度較慢。在Java 8中，HashMap做了一個優化，就是當鏈表長度達到8時，會自動將鏈表轉換成紅黑樹，查詢效率較高（紅黑樹是一種自平衡的二叉查找樹）。

3.2 開放地址法

在開放地址法中，若數據不能直接存放在哈希函數計算出來的數組下標時，就需要尋找其他位置來存放。在開放地址法中有三種方式來尋找其他的位置，分別是 線性探測、二次探測、再哈希法 。

3.2.1 線性探測法

線性探測的插入比較簡單，做法是：首先將元素進行hash映射，如果映射的位置上沒有其他元素，就直接在這個位置上插入數據；如果這個位置上已經有數據了，那麼判斷下個位置上有無數據，如果沒有直接插入如果有數據再進行下一次判斷，直到找到空位。

線性探測的查找：先通過鍵值定位到數組下標位置，然後將這個位置上數據的值和你要查找數據的值對比，如果相等就直接找到了，如果不相等則繼續判斷下個元素，所有元素遍歷完都沒找到的話，則不存在。

線性探測的刪除：首先還是通過鍵值映射到數組某個下標的位置，然後通過數組中元素的值和你要刪除的元素的值進行比較，找出你要刪除的那個元素。然後將這個位置上的元素刪除並設置一個標誌位說明這個位置上曾經有過數據（這步大家自己想想為什麼要這麼做）

3.2.2 二次探測法

在線性探測哈希表中，數據會發生聚集，一旦聚集形成，它就會變的越來越大，那些哈希函數後落在聚集範圍內的數據項，都需要一步一步往後移動，並且插入到聚集的後面，因此聚集變的越大，聚集增長的越快。這個就像我們在逛超市一樣，當某個地方人很多時，人只會越來越多，大家都只是想知道這裡在幹什麼。

二次探測是防止聚集產生的一種嘗試，思想是探測相隔較遠的單元，而不是和原始位置相鄰的單元。在線性探測中，如果哈希函數得到的原始下標是x,線性探測就是x+1,x+2,x+3......，以此類推，而在二次探測中，探測過程是x+1,x+4,x+9,x+16,x+25......,以此類推，到原始距離的步數平方。

3.2.3 雙哈希法

雙哈希是為了消除原始聚集和二次聚集問題，不管是線性探測還是二次探測，每次的探測步長都是固定的。雙哈希是除了第一個哈希函數外再增加一個哈希函數用來根據關鍵字生成探測步長，這樣即使第一個哈希函數映射到了數組的同一下標，但是探測步長不一樣，這樣就能夠解決聚集的問題。

第二個哈希函數必須具備如下特點

• 和第一個哈希函數不一樣；
• 不能輸出為0，因為步長為0，每次探測都是指向同一個位置，將進入死循環，經過試驗得出 stepSize=constant-(key%constant);形式的哈希函數效果非常好，constant是一個質數並且小於數組容量。

雙hash的核心思想是，第二步生成一個隨機的探測步長。

4. Hash表的相關應用

電腦只有2G內存，怎麼在20億個數據中找到出現次數最多的整數

首先我們需要確定value的範圍，因為這個20億個數有可能是同一個數，那麼value就為20億次。因此我們最少需要用一個int型的數據來存這個數（Java中int佔4個字節）；

同時我們還要確定下這個20億整數的取值範圍是多少。如果取值範圍是1~20億的話，我們也可以用int來存key，如果是更大的取值範圍的話，就需要考慮用long來存了。我們以極端壞的情況來考慮下這個問題：也就是20一個數據全是不同的數據，這些數據的取值範圍是超過20億的，因此我們需要用long類型來存key值，應int類型來存value值，20億條記錄的話大概需要26G左右的內存空間。這樣的話顯然內存不足，因此一次性統計20億個數風險很大。

解決方案：將包含有20億個數的大文件分成16個小文件，利用哈希函數，這樣的話，同一個重複的數肯定不會分到不同的文件中去，並且，如果哈希函數足夠好，那麼這16個文件中不同的數也不會大於2億（20 / 16）。然後我們在這16個文件中依次統計就可以了，最後進行彙總得到重複數最多的數。（彙總的時候我只需要取出每個小文件中出現次數最多的數，然後將這16個數進行比較就行了）

問題：如果這個20億個數都相同怎麼判斷呢？