Ridimensionamento della tabella degli array nell'implementazione di HashMap

Aug 20 2020

Questa è una domanda semplice, per coloro che conoscono l'implementazione interna di HashMap :)

La dimensione iniziale è di 16 secchi, il fattore di carico è 0,75. Significa che quando ottiene (guarda quella parola) 12, si ridimensiona a 32 bucket.

La mia domanda è: si ridimensiona da 16 a 32 bucket quando riceve 12 coppie chiave-valore o quando riceve 12 bucket "pieni"? Lo chiedo perché potrebbe accadere che da quei 16 bucket tutte le 12 coppie chiave-valore vengano inserite nello stesso bucket. In tal caso sarebbe strano ridimensionare poiché gli altri 15 sono completamente vuoti.

Grazie, qualsiasi opinione in merito sarebbe apprezzata :)

Risposte

2 ThRnk Aug 20 2020 at 20:07

Come accennato in questo collegamento .

Rappresenta che la dodicesima coppia chiave-valore di hashmap manterrà la sua dimensione a 16. Non appena il 13 ° elemento (coppia chiave-valore) entrerà nella hashmap, aumenterà la sua dimensione dal valore predefinito 2 ^ 4 = 16 bucket a 2 ^ 5 = 32 secchi.

Indipendentemente da dove è stata inserita ogni chiave, quando il prodotto del fattore di carico e della capacità di corrente supera, la tabella verrà ridimensionata.

L'HashMap non si preoccupa di quanti bucket sono stati utilizzati fino a quando il fattore di carico non è stato raggiunto, sa che la probabilità di avere collisioni sta diventando troppo grande e la mappa dovrebbe essere ridimensionata. Anche se sono già avvenute molte collisioni.

2 AndrewBlagij Aug 20 2020 at 20:03

Da 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.

Quindi, HashMap si ridimensiona quando ha 12 coppie chiave-valore. Non è strano, perché dopo aver ridimensionato le voci cambierà il loro bucket.