摘要：

判斷目標值是否在一個大的集合中是比較常見的業務場景，相應的解決方案有很多，比如大的Hash表、Byte數組、BitSet等方案。當集合非常大的時候，這些方案在內存佔用方面都比較大。BitSet方案相對比較可行。

BloomFilter是解決這種問題最好的方案，它在內存佔用、查詢性能等方面都是最優秀的，但是它有一定的誤判概率，這種誤判概率是可以接受的。

假設我們有這樣的一個業務邏輯：

我們有一個網站，並且網站的流量和獨立用戶數非常大。當有用戶訪問我們網站的時候，我們需要判斷該用戶是否是第一次訪問我們的網站。這是一個很場景的業務場景，我們可以想到以下兩種方案來解決該問題。

一、Hash表來存儲每個用戶的IP

當有用戶訪問網站發送請求的時候，我們把用戶的IP存到一張Hash表中。當有用戶發送訪問請求的時候，我們先去Hash表中找該IP，如果可以找到，則證明用戶訪問過。Hash表的存取時間複雜度都是O(1)，效率很高。

這種方案看似沒什麼問題，但是前提是網站的獨立用戶數不大。如果網站的獨立用戶數非常大，我們假設達到了1個億。那這1個億的IP Hash值需要多大的內存空間呢？每個ip的長度是15，一共需要15 * 100000000 = 1500000000Bytes = 1.4G，這還沒考慮hash衝突的問題（hash表中的槽位越多，越浪費空間，槽位越少，效率越低）。

二、IP轉換成無符號的int型值來存儲

Hash表佔用太大的內存空間，為了節省內存空間。我們可以把ip轉換成無符號的int型值來存儲，這樣一個ip只需要佔用4個字節就行了，這時1億個ip佔用的空間是4 * 100000000 = 400000000Bytes = 380M，空間消耗降低了很多。

三、BitSet

32位無符號int型能表示的最大值是4294967295，所有的ip都在這個範圍內，我們可以用一個bit位來表示某個ip是否出現過，如果出現過，就把代表該ip的bit位置為1，那麼我們最多需要429496729個bit就可以表示所有的ip了。

舉個例子比如127.0.0.1轉換成int是167772161，那麼把長度為4294967295的bit數組的第167772161個位置置為1即可，當有ip訪問時，只需要檢查該標誌位是否為1就行了。

<code>4294967295bit = 536870912Byte = 512M/<code>

如果用hash表示所有4294967295範圍內的數組的話，需要十幾G的空間。

我們來看看BitSet具體怎樣實現。

首先，比如我們有一個長度=2的byte數組，2個字節一共有16位，可以表示0-15的數字是否存在。比如我們要驗證11是否出現過，那麼我們先檢查第11個位置是否為1，如果為0，說明11沒出現過，然後我們把第11位置為1，表示11已經出現過了

所以，BitSet基本只有兩個操作，set(int value) 和 isHas(int value)

• set(int value)

我們先來看set怎麼實現，因為一個byte佔8位，所以對於一個給定的value，我們先求出該value應該位於哪個Byte上，這很簡單，

<code> int byteIndex = value / 8/<code>

找到value在byte數組中的位置後，再就是在該字節中尋找表示value的bit位，我們知道，一個byte其實就是一個長為8的bit數組，那麼value在該bit數組中的位置也就很好算了

<code>int bitIndex = value % 8;/<code>

最後我們把該bit位設置為1就可以了

<code>byte[byteIndex] = byte[byteIndex] | 1 << ( 7 - bitIndex)

/<code>

<code>public void set(int value){

int byteIndex = value / 8;

int bitIndex = value % 8;

byte[byteIndex] = byte[byteIndex] | 1 << (7 - bitIndex)

}/<code>

• isHas(int value)

<code>public boolean isHash(int value){

int byteIndex = value / 8;

int bitIndex = value % 8;

return byte[byteIndex] & 1 << (7 - bitIndex) > 0 


}/<code>

BitSet的侷限性

BitSet有兩個比較侷限的地方：

• 當樣本分佈極度不均勻的時候，BitSet會造成很大空間上的浪費。

舉個例子，比如你有10個數，分別是1、2、3、4、5、6、7、8、99999999999；那麼你不得不用99999999999個bit位去實現你的BitSet,而這個BitSet的中間絕大多數位置都是0，並且永遠不會用到，這顯然是極度不划算的。

• 當元素不是整型的時候，BitSet就不適用了。

想想看，你拿到的是一堆url，然後如果你想用BitSet做去重的話，先得把url轉換成int型，在轉換的過程中難免某些url會計算出相同的int值，於是BitSet的準確性就會降低。

那針對這兩種情況有沒有解決辦法呢？

• 第一種分佈不均勻的情況可以通過hash函數，將元素都映射到一個區間範圍內，減少大段區間閒置造成的浪費，這很簡單，取模就好了，難的是取模之後的值保證不相同，即不發生hash衝突。

• 第二種情況，把字符串映射成整數是必要的，那麼唯一要做的就是保證我們的hash函數儘可能的減少hash衝突，一次不行我就多hash幾次，hash還是容易碰撞，那我就擴大數組的範圍，使hash值儘可能的均勻分佈，減少hash衝突的概率。

基於這種思想，BloomFilter誕生了。

BloomFilter

BloomFiler又叫布隆過濾器，下面舉例說明BlooFilter的實現原理：

比如你有10個Url，你完全可以創建一長度是100bit的數組，然後對url分別用5個不同的hash函數進行hash，得到5個hash後的值，這5個值儘可能的保證均勻分佈在100個bit的範圍內。然後把5個hash值對應的bit位都置為1，判

BloomFilter的核心思想有兩點：

• 多個hash，增大隨機性，減少hash碰撞的概率。

• 擴大數組範圍，使hash值均勻分佈，進一步減少hash碰撞的概率。

BloomFilter的準確性

儘管BloomFilter已經儘可能的減小hash碰撞的概率了，但是，並不能徹底消除，因此正如上面提到的：

• 如果對應的bit位值都為1，那麼也不能肯定這個url一定存在。

• BloomFilter其實是存在一定的誤判的，這個誤判的概率顯然和數組的大小以及hash函數的個數以及每個hash函數本身的好壞有關。不過這種誤判概率還是比較小的，空間利用率也很高。

BloomFilter的應用

• 黑名單

比如郵件黑名單過濾器，判斷郵件地址是否在黑名單中

• 排序(僅限於BitSet)

BitSet在set(int value)的時候，“順便”把value也給排序了。

• 網絡爬蟲

判斷某個URL是否已經被爬取過

• K-V系統快速判斷某個key是否存在

典型的例子有Hbase，Hbase的每個Region中都包含一個BloomFilter，用於在查詢時快速判斷某個key在該region中是否存在，如果不存在，直接返回，節省掉後續的查詢。

BloomFilter Golang代碼實現：

• 1、定義BloomFilter以及Hash方法

• 2、初始化BloomFilter

• 3、定義add方法

• 4、定義contain方法

最後：

布隆過濾器是一個非常經典的算法，在大數匹配的場景中很有用。如果業務中涉及到判斷目標值是否在一個大的集合中，可以考慮選擇使用布隆過濾器。

閱讀更多 阿邁達聊技術 的文章

關鍵字: Hash BitSet 方案