6

我们需要将超过 1000 万个字符串读/写到一个文件中。此外，我们不希望文件中有重复项。由于字符串一旦被读取就会被刷新到文件中，我们不会在内存中维护它。

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

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

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

有没有其他可用的方法。谢谢。

4

6 回答 6

7

如果您对碰撞的微观风险没意见，您可以按照您的建议使用一些哈希函数，例如 MD5，并依赖哈希。

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

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

于 2010-06-14T13:19:10.810 回答
6

在内存中存储 1000 万个字符串确实很多，所以我理解为什么要立即将其写入文件而不是TreeSet<String>首先存储，但是您想在哪里存储要比较的 1000 万个唯一数字键？当你想保持它的唯一性和数字（它的基数/基数比字母小得多）时，你不能使键比字符串本身更短，所以你不会节省任何内存。或者可能最高使用 GZIP 等数据压缩，但这只会增加很多开销。MD5 也不合适，因为两个不同的字符串可以产生相同的散列。

我真的认为没有比使用像样的 RDBMS（SQL 数据库）更好的解决方案了，在其中您将列设置为UNIQUE并相应地处理约束违规。RDBMS 针对此类任务进行了高度优化。

如果您真的不能考虑数据库，那么您需要在写入/刷新之前重新读取任何现有条目的文件。也许不是很快，但肯定是内存效率。

于 2010-06-14T13:20:31.983 回答
1

没有办法创建一个可以为字符串生成唯一键的函数，该键比该字符串短。
有一些数据结构可以解决您的任务。如果您的数据足够大，B-tree 可能适合。根据您输入的性质，可能会有更有效的方法。

于 2010-06-14T13:25:10.773 回答
1

可靠地删除重复文件与对文件进行排序一样困难。正如另一个答案所表明的那样，如果不将每个字符串的完整副本保存在内存中，就无法保证精确检测重复项，这似乎正是您要避免的。

您可以保留哈希码的内存或磁盘索引，并使用它们从文件存储中检索实际字符串以进行比较，但这实际上会复制数据库能够为您做的事情。

另一种方法是在文件完成后对其进行后处理。UNIX sort 命令非常擅长处理大文件（UNIX sort 命令如何对非常大的文件进行排序？），所以我希望标准的 UNIX 命令行方法能够合理地工作：

    sort my-file-of-strings.txt | uniq > my-filtered-file-of-strings.txt

（请注意，在传递给 uniq 以删除重复文件之前，必须先对文件进行排序）。

如果您没有这些工具（或等效工具）可用，那么您总是可以尝试自己实现一些外部合并排序的变体。

于 2010-06-14T14:27:41.900 回答
0

如果字符串来自固定的可能字符串池 (N)，那么您可以使用最小完美散列来创建数组 0...N-1。由完美哈希函数确定的槽中的零表示到目前为止尚未看到该字符串。

否则，在大量内存之外唯一有效的正确方法，到目前为止建议的解决方案是在决定将字符串写入文件之前重新读取文件。

您可以通过文件的内存映射部分尽可能有效地执行此操作。

于 2010-06-14T14:15:38.643 回答
0

我真的认为最好的解决方案是 - 正如其他人已经建议的那样 - 使用数据库。

如果由于某种原因您不能使用数据库，您仍然可以使用哈希码。肯定会有碰撞。只需添加一些代码，以便当您检测到重复的哈希码时，您的程序会检查文件以确定它是真正的重复还是冲突。

于 2010-06-15T04:08:42.220 回答