# 布隆过滤器

## 算法简介

布隆过滤器（Bloom Filter）是布隆在 1970 年提出的算法，可以用于检测一个元素是否存在于集合当中，优点是空间效率和查询效率都远超一般算法，缺点是有一定的误判率并且难以删除已经存在的元素。布隆过滤器的本质是一个很长的二进制向量和一系列的随机 hash 函数。

## 实现思路

判断一个元素是否存在于集合当中，一般的思路是先保存集合当中所有的元素，然后通过比较确定结果。但是随着集合中元素的增加，这种算法所消耗的空间也会越来也大，同时查询元素的速度也会越来越慢。

在布隆过滤器算法中，当一个元素被添加到集合当中时，先通过 N 个不同 hash 函数生成 N 个不同的 hash 值，然后在很长的二进制向量当中把 N 个 hash 值对应的位设置为 1。判断元素是否存在的时候，再检查这些 N 个 hash 值对应的位：如果有任何一个为 0 则表示元素肯定不存在，如果全部都为 1 则表示元素很大可能存在。

```
hash1(value) -> 1
hash2(value) -> 4
hash3(value) -> 7


       value
    /    |    \
   /     |     \
 hash1 hash2 hash3
   |     |     |
   v     v     v
+-+-+-+-+-+-+-+-+-+-+
|0|1|0|0|1|0|0|1|0|0|
+-+-+-+-+-+-+-+-+-+-+
 0 1 2 3 4 5 6 7 8 9
```

## 优点/缺点

相比于其它算法，布隆过滤器在空间和时间方面都有巨大的优势。另外，由于 hash 函数之间没有互相关系，因此方便程序并行计算。布隆过滤器本身不会存储数据，因此也适用于数据安全敏感的场景。

但是，布隆过滤器存在误判的概率，当存储的元素越来越多，误判的概率就越来越大。并且，一般情况下，布隆过滤不能删除已经存在的元素。

## 参考资料

* [数学之美系列二十一 － 布隆过滤器（Bloom Filter）](https://china.googleblog.com/2007/07/bloom-filter_7469.html)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gitbook.fantasticmao.cn/tech/shu-ju-jie-gou-he-suan-fa/bu-long-guolqi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.