本文作者：jeffhe，騰訊 IEG 開發(fā)工程師
提到hash，相信大多數(shù)同學都不會陌生，之前很火現(xiàn)在也依舊很火的技術(shù)區(qū)塊鏈背后的底層原理之一就是hash，下面就從hash算法的原理和實際應用等幾個角度，對hash算法進行一個講解。
1、什么是Hash
Hash也稱散列、哈希，對應的英文都是Hash。基本原理就是把任意長度的輸入，通過Hash算法變成固定長度的輸出。這個映射的規(guī)則就是對應的Hash算法，而原始數(shù)據(jù)映射后的二進制串就是哈希值。活動開發(fā)中經(jīng)常使用的MD5和SHA都是歷史悠久的Hash算法。
echo md5("這是一個測試文案");
// 輸出結(jié)果：2124968af757ed51e71e6abeac04f98d
在這個例子里，這是一個測試文案是原始值，2124968af757ed51e71e6abeac04f98d就是經(jīng)過hash算法得到的Hash值。整個Hash算法的過程就是把原始任意長度的值空間，映射成固定長度的值空間的過程。
2、Hash的特點
一個優(yōu)秀的hash算法，需要什么樣的要求呢？
- a)、從hash值不可以反向推導出原始的數(shù)據(jù)
- 這個從上面MD5的例子里可以明確看到，經(jīng)過映射后的數(shù)據(jù)和原始數(shù)據(jù)沒有對應關系
- b)、輸入數(shù)據(jù)的微小變化會得到完全不同的hash值，相同的數(shù)據(jù)會得到相同的值echo md5("這是一個測試文案");
- // 輸出結(jié)果：2124968af757ed51e71e6abeac04f98d
- echo md5("這是二個測試文案");
- // 輸出結(jié)果：bcc2a4bb4373076d494b2223aef9f702
- 可以看到我們只改了一個文字，但是整個得到的hash值產(chǎn)生了非常大的變化。
- c)、哈希算法的執(zhí)行效率要高效，長的文本也能快速地計算出哈希值
- d)、hash算法的沖突概率要小由于hash的原理是將輸入空間的值映射成hash空間內(nèi)，而hash值的空間遠小于輸入的空間。根據(jù)抽屜原理，一定會存在不同的輸入被映射成相同輸出的情況。那么作為一個好的hash算法，就需要這種沖突的概率盡可能小。
桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，無論怎樣放，我們會發(fā)現(xiàn)至少會有一個抽屜里面放不少于兩個蘋果。這一現(xiàn)象就是我們所說的“抽屜原理”。抽屜原理的一般含義為：“如果每個抽屜代表一個集合，每一個蘋果就可以代表一個元素，假如有n+1個元素放到n個集合中去，其中必定有一個集合里至少有兩個元素。” 抽屜原理有時也被稱為鴿巢原理。它是組合數(shù)學中一個重要的原理
3、Hash碰撞的解決方案
前面提到了hash算法是一定會有沖突的，那么如果我們?nèi)绻龅搅薶ash沖突需要解決的時候應該怎么處理呢？比較常用的算法是鏈地址法和開放地址法。
3.1 鏈地址法
鏈表地址法是使用一個鏈表數(shù)組，來存儲相應數(shù)據(jù)，當hash遇到?jīng)_突的時候依次添加到鏈表的后面進行處理。
鏈地址法示意圖
鏈地址在處理的流程如下：
添加一個元素的時候，首先計算元素key的hash值，確定插入數(shù)組中的位置。如果當前位置下沒有重復數(shù)據(jù)，則直接添加到當前位置。當遇到?jīng)_突的時候，添加到同一個hash值的元素后面，行成一個鏈表。這個鏈表的特點是同一個鏈表上的Hash值相同。JAVA的數(shù)據(jù)結(jié)構(gòu)HashMap使用的就是這種方法來處理沖突，JDK1.8中，針對鏈表上的數(shù)據(jù)超過8條的時候，使用了紅黑樹進行優(yōu)化。由于篇幅原因，這里不深入討論相關數(shù)據(jù)結(jié)構(gòu)，有興趣的同學可以參考這篇文章：
《Java集合之一—HashMap》
3.2 開放地址法
開放地址法是指大小為 M 的數(shù)組保存 N 個鍵值對，其中 M > N。我們需要依靠數(shù)組中的空位解決碰撞沖突。基于這種策略的所有方法被統(tǒng)稱為“開放地址”哈希表。線性探測法，就是比較常用的一種“開放地址”哈希表的一種實現(xiàn)方式。線性探測法的核心思想是當沖突發(fā)生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。簡單來說就是：一旦發(fā)生沖突，就去尋找下 一個空的散列表地址，只要散列表足夠大，空的散列地址總能找到。
線性探測法的數(shù)學描述是：h(k, i) = (h(k, 0) + i) mod m，i表示當前進行的是第幾輪探查。i=1時，即是探查h(k, 0)的下一個；i=2，即是再下一個。這個方法是簡單地向下探查。mod m表示：到達了表的底下之后，回到頂端從頭開始。
對于開放尋址沖突解決方法，除了線性探測方法之外，還有另外兩種比較經(jīng)典的探測方法，二次探測（Quadratic probing）和雙重散列（Double hashing）。但是不管采用哪種探測方法，當散列表中空閑位置不多的時候，散列沖突的概率就會大大提高。為了盡可能保證散列表的操作效率，一般情況下，我們會盡可能保證散列表中有一定比例的空閑槽位。我們用裝載因子（load factor）來表示空位的多少。
散列表的裝載因子=填入表中的元素個數(shù)/散列表的長度。裝載因子越大，說明沖突越多，性能越差。
3.3 兩種方案的demo示例
假設散列長為8，散列函數(shù)H(K)=K mod 7，給定的關鍵字序列為{32,14,23,2, 20}
當使用鏈表法時，相應的數(shù)據(jù)結(jié)構(gòu)如下圖所示：
鏈表法demo
當使用線性探測法時，相應的數(shù)據(jù)結(jié)果如下圖所示：
開放地址-線性探測法
這里的兩種算法的區(qū)別是2這個元素，在鏈表法中還是在節(jié)點2的位置上，但是在線性探測法遇到?jīng)_突時會將沖突數(shù)據(jù)放到下一個空的位置下面。
4、hash算法在日常活動中的應用
在日常運營活動中，我們活動開發(fā)經(jīng)常遇到的應用場景是信息加密、數(shù)據(jù)校驗、負載均衡。下面分別對這三種應用場景進行講解。
4.1 信息加密
首先我們看一下信息加密的應用。2011年CSDN脫庫事件，導致超過600W的用戶的密碼泄露，讓人失望的是，CSDN是明文存儲用戶的注冊郵箱和密碼的。作為用戶的非常隱私的信息，最簡單的保護措施就是對密碼進行hash加密。在客戶端對用戶輸入的密碼進行hash運算，然后在服務端的數(shù)據(jù)庫中保存用戶密碼的hash值。由于服務器端也沒有存儲密碼的明文，所以目前很多網(wǎng)站也就不再有找回密碼的功能了。
- 這里也友情提示一下大家：如果在使用中發(fā)現(xiàn)某網(wǎng)站還有提供找回密碼的功能，就要好好擔心下這個網(wǎng)站的安全性了。
看到這里有些同學會覺得那么我們是不是對用戶輸入的密碼進行一次MD5加密就可以了呢，這樣就算惡意用戶知道了hash值，也沒有辦法拿到用戶的真實密碼。假設用戶的密碼是123456789，經(jīng)過一次md5以后得到的值是:
25f9e794323b453885f5181f1b624d0b
那么是不是使用了這個加密后的字符串來存密碼就萬無一失了呢，理想總是很豐滿，而現(xiàn)實總是很骨感的。
大家可以看一下這個網(wǎng)站：
https://www.cmd5.com/
這里是該網(wǎng)站的相關介紹：
本站針對md5、sha1等全球通用公開的加密算法進行反向查詢，通過窮舉字符組合的方式，創(chuàng)建了明文密文對應查詢數(shù)據(jù)庫，創(chuàng)建的記錄約90萬億條，占用硬盤超過500TB，查詢成功率95%以上，很多復雜密文只有本站才可查詢。已穩(wěn)定運行十余年，國內(nèi)外享有盛譽
md5反查結(jié)果
那么一般針對這種問題，我們的解決之道就是引入salt(加鹽)，即利用特殊字符（鹽）和用戶的輸入合在一起組成新的字符串進行加密。通過這樣的方式，增加了反向查詢的復雜度。但是這樣的方式也不是萬無一失，如果發(fā)生了鹽被泄露的問題，就需要所有用到的地方來重置密碼。
針對salt泄露的問題，其實還有一種解決辦法，即使用Hmac進行加密（Hash-based Message Authentication Code）。這種算法的核心思路是加密使用的key是從服務器端獲取的，每一個用戶的是不一樣的。如果發(fā)生了泄露，那么也就是這一個用戶的會被泄露，不會影響到全局。
這里也留給大家一個思考點，如果惡意用戶直接抓取了你的活動參與鏈接，也就是拿到了你計算后的hash值，那從技術(shù)的角度上說，我們還有沒有其他可以提升惡意用戶的違法成本呢？
4.2 數(shù)據(jù)校驗
- git commit id
使用過git的同學都應該清楚，每次git提交后都有一個commit id，比如:
19d02d2cc358e59b3d04f82677dbf3808ae4fc40
就是一次git commit的結(jié)果，那么這個id是如何生成出來的呢？查閱了相關資料，使用如下代碼可以進行查看：
printf "commit %s" $(git cat-file commit HEAD | wc -c); git cat-file commit HEAD
git的commit id主要包括了以下幾部分內(nèi)容：Tree 哈希，parent哈希、作者信息和本次提交的備注。
單次git commit相關信息
針對這些信息進行SHA-1 算法后得到值就是本次提交的commit id。簡單來講，就是對于單次提交的頭信息的一個校驗和。
linux kernel開創(chuàng)者和Git的開發(fā)者——Linus說，Git使用了sha1并非是為了安全性，而是為了數(shù)據(jù)的完整性；它可以保證，在很多年后，你重新checkout某個commit時，一定是它多年前的當時的狀態(tài)，完全一摸一樣，完全值得信任。
但最新研究表明，理論上對其進行哈希碰撞（hash collision，不同的兩塊數(shù)據(jù)有相同的hash值）的攻擊可以在2^51（2的51次方）左右的次數(shù)內(nèi)實現(xiàn)。不過由于commit id 是針對單個倉庫里的，所以實際應用中我們可以認為如果兩個文件的SHA-1值是相同的，那么它們確是完全相同的內(nèi)容。
注：對于git里tree、parent等結(jié)構(gòu)感興趣的同學，可以參考下這篇文章《Git 內(nèi)部原理 - Git 對象》，這里由于篇幅原因就不進行深入分析了。
- 版權(quán)校驗
- 在數(shù)據(jù)校驗方面的另一個應用場景就是版權(quán)的保護或者違禁信息的打擊，比如某個小視頻，第一個用戶上傳的時候，我們認為是版權(quán)所有者，計算一個hash值存下來。當?shù)诙€用戶上傳的時候，同樣計算hash值，如果hash值一樣的話，就算同一個文件。這種方案其實也給用戶傳播違禁文件提高了一些門檻，不是簡單的換一個名字或者改一下后綴名就可以躲避掉打擊了。（當然這種方式也是可以繞過的，圖片的你隨便改一下顏色，視頻去掉一幀就又是完全不同的hash值了。注意：我沒有教你變壞，我只是和你在討論這個技術(shù)。。。）另外我們在社區(qū)里，也會遇到玩家重復上傳同一張圖片或者視頻的情況，使用這種校驗的方式，可以有效減少cos服務的存儲空間。
- 大文件分塊校驗
- 使用過bt的同學都有經(jīng)驗，在p2p網(wǎng)絡中會把一個大文件拆分成很多小的數(shù)據(jù)各自傳輸。這樣的好處是如果某個小的數(shù)據(jù)塊在傳輸過程中損壞了，只要重新下載這個塊就好。為了確保每一個小的數(shù)據(jù)塊都是發(fā)布者自己傳輸?shù)模覀兛梢詫γ恳粋€小的數(shù)據(jù)塊都進行一個hash的計算，維護一個hash List，在收到所有數(shù)據(jù)以后，我們對于這個hash List里的每一塊進行遍歷比對。這里有一個優(yōu)化點是如果文件分塊特別多的時候，如果遍歷對比就會效率比較低。可以把所有分塊的hash值組合成一個大的字符串，對于這個字符串再做一次Hash運算，得到最終的hash（Root hash）。在實際的校驗中，我們只需要拿到了正確的Root hash，即可校驗Hash List，也就可以校驗每一個數(shù)據(jù)塊了。
大文件分塊示意圖
4.3 負載均衡
活動開發(fā)同學在應對高星級業(yè)務大用戶量參與時，都會使用分庫分表，針對用戶的openid進行hashtime33取模，就可以得到對應的用戶分庫分表的節(jié)點了。
活動分庫分表示意圖
如上圖所示，這里其實是分了10張表，openid計算后的hash值取模10，得到對應的分表，在進行后續(xù)處理就好。對于一般的活動或者系統(tǒng)，我們一般設置10張表或者100張表就好。
下面我們來看一點復雜的問題，假設我們活動初始分表了10張，運營一段時間以后發(fā)現(xiàn)需要10張不夠，需要改到100張。這個時候我們?nèi)绻苯訑U容的話，那么所有的數(shù)據(jù)都需要重新計算Hash值，大量的數(shù)據(jù)都需要進行遷移。如果更新的是緩存的邏輯，則會導致大量緩存失效，發(fā)生雪崩效應，導致數(shù)據(jù)庫異常。造成這種問題的原因是hash算法本身的緣故，只要是取模算法進行處理，則無法避免這種情況。針對這種問題，我們就需要利用一致性hash進行相應的處理了。
一致性hash的基本原理是將輸入的值hash后，對結(jié)果的hash值進行2^32取模，這里和普通的hash取模算法不一樣的點是在一致性hash算法里將取模的結(jié)果映射到一個環(huán)上。將緩存服務器與被緩存對象都映射到hash環(huán)上以后，從被緩存對象的位置出發(fā)，沿順時針方向遇到的第一個服務器，就是當前對象將要緩存于的服務器，由于被緩存對象與服務器hash后的值是固定的，所以，在服務器不變的情況下，一個openid必定會被緩存到固定的服務器上，那么，當下次想要訪問這個用戶的數(shù)據(jù)時，只要再次使用相同的算法進行計算，即可算出這個用戶的數(shù)據(jù)被緩存在哪個服務器上，直接去對應的服務器查找對應的數(shù)據(jù)即可。這里的邏輯其實和直接取模的是一樣的。如下圖所示：
初始3臺機器的情況
初始情況如下：用戶1的數(shù)據(jù)在服務器A里，用戶2、3的數(shù)據(jù)存在服務器C里，用戶4的數(shù)據(jù)存儲在服務器B里
下面我們來看一下當服務器數(shù)量發(fā)生變化的時候，相應影響的數(shù)據(jù)情況：
- 服務器縮容
服務器縮容
服務器B發(fā)生了故障，進行剔除后，只有用戶4的數(shù)據(jù)發(fā)生了異常。這個時候我們需要繼續(xù)按照順時針的方案，把緩存的數(shù)據(jù)放在用戶A上面。
- 服務器擴容
- 同樣的，我們進行了服務器擴容以后，新增了一臺服務器D，位置落在用戶2和3之間。按照順時針原則，用戶2依然訪問的是服務器C的數(shù)據(jù)，而用戶3順時針查詢后，發(fā)現(xiàn)最近的服務器是D，后續(xù)數(shù)據(jù)就會存儲到d上面。
服務器擴容示意圖
- 虛擬節(jié)點
- 當然這只是一種理想情況，實際使用中，由于服務器節(jié)點數(shù)量有限，有可能出現(xiàn)分布不均勻的情況。這個時候會出現(xiàn)大量數(shù)據(jù)都被映射到某一臺服務器的情況，如下圖左側(cè)所示。為了解決這個問題，我們采用了虛擬節(jié)點的方案。虛擬節(jié)點是實際節(jié)點（實際的物理服務器）在hash環(huán)上的復制品，一個實際節(jié)點可以對應多個虛擬節(jié)點。虛擬節(jié)點越多，hash環(huán)上的節(jié)點就越多，數(shù)據(jù)被均勻分布的概率就越大。
虛擬節(jié)點示意圖
如右圖所示，B、C、D 是原始節(jié)點復制出來的虛擬節(jié)點，原本都要訪問機器D的用戶1、4，分別被映射到了B,D。通過這樣的方式，起到了一個服務器均勻分布的作用。
5、幾種hash算法的擴展應用
下面介紹幾種大家可能不經(jīng)常遇到的應用，由于篇幅原因，不做深入介紹，只拋磚引玉。
5.1 SimHash
simHash是google用于海量文本去重的一種方法，它是一種局部敏感hash。那什么叫局部敏感呢，假定兩個字符串具有一定的相似性，在hash之后，仍然能保持這種相似性，就稱之為局部敏感hash。普通的hash是不具有這種屬性的。simhash被Google用來在海量文本中去重。
simHash算法的思路大致如下：
- 將Doc進行關鍵詞抽取(其中包括分詞和計算權(quán)重)，抽取出n個(關鍵詞，權(quán)重)對， 即圖中的多個(feature, weight)。記為 feature_weight_pairs = [fw1, fw2 … fwn]，其中 fwn = (feature_n,weight_n)。
- 對每個feature_weight_pairs中的feature進行hash。然后對hash_weight_pairs進行位的縱向累加，如果該位是1，則+weight,如果是0，則-weight，最后生成bits_count個數(shù)字，大于0標記1，小于0標記0
- 最后轉(zhuǎn)換成一個64位的字節(jié)，判斷重復只需要判斷他們的特征字的距離是不是
SimHash計算流程
如下圖所示，當兩個文本只有一個字變化時，如果使用普通Hash則會導致兩次的結(jié)果發(fā)生較大改變，而SimHash的局部敏感特性，會導致只有部分數(shù)據(jù)發(fā)生變化。
SimHash結(jié)果
5.2 GeoHash
GeoHash將地球作為為一個二維平面進行遞歸分解。每個分解后的子塊在一定經(jīng)緯度范圍內(nèi)擁有相同的編碼。以下圖為例，這個矩形區(qū)域內(nèi)所有的點（經(jīng)緯度坐標）都共享相同的GeoHash字符串，這樣既可以保護隱私（只表示大概區(qū)域位置而不是具體的點），又比較容易做緩存。
GeoHash示意圖
下面以一個例子來理解下這個算法，我們對緯度39.3817進行逼近編碼 ：
- 地球緯度區(qū)間是[-90,90]，對于這個區(qū)間進行二分劃分左區(qū)間[-90,0), 右區(qū)間[0,90]。39.3817屬于右區(qū)間，標記為1
- 將右區(qū)間[0,90]繼續(xù)進行劃分，左區(qū)間[0,45) ,右區(qū)間[45,90]。39.3817屬于左區(qū)間，標記為0
- 遞歸上面的過程，隨著每次迭代，區(qū)間[a，b]會不斷接近39.3817。遞歸的次數(shù)決定了生成的序列長度。
- 對于經(jīng)度做同樣的處理。得到的字符串，偶數(shù)位放經(jīng)度，奇數(shù)位放緯度，把2串編碼組合生成新串。對于新串轉(zhuǎn)成對應10進制查出實際的base32編碼就是類似WX4ER的hash值。
整體遞歸過程如下表所示：
這里有一篇文章詳細介紹了GeoHash，有興趣的同學可以移步這里：
是什么能讓 App 快速精準定位到我們的位置？
5.3 布隆過濾器
布隆過濾器被廣泛用于黑名單過濾、垃圾郵件過濾、爬蟲判重系統(tǒng)以及緩存穿透問題。對于數(shù)量小，內(nèi)存足夠大的情況，我們可以直接用hashMap或者hashSet就可以滿足這個活動需求了。但是如果數(shù)據(jù)量非常大，比如5TB的硬盤上放滿了用戶的參與數(shù)據(jù)，需要一個算法對這些數(shù)據(jù)進行去重，取得活動的去重參與用戶數(shù)。這種時候，布隆過濾器就是一種比較好的解決方案了。
布隆過濾器其實是基于bitmap的一種應用，在1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)，用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難，主要用于大數(shù)據(jù)去重、垃圾郵件過濾和爬蟲url記錄中。核心思路是使用一個bit來存儲多個元素，通過這樣的方式來減少內(nèi)存的消耗。通過多個hash函數(shù)，將每個數(shù)據(jù)都算出多個值，存放在bitmap中對應的位置上。
布隆過濾器的原理見下圖所示：
布隆過濾器原理示意
上圖所示的例子中，數(shù)據(jù)a、b、c經(jīng)過三次hash映射后，對應的bit位都是1，表示這三個數(shù)據(jù)已經(jīng)存在了。而d這份數(shù)據(jù)經(jīng)過映射后有一個結(jié)果是0，則表明d這個數(shù)據(jù)一定沒有出現(xiàn)過。布隆過濾器存在假陽率（判定存在的元素可能不存在）的問題，但是沒有假陰率（判斷不存在的原因可能存在）的問題。即對于數(shù)據(jù)e，三次映射的結(jié)果都是1，但是這份數(shù)據(jù)也可能沒有出現(xiàn)過。
誤判率的數(shù)據(jù)公式如下所示：
其中，p是誤判率，n是容納的元素，m是需要的存儲空間。由公示可以看出，布隆過濾器的長度會直接影響誤報率，布隆過濾器越長其誤報率越小。哈希函數(shù)的個數(shù)也需要權(quán)衡，個數(shù)越多則布隆過濾器 bit 位置位 1 的速度越快，且布隆過濾器的效率越低；但是如果太少的話，則會導致誤報率升高。
6、總結(jié)
Hash算法作為一種活動開發(fā)經(jīng)常遇到的算法，我們在使用中不僅僅要知道這種算法背后真正的原理，才可以在使用上做到有的放矢。Hash的相關知識還有很多，有興趣的同學可以繼續(xù)深入研究。
