如何通过不断增长的TDictionary避免内存不足？

Question

TDictionary<TKey,TValue> 使用内部数组,如果它已满,则加倍:

newCap := Length(FItems) * 2;
if newCap = 0 then
  newCap := 4;
Rehash(newCap);

这适用于中等数量的项目,但如果达到上限,则非常不幸,因为EOutOfMemory即使几乎有一半的内存仍然可用,它也可能抛出异常.

有没有办法影响这种行为？其他集合类如何处理这种情况？

Answer 1

您需要了解字典的工作原理.字典包含"哈希桶"列表,其中放置了您插入的项目.这是一个有限的数字,所以一旦你填满它你需要分配更多的桶,没有办法解决它.由于对象到桶的分配基于散列函数的结果,因此您不能简单地将桶添加到数组的末尾并将内容放入其中,您需要重新分配整个块列表,重新哈希所有内容并将其放入(新)相应的存储桶中.

鉴于此行为,使字典在完整时不重新分配的唯一方法是确保它永远不会满.如果你知道你将在字典中插入的项目数量作为参数传递给构造函数,你将完成,不再需要字典重新分配.

如果你不能这样做(你不知道你在字典中会有多少项),你需要重新考虑一下你选择的TDictionary是什么,并选择一个提供更好折衷的数据结构.你的特定算法.例如,你可以使用二叉搜索树,因为他们通过旋转在现有节点的信息做了平衡,没有必要重新分配过.