哈希

? 前言：大一大二就一直聽說哈希哈希，但一直都沒有真正的概念：What is 哈希？這篇博客就淺淺聊一下作者認知中的哈希。

理解哈希

? 哈希（Hash）也可以稱作散列，實質(zhì)就是一種映射，過程是將值作為參數(shù)輸入到哈希函數(shù)中，通過一定的算法得到輸出值，輸入值和輸出值幾乎是一一對應(yīng)的（注意這里的幾乎），在這個過程中輸入是無限的（任意長度），一樣的輸入對應(yīng)一樣的輸出，不同的輸入也有可能對應(yīng)相同的輸出（即哈希碰撞），最終結(jié)果具有離散均勻性。

根據(jù)以上過程可知哈希具有四個特點：

①輸入是無限的

②一樣的輸入對應(yīng)一樣的輸出

③不同的輸入也可能一樣的輸出（哈希碰撞）但概率很小

④離散均勻性

? 這還是很抽象，接下來就舉個栗子吧~~

? 首先根據(jù)經(jīng)典的哈希，假設(shè)兩個條件：①無窮的輸入域（例如任意長度字符串）②有限的輸出域S（即輸出的結(jié)果肯定在S范圍中）

? 現(xiàn)在假設(shè)我有一個函數(shù)Function(參數(shù)為整數(shù))，那么我可以試著輸入任意數(shù)量任意大小整數(shù)都會有一個輸出，例如Function(1234567)會有一個輸出結(jié)果，當我再次調(diào)用Function(1234567)時輸出結(jié)果不變（即函數(shù)內(nèi)部不存在隨機數(shù)的計算），如果給定參數(shù)不同，那么輸出結(jié)果也有可能相同，原因是S是有限的輸出域，而我有無限的輸入，有可能導致不同的輸入經(jīng)過哈希函數(shù)計算得到相同的結(jié)果，一般碰撞概率很小，只有當輸入數(shù)據(jù)極大量時才有可能產(chǎn)生碰撞，接著我用一個大圓來抽象表示輸出域，輸出結(jié)果抽象為一個個小黑點，大量數(shù)據(jù)輸入后，產(chǎn)生的圖像如下圖所示。

? 可以看到輸出結(jié)果分布是非常離散且均勻的，此時若用一個小圓在輸出域中采樣，采樣出的數(shù)量也是非常均勻的，like下圖。

? 那么能實現(xiàn)以上四個特點的這樣一個Function函數(shù)就稱為哈希函數(shù)，經(jīng)典的哈希函數(shù)模板有 MD5 算法：返回值在0~2⁶⁴-1，SHAL算法：返回值在0~2¹²⁸-1，java中的哈希函數(shù)返回值在0~2³²-1，哈希函數(shù)的具體實現(xiàn)算法先不用管（大牛搞出來的）。

加工

? 日常使用哈希我們不希望輸出域太大，此時我們就需要加工一下來使用，具體加工方法是在最后增加一個過程：即樣本經(jīng)過哈希函數(shù)得到的輸出再模一個值m得到最終輸出結(jié)果，如下圖。

? 此時最終的輸出結(jié)果范圍就在0~m-1上，并且結(jié)果在0~m-1上也同樣均勻分布（很簡單推），這樣我們就人為縮小了哈希的結(jié)果域。

用途

問題：

假設(shè)有一個大文件，文件中有40億個的無符號整數(shù)（范圍在0~42億+），若只給1G內(nèi)存，內(nèi)存中出現(xiàn)最多次的是哪個數(shù)？

題解：

此時就有小朋友想用哈希表做了，HashMap中含有一個key和一個value，我們可以用key代表一個無符號整數(shù)，value代表這個無符號整數(shù)出現(xiàn)的次數(shù)，看起來這樣好像能輕松解決這個問題。真的是這樣嗎？我們可以看到該問題給定的要求是1G內(nèi)存，而在這題中，key的類型是int（4字節(jié)），value類型也考慮為int，那么一個HashMap結(jié)構(gòu)至少占8個字節(jié)（不考慮哈希表內(nèi)部索引空間浪費了，就假定為沒有該空間），40億個HashMap最壞情況（即每個數(shù)都不一樣）那就是需要占用32G的內(nèi)存，這遠遠超出了問題中所給定的要求。

那么這時，我們就可以加工了，直接把每一個結(jié)果取余100，就能將32G的文件分割為一百份，由于離散均勻性，我們可以將這一百份小文件看成大小相等的一百份，并且每個種類的key都只會出現(xiàn)在其中一份小文件中，那么每一份小文件就只占用32G / 100的內(nèi)存，即滿足題目要求，此時再分別統(tǒng)計所有小文件中的最大值求出最終結(jié)果。

哈希表的實現(xiàn)

? 哈希表是怎么實現(xiàn)的呢，為什么能做到查詢的時間復雜度是O(1)，假設(shè)有一個大小為18的輸出域，輸入字符串“abc”、”bcd”、“xyz”，若經(jīng)過哈希函數(shù)計算后取模18得到以下結(jié)果，可以發(fā)現(xiàn)，當?shù)玫较嗤禃r，將他們接成一個鏈表就行。由于離散均勻性，每一個鏈的長度幾乎是均勻變長的。哈希表查詢的時候就是相同流程，計算出結(jié)果后去對應(yīng)的位置遍歷鏈表查詢，此時就有一個問題，如果輸出域太小，鏈表長度過長，那么查詢的時候就無法做到O(1)的時間復雜度，所以當鏈表長度達到一個閾值，就觸發(fā)擴容（擴容規(guī)則可以是變?yōu)閮杀?#xff09;，18擴容為36，那么每個鏈表長度就變?yōu)橐话?#xff0c;不過此時就需要把所有值重新計算（將模18改為用模36計算）放入輸出域。

? 說完實現(xiàn)原理，再說說增刪查改時間復雜度O(1)到底是怎么來的？輸入的值經(jīng)過哈希函數(shù)計算這個過程時間復雜度是O(1)，得到的值再進行模運算時間復雜度同樣是O(1)，假設(shè)鏈表長度是k，遍歷鏈表的時間復雜度就是O(k)，當我們讓k的大小始終很小時，就能看作O(1)，所以擴容就是為了保證時間復雜度維持在O(1)。

? 接下來看看擴容的代價，假設(shè)有1000個字符串要加進去，設(shè)一開始哈希表格子大小為2，每次擴容容量乘2，那么需要經(jīng)歷log1000次擴容，所以擴容的次數(shù)理論來說是O(log_kN)，k為初始容量大小，N為要加入的內(nèi)容大小，但實際情況遠遠小于logN，而每次重新計算哈希值的代價是O(N)，因為每個值擴容后都要重新計算，故總的擴容代價是O(N*logN)，那么單次代價即為O(logN)水平，當我將k的值稍微設(shè)計大一些，此時O(logN)就會變成一個特別小的代價值，實際情況N并不會過大，而且哈希表有增有刪，刪的情況還會減小擴容次數(shù)，故O(logN)可以逼近O(1)。Java等一些虛擬機語言還有離線擴容技術(shù)，可以不占用用戶在線時間進行擴容，進一步加速了哈希表的使用，所以哈希表在實際使用是O(1)，理論上是O(logN)。

? 以上就是哈希表的原理，具體的實現(xiàn)改進還有很多，比如開放地址法等等，這里就不過多贅述。

Tips：java中的HashMap、HashSet就是用哈希原理實現(xiàn)的哈希表，HashMap就只是比HashSet多了一個伴隨的value值，原理是相同的，算法時間復雜度為O(1)；TreeMap和TreeSet即 java 中利用搜索樹實現(xiàn)的 Map 和 Set，實際上用的是紅黑樹，而紅黑樹是一棵近似平衡的 二叉搜索樹，算法時間復雜度為O(logN)。

布隆過濾器

布隆過濾器是來解決類似黑名單系統(tǒng)、爬蟲去重問題的

比如一個網(wǎng)站的黑名單url有100億個，每個url大小限制為64Byte。需要做到給定一個url，判斷該url是否出現(xiàn)在黑名單中，且這個黑名單只有增加和查詢的需求，沒有刪除需求。

如果直接使用HashSet，那么占用空間大概是640G，十分浪費空間，或者搞成硬盤來記錄url值，但這樣慢的一p，所以咱們還是用內(nèi)存來實現(xiàn)。

布隆過濾器允許一定的失誤率，即有些不位于黑名單的url可能會被判定為在黑名單中（白 -> 黑），但不會出現(xiàn)原本位于黑名單中的url判定為不在黑名單中（黑 -> 白），而且通過人為的設(shè)計，可以讓失誤率很低，讓工程上可以接受，例如爬網(wǎng)頁，有些網(wǎng)頁被殺掉了，沒拿到信息，但在其他網(wǎng)頁同樣能得到信息。

那這么好用的布隆過濾器咋實現(xiàn)？

我們先來看看位圖：

位圖：一個數(shù)組，每個元素所占空間為1bit（bitarr bitmap）

假設(shè)我們想操作第178位，具體實現(xiàn)如下：

實現(xiàn)：使用基礎(chǔ)類型拼湊

public class BitMap {public static void main(String[] args) {int a = 0;int[] arr = new int[10]; //32bit * 10 -> 320bits//arr[0] 0 ~ 31//arr[1] 32 ~ 63int i = 178; //想取第178位bitint numIndex = i / 32;int bitIndex = i % 32;//拿到第178位的狀態(tài)int s = (arr[numIndex] >> bitIndex) & 1;//把第178位的狀態(tài)改為1arr[numIndex] = arr[numIndex] | (1 << bitIndex);//把第178位的狀態(tài)改為0arr[numIndex] = arr[numIndex] & (~(1 << bitIndex));       }
}

布隆過濾器就是一個大位圖，長度為m的bitarr（實際占用空間為m / 8字節(jié)）

加入黑名單的步驟：對于每一個url來說，用k個不同的哈希函數(shù)算出k個哈希值out，然后將每一個out模m，得到對應(yīng)于位圖中的位置，將該位置設(shè)置為1，可以想象成將這些位置描黑，而取k個哈希函數(shù)相當于取k個特征，特征越多就越精確，就像一張圖片你需要多取一些特征點才能歸類為貓而不是歸類為動物，從而使結(jié)果更精準。

查詢黑名單的步驟：對于某一個url來說，算出k個哈希值，然后模m算出對應(yīng)于位圖中的位置，只有這些位置全是1(也就是都被描黑了），這個url才處于黑名單中，只要有一個位置不是1，就代表其不在黑名單中

決定失誤率p的因素：位圖大小m和哈希函數(shù)個數(shù)k。n（樣本量）假定為100億，若m越大，p則會越小（類似于反比例函數(shù)）；當m由p-m圖像確定后，k較小時，隨著k的增加，p會下降，但到達某一個臨界（與m有關(guān)）時，隨著k的增加，p會上升（類似于二次函數(shù)），因為k逼近m，空間占用率太大了。

————————————————p（失誤率）與m（位圖大小）的關(guān)系圖————————————————

————————————————p（失誤率）與k（哈希函數(shù)個數(shù)）的關(guān)系圖————————————————

布隆過濾器只和樣本量n、失誤率p這兩個參數(shù)有關(guān)，與單樣本大小無關(guān)（例如url大小），因為最后會被轉(zhuǎn)化為哈希值，只要保證哈希函數(shù)能接受這個數(shù)值即可。

三個相關(guān)的公式：
$$\begin{gathered} m=?\frac{n?lnp}{(ln2{)}^2}bit(向上取整) \\ k=ln2?\frac{m}{n}\approx 0.7?\frac{m}{n}個(向上取整) \\ {p}_{真}=(1?e^{?\frac{n?k_{真}}{m_{真}}}{)}^{k_{真}} \end{gathered}$$
當類似于黑名單這個集合結(jié)構(gòu)系統(tǒng)，不需要刪除行為，允許有一定失誤率，那么就需要設(shè)計布隆過濾器，設(shè)計布隆過濾器只需要以上三個公式。

已經(jīng)有的條件：

①樣本量n

②失誤率p

對于上述黑名單示例，經(jīng)計算后m的大小理論值大概是26G（原本需要640G），極大地減小了內(nèi)存的占用，實際使用可以多申請一點比如申請32G內(nèi)存，實際失誤率會更小，計算就是第三個公式。

一致性哈希（Google改變世界技術(shù)三架馬車之一）

一致性哈希原理：

一致性哈希是用來討論分布式數(shù)據(jù)服務(wù)器（多臺機器）怎么組織的問題

經(jīng)典組織方式：假設(shè)有3臺服務(wù)器，那么就先將數(shù)據(jù)轉(zhuǎn)化為哈希值，再模3，分配到對應(yīng)的服務(wù)器上，可以做到數(shù)據(jù)種類的均勻分配

負載均衡是由高頻、中頻、低頻各自是否達到一定的數(shù)量來決定，此時由哈希函數(shù)是可以將這些數(shù)據(jù)均分的（根據(jù)離散均勻性，此時哈希函數(shù)需要選擇種類較多的key，比如人名、身份證，而不適于選擇類似于國家名的key）

經(jīng)典結(jié)構(gòu)的問題：若增加機器或減少機器，所有數(shù)據(jù)都需要重新計算哈希值，因此數(shù)據(jù)遷移的代價是全量的（比如原本模3，加了一個機器之后，就需要將全部數(shù)據(jù)模4重新計算分配，所以像MySQL這種一臺機器的就搞不了，太慢了）

**一致性哈希的處理方式：**將哈希值的域比作一個環(huán)，先使用一個特定于服務(wù)器的哈希函數(shù)為每個服務(wù)器計算一個哈希值，將這些機器插入到這個環(huán)中。此時數(shù)據(jù)分配的方式是，這個數(shù)據(jù)所計算出的哈希值在環(huán)上順時針方向最近的機器。實現(xiàn)方式是通過二分的方式查找大于等于當前哈希值中最近的機器，若沒有比當前哈希值大的機器，則代表是最小的那個機器（因為是環(huán)）邏輯圖如下。

在一致性哈希下，若新增或刪減了服務(wù)器，則只需要遷移部分的數(shù)據(jù)即可完成數(shù)據(jù)的遷移，因為此時只用考慮增加或刪減的那臺機器與鄰近機器的那一段數(shù)據(jù)。

例如下圖，新增一個結(jié)點五，只需要把結(jié)點四到結(jié)點五之間的數(shù)據(jù)從節(jié)點一要回給結(jié)點五即可。

一致性哈希的問題：

① 當機器較少時，可能做不到這些機器將環(huán)均分
② 即使可以做到機器數(shù)量較少時將環(huán)均分，也無法保證增加或減少機器后負載均衡

解決方式：虛擬結(jié)點技術(shù)

虛擬結(jié)點技術(shù)本質(zhì)上是按比例去搶環(huán)。假設(shè)有3臺機器，則給這3臺機器每個分配1000個字符串，此時不再讓機器去占環(huán)上的位置，而讓虛擬結(jié)點去占，即每臺機器計算1000個哈希值，讓這1000個哈希值占環(huán)上。此時這些虛擬結(jié)點之間的數(shù)據(jù)遷移可以用很簡單的方式實現(xiàn)。當增加服務(wù)器時，則同理給這臺服務(wù)器添加1000個虛擬結(jié)點，由于哈希分配均勻，因此它會均勻地從前3臺機器中奪取數(shù)據(jù)到自己身上。減少機器也同理，減少機器時，自己的數(shù)據(jù)會均勻地分配到其他機器上。

一致性哈希還可以管理負載。例如若某臺機器比較強，則可以分配更多的虛擬結(jié)點，而某臺機器較弱，則可分配較少的虛擬結(jié)點。

以上就是關(guān)于作者對哈希的學習和理解，真的很想描述清楚分享給大家，能力有限，覺得寫的不好不要見怪，有問題或錯誤歡迎評論區(qū)指出。