辞書のアクセス時間<Dictionary <char,int>、リスト<string>>はまだO（1）ですか？

Question

Dictionary<Dictionary<char,int>, List<string>>のアルゴリズムを実装して、辞書内のアナグラム語を探したかったのです。

この辞書に私のカスタムEqualityComparerを実装する必要があるため、アクセス時間は依然としてO（1）つまり大きなO（1）ですか？

第2の質問は、EqualityComparerの一部として、GetHashCode()も実装する必要があります。 Dictionary<Dictionary<char,int>, List<string>>の効率的な方法は、GetHashCode()ですか？

私はちょうどこの方法を思いついた、より良い選択肢はありますか？

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

ディクショナリをキーとして使用する代わりに、単語「need」を文字列「d1e2n1」に変換するのはどうですか？この文字列を作成するには、バイナリツリーを使用できます。 charはキーとして使用され、文字数はvalueとしてカウントされます。バイナリツリーはキーによって自動的にソートされますが、これは辞書には当てはまりません。

バイナリ表現とXOR演算を組み合わせることで、1つのハッシュ値から結合ハッシュ値を計算できます。 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））操作と同じです。

---

EDIT：言葉のために、この定義を使用して

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

はそれがキーを取得するには、このメソッドを使用しています。ここでは

が可能な実装であります...

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 

---

EDIT＃2：テスト結果は次のようになり

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

コンテナの内容に基づくハッシュコードは、コンテナ内の項目の数がO(n)になります。あなたは別の型で辞書をラップし、ハッシュコードをキャッシュすることができますので、一度だけ計算する必要があります...しかし、私は辞書よりもそのデータを格納するいくつかのより効率的な方法を考えることができます。

Answer 3

Dictionary<TKey, TValue>のアクセス時間は、 O（1）に近づいていますが、それほど正確ではありません。理想的なシナリオ（良い流通/少数の衝突）では、それはO（1）であると考えることができます。 GetHashCode値の分散が小さいために多くの衝突が発生する状況では、アクセス時間が劣化し、O（N）に近づく可能性があります。