Was ist ein korrekter und guter Weg, um __hash __ () zu implementieren?

Was ist ein korrekter und guter Weg, um zu implementieren __hash__()?

Ich spreche von der Funktion, die einen Hashcode zurückgibt, der dann zum Einfügen von Objekten in Hashtabellen oder Wörterbücher verwendet wird.

Da __hash__()eine Ganzzahl zurückgegeben wird und zum "Binning" von Objekten in Hashtabellen verwendet wird, gehe ich davon aus, dass die Werte der zurückgegebenen Ganzzahl für allgemeine Daten gleichmäßig verteilt sein sollten (um Kollisionen zu minimieren). Was ist eine gute Praxis, um solche Werte zu erhalten? Sind Kollisionen ein Problem? In meinem Fall habe ich eine kleine Klasse, die als Containerklasse fungiert und einige Ints, einige Floats und eine Zeichenfolge enthält.

Eine einfache und korrekte Implementierung __hash__()ist die Verwendung eines Schlüsseltupels. Es ist nicht so schnell wie ein spezialisierter Hash, aber wenn Sie das brauchen, sollten Sie den Typ wahrscheinlich in C implementieren.

Hier ist ein Beispiel für die Verwendung eines Schlüssels für Hash und Gleichheit:

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

Außerdem enthält die Dokumentation von__hash__ mehr Informationen, die unter bestimmten Umständen wertvoll sein können.

John Millikin schlug eine ähnliche Lösung vor:

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

Das Problem bei dieser Lösung ist, dass die hash(A(a, b, c)) == hash((a, b, c)). Mit anderen Worten, der Hash kollidiert mit dem des Tupels seiner Schlüsselmitglieder. Vielleicht spielt das in der Praxis keine Rolle?

Update: In den Python-Dokumenten wird jetzt empfohlen, ein Tupel wie im obigen Beispiel zu verwenden. Beachten Sie, dass in der Dokumentation angegeben ist

Die einzige erforderliche Eigenschaft ist, dass Objekte, die gleich sind, denselben Hashwert haben

Beachten Sie, dass das Gegenteil nicht der Fall ist. Objekte, die nicht gleich sind, haben möglicherweise denselben Hashwert. Eine solche Hash-Kollision führt nicht dazu, dass ein Objekt ein anderes ersetzt, wenn es als Diktatschlüssel oder Set-Element verwendet wird , solange die Objekte nicht auch gleich sind .

Veraltete / schlechte Lösung

Die Python-Dokumentation zu__hash__ schlägt vor, die Hashes der Unterkomponenten mit etwas wie XOR zu kombinieren , was uns Folgendes gibt:

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

Update: Wie Blckknght betont, kann das Ändern der Reihenfolge von a, b und c zu Problemen führen. Ich habe eine zusätzliche hinzugefügt ^ hash((self._a, self._b, self._c)), um die Reihenfolge der gehashten Werte zu erfassen. Dieses Finale ^ hash(...)kann entfernt werden, wenn die zu kombinierenden Werte nicht neu angeordnet werden können (z. B. wenn sie unterschiedliche Typen haben und daher der Wert von _aniemals _boder _cusw. zugewiesen wird).

Paul Larson von Microsoft Research untersuchte eine Vielzahl von Hash-Funktionen. Er hat mir das erzählt

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

funktionierte überraschend gut für eine Vielzahl von Saiten. Ich habe festgestellt, dass ähnliche Polynomtechniken gut für die Berechnung eines Hashs unterschiedlicher Unterfelder geeignet sind.

Ich kann versuchen, den zweiten Teil Ihrer Frage zu beantworten.

Die Kollisionen resultieren wahrscheinlich nicht aus dem Hash-Code selbst, sondern aus der Zuordnung des Hash-Codes zu einem Index in einer Sammlung. So könnte Ihre Hash-Funktion beispielsweise zufällige Werte von 1 bis 10000 zurückgeben. Wenn Ihre Hash-Tabelle jedoch nur 32 Einträge enthält, werden beim Einfügen Kollisionen auftreten.

Darüber hinaus würde ich denken, dass Kollisionen von der Sammlung intern aufgelöst werden, und es gibt viele Methoden, um Kollisionen aufzulösen. Das einfachste (und schlechteste) ist, wenn Sie einen Eintrag zum Einfügen am Index i erhalten, 1 zu i addieren, bis Sie eine leere Stelle finden und dort einfügen. Das Abrufen funktioniert dann genauso. Dies führt zu ineffizienten Abrufen für einige Einträge, da Sie möglicherweise einen Eintrag haben, für dessen Suche die gesamte Sammlung durchlaufen werden muss!

Andere Kollisionsauflösungsmethoden reduzieren die Abrufzeit, indem Einträge in der Hash-Tabelle verschoben werden, wenn ein Element eingefügt wird, um Dinge zu verteilen. Dies erhöht die Einfügezeit, setzt jedoch voraus, dass Sie mehr lesen als einfügen. Es gibt auch Methoden, die versuchen, verschiedene kollidierende Einträge zu verzweigen, damit Einträge an einer bestimmten Stelle gruppiert werden.

Wenn Sie die Größe der Sammlung ändern müssen, müssen Sie alles erneut aufbereiten oder eine dynamische Hashing-Methode verwenden.

Kurz gesagt, je nachdem, wofür Sie den Hash-Code verwenden, müssen Sie möglicherweise Ihre eigene Kollisionsauflösungsmethode implementieren. Wenn Sie sie nicht in einer Sammlung speichern, können Sie wahrscheinlich mit einer Hash-Funktion davonkommen, die nur Hash-Codes in einem sehr großen Bereich generiert. In diesem Fall können Sie sicherstellen, dass Ihr Container größer ist als er sein muss (je größer, desto besser natürlich), abhängig von Ihren Speicherproblemen.

Hier sind einige Links, wenn Sie mehr interessiert sind:

Koalesziertes Hashing auf Wikipedia

Wikipedia hat auch eine Zusammenfassung verschiedener Methoden zur Kollisionsauflösung:

Außerdem behandelt " File Organization And Processing " von Tharp viele Methoden zur Kollisionsauflösung ausführlich. IMO ist eine großartige Referenz für Hashing-Algorithmen.

Eine sehr gute Erklärung, wann und wie die __hash__Funktion implementiert wird, finden Sie auf der Website von programiz :

Nur ein Screenshot, um einen Überblick zu geben: (Abgerufen am 13.12.2019)

Für eine persönliche Implementierung der Methode bietet die oben genannte Site ein Beispiel, das der Antwort von millerdev entspricht .

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

Hängt von der Größe des zurückgegebenen Hashwerts ab. Es ist eine einfache Logik, dass Sie Kollisionen bekommen, wenn Sie einen 32-Bit-Int basierend auf dem Hash von vier 32-Bit-Ints zurückgeben müssen.

Ich würde Bitoperationen bevorzugen. Wie der folgende C-Pseudocode:

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

Ein solches System könnte auch für Floats funktionieren, wenn Sie sie einfach als Bitwert verwenden, anstatt tatsächlich einen Gleitkommawert darzustellen, vielleicht besser.

Für Streicher habe ich wenig / keine Ahnung.