Dlaczego dyktowanie w Pythonie może mieć wiele kluczy z tym samym hashem?

Próbuję zrozumieć funkcję Pythona hashpod maską. Utworzyłem niestandardową klasę, w której wszystkie instancje zwracają tę samą wartość skrótu.

class C:
    def __hash__(self):
        return 42

Po prostu założyłem, że tylko jedna instancja powyższej klasy może znajdować się dictw dowolnym momencie, ale w rzeczywistości dictmoże mieć wiele elementów z tym samym hashem.

c, d = C(), C()
x = {c: 'c', d: 'd'}
print(x)
# {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'}
# note that the dict has 2 elements

Poeksperymentowałem trochę więcej i stwierdziłem, że jeśli nadpisuję __eq__metodę w taki sposób, że wszystkie wystąpienia klasy są równe, wówczas dictjedyna zezwala na jedną instancję.

class D:
    def __hash__(self):
        return 42
    def __eq__(self, other):
        return True

p, q = D(), D()
y = {p: 'p', q: 'q'}
print(y)
# {<__main__.D object at 0x7f0823a9af40>: 'q'}
# note that the dict only has 1 element

Jestem więc ciekawy, jak dictmoże mieć wiele elementów z tym samym hashem.

Aby uzyskać szczegółowy opis działania haszowania w Pythonie, zobacz moją odpowiedź na pytanie: Dlaczego wczesny powrót jest wolniejszy niż gdzie indziej?

Zasadniczo używa skrótu, aby wybrać miejsce w tabeli. Jeśli w slocie znajduje się wartość, a hash pasuje, porównuje elementy, aby sprawdzić, czy są równe.

Jeśli hash nie pasuje lub elementy nie są równe, próbuje użyć innego gniazda. Istnieje formuła, która to wybiera (którą opisuję w przytoczonej odpowiedzi) i stopniowo pobiera nieużywane części wartości skrótu; ale gdy wykorzysta je wszystkie, w końcu przejdzie przez wszystkie gniazda w tablicy mieszania. To gwarantuje, że w końcu znajdziemy pasujący przedmiot lub puste miejsce. Kiedy wyszukiwanie znajdzie puste miejsce, wstawia wartość lub rezygnuje (w zależności od tego, czy dodajemy, czy pobieramy wartość).

Ważną rzeczą do zapamiętania jest to, że nie ma list ani zasobników: jest tylko tabela skrótów z określoną liczbą przedziałów, a każdy skrót jest używany do generowania sekwencji kandydujących gniazd.

Oto wszystko, co udało mi się zebrać na temat Pythona (prawdopodobnie więcej niż ktokolwiek chciałby wiedzieć; ale odpowiedź jest wyczerpująca). Krzyk do Duncana za wskazanie, że Python dyktuje używanie automatów i prowadzi mnie do tej króliczej nory.

• Słowniki Pythona są implementowane jako tabele skrótów .
• Tabele skrótów muszą zezwalać na kolizje skrótów, tj. Nawet jeśli dwa klucze mają tę samą wartość skrótu, implementacja tabeli musi mieć strategię umożliwiającą jednoznaczne wstawianie i pobieranie par klucz i wartość.
• Python dict używa otwartego adresowania do rozwiązywania kolizji hash (wyjaśnionych poniżej) (zobacz dictobject.c: 296-297 ).
• Tablica mieszająca Pythona to po prostu ciągły blok pamięci (coś w rodzaju tablicy, więc możesz O(1)wyszukiwać według indeksu).
• Każdy slot w tabeli może przechowywać jeden i tylko jeden wpis. To jest ważne
• Każdy wpis w tabeli jest właściwie kombinacją trzech wartości -. Jest to zaimplementowane jako struktura C (patrz dictobject.h: 51-56 )

• Poniższy rysunek jest logiczną reprezentacją tablicy skrótów Pythona. Na poniższym rysunku 0, 1, ..., i, ... po lewej stronie znajdują się indeksy slotów w tablicy haszującej (służą jedynie do celów ilustracyjnych i oczywiście nie są przechowywane razem z tabelą!).

  # Logical model of Python Hash table
  -+-----------------+
  0| <hash|key|value>|
  -+-----------------+
  1|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  i|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  n|      ...        |
  -+-----------------+
  

• Kiedy nowy dykt jest inicjowany, zaczyna się od 8 gniazd . (patrz dictobject.h: 49 )

• Dodając wpisy do tabeli zaczynamy od jakiegoś slotu, iczyli bazującego na hashu klucza. CPython używa initial i = hash(key) & mask. Gdzie mask = PyDictMINSIZE - 1, ale to nie jest naprawdę ważne). Zwróć uwagę, że początkowe miejsce, i, które jest sprawdzane, zależy od skrótu klucza.
• Jeśli ten slot jest pusty, wpis jest dodawany do slotu (mam na myśli wpis <hash|key|value>). Ale co jeśli to miejsce jest zajęte !? Najprawdopodobniej dlatego, że inny wpis ma ten sam hash (kolizja hash!)
• Jeśli miejsce jest zajęte, CPython (a nawet PyPy) porównuje hash ORAZ klucz (porównując, mam na myśli ==porównanie, a nie isporównanie) wpisu w gnieździe z kluczem bieżącego wpisu do wstawienia ( dictobject.c: 337 , 344-345 ). Jeśli oba pasują, to uważa, że ​​wpis już istnieje, poddaje się i przechodzi do następnego wpisu do wstawienia. Jeśli hash lub klucz nie pasują, rozpoczyna sondowanie .
• Sondowanie oznacza po prostu, że przeszukuje gniazda według gniazd, aby znaleźć puste miejsce. Technicznie rzecz biorąc, moglibyśmy przejść jeden po drugim, i + 1, i + 2, ... i użyć pierwszego dostępnego (to jest sondowanie liniowe). Ale z powodów pięknie wyjaśnionych w komentarzach (patrz dictobject.c: 33-126 ), CPython używa sondowania losowego . W przypadku sondowania losowego następny slot jest wybierany w pseudolosowej kolejności. Wpis zostanie dodany do pierwszego wolnego miejsca. W tej dyskusji rzeczywisty algorytm użyty do wybrania następnej szczeliny nie jest naprawdę ważny (patrz dictobject.c: 33-126 dla algorytmu sondowania). Ważne jest, aby sloty były sprawdzane do momentu znalezienia pierwszego wolnego miejsca.
• To samo dzieje się w przypadku wyszukiwań, po prostu zaczyna się od początkowego gniazda i (gdzie i zależy od skrótu klucza). Jeśli hash i klucz nie pasują do wpisu w gnieździe, rozpoczyna sondowanie, aż znajdzie gniazdo z dopasowaniem. Jeśli wszystkie miejsca są wyczerpane, zgłasza niepowodzenie.
• Przy okazji, rozmiar dyktowania zostanie zmieniony, jeśli jest zapełniony w dwóch trzecich. Pozwala to uniknąć spowolnienia wyszukiwania. (patrz dictobject.h: 64-65 )

Proszę bardzo! Implementacja funkcji dict w języku Python sprawdza zarówno wartość skrótu dwóch kluczy, jak i normalną równość ( ==) kluczy podczas wstawiania elementów. Podsumowując, jeśli istnieją dwa klucze ai bi hash(a)==hash(b), ale a!=b, to oba mogą harmonijnie istnieć w dyktandzie Pythona. Ale jeśli hash(a)==hash(b) i a==b , to nie mogą obaj być w tym samym dyktandzie.

Ponieważ musimy sondować po każdej kolizji hash, jednym z efektów ubocznych zbyt wielu kolizji hash jest to, że wyszukiwania i wstawiania będą bardzo powolne (jak wskazuje Duncan w komentarzach ).

Chyba krótka odpowiedź na moje pytanie brzmi: „Ponieważ tak to jest zaimplementowane w kodzie źródłowym;)”

Chociaż dobrze jest to wiedzieć (w przypadku punktów dla maniaków?), Nie jestem pewien, jak można go wykorzystać w prawdziwym życiu. Ponieważ jeśli nie próbujesz jawnie czegoś złamać, dlaczego dwa obiekty, które nie są równe, miałyby mieć ten sam hash?

Edycja : odpowiedź poniżej jest jednym z możliwych sposobów radzenia sobie z kolizjami skrótów, jednak nie jest to sposób, w jaki robi to Python. Witryna wiki Pythona, o której mowa poniżej, również jest niepoprawna. Najlepszym źródłem podanym poniżej przez @Duncan jest sama implementacja: https://github.com/python/cpython/blob/master/Objects/dictobject.c Przepraszam za pomyłkę.

Przechowuje listę (lub zasobnik) elementów pod hashem, a następnie przechodzi przez tę listę, aż znajdzie rzeczywisty klucz na tej liście. Obraz mówi więcej niż tysiąc słów:

Tutaj widzisz John Smithi Sandra Deeoba haszują 152. Wiadro 152zawiera oba z nich. Podczas wyszukiwania Sandra Deenajpierw znajduje listę w zasobniku 152, a następnie przechodzi przez tę listę, aż Sandra Deezostanie znaleziona i wróci 521-6955.

Poniższe jest błędne, że jest tu tylko dla kontekstu: Na wiki Pythona można znaleźć (pseudo?) Kod, w jaki sposób Python wykonuje wyszukiwanie.

W rzeczywistości istnieje kilka możliwych rozwiązań tego problemu, zapoznaj się z artykułem na Wikipedii, aby uzyskać ładny przegląd: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

Tabele skrótów generalnie muszą zezwalać na kolizje skrótów! Będziesz miał pecha i dwie rzeczy w końcu doprowadzą do tego samego. Poniżej znajduje się zestaw obiektów na liście elementów, które mają ten sam klucz skrótu. Zwykle na tej liście jest tylko jedna rzecz, ale w tym przypadku będzie układać je w tę samą. Jedynym sposobem, w jaki wie, że są różne, jest operator równości.

W takim przypadku wydajność z czasem będzie się pogarszać, dlatego chcesz, aby funkcja skrótu była jak najbardziej „losowa”.

W wątku nie widziałem, co dokładnie robi Python z instancjami klas zdefiniowanych przez użytkownika, kiedy umieszczamy je w słowniku jako klucze. Przeczytajmy trochę dokumentacji: deklaruje, że jako klucze mogą być używane tylko obiekty dające się hashować. Hashable to niezmienne klasy wbudowane i wszystkie klasy zdefiniowane przez użytkownika.

Klasy zdefiniowane przez użytkownika mają domyślnie metody __cmp __ () i __hash __ (); z nimi wszystkie obiekty porównują się nierówno (poza sobą), a x .__ hash __ () zwraca wynik pochodzący z id (x).

Więc jeśli masz stale __hash__ w swojej klasie, ale nie podajesz żadnej metody __cmp__ ani __eq__, to wszystkie instancje są nierówne dla słownika. Z drugiej strony, jeśli podasz jakąkolwiek metodę __cmp__ lub __eq__, ale nie podasz __hash__, Twoje wystąpienia będą nadal nierówne pod względem słownika.

class A(object):
    def __hash__(self):
        return 42


class B(object):
    def __eq__(self, other):
        return True


class C(A, B):
    pass


dict_a = {A(): 1, A(): 2, A(): 3}
dict_b = {B(): 1, B(): 2, B(): 3}
dict_c = {C(): 1, C(): 2, C(): 3}

print(dict_a)
print(dict_b)
print(dict_c)

Wynik

{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2}
{<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3}
{<__main__.C object at 0x7f9672f04a10>: 3}