c# - 是否有用于大型字典的 IDictionary 实现不会最终出现在大型对象堆上？

Question

这与.NET 集合和大对象堆 (LOH)密切相关。简而言之，如果有超过 85K 的存储桶，它会自动在 LOH 上，并且何时释放是未知的。有没有人知道基于数组列表或类似的东西的 IDictionary 的良好实现可以防止它进入 LOH？

Answer 1

您可以使用SortedDictionary，它是二叉树。

如果您需要 Dictionary 的 O(1) 性能，或者更接近的性能，您可以使用不同的哈希表实现，将数据存储在足够小的块中，不会继续 LOH。我不知道任何公开的信息；以前用过SortedDictionary，发现性能下降很小，所以没有再看。

Answer 2

这是一个选项的开始。我假设您可以按照给出的模式来实现其他方法。

只需更改numDictionaries以确定它是如何分解的。

如果您真的需要，您可以使字典的数量动态化，并在现有字典足够大时添加更多。

public class NonContigousDictionary<TKey, TValue>
//TODO make this implement IEnumerable, IDictionary, 
//and any other relevant interfaces.
{
    public Dictionary<TKey, TValue>[] dictionaries;

    private readonly int numDictionaries = 5;
    public NonContigousDictionary()
    {
        dictionaries = Enumerable.Range(0, numDictionaries)
            .Select(_ => new Dictionary<TKey, TValue>())
            .ToArray();
    }

    public TValue this[TKey key]
    {
        get
        {
            int hash = key.GetHashCode();
            return dictionaries[GetBucket(hash)][key];
        }
        set
        {
            int hash = key.GetHashCode();
            dictionaries[GetBucket(hash][key] = value;
        }
    }

    public bool Remove(TKey key)
    {
        int hash = key.GetHashCode();
        return dictionaries[GetBucket(hash].Remove(key);
    }

    public void Clear()
    {
        foreach (var dic in dictionaries)
        {
            dic.Clear();
        }
    }

    private int GetBucket(int hash)
    {
        return (hash % numDictionaries + numDictionaries) % numDictionaries;
    }
}