eindeutige Schlüssel-Wert-Paar Sammlung

Question

Gibt es eine Struktur, die BEIDE diese Operationen ermöglicht: In einer besseren Zeit als O (n)

• collection.TryGetValue(TKey, out TValue)
• collection.TryGetKey(TValue, out TKey)

?

Mein Problem:

Ich muss grundsätzlich in der Lage Schlüsselwert oder Wert des Schlüssels wirklich schnell abzurufen, ohne den Speicher zu duplizieren (so zwei Wörterbücher außer Frage sind).

Sehr wichtiger Hinweis: alle Schlüssel sind einzigartig und alle Werte sind einzigartig. Mit diesen Informationen I fühlen sollte es möglich sein, diese Aufgabe in einer besseren Zeit als nur O (1) für .TryGetValue und O (n) für .TryGetKey zu erreichen.

EDIT:

In meinem Fall habe ich eine Zuordnung zwischen strings und ints. Es gibt ~ 650.000 Schlüssel-Wert-Paare von Texten und ihre IDs. Ich möchte also die Zeichenfolge mit einer bestimmten ID, aber auch die ID einer bestimmten Zeichenfolge erhalten.

Answer 1

können Sie so etwas tun;

Dictionary<string, string> types = new Dictionary<string, string>() 
      { 
         {"1", "one"}, 
         {"2", "two"}, 
         {"3", "three"} 
      }; 

      var myValue = types.FirstOrDefault(x => x.Value == "one").Key; 

Answer 2

Sie können einige Wrapper für key schreiben, sollte für value Schlüssel und Link enthält zu value Wrapper und Wrapper, der sollte Wert und Link zu key Wrapper enthält. Und verwenden Sie zwei verschiedene HashSet s.
In diesem Fall vermeiden Sie Speicherduplizierung. Sie benötigen nur zusätzlichen Speicher für Links.

Answer 3

Um besser als O (n) zu werden, müssen Sie ein 2. Wörterbuch verwenden. Wie Sie bereits erwähnt haben, verwenden Sie Strukturen und sind besorgt über die Speichernutzung mit einem zweiten Wörterbuch mit einer doppelten Kopie der Struktur.

Um dies zu erreichen, geben Sie den Strukturwert in einem Objekt ein und teilen Sie dann das eingerahmte Objekt in den beiden Wörterbüchern. Wenn Sie von DictionaryBase erben, ist das eigentlich ziemlich einfach zu implementieren.

public sealed class TwoWayDictionary<TKey, TValue> : DictionaryBase 
{ 
    Hashtable reverseLookup = new Hashtable(); 

    public void Add(TKey key, TValue value) 
    { 
     this.Dictionary.Add(key, value); 
    } 

    public void Remove(TKey key) 
    { 
     this.Dictionary.Remove(key); 
    } 

    public bool TryGetValue(TKey key, out TValue value) 
    { 
     object lookup = Dictionary[key]; 
     if (lookup == null) 
     { 
      value = default(TValue); 
      return false; 
     } 
     else 
     { 
      value = (TValue)lookup; 
      return true; 
     } 
    } 

    public bool TryGetKey(TValue value, out TKey key) 
    { 
     object lookup = reverseLookup[value]; 
     if (lookup == null) 
     { 
      key = default(TKey); 
      return false; 
     } 
     else 
     { 
      key = (TKey)lookup; 
      return true; 
     } 
    } 

    //If OnInsertComplete or OnSetComplete raises a exception DictionaryBase will 
    // roll back the operation it completed. 
    protected override void OnInsertComplete(object key, object value) 
    { 
     reverseLookup.Add(value, key); 
    } 

    protected override void OnSetComplete(object key, object oldValue, object newValue) 
    { 
     if(reverseLookup.Contains(newValue)) 
      throw new InvalidOperationException("Duplicate value"); 
     if(oldValue != null) 
      reverseLookup.Remove(oldValue); 
     reverseLookup[newValue] = key; 
    } 

    protected override void OnRemoveComplete(object key, object value) 
    { 
     reverseLookup.Remove(value); 
    } 
} 

Die Dictionary und reverseLookup Wörterbücher werden die gleichen Referenzen teilen, so dass es einen kleineren Speicherbedarf als die Verwendung von zwei stark typisierten Wörterbücher mit großen Strukturen haben.

Ohne eine vollständige Dictionary<TKey, TValue> Implementierung zu schreiben, die zwei interne Bucket-Sammlungen für Schlüssel und Werte und zwei verknüpfte Listen für die Ketten aus den Buckets verwendet, glaube ich nicht, dass Sie viel bessere Ergebnisse erhalten können.