布隆过滤器

布隆过滤器应用场景：

1. yahoo, gmail等邮箱垃圾邮件过滤功能

2. 网络爬虫里，记录一个网址是否被访问过

3. 文档编辑器，检查一个英语单词拼写是否正确

4. 检查一个嫌疑人的名字是否在嫌疑名单上

常规思路：

    数组

    链表

    树、平衡树、Trie

    Map(红黑树)

    哈希表

缺陷：

    一旦数据量过大，消耗的内存呈线性增长，容易达到瓶颈。

哈希函数：

    将任意大小的数据转换成特定大小的数值的函数，转换后的数值被称为哈希值或哈希编码。

布隆过滤器介绍：

1970 年提出

一个很长的二进制向量（位数组）

一系列随机函数（哈希函数）

空间效率和查询效率高

有一定的误判率（哈希表是精确匹配）

添加元素

1. 计算

2. 设置

查询元素

1. 计算

2. 判断