Sposób implementacji słownika .NET działa z obiektami zmiennymi

Question

Rozumiem, że nie zaleca się używania obiektów "zmiennych" (obiektów, których metoda GetHashCode() może zwracać różne wyniki, gdy są one używane jako klucze w Dictionary).

Poniżej jest moje zrozumienie, jak słownik, który jest realizowany w tabeli mieszania, działa:

Kiedy dodaję nowy klucz, na przykład dict.Add(m1, "initially here was m1 object");, dict oblicza hashcode z m1 używając metody GetHashCode(). Następnie wykonuje pewne wewnętrzne obliczenia i ostatecznie umieszcza ten obiekt w pewnej pozycji swojej wewnętrznej tablicy.

Kiedy używam indeksu klucza, aby uzyskać wartość, na przykład dict[m1], dict ponownie oblicza kod skrótu. Następnie wykonuje pewne wewnętrzne obliczenia i daje mi obiekt, który znajduje się w obliczonej pozycji wewnątrz swojej wewnętrznej tablicy.

Ale myślę, że jest błąd, którego nie mogę znaleźć.

Więc pozwala założyć, że mam ten kod:

class MutableObject 
    { 
     Int32 m_value; 

     public MutableObject(Int32 value) 
     { 
      m_value = value; 
     } 

     public void Mutate(Int32 value) 
     { 
      m_value = value; 
     } 

     public override int GetHashCode() 
     { 
      return m_value; 
     } 
    } 

    static void Main(string[] args) 
    { 
     MutableObject m1 = new MutableObject(1); 
     MutableObject m2 = new MutableObject(2); 

     var dict = new Dictionary<MutableObject, String>(); 
     dict.Add(m1, "initially here was m1 object"); 
     dict.Add(m2, "initially here was m2 object"); 

     Console.WriteLine("Before mutation:"); 
     Console.WriteLine("dict[m1] = " + dict[m1]); 
     Console.WriteLine("dict[m2] = " + dict[m2]); 

     m1.Mutate(2); 
     m2.Mutate(1); 

     Console.WriteLine("After mutation:"); 
     Console.WriteLine("dict[m1] = " + dict[m1]); 
     Console.WriteLine("dict[m2] = " + dict[m2]); 

     Console.ReadKey(true); 
    } 

Kiedy zadzwonić Mutate metody, klucze są zamienione. Pomyślałem więc, że da to zamienione wyniki. Ale w rzeczywistości ta linia: Console.WriteLine("dict[m1] = " + dict[m1]); wyrzuca KeyNotFoundException i nie mogę zrozumieć, dlaczego. Oczywiście brakuje mi tutaj ...

Answer 1

Jak.Implementacja słownika NET działa z obiektami zmiennymi

Nie ma. W documentation for Dictionary stany:

Dopóki obiekt jest używany jako klucz w Dictionary<TKey, TValue>, musi nie zmienia w żaden sposób, który wpływa na jego wartość hash.

Ponieważ zmieniasz obiekt, gdy znajduje się on w Dictionary, nie będzie on działał.

Co do tego, nie jest to trudne. Włożyliśmy obiekt. Załóżmy, że kod skrótu to 1. Umieściliśmy obiekt w wiadrze 1 naszego stołu mieszającego. Teraz obiekt jest zmutowany spoza Słownika, więc jego wartość (i kod skrótu) to 2. Teraz, gdy ktoś poda ten obiekt do indeksu słownikowego, otrzymuje kod skrótu, zobacz, czy jest to 2 i wygląda w wiadrze 2. To wiadro jest puste, więc mówi "przepraszam, nie ma elementu".

Załóżmy teraz, że nowy obiekt został utworzony z wartością i hashiem 1. Jest przekazywany do Słownika, który widzi, że hash to 1. Wygląda w wiadrze 1 i stwierdza, że ​​rzeczywiście istnieje element w tym indeksie. Teraz używa Equals, aby określić, czy obiekty są w rzeczywistości równe (lub czy jest to tylko kolizja hash).

Teraz, w twoim przypadku, nie powiedzie się tutaj, ponieważ nie zastępujesz Equals, używasz domyślnej implementacji, która porównuje odniesienia, a ponieważ jest to inny obiekt, nie będzie mieć tego samego odniesienia. Jednak nawet jeśli zmieniłeś go, aby porównać wartości, * pierwszy obiekt został zmutowany, aby mieć wartość 2, a nie 1, więc i tak nie będzie pasował. Inni sugerowali naprawienie tej metody, i naprawdę powinieneś to zrobić, , ale nadal nie rozwiąże problemu.

Po zmutowaniu obiektu jedynym sposobem jego znalezienia jest sytuacja, w której zmutowana wartość jest kolizją haszującą (co jest możliwe, ale mało prawdopodobne). Jeśli tak nie jest, to wszystko, co jest równe zgodnie z Equals, nigdy nie będzie wiedzieć, aby sprawdzić właściwy zasobnik, a wszystko, co zostanie sprawdzone, nie będzie równe zgodnie z Equals.

Cytat, o którym wspomniałem na początku, to nie tylko najlepsza praktyka. To nie jest po prostu nieoczekiwane lub dziwne lub nieskuteczne mutowanie elementów w słowniku. Po prostu nie działa.

Teraz, jeśli obiekt jest zmienny , ale nie jest zmutowany, gdy znajduje się w słowniku, to jest w porządku. Może to być trochę dziwne, i to przypadek, który ludzie mogą powiedzieć, jest złą praktyką, nawet jeśli działa.

Answer 2

Nie wystarczy wykonać wyszukiwanie w słowniku, aby mieć ten sam kod skrótu. Ponieważ możliwe są kolizje mieszania, klucz musi być równy indeksowi, który jest wyszukiwany.

Answer 3

Twoja klasa MutableObject nie zastępuje Equals(object). Stąd używa się równania odniesienia (odziedziczonego z klasy bazowej System.Object).

Najpierw (szybko) znajduje wszystkie klucze z poprawnym kodem skrótu. Następnie sprawdza każdy z tych kluczy kandydatów, aby sprawdzić, czy jeden z nich szuka klucza.

Dlatego też Equals(object) i GetHashCode() powinny zostać zastąpione. Otrzymasz ostrzeżenie od kompilatora, jeśli przełożyłeś tylko jeden z nich.

Gdy kod skrótu klucza zmieni się, gdy klucz znajduje się w Dictionary<,>, klucz ten (prawdopodobnie) zostanie umieszczony w niewłaściwym miejscu wewnątrz Dictionary<,>, będzie w niewłaściwym "wiadrze", a zatem zostanie zgubiony. Nie zostanie znaleziony, ponieważ wyszukiwanie go zawsze odbywa się w wiadrze, w którym nie znajduje się.

W tym przykładzie kluczem jest tracona, a zatem może być ponownie dodane:

var dict = new Dictionary<MutableObject, string>(); 

var m = new MutableObject(1); 

dict.Add(m, "Hello"); 

m.Mutate(2); 

dict.Add(m, "world"); 

foreach (var p in dict) 
    Console.WriteLine(p); 

var otherDict = new Dictionary<MutableObject, string>(dict); // throws 

I rzeczywiście widać wyjątek takiego, podczas inicjalizacji jednego Dictionary<,> z elementów z istniejącej Dictionary<,> (zarówno użycie domyślnego EqualityComparer<> dla typu klucza).