Quel est AccessTime pour Dictionary , List >, est-ce toujours O (1)?

Question

Je voulais implémenter un algorithme avec Dictionary<Dictionary<char,int>, List<string>> pour trouver les mots anagrammes dans un dictionnaire.

Comme j'ai besoin d'implémenter mon EqualityComparer personnalisé pour ce dictionnaire, le temps d'accès est-il toujours O (1), c'est-à-dire gros O (1)?

Deuxième question, dans le cadre du EqualityComparer, je dois également implémenter le GetHashCode().Quelle est la manière efficace de déterminer GetHashCode() pour Dictionary<Dictionary<char,int>, List<string>>?

Je viens de proposer cette méthode, y a-t-il une meilleure alternative?

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

Tout conseil est apprécié.Merci!

Answer 1

Que diriez-vous de convertir le mot "besoin" en chaîne "d1e2n1" au lieu d'utiliser un dictionnaire comme clé? Afin de construire cette chaîne, vous pouvez utiliser un arbre binaire. Un caractère serait utilisé comme clé et le nombre de caractères comme valeur. L'arbre binaire est automatiquement trié par clé, ce qui n'est pas le cas pour un dictionnaire.

Vous pouvez calculer une valeur de hachage combinée à partir de valeurs de hachage uniques en combinant leur représentation binaire avec l'opération XOR. Avec C #, vous feriez quelque chose comme ceci:

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

---

La recherche d'une entrée dans une liste non triée est une opération O (n). Trouver une entrée dans une liste triée est une opération O (log (n)), si une recherche binaire est utilisée.

Trouver un mot dans une liste dans un dictionnaire est une opération O (1 + n), qui est identique à une opération O (n), ou une opération O (1 + log (n)), qui est la identique à une opération O (log (n)).

---

< EDIT:

Voici une implémentation possible:

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

Il utilise cette méthode pour obtenir la clé:

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

Utilisation de cette définition pour les mots ...

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

Ce test ...

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

... produit cette sortie

a1e1m1t1:
    meat
    meta
    team

a1n1t1:
    Nat
    tan

d1e2n1:
    eden
    need

---

MODIFIER # 2:

Voici le calcul de fréquence tel que suggéré par Ben Voigt

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

Le résultat du test serait

aemt:
    meat
    meta
    team

ant:
    Nat
    tan

deen:
    eden
    need

Answer 2

Le temps d'accès d'un Dictionary<TKey, TValue> approche O (1) mais ne l'est pas exactement.Dans les scénarios idéaux (bonne distribution / peu de collisions), vous pouvez le considérer comme étant O (1).Dans les situations où il y a beaucoup de collisions en raison d'une faible variance dans les valeurs GetHashCode, le temps d'accès se dégrade et peut approcher O (N).

Answer 3

Un code de hachage basé sur le contenu du conteneur sera O(n) dans le nombre d'éléments dans le conteneur.Vous pouvez envelopper le dictionnaire dans un autre type et mettre en cache le code de hachage afin qu'il ne soit calculé qu'une seule fois ... mais je peux penser à plusieurs moyens plus efficaces de stocker ces données qu'un dictionnaire.