Ich schaue auf die Implementierung von HashMap in Java und bin an einem Punkt fest.
Wie wird die indexFor Funktion berechnet?HashMap-Implementierung in Java. Wie funktioniert die Bucket-Index-Berechnung?
static int indexFor(int h, int length) {
return h & (length-1);
}
Dank
Es ist nicht die Hash-Berechnung, ist es die Berechnung der Eimer.
Der Ausdruck h & (length-1) hat eine bitweise AND auf hlength-1 verwenden, die wie eine Bitmaske ist, werden nur die niederwertigen Bits von h zurückzukehren, um dadurch für eine superschnelle Variante h % length machen.
Er berechnet den Bucket der Hash-Map, in dem der Eintrag (Schlüssel/Wert-Paar) gespeichert wird. Die Bucket-ID lautet hashvalue/buckets length.
Eine Hash-Map besteht aus Buckets; Objekte werden basierend auf der Bucket-ID in diesen Buckets platziert.
Eine beliebige Anzahl von Objekten kann basierend auf ihrem hash code/buckets length Wert in den gleichen Bucket fallen. Dies wird als "Kollision" bezeichnet.
Wenn viele Objekte in den gleichen Bucket fallen, wird während der Suche nach ihrer equals() -Methode zur Disambiguierung aufgerufen.
Die Anzahl der Kollisionen ist indirekt proportional zur Bucket-Länge.
Der Hash selbst wird mit der Methode hashCode() des Objekts berechnet, das Sie speichern möchten.
Was Sie hier sehen, berechnet den "Eimer", um das Objekt basierend auf dem Hash h zu speichern. Um Kollisionen zu vermeiden, hätten Sie idealerweise die gleiche Anzahl an Buckets wie der maximal erreichbare Wert von h - aber das könnte zu viel Speicher erfordern. Daher haben Sie normalerweise eine geringere Anzahl von Buckets mit der Gefahr von Kollisionen.
Wenn h ist, sagen wir 1000, aber Sie haben nur 512 Eimer in Ihrem zugrunde liegenden Array, müssen Sie wissen, wo das Objekt zu setzen. Normalerweise würde eine mod Operation auf h reichen, aber das ist zu langsam. Angesichts der internen Eigenschaft HashMap dass das zugrunde liegende Array immer hat Anzahl von Buckets gleich 2^n, die Sonnen Ingenieure die Idee h & (length-1) nutzen könnten, es hat eine bitwise AND mit einer Reihe bestehend aus allen 1 ‚s, praktisch das Lesen nur die n niedrigste Bits des Hash (das ist das gleiche wie , nur viel schneller).
Beispiel:
hash h: 11 1110 1000 -- (1000 in decimal)
length l: 10 0000 0000 -- (512 in decimal)
(l-1): 01 1111 1111 -- (511 in decimal - it will always be all ONEs)
h AND (l-1): 01 1110 1000 -- (488 in decimal which is a result of 1000 mod 512)
Macht es jetzt Sinn, oder sollte ich mehr über die Interna erfahren ? –
_Very_ gut erklärt. Ich bin beeindruckt. –
habe es .... danke – gnreddy
Können Sie bitte diese Berechnung hier erklären? – gnreddy
Wird davon ausgegangen, dass "Länge" eine Potenz von 2 ist? – LarsH
@LarsH Nun, es wäre viel besser, wenn es eine Potenz von 2 wäre, dann würdest du die Bits der höheren Ordnung sauber abschneiden. Wie dem auch sei, die Implementierung von HashMap beginnt mit Größe 16 und wird bei der Größenänderung tatsächlich um zwei multipliziert.Es würde immer noch funktionieren, wenn nicht eine Zweierpotenz, aber du würdest so viele Bits wie möglich für "Länge -1" wollen, um den Abstand zwischen den Buckets auszugleichen. – Bohemian