辞書のアクセス時間は何ですか<辞書、list >、それはまだo（1）ですか？

Question

アルゴリズムを実装したかった Dictionary<Dictionary<char,int>, List<string>> 辞書でアナグラムの単語を見つける。

カスタムを実装する必要があるため EqualityComparer この辞書では、アクセス時間はまだo（1）ie big o（1）ですか？

の一部としての2番目の質問 EqualityComparer また、実装する必要があります GetHashCode(). 。決定する効率的な方法は何ですか GetHashCode() 為に Dictionary<Dictionary<char,int>, List<string>>?

私はこの方法を思いついたばかりです、より良い選択肢はありますか？

public int GetHashCode(Dictionary<char, int> obj)
    {
        unchecked
        {
            int hashCode = 17;
            foreach (var item in obj)
            {
                hashCode += 23 * item.Key.GetHashCode();
            }
            return hashCode;
        }
    }

どんなアドバイスでも感謝されています。ありがとう！

Answer 1

辞書をキーとして使用する代わりに、「ニーズ」という単語を文字列「D1E2N1」に変換するのはどうですか？この文字列を構築するために、バイナリツリーを使用できます。 Charはキーとして使用され、文字は値としてカウントされます。バイナリツリーはキーによって自動的にソートされますが、これは辞書の場合ではありません。

バイナリ表現とXOR操作を組み合わせることにより、単一のハッシュ値から結合されたハッシュ値を計算できます。 C＃を使用すると、次のようなことをします。

public override int GetHashCode()
{
    // Combine hashcode of a and b
    return a.GetHashCode() ^ b.GetHashCode();
}

---

未解決のリストでエントリを見つけることは、O（n）操作です。ソートされたリストでエントリを見つけることは、バイナリ検索が使用される場合、O（log（n））操作です。

辞書のリストに単語を見つけることは、O（1 + n）操作であり、これはO（n）操作と同じ、またはO（1 + log（n））操作と同じです。 o（log（n））操作。

---

編集：

可能な実装は次のとおりです。

var anagrams = new Dictionary<string, List<string>>();
foreach (string word in words) {
    string key = GetFrequency(word);
    List<string> list;
    if (anagrams.TryGetValue(key, out list)) {
        list.Add(word);
    } else {
        list = new List<string> { word };
        anagrams.Add(key, list);
    }
}

この方法を使用してキーを取得します。

private string GetFrequency(string word)
{
    var dict = new SortedDictionary<char, int>(); // Implemented as binary tree
    foreach (char c in word.ToLower()) {
        int count;
        if (dict.TryGetValue(c, out count)) {
            dict[c] += 1;
        } else {
            dict[c] = 1;
        }
    }
    return dict.Aggregate(new StringBuilder(), (sb, item) => sb.Append(item.Key).Append(item.Value), sb => sb.ToString());
}

言葉にこの定義を使用して...

var words = new List<string> { "need", "eden", "team", "meat", "meta", "Nat", "tan" };

このテスト...

foreach (var item in anagrams.OrderBy(x => x.Key)) {
    Console.WriteLine();
    Console.WriteLine(item.Key + ":");
    foreach (string word in item.Value.OrderBy(w => w)) {
        Console.WriteLine("    " + word);
    }
}

...この出力を生成します

a1e1m1t1:
    meat
    meta
    team

a1n1t1:
    Nat
    tan

d1e2n1:
    eden
    need

---

編集＃2：

これがBen Voigtが示唆する頻度計算です

private string GetFrequencyByBenVoigt(string word)
{
    char[] chars = word.ToLower().ToCharArray();
    Array.Sort(chars);
    return new string(chars);
}

テスト結果はそうです

aemt:
    meat
    meta
    team

ant:
    Nat
    tan

deen:
    eden
    need

Answer 2

Aのアクセス時間 Dictionary<TKey, TValue> アプローチ o（1）ですが、まさにそうではありません。理想的なシナリオ（適切な分布 /衝突の数）では、それをO（1）であると考えることができます。 GethashCodeの分散が低いために多くの衝突がある状況では、アクセス時間が低下し、O（n）に近づくことができます。

Answer 3

コンテナコンテンツに基づいたハッシュコードは次のとおりです O(n) コンテナ内のアイテムの数。辞書を別のタイプにラップして、ハッシュコードを1回だけ計算する必要があるため、ハッシュコードをキャッシュできます...しかし、辞書よりもそのデータを保存するためのいくつかのより効率的な方法を考えることができます。