comment faire une recherche inversée de dictionnaire

J'ai un dictionnaire de type <string, string> et pour un cas particulier, j'ai besoin de faire une recherche inversée. Ainsi, par exemple, supposons que j'ai cette entrée <"SomeString", "ab"> et que je passe dans "ab" ensuite, je voudrais revenir "SomeString".
Avant de m'embarquer sur un foreach boucle sur chaque entrée dans le dictionnaire, je me demandais quel serait le moyen le plus efficace pour ce faire de recherche inversée?

source d'informationauteur frenchie

  1. 21

    Fondamentalement, Vous pouvez utiliser LINQ et obtenir le Key comme ça, sans inverser quoi que ce soit: 

    var key = dictionary.FirstOrDefault(x => x.Value == "ab").Key;

    Si vraiment vous voulez inverser votre Dictionnaire, vous pouvez utiliser une méthode d'extension comme ceci:

    public static Dictionary<TValue, TKey> Reverse<TKey, TValue>(this IDictionary<TKey, TValue> source)
{
     var dictionary = new Dictionary<TValue, TKey>();
     foreach (var entry in source)
     {
         if(!dictionary.ContainsKey(entry.Value))
             dictionary.Add(entry.Value, entry.Key);
     }
     return dictionary;
}

    Alors vous pouvez l'utiliser comme ceci:

    var reversedDictionary = dictionary.Reverse();
var key = reversedDictionary["ab"];

    Remarque: si vous avez des valeurs, cette méthode permettra d'ajouter de la première Value et ignore les autres.

  2. 14

    Utiliser Linq ToDictionary fonction:

    var reversed = d.ToDictionary(x => x.Value, x => x.Key);

    Vous pouvez voir ci-dessous que cela fonctionne, testé dans Linqpad:

    var d = new Dictionary<int, string>();
d.Add(1,"one");
d.Add(2,"two");
d.Dump(); //prints it out in linq-pad
var reversed = d.ToDictionary(x => x.Value, x => x.Key);
reversed.Dump(); //prints it out in linq-pad

    comment faire une recherche inversée de dictionnaire

  3. 3

    Comment sur l'utilisation de linq fonction ToDictionary:

    var reversedDictionary = dictionary.ToDictionary(x => x.Value, x => x.Key);
  4. 1

    1) les Clés sont uniques, les valeurs ne sont pas. Pour une valeur donnée de vous ont un ensemble de touches.

    2) Recherche par clé est O(log n). Itération avec foreach ou LINQ est O(n).

    Donc

    Option A: Itérer avec LINQ, passer O(n) par demande, pas de mémoire supplémentaire.

    Option B: Maintenir Dictionary<ValueType, HashSet<KeyType>>, passer O(log n) par la demande, utilisation O(n) de la mémoire supplémentaire. (Il y a deux sous-options: construire ce dictionnaire avant une série de look-ups; maintenir tout le temps)