사전에 대한 액세스 시간 <사전 <char,int>, 목록 <string>>은 아직 O (1)입니까?

Question

사전에 anagram 단어를 찾으려면 Dictionary<Dictionary<char,int>, List<string>>의 알고리즘을 구현하고 싶습니다.

이 사전에 내 맞춤형 EqualityComparer을 구현해야하므로 액세스 시간은 여전히 ​​O (1) 즉 O (1)입니까?

두 번째 질문은 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

Dictionary를 키로 사용하는 대신 "need"를 "d1e2n1"이라는 문자열로 변환하는 것은 어떻습니까? 이 문자열을 만들려면 이진 트리를 사용할 수 있습니다. 문자는 키로 사용되고 문자는 값으로 사용됩니다. 바이너리 트리는 자동으로 키에 의해 정렬됩니다. 이는 사전에 해당하지 않습니다.

이진 표현과 XOR 연산을 결합하여 단일 해시 값에서 조합 해시 값을 계산할 수 있습니다. C#을, 당신은 같은 것을 할 것입니다 : 정렬되지 않은 목록의 항목을 찾기

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

는

---

오 (N) 작업입니다. 이진 검색이 사용되는 경우 정렬 된 목록에서 항목을 찾는 것은 O (log (n)) 연산입니다.

사전의 목록에서 단어를 찾는 것은 O (1 + 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)에 접근 할 수 있습니다.