Über die Implementierung von Java HashMap

Warum muss die Kapazität ein Vielfaches oder 2 sein? Warum "&" im indexFür Funktionen verwenden? Warum den Hash in der Hash-Funktion neu berechnen, anstatt direkt den Hash-Code des Schlüssels zu verwenden?Über die Implementierung von Java HashMap

Ich denke, es gibt einige wichtige Unterschiede zwischen dieser Implementierung und der Beschreibung der "Einführung in den Algorithmus".

Was bedeutet ">>>"?

static int hash(int h) { 
     // This function ensures that hashCodes that differ only by 
     // constant multiples at each bit position have a bounded 
     // number of collisions (approximately 8 at default load factor). 
     h ^= (h >>> 20)^(h >>> 12); 
     return h^(h >>> 7)^(h >>> 4); 
}

Kann mir jemand eine Anleitung geben? Ich schätze es, wenn jemand den Hash-Algorithmus erklären kann. Vielen Dank!

Quelle

2012-04-03 lingguang1997

Ich weiß mit "&", der Schlüssel kann auf die begrenzten Steckplätze zugeordnet werden. Was ist mit Einfluss auf die Kollision in der Hash-Karte? – lingguang1997

'>>>' ist vorzeichenlose Rechtsverschiebung. Reguläres '>>' in Java behält und propagiert das Vorzeichenbit und lässt eine negative Zahl negativ. '>>>' füllt das Vorzeichenbit mit Nullen, wenn eine Verschiebung auftritt. –

Dies ist eine Leistungsoptimierung. Der üblicher Weg, einen Hash-Code in einen Tabellenindex abzubilden ist

table_index = hash_code % table_length;

Der % Betreiber teuer ist. Wenn table_length eine Potenz von 2, dann ist die Berechnung:

table_index = hash_code & (table_length - 1);

entsprechen die (viel) teurer Modulo-Operation.

Quelle

2012-04-03 21:34:28

Deshalb ist es eine gute Idee zu lernen, in Assembly auf einem alten Prozessor zu programmieren. – biziclop

Gefahr wird Robinson! 50% der Hash-Codes sind negative Zahlen, daher kann 'hash_code% table_length' negativ sein, was zu einer' ArrayOutOfBoundsException' führt. Sie müssen 'Math.abs (hash_code% table_length)' verwenden, um einen verwendbaren (dh sicheren) Index zu erhalten – Bohemian

@Bohemian - Ja, negative Zahlen sind eine zusätzliche Komplikation. Das ist ein weiterer Vorteil der zweiten Methode, die bei negativen Hash-Code-Werten gut funktioniert. –

Achten Sie nicht auf den Mann hinter dem Vorhang.

Der eigentliche Algorithmus ist zweifellos eine Kombination aus "was sich gut anfühlt" für den Entwickler, Fixes für einige seltsame degenerierte Fälle und einfache Tradition (für die Benutzer oft dunkle Abhängigkeiten entwickeln).

Und beachten Sie folgendes:

* Applies a supplemental hash function to a given hashCode, which 
* defends against poor quality hash functions. This is critical 
* because HashMap uses power-of-two length hash tables, that 
* otherwise encounter collisions for hashCodes that do not differ 
* in lower bits. Note: Null keys always map to hash 0, thus index 0.

Net: Solange es funktioniert und die Leistung ist gut, Sie kümmern sich nicht.

Quelle

2012-04-03 21:46:02

Danke für die Antwort von allen. Sie sind meine Frage beantwortet. – lingguang1997

Über die Implementierung von Java HashMap

Antwort

Verwandte Themen