1 简介布隆过滤器

Bloom 过滤器的设计围绕以下原则展开：

• 1. 空间效率

与位图一样，布隆过滤器也是空间高效的。但是，布隆过滤器使用位数组和多个哈希函数来表示一组元素。数组的大小和哈希函数的数量经过精心选择，以平衡空间使用量和误报概率之间的权衡。通常，布隆过滤器使用的内存比直接列表或哈希表表示的集合少得多，但偶尔会出现误报。

• 2. 概率保证

布隆过滤器的一个关键设计特性是它是概率性的。虽然它可以保证元素不在集合中（如果哈希函数指示的位置中的任何位为 0），但它不能肯定地保证元素在集合中。布隆过滤器可能会返回误报，表明元素在集合中，但实际上它不在集合中。

• 3. 多个哈希函数

要将元素插入布隆过滤器，需要使用多个独立的哈希函数来计算位数组中的几个位置。这些位置中的每一个都设置为 1。查询时，使用相同的哈希函数。如果所有相应的位都设置为 1，则过滤器指示该元素可能在集合中。如果任何位为 0，则该元素肯定不在集合中。

• 4. 可扩展性

布隆过滤器旨在有效处理大型数据集。可以通过增加位数组的大小或使用更多哈希函数来降低误报率。这种灵活性允许根据应用程序的要求扩展布隆过滤器。

• 5. 固定大小和缺乏删除

与位图一样，布隆过滤器的大小通常在创建时固定。此外，由于哈希函数的重叠性质，布隆过滤器不支持删除，因为清除一个位可能会删除其他元素的证据。有一些变体（如计数布隆过滤器）允许删除，但标准布隆过滤器不允许。

• 6. 布隆过滤器的应用

Web 缓存：用于检查 URL 是否已缓存。
数据库：用于在数据库中执行更昂贵的查找之前快速测试某个项目是否存在于集合中。
网络应用程序：布隆过滤器通过过滤掉不必要的请求来帮助减少网络查询的开销。

2 位图和布隆过滤器设计比较

3 相似之处

空间效率：位图和布隆过滤器都旨在高效使用内存。

在这两种情况下，目标都是使用尽可能少的空间来表示数据（位图中的单个位或布隆过滤器中的一组元素）。

位级操作：两种结构都在位级进行操作，这使得它们的基本操作非常快，非常适合大规模应用程序。
可以使用高效的按位操作对两者进行操作。

固定大小：这两种数据结构通常在创建时都具有固定的大小。这使得内存使用量可预测，但限制了灵活性。

集合表示：两者都可用于表示集合中的成员资格。位图直接执行此操作（例如，固定宇宙中元素的存在或不存在），而布隆过滤器则以概率方式执行此操作。

4 差异

概率性质（误报）：

位图：位图提供精确结果。一位为 0 或 1，表示元素是否存在。
布隆过滤器：布隆过滤器引入了误报的可能性。

节省空间的代价是布隆过滤器可能会说某个元素在集合中，但实际上它不在。但是，没有误报；如果过滤器说某个元素不在集合中，那么它肯定不在。

多个哈希函数与直接索引：

位图：在位图中，每个位的位置直接对应于元素或条件。您无需为单个项目计算多个位置。
布隆过滤器：插入布隆过滤器的每个元素对应于位数组中的多个位置，由哈希函数确定。

内存开销和扩展：

位图：位图所需的内存随其所表示的宇宙（或元素数量）的大小线性增长。如果您拥有大量元素，则位图将需要更多空间。
布隆过滤器：布隆过滤器的内存与宇宙的大小无关，而是取决于所需的误报率和插入的元素数量。对于实际成员数远小于可能成员总数（稀疏数据）的大型集合，布隆过滤器的效率要高得多。

删除功能：

位图：您可以通过清除其相应位来轻松删除元素。
布隆过滤器：在布隆过滤器中删除元素并不简单，因为清除一个位可能会影响多个元素。计数布隆过滤器等特殊变体允许删除，但标准布隆过滤器不支持这一点。

用例：

位图：更适合精确的集合成员资格检查，表示大但稀疏的数组，或在固定的有限宇宙中使用（如内存分配表）。
布隆过滤器：非常适合空间宝贵且可以接受一些误报的情况，尤其是在大型动态数据集（如 Web 缓存或数据库系统）中。

结论

虽然位图和布隆过滤器在设计原理上有相似之处，特别是在空间效率和位级操作的使用方面，但它们的根本区别在于，布隆过滤器是概率数据结构，旨在用内存使用量换取偶尔的误报，而位图是确定性的。
当数据适合预定义的大小并且需要精确的成员资格检查时，位图是理想的选择。
在空间有限、可能元素的范围很大并且可以容忍一定误差（误报）的情况下，布隆过滤器大放异彩。