如何判斷一個(gè)元素是否存在于一個(gè)億級(jí)數(shù)據(jù)集中？

布隆過(guò)濾器的概念
布隆過(guò)濾器（Bloom Filter）于 1970 年由布隆提出的，是專門(mén) 用于檢索一個(gè)元素是否存在于一個(gè)集合中的算法。

你可能會(huì)想，判斷一個(gè)元素是否在集合中，這不就是集合自帶的功能嗎？

元素?cái)?shù)量少的時(shí)候的確沒(méi)問(wèn)題，但如果有海量元素時(shí)就麻煩了，例如千萬(wàn)，甚至上億個(gè)元素，而且每個(gè)元素的大小不一，有可能很大，這時(shí)集合的空間效率和查詢效率都會(huì)堪憂。

而布隆過(guò)濾器就可以巧妙的解決這個(gè)問(wèn)題，它包括了一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列的hash函數(shù)，它不會(huì)實(shí)際存儲(chǔ)元素內(nèi)容，只是在二進(jìn)制向量中標(biāo)識(shí)這個(gè)元素是否存在，而 hash 函數(shù)就是用來(lái)定位元素的。

2. 使用場(chǎng)景
   布隆過(guò)濾器的核心作用是 判斷元素是否存在 ，在如今海量數(shù)據(jù)場(chǎng)景中可以起到非常大的作用。

例如：

2.1 防止數(shù)據(jù)庫(kù)穿庫(kù)
Bigtable、HBase 和 Cassandra 等大數(shù)據(jù)存儲(chǔ)系統(tǒng)也會(huì)使用布隆過(guò)濾器。

查詢操作是磁盤(pán)I/O，代價(jià)高昂，如果大量的查詢不存在的數(shù)據(jù)，就會(huì)嚴(yán)重影響數(shù)據(jù)庫(kù)性能。

使用布隆過(guò)濾器可以提前判斷不存在的數(shù)據(jù)，避免不必要的磁盤(pán)操作。

2.2 防止緩存穿透
查詢時(shí)一般會(huì)先判斷是否在緩存中，如果沒(méi)有，就讀DB，并放入緩存。

這是正常流程，沒(méi)有問(wèn)題。

但如果有惡意請(qǐng)求，一直查詢不存在的數(shù)據(jù)，例如查詢用戶abc的詳細(xì)信息，而abc根本不存在。

按照正常流程的話，就肯定會(huì)去讀DB，那數(shù)據(jù)庫(kù)的壓力就大了。

這時(shí)就可以使用布隆過(guò)濾器，例如請(qǐng)求用戶abc的時(shí)候，先判斷此用戶是否存在，不存在就直接返回了，避免了數(shù)據(jù)庫(kù)查詢。

2.3 爬蟲(chóng)URL去重
避免爬取相同URL地址。

反垃圾郵件
從數(shù)十億垃圾郵件列表中判斷某郵箱是否為垃圾郵箱。

3. 實(shí)現(xiàn)原理
   我們通過(guò)一個(gè)例子來(lái)理解其原理。

假設(shè)一個(gè)二進(jìn)制數(shù)組，長(zhǎng)度為8，初始值都為0（0表示不存在）。

現(xiàn)添加元素 張三 ，先通過(guò)hash函數(shù)定位其在二進(jìn)制數(shù)組的位置，然后將此位置的值設(shè)為 1 ：

hash2(張三) % 8 = 4

現(xiàn)在需要判斷 李四 是否存在，用同樣的方法計(jì)算出其位置，然后取此位置的值

值為 0 ，說(shuō)明 李四 不存在。

這就是基本原理。

我們都知道哈希沖突是普遍存在的，所以通過(guò)一個(gè)hash函數(shù)定位元素是不可靠的。

例如張三、王五的hash定位都是4：

hash2(張三) % 8 = 4

hash2(王五) % 8 = 4

張三 是已經(jīng)存在的元素， 王五 不存在，但因?yàn)? [4] 的值是 1 ，所以對(duì) 王五 的判斷結(jié)果是 存在 ，這就誤判了。

為了解決哈希沖突的問(wèn)題，通常會(huì)使用多個(gè)hash函數(shù)對(duì)元素進(jìn)行定位，例如：

同一個(gè)元素，經(jīng)過(guò)多個(gè)不同的hash算法，計(jì)算出來(lái)的結(jié)果相同的概率就非常低了。

計(jì)算出來(lái)的位置的值如果包含 0 ，那么可以肯定元素一定不存在

相反，如果都是1，卻不能肯定元素一定存在，因?yàn)榭赡苡泄_突

Redis 實(shí)現(xiàn)布隆過(guò)濾器
Redis 4.0 推出了 module 模式，可以開(kāi)發(fā)擴(kuò)展模塊， RedisBloom 就是布隆過(guò)濾器的擴(kuò)展模塊。

實(shí)踐
啟動(dòng)帶有 RedisBloom 的 Redis 環(huán)境：

docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest

進(jìn)入容器中的 redis 客戶端：

# 進(jìn)入容器

docker exec -it redis-redisbloom bash

# 登錄redis客戶端

redis-cli

添加元素：

127.0.0.1:6379> BF.ADD newFilter foo

(integer) 1

檢測(cè)元素是否存在：

127.0.0.1:6379> BF.EXISTS newFilter foo

(integer) 1

127.0.0.1:6379> BF.EXISTS newFilter foo2

(integer) 0