1、什么情況下需要布隆過濾器？

先來看幾個(gè)比較常見的例子

• 字處理軟件中，需要檢查一個(gè)英語單詞是否拼寫正確
• 在 FBI，一個(gè)嫌疑人的名字是否已經(jīng)在嫌疑名單上
• 在網(wǎng)絡(luò)爬蟲里，一個(gè)網(wǎng)址是否被訪問過
• yahoo, gmail等郵箱垃圾郵件過濾功能

這幾個(gè)例子有一個(gè)共同的特點(diǎn)： 如何判斷一個(gè)元素是否存在一個(gè)集合中？

常規(guī)思路
數(shù)組
鏈表
樹、平衡二叉樹、Trie
Map (紅黑樹)
哈希表

雖然上面描述的這幾種數(shù)據(jù)結(jié)構(gòu)配合常見的排序、二分搜索可以快速高效的處理絕大部分判斷元素是否存在集合中的需求。但是當(dāng)集合里面的元素?cái)?shù)量足夠大，如果有500萬條記錄甚至1億條記錄呢？這個(gè)時(shí)候常規(guī)的數(shù)據(jù)結(jié)構(gòu)的問題就凸顯出來了。數(shù)組、鏈表、樹等數(shù)據(jù)結(jié)構(gòu)會(huì)存儲(chǔ)元素的內(nèi)容，一旦數(shù)據(jù)量過大，消耗的內(nèi)存也會(huì)呈現(xiàn)線性增長(zhǎng)，最終達(dá)到瓶頸。有的同學(xué)可能會(huì)問，哈希表不是效率很高嗎？查詢效率可以達(dá)到O(1)。但是哈希表需要消耗的內(nèi)存依然很高。使用哈希表存儲(chǔ)一億 個(gè)垃圾 email 地址的消耗？哈希表的做法：首先，哈希函數(shù)將一個(gè)email地址映射成8字節(jié)信息指紋；考慮到哈希表存儲(chǔ)效率通常小于50%（哈希沖突）；因此消耗的內(nèi)存：8 * 2 * 1億 字節(jié) = 1.6G 內(nèi)存，普通計(jì)算機(jī)是無法提供如此大的內(nèi)存。這個(gè)時(shí)候，布隆過濾器（Bloom Filter）就應(yīng)運(yùn)而生。在繼續(xù)介紹布隆過濾器的原理時(shí)，先講解下關(guān)于哈希函數(shù)的預(yù)備知識(shí)。

2、哈希函數(shù)

哈希函數(shù)的概念是：將任意大小的數(shù)據(jù)轉(zhuǎn)換成特定大小的數(shù)據(jù)的函數(shù)，轉(zhuǎn)換后的數(shù)據(jù)稱為哈希值或哈希編碼。下面是一幅示意圖：

可以明顯的看到，原始數(shù)據(jù)經(jīng)過哈希函數(shù)的映射后稱為了一個(gè)個(gè)的哈希編碼，數(shù)據(jù)得到壓縮。哈希函數(shù)是實(shí)現(xiàn)哈希表和布隆過濾器的基礎(chǔ)。

3、布隆過濾器介紹

• 巴頓.布隆于一九七零年提出
• 一個(gè)很長(zhǎng)的二進(jìn)制向量 （位數(shù)組）
• 一系列隨機(jī)函數(shù) (哈希)
• 空間效率和查詢效率高
• 有一定的誤判率（哈希表是精確匹配）

存在：在集合內(nèi)（可能錯(cuò)誤）”和“不在集合內(nèi)（絕對(duì)不在集合內(nèi)）”兩種情況，可見 Bloom filter 是犧牲了正確率換取時(shí)間和空間。

3.1布隆過濾器原理

布隆過濾器（Bloom Filter）的核心實(shí)現(xiàn)是一個(gè)超大的位數(shù)組和幾個(gè)哈希函數(shù)。假設(shè)位數(shù)組的長(zhǎng)度為m，哈希函數(shù)的個(gè)數(shù)為k。

布隆過濾器原理很簡(jiǎn)單：就是把一個(gè)字符串哈希成一個(gè)整數(shù)key，然后選取一個(gè)很長(zhǎng)的比特序列，開始都是0，在key把此位置的0變?yōu)?；下次進(jìn)來一個(gè)字符串，哈希之后的值key，如果在此比特位上的值也是1，那么就說明這個(gè)字符串存在了。

以上圖為例，具體的操作流程：假設(shè)集合里面有3個(gè)元素{x, y, z}，哈希函數(shù)的個(gè)數(shù)為3。首先將位數(shù)組進(jìn)行初始化，將里面每個(gè)位都設(shè)置位0。對(duì)于集合里面的每一個(gè)元素，將元素依次通過3個(gè)哈希函數(shù)進(jìn)行映射，每次映射都會(huì)產(chǎn)生一個(gè)哈希值，這個(gè)值對(duì)應(yīng)位數(shù)組上面的一個(gè)點(diǎn)，然后將位數(shù)組對(duì)應(yīng)的位置標(biāo)記為1。查詢W元素是否存在集合中的時(shí)候，同樣的方法將W通過哈希映射到位數(shù)組上的3個(gè)點(diǎn)。如果3個(gè)點(diǎn)的其中有一個(gè)點(diǎn)不為1，則可以判斷該元素一定不存在集合中。反之，如果3個(gè)點(diǎn)都為1，則該元素可能存在集合中。注意：此處不能判斷該元素是否一定存在集合中，可能存在一定的誤判率?？梢詮膱D中可以看到：假設(shè)某個(gè)元素通過映射對(duì)應(yīng)下標(biāo)為4，5，6這3個(gè)點(diǎn)。雖然這3個(gè)點(diǎn)都為1，但是很明顯這3個(gè)點(diǎn)是不同元素經(jīng)過哈希得到的位置，因此這種情況說明元素雖然不在集合中，也可能對(duì)應(yīng)的都是1，這是誤判率存在的原因。

布隆過濾器添加元素

• 將要添加的元素給k個(gè)哈希函數(shù)
• 得到對(duì)應(yīng)于位數(shù)組上的k個(gè)位置
• 將這k個(gè)位置設(shè)為1

布隆過濾器查詢?cè)?/h4>

• 將要查詢的元素給k個(gè)哈希函數(shù)
• 得到對(duì)應(yīng)于位數(shù)組上的k個(gè)位置
• 如果k個(gè)位置有一個(gè)為0，則肯定不在集合中
• 如果k個(gè)位置全部為1，則可能在集合中

3.2布隆過濾器實(shí)現(xiàn)

下面給出python的實(shí)現(xiàn)，使用murmurhash算法

#!/usr/bin/python
# -*- coding: utf-8 -*-

import mmh3
from bitarray import bitarray
"""
首先需要使用pip安裝這兩個(gè)依賴的包
"""


BIT_SIZE = 5000000

class BloomFilter:
    
    def __init__(self):
        # Initialize bloom filter, set size and all bits to 0
        bit_array = bitarray(BIT_SIZE)
        bit_array.setall(0)

        self.bit_array = bit_array
        
    def add(self, url):
        # Add a url, and set points in bitarray to 1 (Points count is equal to hash funcs count.)
        # Here use 7 hash functions.
        point_list = self.get_postions(url)

        for b in point_list:
            self.bit_array[b] = 1

    def contains(self, url):
        # Check if a url is in a collection
        point_list = self.get_postions(url)

        result = True
        for b in point_list:
            result = result and self.bit_array[b]
    
        return result

    def get_postions(self, url):
        # Get points positions in bit vector.
        point1 = mmh3.hash(url, 41) % BIT_SIZE
        point2 = mmh3.hash(url, 42) % BIT_SIZE
        point3 = mmh3.hash(url, 43) % BIT_SIZE
        point4 = mmh3.hash(url, 44) % BIT_SIZE
        point5 = mmh3.hash(url, 45) % BIT_SIZE
        point6 = mmh3.hash(url, 46) % BIT_SIZE
        point7 = mmh3.hash(url, 47) % BIT_SIZE


        return [point1, point2, point3, point4, point5, point6, point7]

# 測(cè)試一下
if __name__ == '__main__':
    bloom = BloomFilter()
    bloom.add("www.baidu.com")
    bloom.add("www.yahoo.com")
    bloom.add("www.tencen.com")
    flag = bloom.contains("www.baidu.com")
    print flag

至于Java版的實(shí)現(xiàn)，可以參考:

import java.util.BitSet;

/**
 *
 * @author xkey
 */
public class BloomFilter {

    private static final int DEFAULT_SIZE = 2 << 24;//布隆過濾器的比特長(zhǎng)度
    private static final int[] seeds = {3,5,7, 11, 13, 31, 37, 61};//這里要選取質(zhì)數(shù)，能很好的降低錯(cuò)誤率
    private static BitSet bits = new BitSet(DEFAULT_SIZE);
    private static SimpleHash[] func = new SimpleHash[seeds.length];

    public static void addValue(String value)
    {
        for(SimpleHash f : func)//將字符串value哈希為8個(gè)或多個(gè)整數(shù)，然后在這些整數(shù)的bit上變?yōu)?
            bits.set(f.hash(value),true);
    }
    
    public static void add(String value)
    {
        if(value != null) addValue(value);
    }
    
    public static boolean contains(String value)
    {
        if(value == null) return false;
        boolean ret = true;
        for(SimpleHash f : func)//這里其實(shí)沒必要全部跑完，只要一次ret==false那么就不包含這個(gè)字符串
            ret = ret && bits.get(f.hash(value));
        return ret;
    }
    
    public static void main(String[] args) {
        String value = "xkeyideal@gmail.com";
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
        add(value);
        System.out.println(contains(value));
    }
}

class SimpleHash {//這玩意相當(dāng)于C++中的結(jié)構(gòu)體

    private int cap;
    private int seed;

    public  SimpleHash(int cap, int seed) {
        this.cap = cap;
        this.seed = seed;
    }

    public int hash(String value) {//字符串哈希，選取好的哈希函數(shù)很重要
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        return (cap - 1) & result;
    }
}

4、總結(jié)

在計(jì)算機(jī)這個(gè)領(lǐng)域里，我們常常碰到時(shí)間換空間或空間換時(shí)間的情況，為了達(dá)到某一方面的性能，犧牲另外一方面。BloomFilter在時(shí)間和空間著兩者之間引入了另外一個(gè)概念——錯(cuò)誤率。也就是前文提到的布隆過濾不能準(zhǔn)確判斷一個(gè)元素是否在集合內(nèi)（類似的設(shè)計(jì)還有基數(shù)統(tǒng)計(jì)法）。引入錯(cuò)誤率后，極大的節(jié)省了存儲(chǔ)空間。
自從Burton Bloom在70年代提出Bloom Filter之后，Bloom Filter就被廣泛用于拼寫檢查和數(shù)據(jù)庫(kù)系統(tǒng)中。近一二十年，伴隨著網(wǎng)絡(luò)的普及和發(fā)展，Bloom Filter在網(wǎng)絡(luò)領(lǐng)域獲得了新生，各種Bloom Filter變種和新的應(yīng)用不斷出現(xiàn)。可以預(yù)見，隨著網(wǎng)絡(luò)應(yīng)用的不斷深入，新的變種和應(yīng)用將會(huì)繼續(xù)出現(xiàn)，Bloom Filter必將獲得更大的發(fā)展。