java - 可变长度数据要考虑哪些哈希算法

Question

为了避免混淆，我根据我对哈希算法的研究重新设计了我的问题

问题陈述我有多个包含可变长度数据记录的文本文件。我需要查找输入中是否有重复记录。每个文本文件都可能有数百万的数据记录。

由于我无法一次将所有数据加载到内存中，因此我计划在处理记录时创建记录中关键字段的散列。处理记录意味着验证、过滤和转换它。处理所有文本文件中的所有记录后，将它们合并以创建整个输入(文本文件或数据库表)的一个 View 。

如果为所有记录生成哈希值，查找重复项会更快。如果存在哈希值冲突，则只能检查那些记录是否相等(假设哈希算法是确定性的)

问题 - 对于这种输入，即可变长度数据，我应该考虑什么哈希算法？

Answer 1

简答题

不要这样做。使用 Java map 。您可以在此处找到详细信息: http://docs.oracle.com/javase/6/docs/api/java/util/Map.html

长答案

您可以通过将字符串视为以 N 为基数的数字来创建完美的哈希函数，其中 N 是任何字符可以采用的所有可能值。这里的问题是内存。散列函数旨在与数组一起使用，这意味着您需要一个足够大的数组来处理散列的结果，而这是不切实际的。

例如，以 10 个字符的 key 为例。让我们更谦虚一点，假设它们保证只由小写字母组成。这为每个字符提供了 26 种可能性，以及 10 个字符。这意味着可能的组合是:

26 ^ 10 = 141,167,095,653,376

如果您查找哈希算法，它们首先包含的内容之一就是碰撞检测，因为它们承认碰撞是生活中不可避免的事实。

现在你说你没有在内存中加载 key ，但你为什么要使用散列呢？散列的要点是为您提供到数组索引的映射。也许您最好使用另一种机制。

可能的解决方案

如果您担心内存问题，请获取有关文件中重复项的一些统计信息。如果你只存储一个标志来指示散列中特定键的出现，并且你有很多重复项，你可以只使用 Java 的映射。 Java 的映射会处理冲突，因此不会阻止您检测唯一键。您可以放心，如果找到 A[x]，则意味着 x 在 A 中，即使 x 的散列与之前的散列冲突。

接下来，您可以尝试一些实用程序来提取重复项。由于它们是专门为此目的编写的，因此它们应该能够处理大量数据。

最后，您可以尝试将条目放入数据库并使用它来处理重复项。这似乎有点矫枉过正，但数据库已针对处理大量记录进行了优化。