我需要实现一个“常量”集。即只支持成员资格测试的数据结构。另外（当然），我需要一个工厂例程，给定一个元素列表，构造一个常量集。
请注意，不仅常量集不允许突变，而且我不需要返回新常量集的“添加”操作（即，一旦发生初始化，我只对测试元素是否感兴趣是否在集合中）。
旧的哈希表在这里是一个明显的选择，但我想知道，我们能否以某种方式利用我们只需要支持单个操作的事实（并且，在构造集合时，我们知道它的所有元素将是什么）？是否有一种数据结构（也许是一种特殊类型的哈希表）在这里表现得特别好？
问问题
154 次
2 回答
5
正如@Alexandre C. 在评论中提到的，这是使用完美哈希表的绝佳场所。完美哈希表是使用哈希函数保证其元素之间没有冲突的哈希表。有多种方案可以实现这一点；最常见和最简单的选项之一是使用FKS 完美哈希表，它使用两层哈希表。它保证了最坏情况的 O(1) 成员资格测试，并且在实践中非常有效。
希望这可以帮助！
于 2013-11-07T20:07:51.937 回答
1
从理论上讲，它不会比哈希表的 O(1) 快，仅仅是因为 O(1) 是最快的（除了完全避免做任何事情，即 O(0) ;)） .
如果您的哈希表非常大（以至于它必须存储在磁盘上，甚至分布在多台机器上），布隆过滤器可以为您提供快速的成员概率测试。
如果过滤器足够小以适合 L1 高速缓存行，那么布隆过滤器甚至可能值得用于内存中的集合，这样您就不必访问主内存，但这可能是一个过早的优化。
于 2013-11-07T19:58:28.073 回答