資料結構】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億個數都相同怎麼判斷呢？