Cosa succede quando viene raggiunta la capacità massima di HashMap o HashSet?

Question

Solo pochi minuti indietro ho risposto a una domanda per chiedere "Dimensioni massime possibili di HashMap in Java". Come ho sempre letto, HashMap è una struttura dati espandibile. La sua dimensione è limitata solo dalla dimensione della memoria JVM. Quindi ho pensato che non ci fosse un limite rigido alle sue dimensioni e risposto di conseguenza. (Lo stesso vale per HashSet pure.)

Ma qualcuno mi ha corretto dicendo che dal momento che il size() metodo restituisce un HashMap int, non v'è un limite alla sua dimensione. Un punto perfettamente corretto. Ho appena provato a testarlo sul mio locale ma non è riuscito, ho bisogno di più di 8 GB di memoria per inserire più di 2.147.483.647 numeri interi in HashMap, che non ho.

Le mie domande erano:

• Cosa succede quando cerchiamo di inserire 2,147,483,647 + 1 elemento nel HashMap/HashSet?
• C'è un errore generato?
• Se sì, quale errore? In caso contrario, cosa succede a HashMap/HashSet, i suoi elementi già esistenti e il nuovo elemento?

Se qualcuno ha la fortuna di accedere a una macchina con diciamo 16 GB di memoria, è possibile provarlo praticamente. :)

Answer 1

La capacità sottostante dell'array deve essere una potenza di 2 (limitata a 2^30). Quando viene raggiunta questa dimensione, il fattore di carico viene effettivamente ignorato e l'array smette di crescere.

A questo punto la velocità di collisioni aumenta.

Dato che hashCode() ha solo 32 bit, non avrebbe senso crescere molto in ogni caso.

/** 
* Rehashes the contents of this map into a new array with a 
* larger capacity. This method is called automatically when the 
* number of keys in this map reaches its threshold. 
* 
* If current capacity is MAXIMUM_CAPACITY, this method does not 
* resize the map, but sets threshold to Integer.MAX_VALUE. 
* This has the effect of preventing future calls. 
* 
* @param newCapacity the new capacity, MUST be a power of two; 
*  must be greater than current capacity unless current 
*  capacity is MAXIMUM_CAPACITY (in which case value 
*  is irrelevant). 
*/ 
void resize(int newCapacity) { 
    Entry[] oldTable = table; 
    int oldCapacity = oldTable.length; 
    if (oldCapacity == MAXIMUM_CAPACITY) { 
     threshold = Integer.MAX_VALUE; 
     return; 
    } 

    Entry[] newTable = new Entry[newCapacity]; 
    transfer(newTable); 
    table = newTable; 
    threshold = (int)(newCapacity * loadFactor); 
} 

Quando la dimensione supera il valore Integer.MAX_VALUE, viene espulsa.

void addEntry(int hash, K key, V value, int bucketIndex) { 
Entry<K,V> e = table[bucketIndex]; 
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
    if (size++ >= threshold) 
     resize(2 * table.length); 
}