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

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.

Ł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 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.).

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.

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.

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)

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

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.