c# - 用于识别重复值的数据结构

Question

我正在运行相当大的搜索，并收到 System.OutOfMemoryException。

问题是我正在为我之前访问过的每个状态存储一个字符串键作为 HashSet<sting> .一旦达到大约 700 万个元素，它就会崩溃。我的想法是我不需要能够检索字符串，只需要识别它是否存在于集合中。

我似乎记得这种东西有专门的数据结构，但我一辈子都记不起它的名字了。如果我没记错的话，它有相当稳定的内存需求，你向它添加元素，它可以在一定程度上确定你是否已经向它添加了一些值。这是我编的，还是真的存在。有什么建议吗？

Answer 1

您可能正在考虑 Bloom filter .当您检查字符串是否在集合中时，它会为您提供概率结果。如果是的话，你总能找到它。如果不是，您仍然可以检测到它是，这取决于您集合中的其他内容。它的内存需求确实会根据您添加的唯一元素的数量而变化，但它远低于 HashSet 将占用的空间。