BitSet 在 List、Set 上的用例

Question

BitSet 优于 Set 和 List 的用例是什么？此外，它对性能有什么影响吗？

至少，我想知道 BitSet 的最佳用例以及何时需要在生产代码中使用它们，而不考虑问题中提到的其他数据结构。

Answer 1

一般用例： 如果值 V 存在于数据集 DS 中，则进行搜索.

特殊用例： 有一个组织在数据库中存储了员工电子邮件的数据集 DS。您想要实施一个解决方案来验证在创建新员工帐户时数据库 DS 中是否已经存在这样的电子邮件 V。理想情况下，您希望避免对 DB 的额外调用。该组织的员工总数为 220 万（根据现有统计数据，沃尔玛在 2019 年拥有）。

理论： 为避免对数据库的额外调用，您可以将数据库中的所有现有电子邮件放入某个集合并搜索电子邮件是否已存在在数据库中针对此集合。如果我们谈论 List 和 Set，它们都自己至少存储数据元素，并可能附加基于支持数据结构的开销，例如，LinkedList 将需要指针的内存开销。我们很有可能没有足够的内存来将所有这些数据放入我们的集合中。

现在，是时候谈谈布隆过滤器了。 Bloom Filter 是一种快速且内存高效的概率数据结构。概率数据结构提供了内存高效的解决方案，并在提供“可能”结果而不是“保证”结果（上面讨论过）的权衡下进行了权衡。具有 1% 错误和最佳数量的散列函数（极快的散列函数）的布隆过滤器每个元素只需要大约 9.6 位，无论元素的大小如何。布隆过滤器 本身不存储数据元素。

Bloom 过滤器中有 2 个主要组件：

位数组（在Java中可以用java.util.BitSetclass表示）
哈希函数（一个或多个）

布隆过滤器中有2个操作：

插入

值 V 由 K 散列函数散列生成 K 不同的索引。

这些指数的值标记为 1（真）。

//see more details about actual implementation by the link below
BloomFilter bf = new BloomFilter(0.1, 10); 
//BitSet {0,0,0,0,0,0,0,0,0,0}
bf.add("tim.brand@organization.com");
//BitSet {0,1,0,1,0,0,0,1,0,0}
bf.add("angel.born1@organization.com");
//BitSet {0,1,0,1,1,0,0,1,0,1}
bf.add("casey.clous@organization.com");
//BitSet {1,1,0,1,0,0,1,1,0,0}

搜索
1. 值 V 由 K 散列函数散列生成 K 不同的索引。
2. 检查这些索引的值，如果它们都是 1，那么很有可能在数据集 DS 中包含此数据（需要调用 DB）。如果其中任何一个为零，那么我们肯定不会在数据集中出现此值 DS（不需要调用 DB）。

调查结果： 因此，在这种特殊情况下，基于 BitSet 的 BloomFilter 似乎比 Set 或列表.

链接：

注意：有使用函数和布隆过滤器参数调整的要求，但它们超出了本题的范围。

BitSet 在 List、Set 上的用例

Use cases of the BitSet over List, Set

java

list

set

bitset