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 的哈希值与之前的哈希值发生冲突。

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

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