c# - 大对象堆友好的 IDictionary

Question

我们有一个应用程序在多个 Dictionary 中保存大量对象，其中一些对象在应用程序的生命周期中不断增长(交易应用程序有很多工具和不断增长的订单/交易) .

由于大型对象堆的碎片，我们遇到了 OutOfMemoryException 问题。

为了解决这个问题，我尝试编写一个“大”字典，它实现为一个二级字典，其中所有叶字典都不够大，无法在 LOH 上分配。我使用了一致的哈希算法来避免在单个桶变得太大时不得不重新哈希整个字典。一致性哈希“圆”是来自 C5 集合库的 TreeDictionary。

我的问题是，是否有更好的 C# 数据结构(或者可能是我描述的更好的实现)？

更新

这是“大”字典的实现:https://gist.github.com/956621

我知道这不是万无一失的，因为规范中既没有 LOH 堆阈值，也没有每个字典条目或缩放算法的大小。但是，这是目前我能想到的避免应用程序在中午崩溃的最佳方法。

Answer 1

当字典是应用程序中最大的数据结构时，它是一种不幸的数据结构。当哈希表变得太满时，哈希表的大小通常会加倍，这就在关键时刻需要在调整大小时进行 150% 的过度分配。当哈希表很大时，哈希表工作得非常好，但它需要连续分配，这会给堆算法带来压力。

您可以使用多级哈希表来减少这些缺点，例如使用哈希码的一个字节作为 256 个哈希表的索引。这肯定会增加一些开销，但更重要的是，这种策略和其他策略充满了危险，因为它们会摆弄随机性，例如您获得的哈希码的随机性，并可能使事情在性能方面变得非常非常糟糕。使用这种方法需要良好的理论基础和扎实的实证检验。但它可以工作。

另一种策略是为最坏的情况预分配最大的数据结构并尽早分配。不需要细粒度的分配，但现在如果它用完了，你将面临灾难性的失败。这是一个选项。