Is there an IDictionary implementation for large dictionaries not to end up on large object heap?

Question

This is closely related to .NET Collections and the Large Object Heap (LOH). In a nutshell, if there are more than 85K buckets, it's automatically on LOH and when it's released is unknown. Does anyone aware of a good implementation of IDictionary based on lists of array or something like it that prevents it from going to LOH?

Answer 1

You can use the SortedDictionary, which is a binary tree.

If you need the Dictionary's O(1) performance, or something closer to that, you could use a different hash table implementation that stores the data in chunks small enough not to go on the LOH. I'm not aware of anything publicly available; I have used SortedDictionary in the past and found that the decrease in performance was minimal, so I didn't look any further.

Answer 2

Here's a start of one option. I assume you can follow the pattern given to implement the other methods.

Just change the numDictionaries to determine how it's broken up.

If you really need to you could make the number of dictionaries dynamic and have it add more when the existing ones get sufficiently large.

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;
    }
}