我正在阅读可以任意顺序排列的文本行。问题在于输出实际上可以与先前的输出相同。我如何才能检测到这种情况，而无需先对输出进行排序？

是否存在某种哈希函数可以接受相同的输入，但是以任何顺序输入，并且仍会产生相同的结果？

解决方案

回答

所以你输入像

A B C D
D E F G
C B A D

并且我们需要检测第一行和第三行是否相同？

回答

如果要确定两个文件是否包含相同的行集，但顺序不同，可以在每行上单独使用常规哈希函数，然后将它们与顺序无关紧要的函数(例如加法)组合在一起。

回答

如果行相当长，则可以保留每行的哈希列表-对其进行排序并与以前的输出进行比较。

如果不需要100％防呆解决方案，则可以将每行的哈希存储在Bloom过滤器中(在Wikipedia上查找)，并在处理结束时比较Bloom过滤器。这可能会给我们带来误报(即我们认为我们具有相同的输出，但实际上并不相同)，但是我们可以通过调整Bloom过滤器的大小来调整错误率...

回答

如果将每个字符的ASCII值相加，则无论顺序如何，都会得到相同的结果。

(这可能有点简化，但也许会激发我们一个主意。
有关有趣的背景故事，请参见《编程珍珠》第2.8节。)

回答

最简单的方法似乎是散列途中的每一行，存储散列和原始数据，然后将每个新散列与现有散列的集合进行比较。如果得到肯定的结果，则可以比较实际数据，以确保它不是假阳性，尽管这种情况极为罕见，我们可以使用更快的哈希算法，例如MD5或者CRC(而不是SHA等，速度较慢，但​​发生碰撞的可能性较小)，只是速度很快，然后在我们遇到问题时比较实际数据。

回答

任何基于散列的方法都可能产生不好的结果，因为一个以上的字符串可以产生相同的散列。 (这不太可能，但是有可能。)添加散列的建议尤其如此，因为从本质上讲，我们将对散列值进行特别糟糕的散列。

仅当对遗漏更改或者发现不存在更改的情况并不重要时，才应尝试使用哈希方法。

最准确的方法是使用线串作为键保留Map，并将每个计数存储为值。 (如果每个字符串只能出现一次，则不需要计数。)为预期的行集计算此值。复制此集合以检查传入的行，从而减少看到的每行的计数。

• 如果遇到计数为零的行(或者根本没有映射条目)，那么我们会看到未曾想到的行。
• 如果我们以在地图中剩余的非零条目结束此操作，那么我们将看不到预期的内容。

回答

好了，问题说明有点受限制。

据我了解，我们希望查看几个字符串是否包含相同的元素，而不管顺序如何。

例如：

A B C
C B A

是相同的。

这样做的方法是创建一组值，然后比较这些组。要创建集合，请执行以下操作：

HashSet set = new HashSet();
foreach (item : string) {
   set.add(item);
}

然后，只需遍历其中一个集合并与其他集合进行比较，就可以比较集合的内容。对于排序示例，执行时间将是O(N)而不是O(NlogN)。