文章目錄

• • 1. 位圖
  • 2. 位圖代碼
  • 3. 布隆過濾器 Bloom Filter
  • 4. 總結(jié)

1. 位圖

我們有1千萬個整數(shù)，整數(shù)的范圍在1到1億之間。如何快速查找某個整數(shù)是否在這1千萬個整數(shù)中呢？

• 當然，這個問題可以用散列表來解決。可以使用一種特殊的散列表，那就是位圖。
• 申請一個大小為1億、布爾類型（true或者false）的數(shù)組。將這1千萬個整數(shù)作為數(shù)組下標，將對應(yīng)的數(shù)組值設(shè)置成true。比如，整數(shù)5對應(yīng)下標為5的數(shù)組值設(shè)置為true，也就是array[5]=true。
• 查詢某個整數(shù)K是否在這1千萬個整數(shù)中的時候，只需將array[K]取出來，看是否等于true。如果等于true，那說明1千萬整數(shù)中包含這個整數(shù)K；相反，就表示不包含這個整數(shù)K。
• 不過，很多語言中提供的布爾類型，大小是1個字節(jié)的，并不能節(jié)省太多內(nèi)存空間。實際上，表示true和false，只需要**一個二進制位（bit）**就可以了。
• 我們可以借助編程語言中提供的數(shù)據(jù)類型，比如int、long、char等類型，通過位運算，用其中的某個位表示某個數(shù)字。

2. 位圖代碼

#include <iostream> #include <cstring> using namespace std; class BitMap {char *bytes; //char是1字節(jié)，8位int nbits; public:BitMap(int n){nbits = n;bytes = new char [nbits/8 + 1];memset(bytes, 0, (nbits/8+1)*sizeof(char));}~BitMap(){delete [] bytes;}void set(int k){if(k > nbits)return;int byteIndex = k/8;int bitIndex = k%8;bytes[byteIndex] |= (1<<bitIndex);}bool get(int k){if(k > nbits)return false;int byteIndex = k/8;int bitIndex = k%8;return (bytes[byteIndex] & (1 << bitIndex)) != 0;}void print(){for(int i = 15; i >= 0; --i)cout << get(i) << " ";} }; int main() {BitMap bm(8);bm.set(8);cout << bm.get(8) << endl;bm.print();return 0; }

比如上面例子，如果用散列表存儲這1千萬的數(shù)據(jù)，數(shù)據(jù)是32位的整型數(shù)，也就是需要4個字節(jié)的存儲空間，那總共至少需要40MB的存儲空間。如果通過位圖的話，數(shù)字范圍在1到1億之間，只需要1億個二進制位，1億/8/1024/1024 = 12, 也就是12MB左右的存儲空間就夠了。

不過，這里我們有個假設(shè)，就是數(shù)字范圍不是很大。如果數(shù)字的范圍很大，數(shù)字范圍不是1到1億，而是1到10億，那位圖的大小就是10億個二進制位，也就是120MB的大小，消耗的內(nèi)存空間，不降反增！

怎么辦？請布隆過濾器登場！

3. 布隆過濾器 Bloom Filter

• 布隆過濾器就是為了解決剛剛這個問題，對位圖這種數(shù)據(jù)結(jié)構(gòu)的一種改進。

還是剛剛那個例子，數(shù)據(jù)個數(shù)是1千萬，數(shù)據(jù)的范圍是1到10億。

• 布隆過濾器的做法是，我們?nèi)匀皇褂靡粋€1億個二進制大小的位圖，然后通過哈希函數(shù)，對數(shù)字進行處理，讓它落在這1到1億范圍內(nèi)。比如我們把哈希函數(shù)設(shè)計成f(x) = x%n。其中，x表示數(shù)字，n表示位圖的大小（1億），也就是，對數(shù)字跟位圖的大小進行取模求余。

• 哈希函數(shù)會存在沖突的問題，為了降低沖突概率，可以設(shè)計一個復(fù)雜點、隨機點的哈希函數(shù)。除此之外，還有其他方法嗎？

• 我們來看布隆過濾器的處理方法。既然一個哈希函數(shù)可能會存在沖突，那用多個哈希函數(shù)一起定位一個數(shù)據(jù)，是否能降低沖突的概率呢？

• 使用 K 個哈希函數(shù)，對同一個數(shù)字進行求哈希值，那會得到K個不同的哈希值，我們分別記作X₁，X₂，X₃，……X_k 。我們把這 K 個數(shù)字作為位圖中的下標，將對應(yīng)的BitMap[X₁],BitMap[X₂],BitMap[X₃],……BitMap[X_k]都設(shè)置成true，也就是說，我們用 K 個二進制位，來表示一個數(shù)字的存在。

• 當我們要查詢某個數(shù)字是否存在的時候，我們用同樣的 K 個哈希函數(shù)，對這個數(shù)字求哈希值，分別得到Y(jié)₁，Y₂，Y₃，……Y_k 。看這 K 個哈希值，對應(yīng)位圖中的數(shù)值是否都為true，都是true，這個數(shù)字存在，任意一個不為true，說明這個數(shù)字不存在。
  
  對于兩個不同的數(shù)字，經(jīng)過 K 個哈希函數(shù)處理之后，K 個哈希值都相同的概率就非常低了。盡管采用 K 個哈希函數(shù)之后，兩個數(shù)字哈希沖突的概率降低了，但是，這種處理方式又帶來了新的問題，那就是容易誤判。看下面例子。
  

• 布隆過濾器的誤判有一個特點，那就是，它只會對存在的情況有誤判。

• 如果某個數(shù)字經(jīng)過布隆過濾器判斷不存在，那說明這個數(shù)字真的不存在，不會誤判

• 如果某個數(shù)字經(jīng)過布隆過濾器判斷存在，有可能誤判，有可能并不存在。不過，只要我們調(diào)整哈希函數(shù)的個數(shù)、位圖大小跟要存儲數(shù)字的個數(shù)之間的比例，那就可以將這種誤判的概率降到非常低。

• 盡管布隆過濾器會存在誤判，但是，這并不影響它發(fā)揮大作用。很多場景對誤判有一定的容忍度。

4. 總結(jié)

布隆過濾器非常適合這種不需要100%準確的、允許存在小概率誤判的大規(guī)模判重場景。比如統(tǒng)計一個大型網(wǎng)站的每天的UV數(shù)，也就是每天有多少用戶訪問了網(wǎng)站，就可以使用布隆過濾器，對重復(fù)訪問的用戶，進行去重。

布隆過濾器的誤判率，主要跟哈希函數(shù)的個數(shù)、位圖的大小有關(guān)。往布隆過濾器中不停地加入數(shù)據(jù)之后，位圖中不是true的位置就越來越少了，誤判率就越來越高了。所以，對于無法事先知道要判重的數(shù)據(jù)個數(shù)的情況，我們需要支持自動擴容的功能。

當布隆過濾器中，數(shù)據(jù)個數(shù)與位圖大小的比例超過某個閾值的時候，我們就重新申請一個新的位圖。后面來的新數(shù)據(jù)，會被放置到新的位圖中。但是，如果我們要判斷某個數(shù)據(jù)是否在布隆過濾器中已經(jīng)存在，我們就需要查看多個位圖，相應(yīng)的執(zhí)行效率就降低了一些。

位圖、布隆過濾器應(yīng)用如此廣泛，很多編程語言都已經(jīng)實現(xiàn)了。比如 Java 中的 BitSet 類就是一個位圖，Redis 也提供了 BitMap 位圖類，Google 的 Guava 工具包提供了BloomFilter 布隆過濾器的實現(xiàn)。

課后思考
1.假設(shè)我們有1億個整數(shù)，數(shù)據(jù)范圍是從1到10億，如何快速并且省內(nèi)存地給這1億個數(shù)據(jù)從小到大排序？

傳統(tǒng)做法：1億個整數(shù)，存儲需要400M空間
位圖算法：數(shù)字范圍是1到10億，用位圖存儲125M就夠了，然后將1億個數(shù)字依次添加到位圖中，再將位圖按下標從小到大輸出值為1的下標，排序就完成了，時間復(fù)雜度為O(n)

總結(jié)

以上是生活随笔為你收集整理的数据结构--位图 BitMap的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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