java - 在java中为字符串构造一个唯一的数字

Question

我们有一个需求，要在一个文件中读取/写入超过 1000 万个字符串。我们也不希望文件中有重复项。由于字符串在读取后会立即刷新到文件中，因此我们不会在内存中维护它。

我们不能使用哈希码，因为哈希码中存在冲突，我们可能会错过重复的字符串。我在谷歌搜索中发现的另外两种方法:

1.使用像 MD5 这样的消息摘要算法 - 但计算和存储的成本可能太高。

2.使用校验和算法。 [我不确定这是否会为字符串生成唯一键 - 有人可以确认]

还有其他方法吗？谢谢。

Answer 1

如果您可以接受微小的碰撞风险，您可以按照您的建议使用一些散列函数，例如 MD5，并依赖于散列。

另一种可能占用更大内存的替代方法是将已经遇到的字符串存储在 trie 中。 (一种特殊类型的树)。

---

更新:另一种选择是使用 Bloom filter .然而，这仍然依赖于散列，但可以调整为具有任意小的冲突概率。