Bloom Filter

Source: Jiuzhang's Tutorial: https://www.jiuzhang.com/tutorial/big-data-interview-questions/238

BF是一个更省空间的哈希表。在海量数据处理类问题中，我们经常需要用到哈希表，也经常会碰到内存不够的问题。那么 BF 就是一个很好的选择。

Bloom Filter一般有两个作用：

1. 检测一个元素在不在一个集合中

2. 统计一个元素的出现次数

BF能做的事情确实就是哈希表能做的事情，但是BF 相比哈希表，耗费更少的存储空间。既然节省了空间，同样也有一个副作用：存在 False Positive

什么是False Positive? 简单的说就是，如果是 Hash 的话，他说这个元素在集合里，那就是在集合里。

但BF不会有False Negative。BF 说这个元素不在集合里，那就一定不在集合里。

根据要处理的问题的不同，BF（BloomFilter的专业简称）可以分为：

1. 标准型布隆过滤器（Standard Bloom Filter，简写为 SBF，对应到 Java 里的 HashSet）

2. 计数型布隆过滤器（Counting Bloom Filter，简写为 CBF，对应到 Java 里的 HashMap）

k个独立的哈希函数

可以使用几个不同的算法，来获得不同的哈希函数。一个比较通用的哈希函数的写法是这样：

def hashfunc(string, hashsize):
    code = 0
    for c in string:
        code = code * 31 + ord(c)
        code = code % hashsize

    return code

在 LintCode 上练习这个知识点： http://www.lintcode.com/problem/hash-function/

如果需要设计 k 个独立的哈希函数，只需要简单的修改上面的函数中的 Magic Number31即可，比如换成 37，41 这样。

Magic Number 31 是什么？

上面的这个算法，相当于把一个字符串当做了 31 进制，然后转换为整数。一遍转换的过程中一遍对 hashsize 取模，避免溢出。

这个 31 并不是唯一的选择，但是有一些基本的法则我们需要遵循：

1. 不能太小。太小的话，容易出现 hashfunc 算出来的值在字符串比较短的时候出现扎堆的情况。增加了哈希碰撞的几率。

2. 不能太大。太大的话，影响了计算效率。

3. 尽量不要是合数。合数也可能会增加哈希碰撞的几率。

标准布隆过滤器 Standard Bloom Filter

标准布隆过滤器的作用相当于一个 HashSet，即提供了这样一个数据结构，他支持如下操作：

1. 在集合中加入一个元素

2. 判断一个元素是否在集合中（允许 False Positive）

实现步骤

1. 初始化：开一个足够大的 boolean 数组，初始值都是 false。

2. 插入一个元素：通过k个哈希函数，计算出元素的k个哈希值，对 boolean 数组的长度取模之后，标记对应的k个位置上的值为 true。

3. 查询一个元素：通过同样的k个哈希函数，在 boolean 数组中取出对应的k个位置上的值。如果都是 true，则表示该元素可能存在，如果有一个 false，则表示一定不存在。

伪代码 Pseudo Code

class StandardBloomFilter:

    def __init__(self, capacity, hash_functions):
        # capacity is the initial size of the SBF
        # it should be as big as possible to contains all
        # of the keys
        self.capacity = capacity
        self.bitset = [False] * capacity 

        # k hash functions
        self.hash_functions = hash_functions

    def add(self, key):
        for func in self.hash_functions:
            position = func(key) % self.capacity
            self.bitset[position] = True

    def contains(self, key):
        for func in self.hash_functions:
            position = func(key) % self.capacity
            if self.bitset[position] is False:
                return False

        return True

http://www.lintcode.com/problem/standard-bloom-filter/

空间优化

具体实现的时候，为了更好的节省空间，可以用位运算的方式来取代 boolean 数组。Java 中可以直接用 BitSet 这个结构。

Q: 如果空间不够了怎么办呢？一开始开的 boolean 数组不够的话，如果全部都被赋为 true 了，contains 不就每次都返回 true 了么？

A: 实际运用中，我们通常需要进行预估，也就是估算一下大概需要用到多少的空间，开多大比较合适。另外一个解决办法，是采用 Extended Bloom Filter。具体的解决方案是，当一个 BloomFilter 满了的时候，开一个新的，capacity 更大的（两倍） BloomFilter。原来的 Bloom Filter 依旧保留，这样插入的时候，总是插入到新的 BloomFilter 里，而查询的时候，所有的 BloomFilter 都要查一遍。

Q: 如何定义一个 BloomFilter 是不是满了？

A: 如果哈希函数用4个的话，boolean 数组的大小和实际能够存储的元素个数之间的比例，在 40: 1 比较合适。这是一个经验值。

计数布隆过滤器 Counting Bloom Filter

基于标准的 BloomFilter 稍加改动，把存储所用的 boolean 数组改为 int 数组，就成为了可以计数的 BloomFilter -> Counting Bloom Filter（简写为CBF）。这种数据结构类似 Java 中的 HashMap，但只能用作计数。提供如下的几种操作：

1. O(1)时间内，在集合中加入一个元素

2. O(1)时间内，统计某个元素在该集合中出现的次数 - 但是可能会比实际出现次数要大一些

实现步骤

1. 初始化：开一个足够大的 int 数组，初始值都是 0。

2. 插入一个元素：通过k个哈希函数，计算出元素的k个哈希值，对 int 数组的长度取模之后，将对应的k个位置上的值都加一

3. 查询一个元素的出现次数：通过同样的k哈希函数，在 int 数组中取出对应的k个位置上的值。并取其中的最小值来作为该元素的出现次数预估。

伪代码

class CountingBloomFilter:

    def __init__(self, capacity, hash_functions):
        # capacity is the initial size of the SBF
        # it should be as big as possible to contains all
        # of the keys
        self.capacity = capacity
        self.bitset = [0] * capacity 

        # k hash functions
        self.hash_functions = hash_functions

    def add(self, key):
        for func in self.hash_functions:
            position = func(key) % self.capacity
            self.bitset[position] += 1

    def contains(self, key):
        count = sys.maxint
        for func in self.hash_functions:
            position = func(key) % self.capacity
            count = min(count, self.bitset[position])

        return count

LintCode 练习地址

http://www.lintcode.com/problem/counting-bloom-filter/

Q & A

Q: 为什么要取最小值？ A: 比如我们使用两个哈希函数，key1 算出来的两个下标是 0, 1, key2 算出来的 两个下标是 1, 2。这里 counts[1] 会等于 2，他被 2个 key 都影响到了。所以取最小值，能够让这个计数尽可能的毕竟真实计数。

Q: 为什么说是预估的出现次数？而不是精确的出现次数？ A: 承接上面问题的解答，如果还有一个 key3 算出来的下标是 0 和 2。那么 counts[0~2] 都会是 2，无论对 key1~3 的任何一个 key 取计数，都得到的是 2，要比实际的出现次数大。

Q: CBF算出来的计数，有可能比实际出现次数小么？ A: 不可能