unikalna kolekcja klucz-wartość-pair

Question

Czy istnieje struktura, która pozwala ZARÓWNO tych operacji:

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

W lepszym czasie niż O (n)?

Mój problem:

I w zasadzie muszą być w stanie odzyskać wartość kluczyka lub wartość na klucz bardzo szybko, bez powielania pamięci (tak dwa słowniki są wykluczone).

Bardzo ważna uwaga: wszystkie klucze są niepowtarzalne, a wszystkie wartości są niepowtarzalne. Mając tę ​​informację I czuć powinno być możliwe do wykonania tego zadania w lepszym czasie niż tylko O ​​(1) dla .TryGetValue i O (n) dla .TryGetKey.

EDIT:

W moim przypadku, mam mapowanie pomiędzy strings i ints. Istnieje ~ 650 000 par klucz-wartość tekstów i ich identyfikatorów. Więc zasadniczo chcę uzyskać ciąg z określonym ID, ale także identyfikator pewnego ciągu.

Answer 1

możesz zrobić coś takiego;

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

można napisać otoki dla key który powinien zawiera klucz oraz link value owinięcie i owijkę dla value który powinien zawiera wartość i link do key owijki. I użyj dwóch różnych HashSet s.
W tym przypadku unikniesz duplikowania pamięci. Potrzebujesz tylko dodatkowej pamięci dla linków.

Answer 3

Aby uzyskać lepsze wyniki niż O (n), należy użyć drugiego słownika. Jednak, jak wspomniałeś, używasz struktur i martwisz się wykorzystaniem pamięci przez drugi słownik mający duplikat struktury.

Jednym sposobem obejścia tego pola jest umieszczenie wartości struct wewnątrz obiektu, a następnie udostępnienie obiektu w pudełku w dwóch słownikach. Jeśli używasz dziedziczenia z DictionaryBase, jest to całkiem łatwe do wdrożenia.

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

W Dictionary i reverseLookup słowniki będą dzielić te same referencje, więc będzie mieć mniejsze zużycie pamięci niż przy użyciu dwóch silnie wpisane słowniki z dużych strukturach.

Bez pisania pełnej implementacji Dictionary<TKey, TValue>, która wykorzystuje dwa wewnętrzne zbiory kubełków dla kluczy i wartości oraz dwie połączone listy dla łańcuchów poza segmentami Nie sądzę, że można uzyskać znacznie lepsze wyniki.