algorithm - 当我们处理非常大的数据时，何时使用布隆过滤器以及何时使用位图？

Question

我正在学习Bloom filter和BitMap（也称为位数组）并遇到一个问题，有人能给我一些关于何时使用布隆过滤器和何时使用位图的说明吗？

在我的理解中，我认为当我们需要找到最大的数字或想要对大量数据进行排序时，BitMap 更适合（纯数字）。

如果我们要检查某个 IP 地址是否包含在数十亿条已存在的记录中，那么布隆过滤器更适合（对于字符串或其他非纯数字）。

但是，我希望有人给我更详细的说明或建议，我在谷歌上搜索并没有找到一些有用的信息。提前致谢！

另外我不知道我是否应该将这个问题放在stackoverflow或其他网站上，如果它不是正确的网站，希望有人指出，谢谢！

标签： algorithmbitbitsetbloom-filter

Answer 1

何时使用布隆过滤器：如果您有一组（唯一条目列表）和哈希函数，则可以创建布隆过滤器。它允许类型为“条目 x 是否可能在集合中？”的查询。如果条目在集合中，查询将返回 true。对于不在集合中的条目，它可能返回 true，概率很低，通常为 1% 或更低（取决于布隆过滤器的大小）。您可以将 Bloom 过滤器设置为任意小，但对于 1% 左右的误报率，您需要每个条目大约 10 位。有使用更少空间的替代算法/数据结构，请参见例如https://github.com/FastFilter。顺便说一下，布隆过滤器在内部使用位数组。

何时使用位数组（也称为位集）：如果条目是 0..n 之间的数字，那么您可以使用位数组，如下所示：为每个条目设置位 x。这将需要 n 位（无论有多少条目）。因此，如果您的条目可能是大数字，那么就会出现问题：它会占用大量内存。但是，您可以创建一个稀疏位数组（也称为压缩位数组），例如使用https://roaringbitmap.org/。您不会像使用 Bloom 过滤器那样出现误报，但大小的使用很大程度上取决于您的数据（取决于您拥有的数字），比使用 Bloom 过滤器更重要。