Jaki jest prawidłowy i dobry sposób implementacji hash ()?

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 hash(A(a, b, c)) == hash((a, b, c)). Innymi słowy, hash koliduje z krotką jego kluczowych członków. Może to nie ma znaczenia w praktyce?

Aktualizacja: dokumenty Pythona zalecają teraz użycie krotki, jak w powyższym przykładzie. Zauważ, że dokumentacja stwierdza

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

Zauważ, że przeciwieństwo nie jest prawdą. Obiekty, które nie są równe mogą mieć tę samą wartość skrótu. Taka kolizja skrótu nie spowoduje, że jeden obiekt zastąpi inny, gdy zostanie użyty jako klucz dict lub element zestawu , o ile obiekty nie będą porównywać sobie równych .

Przestarzałe / złe rozwiązanie

dokumentacja Pythona na __hash__ sugeruje połączenie hashów podsystemó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 Blckknght wskazuje, Zmiana kolejności a, b i c może spowodować problemy. Dodałem dodatkowe ^ hash((self._a, self._b, self._c)), aby uchwycić kolejność wartości, które są hashowane. Ta końcowa ^ hash(...) może zostać usunięta, jeśli wartości łączone nie mogą być przestawione (na przykład, jeśli mają różne typy i dlatego wartość _a nigdy nie zostanie przypisana do _b lub _c, itd.).

Paul Larson z Microsoft Research badał szeroką gamę funkcji skrótu. Powiedział mi, że

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

Sprawdził się zaskakująco dobrze dla szerokiej gamy strun. Odkryłem, że podobne techniki wielomianowe działają dobrze do obliczania hashu różnych pól podrzędnych.

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

Kolizje prawdopodobnie nie wynikną z samego kodu hash, ale z mapowania kodu hash do indeksu w kolekcji. Na przykład funkcja skrótu może zwracać losowe wartości od 1 do 10000, ale jeśli twoja tabela skrótu zawiera tylko 32 wpisy, otrzymasz kolizje podczas wstawiania.

Ponadto myślę, że kolizje będą rozwiązywane wewnętrznie przez zbiór i istnieje wiele metod rozwiązywania kolizje. Najprostszym (i najgorszym) jest, biorąc pod uwagę wpis do wstawienia w indeksie i, dodaj 1 do i, aż znajdziesz puste miejsce i wstawisz tam. Odzyskiwanie działa wtedy w ten sam sposób. Powoduje to nieefektywne pobieranie niektórych wpisów, ponieważ możesz mieć wpis, który wymaga przemierzenia całej kolekcji, aby znaleźć!

Inne metody rozwiązywania kolizji skracają czas pobierania poprzez przesuwanie wpisów w tabeli hash, gdy element jest wstawiany w celu rozłożenia rzeczy. Zwiększa to Wkładanie czas, ale zakłada, że czytasz więcej niż wstawiasz. Istnieją również metody, które próbują rozgałęziać różne kolidujące wpisy tak, że wpisy do klastra w jednym konkretnym miejscu.

Ponadto, jeśli chcesz zmienić rozmiar kolekcji, musisz ponownie wszystko zmienić lub użyć dynamicznej metody mieszania.

Krótko mówiąc, w zależności od tego, do czego używasz kodu hashowego, może być konieczne zaimplementowanie własnej metody rozwiązywania kolizji. Jeśli nie przechowujesz ich w kolekcji, prawdopodobnie możesz uzyskać z dala od funkcji hash, która po prostu generuje kody hash w bardzo dużym zakresie. Jeśli tak, możesz upewnić się, że Twój kontener jest większy niż musi być (im większy, tym lepiej oczywiście), w zależności od twoich problemów z pamięcią.

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

Haszowanie na Wikipedii

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

Również " Organizacja i przetwarzanie plików" przez Tharp obejmuje wiele metod rozwiązywania kolizji obszernie. IMO jest to świetne odniesienie do algorytmów haszujących.

Bardzo dobre wyjaśnienie kiedy i jak zaimplementować funkcję __hash__ jest na stronie programiz :

Wystarczy zrzut ekranu, aby uzyskać przegląd: (2019-12-13)

Jeśli chodzi o osobistą implementację metody, wyżej wymieniona strona dostarcza przykład, który pasuje 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 wielkości zwracanej wartości skrótu. To prosta logika, że jeśli chcesz zwrócić 32-bitowy int oparty na hash czterech 32-bitowych int, dostaniesz kolizje.

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

Taki system może działać również dla floatów, jeśli po prostu przyjmiesz je jako ich wartość bitową, a nie faktycznie reprezentującą wartość zmiennoprzecinkową, może lepiej.