4

これは、 .NET コレクションとラージ オブジェクト ヒープ (LOH)に密接に関連しています。簡単に言えば、85K を超えるバケットがある場合、自動的に LOH になり、いつ解放されるかは不明です。配列のリストに基づいた IDictionary の適切な実装など、LOH への移行を妨げるものを知っている人はいますか?

4

2 に答える 2

4

SortedDictionary二分木である を使用できます。

ディクショナリの O(1) パフォーマンス、またはそれに近いものが必要な場合は、LOH に移行しないように十分小さいチャンクでデータを格納する別のハッシュ テーブル実装を使用できます。公開されているものは何も知りません。過去に SortedDictionary を使用したことがありますが、パフォーマンスの低下は最小限であることがわかったため、それ以上は調べませんでした。

于 2012-10-12T17:47:32.633 に答える
3

ここから、1 つのオプションの開始です。他の方法を実装するために与えられたパターンに従うことができると思います。

を変更するだけで、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;
    }
}
于 2012-10-12T17:54:23.110 に答える