.net - 从 LONG 哈希列表中查找哈希

Question

我有一个长文本文件，其中包含大约 1 亿个 MD5 哈希值。我想对一小组文件进行哈希处理，并找出其中任何一个文件的哈希值是否在 1 亿个哈希列表中。我的 1 亿个哈希是按字母顺序排序的。无需将整个列表加载到内存或数据库中，从这个大文本文件中查找哈希值的最有效方法是什么？哈希列表会不时更新，但会保持按字母顺序排序。对找到的命中位置不感兴趣。重要的是是否有命中。

Answer 1

这种作业的关键参数是单个磁盘查找的成本。磁盘查找具有固有的延迟，因为读/写磁头必须移动到正确的位置。在一个典型的磁盘上，每秒可以进行大约一百次查找。另一方面，磁盘非常擅长顺序读取，因此对于每次查找，您可以读取值(value) 1 兆字节的数据，而几乎没有额外的成本。

我在这里假设“文本文件”具有常规范式。例如，每个散列值正好使用 33 个字节，其中 32 个用于 MD5 结果本身(以十六进制表示)和 1 个额外字节用于“换行”字符。如果需要，根据确切的格式进行调整。使用这些数字，您的文本文件的长度约为 3.3 GB。

由于 MD5 的行为主要类似于随机函数，因此 1 亿个哈希值应均匀分布在 128 位值的空间中。这意味着，给定一个哈希值，您可以计算该值在文件中的大致位置(如果它在文件中)。例如，哈希值 9378ec093d09863d008154f1c8f5ca8f应该在接近 0.5761*n*33 的偏移量处，其中 n 是大文件中的哈希数，“33”在上面的段落中进行了解释。 0.5761 是 0x9378EC 除以 0x1000000 的结果。因此，您可以读取以该计算位置为中心的一兆字节的文本文件。这将包含大约 30000 个哈希值。 1 亿个随机值的标准偏差约为 10000，因此 30000 个散列将包含正确值的可能性很高，以决定您的散列是否在列表中。如果估计值不正确，您将不得不再读取 1 兆字节，但这不会经常发生。可能，您可以读取多于 1 兆字节以减少这种情况的发生:有一个权衡，需要通过实际措施进行调整。

一旦您在 RAM 中有一个(小)哈希值块，请使用二进制搜索。但无论如何，最初的查找成本将使那部分完全相形见绌。

另一种解决方案使用额外的索引文件。构建一个二级文件，其中包含大文件中每 10000 个哈希值。该文件的长度约为 330 kB。尽可能将此文件保存在 RAM 中。使用它(通过二分搜索)来了解哪个 10000 个哈希序列与您的查找相关。然后从大文件中读取该块。每当哈希列表发生变化时，必须重建索引文件；这有点昂贵，但比实际的大文件更改要少。根据生成大文件的系统，您也许可以以可忽略不计的额外成本集成索引文件生成。