我需要实现一个“常量”集。即只支持隶属度测试的数据结构。此外(当然)，我需要一个工厂例程，它在给定元素列表的情况下构造一个常量集。
请注意，不仅常量集不允许突变，而且我不需要返回新常量集的“添加”操作(也就是说，一旦初始化发生，我只对测试感兴趣一个元素是否在集合中)。
Goold old hash tables 在这里是一个明显的选择，但我想知道，我们能否以某种方式利用我们只需要支持单个操作的事实(并且，在构建集合时，我们知道它的所有元素将是什么) )?是否有一种数据结构(也许是一种特殊类型的哈希表)在这里表现得特别好？
最佳答案
正如@Alexandre C. 在评论中提到的，这是使用完美哈希表的绝佳场所。完美哈希表是使用哈希函数保证其元素之间不发生冲突的哈希表。有多种方案可以实现这一点；最常见和最简单的选项之一是使用 FKS perfect hash table ，它使用两层哈希表。它保证了最坏情况下的 O(1) 成员资格测试，并且在实践中非常有效。
希望这对您有所帮助!
关于algorithm - 一个 "constant"Set ADT的高效实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19845297/