Verständnis von Hash-Code

Question

Hash-Funktion ist wichtig bei der Implementierung Hash-Tabelle. Ich weiß, dass in Java Objekt hat seinen Hash-Code, der aus schwachen Hash-Funktion generiert werden kann.

Es folgt ein Code-Schnipsel, die „Ergänzung Hash-Funktion“

static int hash(Object x) { 
    int h = x.hashCode(); 

    h += ~(h << 9); 
    h ^= (h >>> 14); 
    h += (h << 4); 
    h ^= (h >>> 10); 
    return h; 
} 

Hilfe erklären Kann jemand ist, was die Grundidee eines Hash-Algorithmus ist ? um nicht duplizierte Ganzzahl zu generieren? Wenn ja, wie machen diese bitweisen Operationen es?

Answer 1

Was Sie normalerweise mit einem Hashalgorithmus versuchen, ist die Umwandlung eines großen Suchschlüssels in eine kleine nichtnegative Zahl, so dass Sie einen zugehörigen Datensatz in einer Tabelle nachschlagen können, und zwar schneller als M log2 N (wobei M die Kosten eines "Vergleichs" und N die Anzahl der Elemente in der "Tabelle" ist, die für eine binäre Suche (oder Baumsuche) typisch sind.

Wenn Sie das Glück haben, einen perfekten Hash zu haben, wissen Sie, dass jedes Element Ihres (bekannten!) Schlüsselsatzes mit einem einzigartigen, anderen Wert hashed wird. Perfekte Hashes sind in erster Linie für Compiler interessant, die Sprachschlüsselwörter nachschlagen müssen.

In der realen Welt haben Sie unvollkommene Hashes, bei denen mehrere Schlüssel alle auf denselben Wert haseln. Das ist in Ordnung: Sie müssen jetzt nur noch den Schlüssel mit einer kleinen Menge von Kandidatenübereinstimmungen (die mit diesem Wert hashen) vergleichen, anstatt mit einem großen Satz (der vollständigen Tabelle). Die kleinen Sets werden traditionell "Eimer" genannt. Sie verwenden den Hash-Algorithmus, um einen Bucket auszuwählen. Anschließend verwenden Sie eine andere durchsuchbare Datenstruktur für die Buckets. (Wenn die Anzahl der Elemente in einem Bucket bekannt oder sicher zu erwarten ist, ist die lineare Suche nicht unangemessen. Binäre Suchbäume sind ebenfalls sinnvoll.)

Die bitweisen Operationen in Ihrem Beispiel sehen ähnlich aus wie a Signaturanalyse-Schieberegister, die versuchen, ein langes, eindeutiges Bitmuster zu einem kurzen, noch eindeutigen Muster zu komprimieren.

Answer 2

Eine Hash-Funktion ist eine wohldefinierte Prozedur oder mathematische Funktion, die eine große, möglicherweise variable Größe von Daten in ein kleines Datum umwandelt, normalerweise eine ganze Zahl, die als Index für ein Array dienen kann. Die von einer Hash-Funktion zurückgegebenen Werte werden Hash-Werte, Hash-Codes, Hash-Summen, Prüfsummen oder einfach Hashes genannt. (wikipedia)

Mit mehr "menschlichen" Sprache Objekt Hash ist ein kurzer und kompakter Wert basierend auf Objekteigenschaften. Das heißt, wenn Sie zwei Objekte haben, die irgendwie variieren - Sie können erwarten, dass ihre Hash-Werte unterschiedlich sind. Ein guter Hash-Algorithmus erzeugt unterschiedliche Werte für verschiedene Objekte.

Answer 3

Dieser Code versucht, die Qualität des Hash-Werts zu verbessern, indem die Bits umgebrochen werden.

Der Gesamteffekt ist, dass für eine gegebene x.hashCode() Sie hoffentlich eine bessere Verteilung von Hash-Werten über den gesamten Bereich von ganzen Zahlen erhalten. Die Leistung bestimmter Algorithmen verbessert sich, wenn Sie mit einer schlechten Hashcode-Implementierung begonnen haben, dann aber die Hash-Codes auf diese Weise verbessern.

Zum Beispiel gibt hashCode() für eine bescheidene Ganzzahl in Java nur den ganzzahligen Wert zurück. Während dies für viele Zwecke in Ordnung ist, möchten Sie in einigen Fällen einen viel besseren Hash-Code. Wenn Sie den Hash-Code durch diese Art von Funktion bringen, würde das den Code deutlich verbessern.

Answer 4

Die Sache, die Sie mit einer Hash-Funktion erreichen wollen, besteht darin, allen Bits im Hash-Code eine Chance von 50% zu geben, ein- oder ausgeschaltet zu sein.Auf diese Weise ist es egal, wie viele "Buckets" Ihre Hash-Tabelle hat (oder einen anderen Weg, wie viele der unteren Bits nehmen Sie, um die Bucket-Nummer zu bestimmen) - wenn alle Bit ist so zufällig wie möglich, dann wird ein Artikel immer einem im Wesentlichen zufälligen Bucket zugewiesen.

Jetzt, im wirklichen Leben, verwenden viele Leute Hash-Funktionen, die nicht so gut sind. Sie haben einige Zufälligkeit in einigen der Bits, aber nicht alle von ihnen. Stellen Sie sich zum Beispiel vor, wenn Sie eine Hash-Funktion haben, deren Bits 6-7 voreingenommen sind - sagen wir, in dem typischen Hash-Code eines Objekts haben sie eine Wahrscheinlichkeit von 75% gesetzt zu werden. Wenn in diesem Beispiel unsere Hash-Tabelle 256 Buckets hat (dh die Bucket-Nummer kommt aus den Bits 0-7 des Hash-Codes), dann werfen wir die Zufälligkeit weg, die in den Bits 8-31 existiert, und eine kleinere Ein Teil der Eimer wird dazu neigen, gefüllt zu werden (dh diejenigen, deren Zahlen die Bits 6 und 7 gesetzt haben).

Die zusätzliche Hash-Funktion versucht grundsätzlich, die in den Hash-Codes vorhandene Zufälligkeit über eine größere Anzahl von Bits zu verteilen. In unserem hypothetischen Beispiel wäre also die Idee, dass etwas von der Zufälligkeit von den Bits 8-31 mit den unteren Bits gemischt wird und die Vorspannung der Bits 6-7 verdünnt wird. Es wird immer noch nicht perfekt sein, aber besser als vorher.

Answer 5

Wenn Sie eine Hash-Tabelle sind zu erzeugen, dann ist die Hauptsache, Sie vermitteln möchten, wenn Ihre Hash-Funktion ist das Schreiben Einheitlichkeit zu gewährleisten, die nicht unbedingt zu schaffen völlig eindeutige Werte.

Zum Beispiel, wenn Sie eine Hash-Tabelle der Größe 10 haben, Sie nicht wollen, eine Hash-Funktion, die einen Hash von 3 über und über zurückgibt. Andernfalls wird dieser Suchbereich eine Suchzeit von O (n) erzwingen. Sie möchten eine Hash-Funktion wie beispielsweise: 1, 9, 4, 6, 8 ... und sicherstellen, dass keiner Ihrer Buckets viel schwerer ist als die anderen.

Für Ihre Projekte würde ich empfehlen, dass Sie einen bekannten Hashing-Algorithmus wie MD5 oder noch besser SHA verwenden und die ersten k Bits verwenden, die Sie benötigen, und den Rest verwerfen. Dies sind bewährte Funktionen und als Programmierer wäre es klug, sie zu verwenden.

Answer 6

Es könnte alles, was Sie wollen, solange Sie auf die in der doc beschrieben general contract haften, die in meiner eigenen Worte sind:

• Wenn Sie 100 anrufen (N) mal hashCode auf ein Objekt, alle die Zeiten, müssen den gleichen Wert zurück, zumindest während dieser Programmausführung (nachfolgende Programmausführung einen anderen zurückkehren)
• Wenn o1.equals(o2) wahr ist, dann o1.hashCode() == o2.hashCode() wahr sein muss auch
• Wenn o1.equals(o2) falsch ist, dann kann o1.hashCode() == o2.hashCode() sein wahr, aber ich t hilft es nicht.

Und das ist es.

Abhängig von der Art Ihrer Klasse kann hashCode() e sehr komplex oder sehr einfach sein. Zum Beispiel benötigt die String Klasse, die Millionen von Instanzen haben kann, eine sehr gute Implementierung und verwendet Primzahlen, um die Beweglichkeit von Kollisionen zu reduzieren.

Wenn für Ihre Klasse es Sinn macht, eine laufende Nummer zu haben, das ist auch in Ordnung, es gibt keinen Grund, warum Sie es jedes Mal, erschweren sollten.