c# - 将大文件读入字典

Question

我有一个 1GB 的文件，其中包含成对的字符串和长整数。 将其读入字典的最佳方式是什么？您认为这需要多少内存？

文件有 6200 万行。 我已经设法使用 5.5GB 的内存读取了它。

假设每个字典条目有 22 字节的开销，即 1.5GB。 long 是 8 个字节，也就是 500MB。 平均字符串长度为 15 个字符，每个字符 2 个字节，即 2GB。 总共大约 4GB，额外的 1.5GB 去哪里了？

初始字典分配占用 256MB。 我注意到我每读取 1000 万行，消耗大约 580MB，这与上面的计算非常吻合，但是在第 6000 行左右的某个地方，内存使用量从 260MB 增加到 1.7GB，这是我缺少的 1.5GB，它在哪里去吗？

谢谢。

Answer 1

了解填充哈希表时发生的情况很重要。 (字典使用哈希表作为其底层数据结构。)

当您创建一个新的哈希表时，.NET 会生成一个包含 11 个桶的数组，这些桶是字典条目的链接列表。当您添加一个条目时，它的键被散列，散列码被映射到 11 个桶之一，条目(键 + 值 + 散列码)被附加到链表。

在某一时刻(这取决于首次构造哈希表时使用的加载因子)，哈希表在添加操作期间确定它遇到了太多的冲突，并且最初的 11 个桶不够用.因此它创建了一个新的存储桶数组，其大小是旧存储桶的两倍(不完全是；存储桶的数量始终是质数)，然后从旧表填充新表。

因此，有两件事在内存利用率方面发挥作用。

首先，Hashtable 每隔一段时间就需要使用两倍于当前使用量的内存，以便它可以在调整大小时复制表。因此，如果您有一个使用 1.8GB 内存的哈希表并且需要调整大小，那么它会暂时需要使用 3.6GB，那么，现在您遇到了问题。

第二个是每个哈希表条目都有大约 12 个字节的开销:指向键、值和列表中下一个条目的指针，加上哈希码。对于大多数用途，该开销微不足道，但如果您要构建一个包含 1 亿个条目的哈希表，那么，这大约是 1.2GB 的开销。

您可以通过使用允许您提供初始容量的 Dictionary 构造函数的重载来克服第一个问题。如果您指定一个足够大的容量来容纳您要添加的所有条目，则在填充它时不需要重建哈希表。对于第二个，您几乎无能为力。