Ändern der Größe der Array-Tabelle in der HashMap-Implementierung

Question

Dies ist eine einfache Frage für diejenigen, die die interne Implementierung von HashMap kennen :)

Die anfängliche Größe beträgt 16 Eimer, der Auslastungsfaktor beträgt 0,75. Das heißt, wenn es 12 erhält (sehen Sie sich dieses Wort an), wird die Größe auf 32 Eimer geändert.

Meine Frage ist, ob die Größe von 16 auf 32 Buckets geändert wird, wenn 12 Schlüssel-Wert-Paare oder 12 "gefüllte" Buckets erhalten werden. Ich frage das, weil es passieren kann, dass aus diesen 16 Buckets alle 12 Schlüssel-Wert-Paare in denselben Bucket eingefügt werden. In diesem Fall wäre es seltsam, die Größe zu ändern, da die anderen 15 völlig leer sind.

Danke, jede Meinung dazu wäre willkommen :)

Answer 1

Wie in diesem Link erwähnt .

Es stellt dar, dass das 12. Schlüssel-Wert-Paar der Hashmap seine Größe auf 16 behält. Sobald das 13. Element (Schlüssel-Wert-Paar) in die Hashmap aufgenommen wird, erhöht es seine Größe von Standard- 2 ^ 4 = 16 Buckets auf 2 ^ 5 = 32 Eimer.

Unabhängig davon, wo jeder Schlüssel eingefügt wurde, wird die Größe der Tabelle geändert, wenn das Produkt aus Lastfaktor und aktueller Kapazität überschritten wird.

Der HashMap ist es egal, wie viele Buckets verwendet wurden, bis der Lastfaktor erreicht wurde. Sie weiß, dass die Wahrscheinlichkeit von Kollisionen zu groß wird, und die Größe der Karte sollte geändert werden. Obwohl schon viele Kollisionen passiert sind.

Answer 2

Von JavaDoc https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#put-K-V-

When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

Daher ändert HashMap die Größe, wenn es 12 Schlüssel-Wert-Paare hat. Es ist nicht seltsam, denn nach dem Ändern der Größe ändern Einträge ihren Bucket.