java - BitSet 在 List、Set 上的用例

Question

在哪些用例中 BitSet 应该优于 Set 和 List？此外，它对性能有什么影响吗？

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

Answer 1

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

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

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

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

布隆过滤器中有两个主要组件:

• bite 数组(在 Java 中可以使用 java.util.BitSet 类表示)
• 哈希函数(一个或多个)

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

• 插入
  1. 值 V 由 K 个哈希函数进行哈希处理，生成 K 个不同的索引。
  2. 这些索引的值标记为 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("<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="5024393d7e3222313e34103f2237313e392a3124393f3e7e333f3d" rel="noreferrer noopener nofollow">[email protected]</a>");
     //BitSet {0,1,0,1,0,0,0,1,0,0}
     bf.add("<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="72131c15171e5c101d001c43321d0015131c1b0813061b1d1c5c111d1f" rel="noreferrer noopener nofollow">[email protected]</a>");
     //BitSet {0,1,0,1,1,0,0,1,0,1}
     bf.add("<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="690a081a0c10470a05061c1a29061b0e08070013081d000607470a0604" rel="noreferrer noopener nofollow">[email protected]</a>");
     //BitSet {1,1,0,1,0,0,1,1,0,0}
     

• 搜索
  1. 值 V 由 K 个哈希函数进行哈希处理，生成 K 个不同的索引。
  2. 检查这些索引的值，如果它们全部为 1，则很有可能在数据集 DS 中包含此数据(需要调用 DB)。如果其中任何一个为零，那么我们肯定在数据集 DS 中不存在该值(不需要调用 DB)。

调查结果: 因此，在这种特殊情况下，基于 BitSet 的 BloomFilter 似乎比 Set 或 List 更高效。

链接:

• Book: Java Coding Problems by Anghel Leonard (128. Bloom filter)
• Bloom Filter implementation in Java
• Bloom Filters in Action
• Probabilistic Data structures: Bloom filter

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