1

我有一堆长字符串，我必须操纵它们。它们可以一次又一次地出现，如果它们出现两次，我想忽略它们。我认为最好的方法是对字符串进行哈希处理并将哈希列表存储在某种有序列表中，并具有快速查找时间，这样每当我的数据集给我一个新字符串时，我就可以进行比较。

要求：

  • 能够将项目（哈希）添加到我的收藏中
  • 能够（快速）检查特定的哈希是否已经在集合中。
  • 不太占用内存。我最终可能会得到大约 100,000 个这些哈希值。

如果这有什么不同，我不需要倒退（键->值）。

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

4

2 回答 2

8

我认为最好的方法是对字符串进行哈希处理并将哈希列表存储在某种有序列表中，并具有快速查找时间，这样每当我的数据集给我一个新字符串时，我就可以进行比较。

不，不要那样做。两个原因：

  • 哈希仅告诉您两个值是否相同；他们不会告诉你它们是否相同。
  • 你会做很多已经为你完成的工作。

基本上，你应该只保留一个HashSet<String>. 那应该没问题，快速查找，您不需要自己实现它。

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

如果你真的想确定，你需要将哈希值保存在内存中，但将实际的字符串数据保存到磁盘或数据库中——然后当你得到一个可能的匹配项时（因为你已经看到了相同的哈希值之前）您需要将存储的字符串与新的字符串进行比较。

如果您将哈希值存储在内存中，最好的方法将取决于您使用的哈希值的大小。例如，对于 64 位散列，您可以使用Long每个散列并将其保存在HashSet<Long>. 对于更长的哈希，您需要一个可以轻松比较的对象等。此时，我建议您查看Guava及其HashCode类，以及HashCodes（自 Guava v16 以来不推荐使用）中的工厂方法。

于 2013-05-29T11:35:17.073 回答
2

使用一套。

ISet<T>接口由例如实现HashSet<T>

Add并且Contains预计为 O(1)，除非您的哈希函数非常差，否则最坏的情况是 O(n)。

于 2013-05-29T11:34:35.180 回答