點(diǎn)擊上方“朱小廝的博客”，選擇“設(shè)為星標(biāo)”

后臺(tái)回復(fù)"k8s"領(lǐng)取阿里云《深入淺出k8s.pdf》

來源：rrd.me/gEtR3

最近對(duì)hash有了更多深入的理解。這里也寫篇文章專門來聊聊hash。

Hash是一種常見的數(shù)據(jù)結(jié)構(gòu)或者說計(jì)算方法，以其O(1)的時(shí)間算法復(fù)雜度聞名于世。曾有人說，如果世界上只有一種數(shù)據(jù)結(jié)構(gòu)，那么我選擇hash，足見hash的地位及牛逼之處，而代碼編寫中hash也屢見不鮮，因?yàn)樗鼘?shí)在是太常見太好用了。

但是實(shí)際使用過程中，基本的hash是遠(yuǎn)遠(yuǎn)不夠的，按照用途，對(duì)hash其實(shí)還有如下需求：

關(guān)于java中hash的數(shù)據(jù)結(jié)構(gòu)：

1.并發(fā)安全。

對(duì)這個(gè)需求，java中有了HashTable，為了進(jìn)一步提升性能，于是有了使用分段鎖的ConcurrentHashMap，亦不做贅述。

2.大數(shù)據(jù)hash。

傳統(tǒng)的HashMap中除了key, value外，每個(gè)entry還要存16個(gè)byte的class header，4byte的hash值，以及8byte的指向下一個(gè)元素的指針，這樣的結(jié)構(gòu)在遇到大數(shù)據(jù)量時(shí)就會(huì)更加耗內(nèi)存，更容易導(dǎo)致GC。

由對(duì)象頭過大可以看出來，只要能夠有一種結(jié)構(gòu)消滅這個(gè)額外的entry對(duì)象，則此處將大大減少內(nèi)存的消耗。

一種可行的方式是：采用二級(jí)索引保存的方式，第一級(jí)索引由Short2ShortMap保存一個(gè)short為key且short為value的Map結(jié)構(gòu)，第二級(jí)索引則由許多數(shù)組構(gòu)成，這些數(shù)組負(fù)責(zé)將被消滅value這個(gè)Object拆解為基本類型并用多個(gè)數(shù)組保存，而一級(jí)索引的value保存的value正是二級(jí)數(shù)組的index。通過這種變換，消滅了額外的entry對(duì)象從而大幅減少內(nèi)存。需要注意的是，這種方式適用于使用了大量HashMap，但是每個(gè)Map內(nèi)數(shù)據(jù)量較小的情況（受short的限制只有3w多index），如果每個(gè)Map內(nèi)數(shù)據(jù)量也比較大，可以考慮Int2IntMap，當(dāng)然，這樣減少內(nèi)存占用的效果就不如Short2ShortMap了。

3.其他。

ImmutableMap，Guava庫(kù)，在初始化完畢后就沒法再put做改變了。

SortedMap，Guava庫(kù)，數(shù)據(jù)會(huì)按key做字母化排序。

BiMap，Guava庫(kù)，創(chuàng)建完之后可以使用inverse將value和key顛倒過來，前提是保證value也是唯一的。

MultiMap，Guava庫(kù)，可以對(duì)每個(gè)key關(guān)聯(lián)多個(gè)值，并且可以很方便的對(duì)list進(jìn)行分組。

關(guān)于hash的一些解決方案：

Hash沖突。

眾所周知，解決hash沖突最好的辦法自然是提升hash table的總數(shù)量（即N的大小），如果待存放元素的數(shù)量k遠(yuǎn)小于N，則hash后有更大概率占據(jù)空槽，而沖突越少則性能越好，本質(zhì)上，這是一種以空間換時(shí)間的方式。然而現(xiàn)實(shí)中，存儲(chǔ)空間也很寶貴，任何公司都很難接受讓大量空間浪費(fèi)。于是，便出現(xiàn)了盡可能增加空間占用但不過分降低性能的hash。

布谷hash。

布谷hash是一種解決沖突的方法。不同于線性探測(cè)，開放定址這樣的常規(guī)方法，布谷hash借鑒了布谷鳥占人巢穴生子的寓意。其算法比較簡(jiǎn)單，采用兩個(gè)（或多個(gè)）hash函數(shù)F1和F2，put操作時(shí)用F1或F2計(jì)算hashcode并定位，如果任意位置為空，則插入；否則擠占其中一個(gè)位置，并將被擠占的元素拿出并重復(fù)該過程；而get操作則讓人比較困惑，到底采用哪個(gè)函數(shù)來get值呢？實(shí)際上布谷hash需要在value中存放key值，這樣對(duì)于兩個(gè)函數(shù)get到的值只要判斷中間key是否正確就可以確認(rèn)其對(duì)應(yīng)的hash函數(shù)。布谷hash在二維時(shí)空間利用率較高，約為80%-90%。下圖是對(duì)put操作的一個(gè)表示。

bloomfilter。

布隆過濾器是一種占小空間且效率很高的算法，通常用來解決垃圾郵件識(shí)別，緩存擊穿及日活計(jì)算等場(chǎng)景。bloomfilter只能判斷一個(gè)元素可能在其中或者一個(gè)元素一定不在其中。他的算法也采用多個(gè)hash函數(shù)，如下例，某數(shù)據(jù)A經(jīng)過x函數(shù)可以映射到4,9兩個(gè)位置，經(jīng)過z函數(shù)可以映射到9,14兩個(gè)位置，經(jīng)過y函數(shù)可以映射到14,19兩個(gè)位置。于是基本的增加操作便可以將這幾個(gè)對(duì)應(yīng)位置的值置為1；對(duì)于基本的查找操作，則對(duì)A進(jìn)行hash后找到其所有對(duì)應(yīng)位置，發(fā)現(xiàn)其所有對(duì)應(yīng)位置都是1，則表示A很可能存在，為什么不能確定呢，因?yàn)橛锌赡苓@些位置并不是對(duì)A進(jìn)行hash后對(duì)應(yīng)的位置，有可能是插入了BCDE等數(shù)據(jù)而這些數(shù)據(jù)剛好覆蓋了A的所有位置而導(dǎo)致的，所以發(fā)現(xiàn)全1僅僅能判斷其可能存在；但是一旦有任意對(duì)應(yīng)位置為0，則表示A一定不存在。對(duì)于基本的刪除和更新操作，布隆過濾器是不支持的，本質(zhì)原因是位置是多數(shù)據(jù)共享的，任何對(duì)數(shù)據(jù)的逆向操作都會(huì)導(dǎo)致其他數(shù)據(jù)的不準(zhǔn)。布隆過濾器在Guava中有現(xiàn)成的實(shí)現(xiàn)。

Count–min sketch。

Count-min sketch旨在解決流式大數(shù)據(jù)下做計(jì)數(shù)統(tǒng)計(jì)時(shí)間空間復(fù)雜度過高的問題。設(shè)想這樣一個(gè)場(chǎng)景，線上數(shù)據(jù)源源不斷的進(jìn)來，現(xiàn)在我們需要去統(tǒng)計(jì)cache中每個(gè)ip請(qǐng)求的大致數(shù)量，從而確定哪個(gè)ip來的請(qǐng)求是hot的。碰到這個(gè)問題，可能本能的會(huì)想用HashMap，用ip作為key，用總count當(dāng)做value。但實(shí)際上當(dāng)數(shù)據(jù)量足夠大時(shí)，各種噩夢(mèng)就來了，比如每臺(tái)機(jī)器內(nèi)存非常高（對(duì)應(yīng)上面說到的大數(shù)據(jù)hash帶來的問題），hash沖突也變高，rehash成本也會(huì)迅速增加，并且在實(shí)時(shí)響應(yīng)的要求下，時(shí)間上就很可能無(wú)法滿足需求，Count-min sketch算法就是為此而生的。

count-min sketch算法思想比較簡(jiǎn)單，采用n個(gè)數(shù)組以及n個(gè)hash函數(shù)，對(duì)同一個(gè)數(shù)據(jù)用不同的hash函數(shù)做hash，分配到這n個(gè)數(shù)組不同的位置，存值時(shí)這個(gè)位置所在的value加1，取值時(shí)取這n個(gè)位置最小值，則此最小值大致接近實(shí)際總count數(shù)，且總是大于等于實(shí)際的總count數(shù)。為啥要取最小值，并且為啥結(jié)果總是大于等于實(shí)際總count數(shù)呢，原因其實(shí)與bloomfilter比較像，有可能有其他的hash也落到了該位置并加了count。參考下圖。在java中，著名的caffeine緩存框架中的W-TinyLFU就用的Count-min sketch來記錄訪問頻率。

4.hash分散。

大多數(shù)情況下，希望hash之后的結(jié)果越分散越無(wú)規(guī)律越好。

Murmur hash。Murmur哈希是一種比大多數(shù)算法更為分散更無(wú)規(guī)律的算法。

java中的hash算法稱為Horner，簡(jiǎn)單表示就是

for (int i = 0; i < str.length(); i++) { hash = 31*hash + str.charAt[i]; }

實(shí)際計(jì)算時(shí)經(jīng)常使用移位操作。

Murmur的意思是multiply and rotate，主要優(yōu)點(diǎn)是速度快且hash值足夠分散，目前已經(jīng)在各大框架廣泛使用，比如redis，memcache，cassandra，lucene，如下是其簡(jiǎn)單表示。

x *= m; x = rotate_left(x,r);

5.hash聚集。

少數(shù)情況下，希望通過hash能讓相似的內(nèi)容在hash過后仍然相似，而不是一點(diǎn)改動(dòng)便面目全非。

simhash。simhash是一種局部敏感hash，對(duì)于google百度這樣的大搜索公司，用空間向量去計(jì)算文檔相似度顯得既慢又笨重，simhash用一種相似則海明距離近的方式巧妙而快速的解決了文檔相似的比較。這對(duì)hash提出了另一種不同的要求，以往hash函數(shù)的目的是為了足夠分散，而這里卻希望hash后呈現(xiàn)一定的規(guī)律，實(shí)際上個(gè)人覺得這更像是一種編碼，根據(jù)這種編碼規(guī)則，相似的文檔在hash值上的海明距離更近。

6.其他特殊hash。

一致性hash。

一致性hash主要是為了解決傳統(tǒng)的取模為主的hash將數(shù)據(jù)分配到n臺(tái)服務(wù)器之后，服務(wù)器再擴(kuò)容或縮容所帶來的所有數(shù)據(jù)需要重新計(jì)算hash的問題。這種情況對(duì)于線上某些重要的服務(wù)往往是不可接受的。于是一致性hash出現(xiàn)了，它通過將hash值空間預(yù)先分配到一個(gè)超級(jí)大的虛擬節(jié)點(diǎn)上，再通過實(shí)體節(jié)點(diǎn)就近接管虛擬節(jié)點(diǎn)來解決映射問題。如圖，這個(gè)超級(jí)大的虛擬節(jié)點(diǎn)即是2^32個(gè)，真正的的實(shí)體節(jié)點(diǎn)只有4個(gè)，由于順時(shí)針就近映射，每個(gè)實(shí)體節(jié)點(diǎn)都將接管落入前面一個(gè)實(shí)體節(jié)點(diǎn)以后的所有虛擬節(jié)點(diǎn)的值，這樣每次擴(kuò)容時(shí)只會(huì)影響最多一個(gè)節(jié)點(diǎn)。一致性hash基本人盡皆知，這里就不列舉資料了。

Perfect hash。

perfect hash目的是為了實(shí)現(xiàn)完全無(wú)沖突的hash。perfect hash分為兩種，一種是靜態(tài)hash，一種是動(dòng)態(tài)hash；對(duì)于靜態(tài)hash而言，一個(gè)最好的例子就是數(shù)組，比如總的值有10個(gè)，取hash值后分別映射到3，8，13，18，22，44，53，63，78，92這10個(gè)位置，則我們用一個(gè)長(zhǎng)度為100的數(shù)組可以實(shí)現(xiàn)該值域的靜態(tài)perfect hash。但是你可能會(huì)發(fā)現(xiàn)有多余的位置并沒有被用上，如果能實(shí)現(xiàn)長(zhǎng)度10的數(shù)組完美映射這10個(gè)數(shù)字，則稱之為最小完美hash。動(dòng)態(tài)perfect hash一般比較麻煩，需要做二次hash映射并要第二次映射不會(huì)沖突，有興趣可以查閱相關(guān)資料。

GeoHash。

GeoHash是比較特殊的hash應(yīng)用，主要是用來快速定位。其原理相對(duì)簡(jiǎn)單（實(shí)現(xiàn)起來有不少細(xì)節(jié)）。主要就是將每一級(jí)的地圖劃分為32塊，即每一級(jí)用5bit來標(biāo)識(shí)（為啥是5bit，因?yàn)樽詈笥胋ase32的編碼方式，每個(gè)字母或數(shù)字5bit），每次縮放一級(jí)則用另一個(gè)字母或數(shù)字標(biāo)識(shí)，最終能得到一串字符串wx4gjk32kfrx，從而一級(jí)一級(jí)定位直到最小那一級(jí)。如劃分10級(jí)，則最后字符串長(zhǎng)度為4，范圍到20km，如劃分20級(jí)，則最后字符串長(zhǎng)度為8，范圍可以精確到19m。

想知道更多？掃描下面的二維碼關(guān)注我

后臺(tái)回復(fù)”加群“獲取公眾號(hào)專屬群聊入口

當(dāng)當(dāng)優(yōu)惠碼福利來一波！當(dāng)當(dāng)全場(chǎng)自營(yíng)圖書5折，用優(yōu)惠碼：TASEMU（長(zhǎng)按復(fù)制），滿200（原價(jià)400）再減30，相當(dāng)于170=400，四折多一點(diǎn)。使用渠道：當(dāng)當(dāng)小程序或當(dāng)當(dāng)APP。使用時(shí)間：4/10-4/23。目前優(yōu)惠碼只有少量了，且不會(huì)再增加。

【原創(chuàng)系列 | 精彩推薦】

• Paxos、Raft不是一致性算法嘛？

• 越說越迷糊的CAP

• 面試官居然問我Raft為什么會(huì)叫做Raft!

• 面試官給我挖坑：URI中的//有什么用

• 網(wǎng)關(guān)Zuul科普

• 網(wǎng)關(guān)Spring Cloud?Gateway科普

• 分布式事務(wù)科普——初識(shí)篇

• 分布式事務(wù)科普——終結(jié)篇

• 面試官給我挖坑：a[i][j]和a[j][i]有什么區(qū)別？

• Nginx架構(gòu)原理科普
  

朕已閱?

總結(jié)

以上是生活随笔為你收集整理的如果世界上只有一种数据结构，那么我选择 hash的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。