我应该使用哪种集合类型来存储一堆哈希值？

Question

我有一堆长弦,我必须操纵.它们可以一次又一次地出现,如果它们出现两次我想忽略它们.我认为最好的方法是散列字符串并将哈希列表存储在某种有序列表中,并且查找时间很快,以便每当我的数据集向我发送新字符串时我都可以进行比较.

要求:

• 能够将项目(哈希)添加到我的收藏中
• 能够(快速)检查特定散列是否已经在集合中.
• 不太记忆密集.我最终可能会得到大约100,000个哈希值.

如果这有任何区别,我不需要倒退(键 - >值).

有关哪种.NET数据类型最有效的建议？

Answer 1

我认为最好的方法是散列字符串并将哈希列表存储在某种有序列表中,并且查找时间很快,以便每当我的数据集向我发送新字符串时我都可以进行比较.

不,不要那样做.两个原因:

• 哈希只告诉您两个值是否相同; 他们不会告诉你他们是否一样.
• 你已经做了很多已经完成的工作.

基本上,你应该保持一个HashSet<String>.这应该没问题,快速查找,你不需要自己实现它.

缺点是你最终会将所有字符串保留在内存中.如果这是一个问题,那么你需要制定一个替代策略......这可能最终只能保留内存中的哈希值.确切的细节可能取决于字符串的来源,以及如果你出现误报会导致什么样的问题.例如,您可以将每个字符串的MD5哈希值保留为"优于仅仅hashCode"哈希值 - 但这仍然允许攻击者向您提供具有相同哈希值的另一个字符串.那是问题吗？如果是这样,更安全的哈希算法(例如SHA-256)可能会有所帮助.尽管如此,它仍然不能保证你最终会得到不同字符串的不同哈希值.

如果你真的想确定,你需要将哈希保留在内存中但是保留实际的字符串数据(到磁盘或数据库) - 然后当你有可能的匹配时(因为你看到了相同的哈希)之前)您需要将存储的字符串与新字符串进行比较.

如果要将哈希存储在内存中,最佳方法将取决于您正在使用的哈希值.例如,对于只有64位散列,您可以使用Long每个散列并将其保存在HashSet<Long>.对于更长的哈希,您需要一个可以轻松比较的对象等.此时,我建议您查看Guava及其HashCode类,以及工厂方法HashCodes(自Guava v16后弃用).