¿Qué sucede cuando se alcanza la capacidad máxima de HashMap o HashSet?

Question

Hace solo unos minutos respondí una pregunta sobre el "Tamaño máximo posible de HashMap en Java". Como siempre he leído, HashMap es una estructura de datos de gran tamaño. Su tamaño solo está limitado por el tamaño de la memoria JVM. Por lo tanto, pensé que no existe un límite estricto para su tamaño y se respondió en consecuencia. (Lo mismo es aplicable a HashSet también.)

Pero alguien me corrigió diciendo que desde la size() método devuelve un HashMap int, no es un límite en su tamaño. Un punto perfectamente correcto. Solo traté de probarlo en mi servidor local pero fallaba, necesito más de 8GB de memoria para insertar más de 2,147,483,647 enteros en el HashMap, que no tengo.

Mis preguntas fueron:

• Lo que sucede cuando tratamos de insertar 2147483647 + 1 elemento de la HashMap/HashSet?
• ¿Se ha producido un error?
• En caso afirmativo, ¿qué error? Si no es así, ¿qué sucede con el HashMap/HashSet, ya que es elementos existentes y el nuevo elemento?

Si alguien tiene acceso a una máquina con una memoria de 16 GB, puede probarlo prácticamente. :)

Answer 1

La capacidad subyacente de la matriz debe ser una potencia de 2 (que está limitada a 2^30) Cuando se alcanza este tamaño, el factor de carga se ignora de manera efectiva y la matriz deja de crecer.

En este punto, la tasa de colisiones aumenta.

Dado que hashCode() solo tiene 32 bits, no tendría sentido crecer mucho más que esto en cualquier 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); 
} 

Cuando el tamaño excede Integer.MAX_VALUE se desborda.

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); 
}