检测随机有序输入的变化（哈希函数？）

StackOverflow https://stackoverflow.com/questions/64209

  •  09-06-2019
  •  | 
  •  

题

我正在阅读可以按任何顺序出现的文本行。问题是输出实际上可能与之前的输出相同。如果不先对输出进行排序，如何检测到这一点？

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

有帮助吗？

解决方案

最简单的方法似乎是对传入的每一行进行散列，存储散列和原始数据，然后将每个新散列与现有散列的集合进行比较。如果您得到肯定的结果，您可以比较实际数据，以确保它不是误报 - 尽管这种情况极为罕见，您可以使用更快的哈希算法，例如 MD5 或 CRC（而不是 SHA 之类的算法，速度较慢，但​​碰撞的可能性较小），只是为了速度快，然后在命中时比较实际数据。

其他提示

所以你有这样的输入

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

你需要检测第一行和第三行是否相同？

如果您想查明两个文件是否包含相同的行集，但顺序不同，您可以分别对每行使用常规哈希函数，然后将它们与顺序无关的函数（例如加法）组合起来。

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

如果您不需要 100% 万无一失的解决方案，您可以将每行的哈希存储在布隆过滤器中（在维基百科上查找）并在处理结束时比较布隆过滤器。这可能会给您带来误报（即你认为你有相同的输出，但实际上并不相同），但你可以通过调整布隆过滤器的大小来调整错误率......

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

（这可能有点过于简单，但也许它会激发您的想法。请参阅编程珍珠，第 2.8 节，了解有趣的背景故事。）

任何基于哈希的方法都可能产生不良结果，因为多个字符串可以生成相同的哈希。（这不太可能，但有可能。）对于添加哈希值的建议尤其如此，因为您本质上是在采取 特别糟糕 哈希值的哈希值。

仅当您错过更改或发现不存在更改的更改并不重要时，才应尝试哈希方法。

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

  • 如果您遇到计数为零的线（或根本没有地图条目），则说明您看到了意想不到的线。
  • 如果您以地图中剩余的非零条目结束此操作，则您没有看到预期的内容。

嗯，问题的具体说明有点有限。

据我了解，您希望查看多个字符串是否包含相同的元素，无论顺序如何。

例如：

A B C
C B A

是相同的。

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

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

然后只需通过运行其中一个集合并将其与其他集合进行比较来比较集合的内容。执行时间将是 O(N) 代替 O(NlogN) 对于排序示例。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top