Hash-Funktionen und Hash-Codes

Eine typische Hash-Funktion wandelt zunächst einen Suchschlüssel in einen ganzzahligen Wert um, der als Hash-Code bezeichnet wird, und komprimiert dann den Hash-Code in einen Index für die Hash-Tabelle. Javas Stammklasse Object verfügt über die Methode hashCode, die einen ganzzahligen Hash-Code zurückgibt. Standardmäßig gibt die Methode die Speicheradresse für das Objekt zurück. Der allgemeine Vertrag für die Methode hashCode lautet wie folgt:

1. Sie sollten die Methode hashCode immer dann überschreiben, wenn die Methode equals überschrieben wird, um sicherzustellen, dass zwei gleiche Objekte denselben Hash-Code zurückgeben.
2. Während der Ausführung eines Programms gibt der mehrmalige Aufruf der Methode hashCode dieselbe Ganzzahl zurück, vorausgesetzt, dass die Daten des Objekts nicht geändert werden.
3. Zwei ungleiche Objekte können denselben Hash-Code haben, aber Sie sollten die Methode hashCode implementieren, um zu viele solcher Fälle zu vermeiden.

Hash-Codes für primitive Typen

Für Suchschlüssel des Typs byte, short, int und char wandeln Sie sie einfach in int um . Daher haben zwei verschiedene Suchschlüssel eines dieser Typen unterschiedliche Hash-Codes.

Für einen Suchschlüssel vom Typ float verwenden Sie Float.floatToIntBits(key) als Hash-Code. Beachten Sie, dass floatToIntBits(float f) einen int-Wert zurückgibt, dessen Bitdarstellung mit der Bitdarstellung für die Gleitkommazahl f übereinstimmt. Somit haben zwei verschiedene Suchschlüssel vom Typ float unterschiedliche Hash-Codes.

Für einen Suchschlüssel des Typs long wäre es keine gute Wahl, ihn einfach in int umzuwandeln, da alle Schlüssel, die sich nur in den ersten 32 Bits unterscheiden, das haben Gleicher Hash-Code. Um die ersten 32 Bits zu berücksichtigen, teilen Sie die 64 Bits in zwei Hälften und führen Sie die Exklusiv-ODER-Operation aus, um die beiden Hälften zu kombinieren. Dieser Vorgang wird Falten genannt. Der Hash-Code für einen langen Schlüssel lautet

int hashCode = (int)(key ^ (key >> 32));

Beachten Sie, dass >> der Rechtsverschiebungsoperator ist, der die Bits um 32 Positionen nach rechts verschiebt. Beispiel: 1010110 >> 2 ergibt 0010101. Das ^ ist der bitweise Exklusiv-Oder-Operator. Es arbeitet mit zwei entsprechenden Bits der binären Operanden. Beispielsweise ergibt 1010110 ^ 0110111 1100001.

Für einen Suchschlüssel vom Typ double konvertieren Sie ihn zunächst mit der Methode Double.doubleToLongBits in einen long-Wert und führen Sie dann eine Faltung durch folgt:

lange Bits = Double.doubleToLongBits(key);
int hashCode = (int)(bits ^ (bits >> 32));

Hash-Codes für Strings

Suchschlüssel sind oft Zeichenfolgen, daher ist es wichtig, eine gute Hash-Funktion für Zeichenfolgen zu entwerfen. Ein intuitiver Ansatz besteht darin, den Unicode aller Zeichen als Hash-Code für die Zeichenfolge zu summieren. Dieser Ansatz funktioniert möglicherweise, wenn zwei Suchschlüssel in einer Anwendung nicht dieselben Buchstaben enthalten. Es kommt jedoch zu vielen Kollisionen, wenn die Suchschlüssel dieselben Buchstaben enthalten, z. B. tod und dot .

Ein besserer Ansatz besteht darin, einen Hash-Code zu generieren, der die Position von Zeichen berücksichtigt. Lassen Sie den Hash-Code insbesondere

sein

s0*b(n - 1) + s1*b(n - 2) + c + sn-1

wobei si s.charAt(i) ist. Dieser Ausdruck ist ein Polynom für ein positives b, daher wird dies als Polynom-Hashcode bezeichnet. Unter Verwendung der Horner-Regel zur Polynomauswertung (siehe Fallstudie: Konvertieren von Hexadezimalzahlen in Dezimalzahlen) kann der Hash-Code wie folgt effizient berechnet werden:

(...((s0*b + s1)b + s2)b + ... + sn-2)b + sn-1

Diese Berechnung kann bei langen Zeichenfolgen zu einem Überlauf führen, ein arithmetischer Überlauf wird jedoch in Java ignoriert. Sie sollten einen geeigneten Wert b wählen, um Kollisionen zu minimieren. Experimente zeigen, dass gute Optionen für b 31, 33, 37, 39 und 41 sind. In der Klasse String wird der hashCode mithilfe des Polynom-Hash-Codes überschrieben, wobei b 31.

Komprimieren von Hash-Codes

Der Hash-Code für einen Schlüssel kann eine große Ganzzahl sein, die außerhalb des Bereichs für den Hash-Tabellenindex liegt. Sie müssen ihn daher verkleinern, damit er in den Bereich des Index passt. Angenommen, der Index für eine Hash-Tabelle liegt zwischen

0 und N-1. Die gebräuchlichste Methode zum Skalieren einer Ganzzahl zwischen 0 und N-1 ist die Verwendung von

h(hashCode) = hashCode % N

Um sicherzustellen, dass die Indizes gleichmäßig verteilt sind, wählen Sie N als Primzahl größer als 2.

Idealerweise sollten Sie für N eine Primzahl wählen. Allerdings ist es zeitaufwändig, eine große Primzahl zu finden. In der Java-API-Implementierung für java.util.HashMap ist N auf einen Wert der Potenz von 2 gesetzt. Es gibt einen guten Grund für diese Wahl. Wenn N ein Wert der Potenz von 2 ist,

h(hashCode) = hashCode % N

ist dasselbe wie

h(hashCode) = hashCode & (N – 1)

Das kaufmännische Und-Zeichen & ist ein bitweiser UND-Operator. Das UND zweier entsprechender Bits ergibt eine 1, wenn beide Bits 1 sind. Nehmen wir zum Beispiel an: N = 4 und hashCode = 11, 11 % 4 = 3, was dasselbe ist wie 01011 & 00011 = 11. Der &-Operator kann viel schneller ausgeführt werden als der %-Operator.

Um sicherzustellen, dass das Hashing gleichmäßig verteilt wird, wird in der Implementierung von java.util.HashMap neben der primären Hash-Funktion auch eine zusätzliche Hash-Funktion verwendet. Diese Funktion ist definiert als:

private static int SupplementalHash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

^ und >>> sind bitweise Exklusiv-ODER- und vorzeichenlose Rechtsverschiebungsoperationen. Die bitweisen Operationen sind viel schneller als die Multiplikations-, Divisions- und Restoperationen. Sie sollten diese Operationen nach Möglichkeit durch bitweise Operationen ersetzen.

Die vollständige Hash-Funktion ist definiert als:

h(hashCode) = SupplementalHash(hashCode) % N

Das ist dasselbe wie

h(hashCode) = SupplementalHash(hashCode) & (N – 1)

da N ein Wert der Potenz von 2 ist.

Das obige ist der detaillierte Inhalt vonHash-Funktionen und Hash-Codes. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!