BloomFilter 是一个哈希索引结构，采用类似 BitMap 的方式存储数据，所以空间利用率很高，其独特的地方在于使用多个哈希函数来避免哈希冲突。

简介 #

简单来说，Bloom Filter 是一种空间效率很高的随机数据结构，其工作原理很简单。

在写入一个元素时，通过 K 个相互独立的 Hash 函数将这个元素映射到一个位图 (BitMap) 中的 K 个点，将对应的位置设置为 1 。查询时，同样计算 K 个 Hash 值，如果这 K 个位置只要有一个是 0 ，那么被检索的元素 肯定 不存在；如果都为 1 ，只能判定大概率存在，而不是一定存在。

如上图所示，BitMap 初始化时为全 0，插入 x 时被 3 个哈希函数分别映射到 3 个不同的位上 (置1)；查询 x 时，只有被这3个函数映射到的bit位全部是1才能说明x可能存在，但凡至少出现一个0表示x肯定不存在。

使用限制 #

BloomFilter 在提高效率的同时，存在着两个问题：

• 误报 False Positive ，也就是能确定一定不存在的元素，但无法保证一定存在 (认为存在，但实际可能不存在) ，这主要是由于哈希冲突以及多个元素映射到相同位上导致。
• 不允许删除，因为只有一位，删除时可能导致本来有多个元素的位被删除，就可能导致本来存在，却误判为不存在，带来的问题要严重很多。

也就是说，BloomFilter 允许出现 Probably YES 但必须确保 Definitely NO 。