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

Question

我正在学习 Bloom filter 和 BitMap(也称为 Bit Array )并且遇到了一个问题，有人可以给我一些指导吗什么时候用布隆过滤器，什么时候用位图？

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

如果我们想检查一些IP地址是否包含在数十亿条现有记录中，布隆过滤器更合适(对于字符串或其他非纯数字)。

但是，我想有人给我更详细的指导或建议，我在谷歌上搜索过，没有找到一些有用的信息。提前致谢!

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

Answer 1

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

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