Einige Zweifel in Bezug auf HashMap

Question

HashMap ist in einer sehr einfachen Art und Weise implementiert, aber es braucht ein Genie, um zu verstehen, wie es implementiert ist. Also, ich habe über HashMap in Java-Dokumentation gelesen. Ich habe ein paar kleine Fragen zu HashMap:

1. Ich weiß, Standardkapazität von HashMap ist 16. In Java-docs sie Die Standardanfangskapazität gegeben haben - muss eine Potenz von zwei sein.. Irgendein bestimmter Grund dahinter?
2. Ich weiß ein wenig, wie HashMap funktioniert auf der Grundlage von HashCode, Bucket und LinkedList, wenn ich nicht falsch liege. Dann wird die Größe von HashMap erhöht. Ich meine, wie Buckets Größe und LinkedList Größe verwaltet werden.
3. Dies könnte eine dumme Frage sein. Wenn wir ein neues Element in HashMap hinzufügen, greift es auf Grundlage von HashCode direkt auf diesen bestimmten Bucket zu, ohne wie in LinkedList zu reisen. Habe ich recht? Und anderes ist, dass es Element am Kopf, nicht an den Schwänzen hinzufügt. Was ist der Grund dafür? Ist ein neues Element am Kopf von LinkedList vorhanden, das im Inneren des Bechers vorhanden ist, um eine Überquerung des Schwanzes zu vermeiden. Ist mein Denken richtig?

Answer 1

1. Mit Zweierpotenzen vereinfacht die Implementierung und verbessert seine Leistung.
   Zum Beispiel einen Eimer aus einem Hash-Code zu finden, es Hash & (SIZE -1) statt abs (hash)% SIZE

2. Bis Sie wissen, wie HashMap funktioniert genau werden Sie nicht in der Lage sein, diese Frage beantworten kann. Wenn die Größe der Karte einen gegebenen Schwellenwert überschreitet, der durch den Lastfaktor, z.B. Wenn der Auslastungsfaktor 0,75 ist, wird die Karte neu skaliert, sobald sie 75% gefüllt hat. Ähnlich wie andere Auflistungsklassen wie ArrayList, Java HashMap Größe neu selbst durch Erstellen eines neuen Buckets Array der Größe zweimal der vorherigen Größe HashMap, und dann beginnen, jedes alte Element in diesem neuen Bucket-Array setzen. Dieser Prozess wird als "rehashing" bezeichnet, da er auch eine Hash-Funktion anwendet, um einen neuen Bucket-Speicherort zu finden.

3. Wir speichern jedes neue Element an der Spitze der verketteten Liste, um das Verrunden der Enden zu vermeiden und somit bei der Größenänderung die gesamte Folge von Objekten in verketteten Listen umzukehren, während denen die Wahrscheinlichkeit von Endlosschleifen besteht.

Lesen Sie mehr hier:

• http://java.dzone.com/articles/hashmap-internal
• http://javarevisited.blogspot.in/2011/02/how-hashmap-works-in-java.html

Answer 2

1. Ich würde davon ausgehen, dass die Leistung von zwei Anforderung ist es Kommissionierschächte zu beschleunigen. Wenn Sie 16 Buckets und einen Index von 578123 oder etwas haben, können Sie ein einfaches UND verwenden, um einen Bucket auszuwählen, anstatt 578123 Mod 16 zu berechnen, was langsamer ist.

2. HashMap hat einen Ladefaktor, der standardmäßig 0,75 ist. Wenn die Anzahl der Objekte> Anzahl der Buckets * Ladefaktor ist, wird die Kapazität der HashMap erhöht, um die Leistung zu erhalten. Ich würde annehmen, dass es einfach die Menge der Eimer verdoppelt und alle Elemente neu zuordnet.

3. Entschuldigung, ich bin mir nicht sicher, ob ich diese Frage richtig verstehe.

Answer 3

1. Der Grund für die Herstellung der Kapazität einer Potenz von 2 ist (glaube ich) vor allem um den Code zu vereinfachen. Es gibt einen kleinen Leistungsvorteil, aber er ist nahezu vernachlässigbar.

2. Es geht so:

   • A HashMap erweitert wird, wenn Sie einen neuen Eintrag hinzuzufügen, zu versuchen. Es kommt (grob gesprochen) vor, wenn map.size() * load_factor > array.length. (Genaue Details finden Sie im Code.)

   • Wenn eine HashMap erweitert wird, ist das Array doppelt so groß. Es gibt eine harte Grenze ... durch die Größe von Arrays in Java auferlegt. Danach wird das Array der HasMap nicht erweitert. (Stattdessen erhalten Sie einfach immer längere Hash-Ketten ...)

   • Es wird nichts unternommen, um die Längen der einzelnen Hash-Ketten zu verwalten. Wenn die HashMap erweitert wird, werden stattdessen die Einträge in jeder alten Kette in die entsprechenden Ketten in der expandierten Tabelle verschoben. (Zumindest in der letzten Implementierungen jede Kette Knoten hält einen Cache gespeicherten Hash-Wert für den Eintrag, so gibt es nicht erforderlich, die Hash-Funktionen während der Tabelle Expansion neu zu bewerten.)

3. Grundsätzlich ja und ja . Neue Einträge werden am Anfang jeder Hash-Kette hinzugefügt, da dies die effizienteste (zeit- und raumweise) dafür ist. Da die Reihenfolge der Elemente in einer Hash-Kette nichts bedeutet, hat es keinen Sinn, neue Einträge am Ende der Kette einzufügen. Dies bedeutet auch, dass in einer typischen HashMap-Implementierung das Erweitern der Tabelle die Reihenfolge der Hash-Ketteneinträge umkehrt.

---

Beachten Sie, dass das tatsächliche Verhalten und tatsächliche Implementierungsdetails für HashMap für verschiedene Versionen von Java unterscheiden. Der einzige Weg, um sicher zu sein, ist, den Quellcode für die Version von Java zu lesen, die Sie verwenden.