> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/other-algorithms-and-data-structure/bloom-filter.md).

# 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 Number`31`即可，比如换成 37，41 这样。

**Magic Number 31 是什么？**

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

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

1. 不能太小。太小的话，容易出现 hashfunc 算出来的值在字符串比较短的时候出现扎堆的情况。增加了哈希碰撞的几率。
2. 不能太大。太大的话，影响了计算效率。
3. 尽量不要是合数。合数也可能会增加哈希碰撞的几率。

## 标准布隆过滤器 Standard Bloom Filter

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

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

### 实现步骤

1. **初始化**：开一个足够大的 boolean 数组，初始值都是 false。
2. **插入一个元素**：通&#x8FC7;***k*****个哈希函数**，计算出元素&#x7684;***k*****个哈希值**，对 boolean 数组的长度取模之后，标记对应&#x7684;***k*****个位置**上的值为 true。
3. **查询一个元素**：通过同样&#x7684;***k*****个哈希函数**，在 boolean 数组中取出对应&#x7684;***k*****个位置**上的值。如果都是 true，则表示该元素`可能存在`，如果有一个 false，则表示`一定不存在`。

### 伪代码 Pseudo Code

```python
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*个位置上的值。并取其中的`最小值`来作为该元素的出现次数预估。

### 伪代码

```python
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: 不可能