面試官: 我看你簡(jiǎn)歷上說(shuō)在你的項(xiàng)目中使用了 Redis，并使用它做了緩存，你能給我介紹一下 Redis 的五種基本數(shù)據(jù)類(lèi)型嗎？

于是說(shuō)道：emmm，Redis 中有 string字符串，hash哈希，list列表，set無(wú)序集合，zset有序集合，這五種數(shù)據(jù)類(lèi)型。

面試官：除了這五種基本數(shù)據(jù)類(lèi)型你還了解過(guò)其他 Redis 提供的額外的數(shù)據(jù)類(lèi)型嗎？你說(shuō)你用 Redis 做了緩存，比如我現(xiàn)在查詢(xún)用戶(hù)用一個(gè)本來(lái)就不會(huì)存在的 ID 去調(diào)你接口，這樣的緩存穿透如何防范呢？

沒(méi)辦法了硬著頭皮往上懟：emm， 有了解過(guò) bitMap，緩存穿透我沒(méi)接觸過(guò)。

面試官：那你有使用過(guò) bitMap 實(shí)現(xiàn)什么功能么？

面試者心里想：完了完了，這場(chǎng)涼了，都怪 FrancisQ ，回去找他算賬。

心里已經(jīng)涼涼：沒(méi)有。。。

寫(xiě)在前面的話(huà)

其實(shí) FrancisQ 只是一個(gè)沒(méi)有參加面試過(guò)的小白，在讀大三，想明年暑期實(shí)習(xí)，所以在學(xué)習(xí)之余會(huì)寫(xiě)一些文章進(jìn)行分享并自我總結(jié)(不為賺錢(qián))，如果覺(jué)得 FrancisQ 寫(xiě)的還不錯(cuò)的話(huà)，給我點(diǎn)個(gè)贊哦 (#^.^#)，其實(shí)我只是想早日到 LV4。當(dāng)然我還有分享其他文章比如 SSM框架的原理解析和實(shí)現(xiàn) ，MySQL 等等，如果感興趣的也可以關(guān)注我。

當(dāng)然各位大佬有實(shí)習(xí)崗位的可以幫幫我哈，哈哈哈。

多余的話(huà)不多說(shuō)，今天給大家?guī)?lái)的是 Redis 中的四種特殊的數(shù)據(jù)結(jié)構(gòu) bitmap，hyperLogLog，bloomFilter，GeoHash 。這四種數(shù)據(jù)結(jié)構(gòu)其實(shí)有點(diǎn)類(lèi)似于算法層面了，比如 GeoHash 其實(shí)就是一個(gè) zset，bitmap 就是 string，只是使用的方法不同導(dǎo)致了更多的功能。

BloomFilter

介紹以及場(chǎng)景使用

對(duì) BloomFilter 不熟悉的話(huà)，對(duì)下面的圖片大家肯定很熟悉吧？別告訴我你只玩過(guò)王者農(nóng)藥。

BloomFilter 中文名就是布隆過(guò)濾器，作為過(guò)濾器，有沒(méi)有感覺(jué)很像 LOL 中布隆的 E技能(堅(jiān)不可摧) ？

布隆過(guò)濾器是一個(gè)叫 布隆 的人提出來(lái)的，它是通過(guò)一個(gè)大型位數(shù)組和幾個(gè)不同的hash函數(shù)來(lái)實(shí)現(xiàn)的，我們可以把布隆過(guò)濾器理解為一個(gè)不精確的set。我們都知道 set 可以去重，使用 set 可以幫我們判斷集合中是否已經(jīng)存在某些元素并且或者幫我們實(shí)現(xiàn)去重功能。

但是，set 提供精確的去重功能的同時(shí)也給我們帶來(lái)了一個(gè)更大的問(wèn)題——空間消耗。

比如這個(gè)時(shí)候我們進(jìn)行網(wǎng)頁(yè)爬蟲(chóng)，需要對(duì)爬過(guò)的 url 進(jìn)行去重以避免爬到已經(jīng)爬過(guò)的網(wǎng)站，如果我們使用 set 那么也就意味著我們需要將所有爬過(guò)的 url 放入集合中，假設(shè)一個(gè) url 64字節(jié)，那么一億個(gè) url 意味著我們需要占用 6GB，十億就是 60GB 左右。

請(qǐng)注意，是內(nèi)存。

比如這個(gè)時(shí)候我們要進(jìn)行垃圾郵件或者垃圾短信的過(guò)濾，我們需要從數(shù)十億個(gè)垃圾郵件列表或者垃圾電話(huà)列表中進(jìn)行判斷此時(shí)的郵件或者短信是否是垃圾的。如果我們此時(shí)使用 set 那么占用空間不用我多說(shuō)了，也是百GB級(jí)別的。

上面的面試中我提到了緩存穿透，用戶(hù)故意請(qǐng)求數(shù)據(jù)庫(kù)本來(lái)就不存在的(比如ID = -1)，這個(gè)時(shí)候如果不做處理那么肯定會(huì)穿透緩存去查詢(xún)數(shù)據(jù)庫(kù)，一個(gè)查詢(xún)還好，如果幾千，幾萬(wàn)個(gè)同時(shí)進(jìn)來(lái)呢？你的數(shù)據(jù)庫(kù)頂?shù)米?？那么此時(shí)我們使用 set 進(jìn)行處理，占用那么多內(nèi)存空間，你覺(jué)得值得嗎？？？或者說(shuō)，還有沒(méi)有更好的方法了？

上面所講的三個(gè)典型場(chǎng)景，網(wǎng)站去重，垃圾郵件過(guò)濾，緩存穿透，這三個(gè)只要使用 BloomFilter 就能完美解決。

你有沒(méi)有發(fā)現(xiàn)，上面三個(gè)場(chǎng)景其實(shí)對(duì)精度要求都不是很高，尤其是垃圾郵件過(guò)濾，其實(shí)偶爾收到幾個(gè)垃圾郵件也無(wú)所謂的。像緩存穿透，也正好符合了 BloomFilter 的一個(gè)特性他說(shuō)有的不一定有，他說(shuō)沒(méi)有的肯定沒(méi)有，我說(shuō)你這個(gè) ID 在數(shù)據(jù)庫(kù)不存在那就真的不存在，老子把你過(guò)濾了就是這么自信，怎么，你打我？？？

原理探究

聊了這么久的概念和應(yīng)用場(chǎng)景，是不是還對(duì) BloomFilter 怎么能進(jìn)行去重的還是一臉懵逼？ 下面我們就聊一聊 BloomFilter 的實(shí)現(xiàn)原理。首先給大家放一張結(jié)構(gòu)圖。

其中 F、G、H 是幾種無(wú)偏 Hash 函數(shù)，底下是一個(gè)大型的位數(shù)組，當(dāng)我們向 BloomFilter 添加數(shù)據(jù)的時(shí)候，它首先會(huì)將我們的數(shù)據(jù)(key)做幾次hash運(yùn)算(這里就是FGH)，每個(gè)hash運(yùn)算都會(huì)得到一個(gè)不用的位數(shù)組索引下標(biāo)，此時(shí)我們就將算出的幾個(gè)下標(biāo)的位置的值改成1就行。如果判斷元素是否存在，只要判斷所在的所有索引下標(biāo)的值都是1就行了。

其實(shí)你也發(fā)現(xiàn)了，在 BloomFilter 中會(huì)出現(xiàn)不同key所算出的下標(biāo)重復(fù)了，如上圖所示，這就是誤差的來(lái)源( 你可以配置初始大小和錯(cuò)誤率來(lái)控制誤差 )也是他說(shuō)有的不一定有，他說(shuō)沒(méi)有的肯定沒(méi)有這一特性的根本原因，因?yàn)槿绻?或者存在0那么肯定不存在，如果全是1也有可能是別的幾個(gè)key給放進(jìn)去的1。

基本使用

因?yàn)?BloomFilter 是 Redis 的擴(kuò)展模塊，所以需要額外下載，你可以使用 Docker 進(jìn)行拉取。安裝步驟我不做詳細(xì)解釋?zhuān)憧梢缘剿膅ithub上學(xué)習(xí)怎么安裝

安裝完之后我們就可以愉快的使用啦。

bf.add key element 添加

bf.exists key element 判斷是否存在

bf.madd key element1 element2 ... 批量添加

bf.mexists key element1 element2 ... 批量判斷

命令很簡(jiǎn)單，你可以自己去嘗試。

HyperLogLog

介紹以及場(chǎng)景使用

在 Redis 中還有一個(gè)會(huì)存在誤差的數(shù)據(jù)結(jié)構(gòu) HyperLogLog。

我們首先思考一個(gè)場(chǎng)景，當(dāng)老板讓我們計(jì)算頁(yè)面的 UV 我們?cè)撛趺崔k？

如果訪(fǎng)問(wèn)量不大使用 set 進(jìn)行用戶(hù)去重完全可以，但是訪(fǎng)問(wèn)量如果有幾百萬(wàn)，幾千萬(wàn)，那么就會(huì)又遇到上面提到的浪費(fèi)空間的問(wèn)題。如果我們這個(gè)時(shí)候有一個(gè)能進(jìn)行去重且能進(jìn)行計(jì)數(shù)的數(shù)據(jù)結(jié)構(gòu)就好了。

這個(gè)時(shí)候 HyperLogLog 就閃亮登場(chǎng)了！它能提供不精確的去重計(jì)數(shù)方案(誤差值在 0.81% 左右)，不精確就不精確哇，UV 要你多精確？0.81%我們也能接受。最重要的是 HyperLogLog 只占用12KB的內(nèi)存。

使用方法和場(chǎng)景實(shí)踐

pfadd key element 添加

pfcount key 計(jì)算

pfmerge destkey sourcekey1 sourcekey2 ... 合并

命令都是 pf 開(kāi)頭是因?yàn)檫@是一個(gè)名叫 Philippe Flajolet 的教授發(fā)明的。

可以看到就這三個(gè)基本命令，很簡(jiǎn)單很容易掌握。那我們來(lái)動(dòng)手實(shí)踐一下吧。

BitMap

介紹和使用場(chǎng)景

首先我們?cè)賮?lái)思考一個(gè)比較有意思的場(chǎng)景，老板想讓你統(tǒng)計(jì)一年內(nèi)多個(gè)用戶(hù)之間他們同時(shí)在線(xiàn)的天數(shù)，這個(gè)時(shí)候你怎么辦？

你可能會(huì)想到使用 hash 存儲(chǔ)，這太浪費(fèi)空間了，有沒(méi)有更好的辦法呢？答案是有的，Redis 中使用了 bitmap位圖。

我們知道，字符串中一個(gè)字符是使用8個(gè)比特來(lái)表示的(如上圖)，在 Redis 中 bitmap 底層就是 string，也可以說(shuō) string 底層就是 bitmap。

如果有了這個(gè)我們是不是可以用來(lái)計(jì)算一個(gè)用戶(hù)在指定時(shí)間內(nèi)簽到的次數(shù)？也就是一個(gè)位置代表一天，0代表未簽到，1代表簽到，在上圖中，該用戶(hù)在八天內(nèi)簽到了四次。

Redis 中的 bitmap 還提供了多個(gè) bitmap 進(jìn)行與，或，異或運(yùn)算的命令，當(dāng)然還有單個(gè) bitmap 的 非 運(yùn)算。這是不是給你提供了一點(diǎn)思路對(duì)于我們一開(kāi)始的需求呢？

基本命令使用

setbit key index 0/1 設(shè)置某位的值

getbit key index 獲取某位的值

bitcount key start end 獲取指定范圍內(nèi)為1的數(shù)量

需要注意的是，這里的start 和 end是指的字符位置不是比特位置?。。“ㄏ旅娴?bitpos 也是

bitpos key bit start end 獲取第一個(gè)值為bit的從start到end字符索引范圍的位置

bitop and/or/xor/not destkey key1 key2 對(duì)多個(gè) bitmap 進(jìn)行邏輯運(yùn)算。

對(duì)于bitmap還有一個(gè)好玩的指令就是 bitfield ，這里我不做過(guò)多介紹，感興趣的同學(xué)自己可以了解一下。

動(dòng)手實(shí)踐

我們首先來(lái)實(shí)現(xiàn)一下統(tǒng)計(jì)用戶(hù)簽到次數(shù)的功能。

還記得我們一開(kāi)始的問(wèn)題嗎？統(tǒng)計(jì)一年內(nèi)多個(gè)用戶(hù)之間他們同時(shí)在線(xiàn)的天數(shù)，我們有了 bitmap 還怕什么。

GeoHash

介紹和場(chǎng)景運(yùn)用

GeoHash 常用來(lái)計(jì)算附近的人，附近的商店。

試想一下如果我們使用 關(guān)系數(shù)據(jù)庫(kù) 來(lái)存儲(chǔ)某個(gè)元素的地址 (id,經(jīng)度,緯度) 。這個(gè)時(shí)候我們?cè)撊绾斡?jì)算附近的人？難道我們要遍歷所有元素位置并做距離計(jì)算？這顯然不可能。

當(dāng)然你可以使用劃分區(qū)域并使用 SQL 語(yǔ)句圈出區(qū)域，然后建立雙向復(fù)合索引來(lái)提升性能，但是數(shù)據(jù)庫(kù)的并發(fā)能力畢竟有限，我們能不能使用 Redis 來(lái)做呢？

答案是可以的，Redis 中使用了 GeoHash 提供了很好的解決方案。具體原理是將地球看成一個(gè)平面，并把二維坐標(biāo)映射成一維(精度損失的原因)。如果對(duì)其中的算法感興趣你可以自己額外去了解，篇幅有限不做過(guò)多說(shuō)明。

基本命令和使用實(shí)戰(zhàn)

geoadd key longitude latitude element(后面可配置多個(gè)三元組) 添加元素

geodist key element1 element2 unit 計(jì)算兩個(gè)元素的距離

geopos key element [element] 獲取元素的位置

geohash key element 獲取元素hash

georadiusbymember key element distanceValue unit count countValue ASC/DESC [withdist] [withhash] [withcoord] 獲取元素附近的元素 可附加后面選項(xiàng)[距離][hash][坐標(biāo)]

georadius key longitude latitude distanceValue unit count countValue ASC/DESC [withdist] [withhash] [withcoord] 和上面一樣只是元素改成了指定坐標(biāo)值

總結(jié)

這篇文章中我想大家介紹了 Redis 另外的四種特殊數(shù)據(jù)結(jié)構(gòu)，他們分別是 BloomFilter,HyperLogLog,BitMap還有GeoHash。并且我還想你們介紹了如何使用他們，他們的運(yùn)用場(chǎng)景有哪些，希望對(duì)你們有幫助。

非常感謝你能看到這里，如果喜歡或者對(duì)你有幫助別忘了點(diǎn)贊哦。你也可以關(guān)注我，我會(huì)經(jīng)常做些學(xué)習(xí)分享給大家。