java - example - hashset vs hashmap

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

Question

Hace 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 ampliable. Su tamaño solo está limitado por el tamaño de la memoria JVM. Por lo tanto, pensé que no hay un límite duro para su tamaño y respondí en consecuencia. (Lo mismo se aplica a HashSet también.)

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

Mis preguntas fueron:

• ¿Qué sucede cuando intentamos insertar 2.147.483.647 + 1 elemento en el HashMap / HashSet?
• ¿Hay un error lanzado?
• Si es así, ¿qué error? Si no, ¿qué sucede con el HashMap / HashSet, sus elementos ya existentes y el nuevo elemento?

Si alguien ha sido bendecido con el acceso a una máquina con, por ejemplo, 16 GB de memoria, puede probarla prácticamente. :)

Answer 1

La capacidad subyacente de la matriz debe ser una potencia de 2 (que se limita 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 aumenta la tasa de colisiones.

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