Jaki jest poprawny i dobry sposób implementacji __hash __ ()?

150

Jaki jest prawidłowy i dobry sposób wdrożenia __hash__()?

Mówię o funkcji, która zwraca kod skrótu, który jest następnie używany do wstawiania obiektów do tabel skrótów, czyli słowników.

Ponieważ __hash__()zwraca liczbę całkowitą i służy do „dzielenia” obiektów na tablice mieszające, zakładam, że wartości zwracanej liczby całkowitej powinny być równomiernie rozłożone na wspólne dane (aby zminimalizować kolizje). Jaka jest dobra praktyka, aby uzyskać takie wartości? Czy kolizje są problemem? W moim przypadku mam małą klasę, która zachowuje się jak klasa kontenera zawierająca kilka int, kilka pływaków i string.

user229898
źródło

Odpowiedzi:

185

Łatwym i prawidłowym sposobem implementacji __hash__()jest użycie krotki kluczy. Nie będzie tak szybki jak wyspecjalizowany hash, ale jeśli tego potrzebujesz, prawdopodobnie powinieneś zaimplementować typ w C.

Oto przykład użycia klucza do skrótu i ​​równości:

class A:
    def __key(self):
        return (self.attr_a, self.attr_b, self.attr_c)

    def __hash__(self):
        return hash(self.__key())

    def __eq__(self, other):
        if isinstance(other, A):
            return self.__key() == other.__key()
        return NotImplemented

Ponadto dokumentacja__hash__ zawiera więcej informacji, które mogą być cenne w określonych okolicznościach.

John Millikin
źródło
1
Oprócz drobnych narzutów związanych z wyodrębnieniem __keyfunkcji, jest to tak szybkie, jak to tylko możliwe. Jasne, jeśli wiadomo, że atrybuty są liczbami całkowitymi, a nie ma ich zbyt wiele, przypuszczam, że można by potencjalnie działać nieco szybciej z jakimś hashem wyrzuconym na miejsce, ale prawdopodobnie nie byłby tak dobrze rozłożony. hash((self.attr_a, self.attr_b, self.attr_c))będzie zaskakująco szybkie (i poprawne ), ponieważ tworzenie małych tuples jest specjalnie zoptymalizowane i popycha pracę nad pobieraniem i łączeniem skrótów do wbudowanych C, co jest zwykle szybsze niż kod na poziomie Pythona.
ShadowRanger
Powiedzmy, że obiekt klasy A jest używany jako klucz do słownika i jeśli zmieni się atrybut klasy A, zmieni się również jego wartość skrótu. Czy to nie stworzyłoby problemu?
Mr Matrix
1
Jak wspomniano poniżej w odpowiedzi @oved.by.Jesus, metoda haszowania nie powinna być definiowana / zastępowana dla obiektu zmiennego (zdefiniowanego domyślnie i używa identyfikatora do równości i porównania).
Pan Matrix,
@Miguel, natknąłem się na dokładny problem , co się dzieje, że słownik wraca Nonepo zmianie klucza. Sposób, w jaki to rozwiązałem, polegał na przechowywaniu identyfikatora obiektu jako klucza, a nie tylko obiektu.
Jaswant P
@JaswantP Python domyślnie używa id obiektu jako klucza dla dowolnego obiektu z możliwością mieszania.
Pan Matrix
22

John Millikin zaproponował rozwiązanie podobne do tego:

class A(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        return (isinstance(othr, type(self))
                and (self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))

    def __hash__(self):
        return hash((self._a, self._b, self._c))

Problem z tym rozwiązaniem polega na tym, że plik hash(A(a, b, c)) == hash((a, b, c)). Innymi słowy, hash koliduje z krotką jego kluczowych członków. Może w praktyce nie ma to zbyt często znaczenia?

Aktualizacja: dokumentacja Pythona zaleca teraz używanie krotki, jak w powyższym przykładzie. Zauważ, że w dokumentacji podano

Jedyną wymaganą właściwością jest to, że obiekty, które porównują równe wartości, mają tę samą wartość skrótu

Zauważ, że nie jest odwrotnie. Obiekty, które nie są ze sobą równe, mogą mieć tę samą wartość skrótu. Taka kolizja skrótów nie spowoduje, że jeden obiekt zastąpi inny, gdy zostanie użyty jako klucz dict lub element zestawu, o ile obiekty nie są również równe .

Nieaktualne / złe rozwiązanie

Dokumentacja Pythona__hash__ sugeruje połączenie skrótów podskładników za pomocą czegoś takiego jak XOR , co daje nam to:

class B(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        if isinstance(othr, type(self)):
            return ((self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))
        return NotImplemented

    def __hash__(self):
        return (hash(self._a) ^ hash(self._b) ^ hash(self._c) ^
                hash((self._a, self._b, self._c)))

Aktualizacja: jak wskazuje Blckknght, zmiana kolejności a, b i c może powodować problemy. Dodałem dodatkowy, ^ hash((self._a, self._b, self._c))aby uchwycić kolejność haszowanych wartości. To końcowe ^ hash(...)można usunąć, jeśli łączonych wartości nie można zmienić (na przykład, jeśli mają one różne typy i dlatego wartość _anigdy nie zostanie przypisana do _blub _citp.).

millerdev
źródło
5
Zwykle nie chcesz wykonywać prostego XOR atrybutów razem, ponieważ spowoduje to kolizje, jeśli zmienisz kolejność wartości. Oznacza to, że hash(A(1, 2, 3))będzie równa hash(A(3, 1, 2))(a oni zarówno hash równać do innych Ainstancji z permutacji 1, 2a 3jako jej wartości). Jeśli chcesz, aby Twoja instancja nie miała tego samego skrótu co krotka swoich argumentów, po prostu utwórz wartość wartą (jako zmienną klasy lub jako globalną), a następnie umieść ją w krotce do zaszyfrowania: return hash ((_ sentinel , self._a, self._b, self._c))
Blckknght
1
Twoje użycie isinstancemoże być problematyczne, ponieważ obiekt podklasy klasy type(self)może być teraz równy obiektowi klasy type(self). Może się więc okazać, że dodanie a Cari a Forddo a set()może spowodować wstawienie tylko jednego obiektu, w zależności od kolejności wstawiania. Dodatkowo możesz napotkać sytuację, w której a == bjest prawda, ale b == ajest fałszem.
MaratC,
1
Jeśli tworzysz podklasy B, możesz zmienić to naisinstance(othr, B)
millerdev
7
Myśl: klucz krotki mogą obejmować typ klasy, które mogłyby zapobiec inne klasy z tego samego zestawu kluczowych atrybutów przed okazała się równa: hash((type(self), self._a, self._b, self._c)).
Ben Mosher
2
Oprócz kwestii używania Bzamiast type(self), często uważa się również, że lepszą praktyką jest zwracanie się w NotImplementedprzypadku napotkania nieoczekiwanego typu in __eq__zamiast False. To pozwala innym typom zdefiniowanym przez użytkownika na zaimplementowanie tego, __eq__który wie o tym Bi może go porównać, jeśli chcą.
Mark Amery,
16

Paul Larson z Microsoft Research zbadał szeroką gamę funkcji skrótu. Powiedział mi to

for c in some_string:
    hash = 101 * hash  +  ord(c)

działał zaskakująco dobrze dla szerokiej gamy strun. Odkryłem, że podobne techniki wielomianowe dobrze się sprawdzają przy obliczaniu skrótu różnych podpól.

George V. Reilly
źródło
8
Najwyraźniej Java robi to w ten sam sposób, ale używa 31 zamiast 101
user229898
3
Jakie jest uzasadnienie używania tych liczb? Czy jest powód, aby wybrać 101 lub 31?
bigblind
1
Oto wyjaśnienie dotyczące mnożników pierwszych: stackoverflow.com/questions/3613102/… . 101 wydaje się działać szczególnie dobrze, na podstawie eksperymentów Paula Larsona.
George V. Reilly
4
Python używa (hash * 1000003) XOR ord(c)dla łańcuchów z 32-bitowym mnożeniem z zawijaniem. [Citation ]
tylerl
4
Nawet jeśli to prawda, nie ma to praktycznego zastosowania w tym kontekście, ponieważ wbudowane typy łańcuchów Pythona już zapewniają __hash__metodę; nie musimy tworzyć własnych. Pytanie brzmi, jak zaimplementować __hash__dla typowej klasy zdefiniowanej przez użytkownika (z kilkoma właściwościami wskazującymi na typy wbudowane lub być może na inne takie klasy zdefiniowane przez użytkownika), których ta odpowiedź w ogóle nie dotyczy.
Mark Amery,
3

Mogę spróbować odpowiedzieć na drugą część twojego pytania.

Kolizje prawdopodobnie wynikną nie z samego kodu skrótu, ale z odwzorowania kodu skrótu na indeks w kolekcji. Na przykład twoja funkcja skrótu może zwracać losowe wartości od 1 do 10000, ale jeśli twoja tabela skrótów ma tylko 32 wpisy, po wstawieniu wystąpią kolizje.

Poza tym wydaje mi się, że kolizje byłyby rozwiązywane wewnętrznie przez kolekcję i istnieje wiele metod rozwiązywania kolizji. Najprostszym (i najgorszym) jest, mając wpis do wstawienia pod indeksem i, dodaj 1 do i, aż znajdziesz puste miejsce i wstaw je tam. Odzyskiwanie działa wtedy w ten sam sposób. Powoduje to nieefektywne pobieranie niektórych wpisów, ponieważ możesz mieć wpis, którego znalezienie wymaga przeszukania całej kolekcji!

Inne metody rozwiązywania kolizji skracają czas pobierania, przenosząc wpisy w tablicy skrótów, gdy element jest wstawiany w celu rozłożenia elementów. Zwiększa to czas wstawiania, ale zakłada, że ​​więcej czytasz niż wkładasz. Istnieją również metody, które próbują rozgałęziać różne kolidujące wpisy, tak aby wpisy były zgrupowane w jednym określonym miejscu.

Ponadto, jeśli chcesz zmienić rozmiar kolekcji, będziesz musiał ponownie zhasować wszystko lub użyć dynamicznej metody haszowania.

Krótko mówiąc, w zależności od tego, co używasz kodu skrótu, może być konieczne zaimplementowanie własnej metody rozwiązywania kolizji. Jeśli nie przechowujesz ich w kolekcji, prawdopodobnie możesz uciec dzięki funkcji skrótu, która po prostu generuje kody skrótu w bardzo dużym zakresie. Jeśli tak, możesz upewnić się, że twój pojemnik jest większy niż powinien (im większy, tym lepszy) w zależności od twoich problemów z pamięcią.

Oto kilka linków, jeśli jesteś zainteresowany bardziej:

skondensowany haszowanie na Wikipedii

Wikipedia zawiera również podsumowanie różnych metod rozwiązywania kolizji:

Ponadto „ Organizacja i przetwarzanie plików ” Tharp obszernie omawia wiele metod rozwiązywania kolizji. IMO to świetne odniesienie do algorytmów haszujących.

Kryptic
źródło
1

Bardzo dobre wyjaśnienie, kiedy i jak zaimplementować tę __hash__funkcję na stronie programiz :

Wystarczy zrzut ekranu, aby przedstawić przegląd: (Źródło: 13.12.2019)

Zrzut ekranu https://www.programiz.com/python-programming/methods/built-in/hash 2019-12-13

Jeśli chodzi o osobistą implementację metody, powyższa strona zawiera przykład pasujący do odpowiedzi millerdev .

class Person:
def __init__(self, age, name):
    self.age = age
    self.name = name

def __eq__(self, other):
    return self.age == other.age and self.name == other.name

def __hash__(self):
    print('The hash is:')
    return hash((self.age, self.name))

person = Person(23, 'Adam')
print(hash(person))
kochany przez Jezusa
źródło
0

Zależy od rozmiaru zwracanej wartości skrótu. Jest to prosta logika, że ​​jeśli chcesz zwrócić 32-bitową liczbę int w oparciu o hash czterech 32-bitowych int, wystąpią kolizje.

Wolałbym operacje bitowe. Na przykład następujący pseudokod w C:

int a;
int b;
int c;
int d;
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F);

Taki system mógłby również działać dla liczb zmiennoprzecinkowych, gdybyś po prostu wziął je jako wartość bitową, a nie reprezentował wartość zmiennoprzecinkową, może lepiej.

Jeśli chodzi o struny, nie mam pojęcia.

Szczeniak
źródło
Wiem, że będą kolizje. Ale nie mam pojęcia, jak się z nimi obchodzi. Co więcej, moje wartości atrybutów w połączeniu są bardzo rzadko rozłożone, więc szukałem inteligentnego rozwiązania. I jakoś spodziewałem się, że gdzieś będzie najlepsza praktyka.
user229898