比较大的哈希列表

本文关键字：列表 哈希 比较 | 更新日期: 2023-09-27 18:04:23

我有两个列表。一个是我拥有的计算机(ListA)中文件的MD5和SHA1哈希列表。另一个是我从NSRL (ListB)下载的MD5和SHA1哈希列表。它是MD5和SHA1哈希值的汇编，这些哈希值来自许多不同应用程序中的文件。

我正试图找到一个快速的方法来比较这些列表。

仅供性能参考，系统的哈希值为7.2gb的文本文件，NSRL哈希列表约为20gb。我的系统有32gb的内存来执行处理，所以它应该有足够的内存来加载这两个文件到内存中，如果需要的话。

我已经研究了Except，也考虑过从ListA中读取每一行并将其与ListB进行比较，但是必须有比这更好的方法。什么好主意吗?

同样，这是来自机器的哈希值与来自哈希数据库的已知哈希值的比较。这在取证中是很常见的做法(据我所知)，所以我对已经存在的应用程序的建议持开放态度。

比较大的哈希列表

使用散列将是最快的，但是您没有足够的内存将所有这些项加载到散列中。假设SHA-1和MD5条目的数量相等，那么ListA中大约有5亿个条目，ListB中大约有10亿个条目。假设每个指针有8个字节，那么至少有80亿个字节。

相反，您应该首先使用一个Radix Trie来存储ListB，然后在读取ListA时执行比较。它的性能不如哈希，但它是一个很好的时空权衡。

使用HashSets。首先将两个列表中的所有项目加载到HashSet s中。然后是IntersectWith，它需要O(n)。

非常确定，在您的情况下，瓶颈将是从文件读取数据到内存。在性能方面，我建议将文本文件读入内存，然后解析它。

  1. 创建一个类，可以保存单个哈希项的数据
  2. 确保正确实现GetHashCode和Equals。
  3. 创建2个您创建的类型的HashSet s，一个用于ListA，一个用于ListB。
  4. 将列表中的所有项加载到哈希集。
  5. 使用SymmetricExceptWith(需要O(n))来获得不在两个列表中的所有哈希值。
var setA = new HashSet<Item>(LoadListA());
var setB = new HashSet<Item>(LoadListb());
setA.SymmetricExceptWith(setB);
if (setA.Count > 0)
{
    Console.WriteLine("Extra items ןn A or B");
}
相关文章：