Just a few minutes back I answered a question asking about the "Maximum possible size of HashMap in Java". As I have always read, HashMap is a growable data-structure. It's size is only limited by the JVM memory size. Hence I thought that there is no hard limit to its size and answered accordingly. (The same is applicable to HashSet as well.)
But someone corrected me saying that since the size() method of HashMap returns an int, there is a limit on its size. A perfectly correct point. I just tried to test it on my local but failed, I need more than 8GB memory to insert more than 2,147,483,647 integers in the HashMap, which I don't have.
My questions were:
If someone is blessed with access to a machine with say 16GB memory, you can try it out practically. :)
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.
it's two's complement binary integer is 10000000-00000000-00000000-00000000. It says the maximum size to which hash-map can expand is 1,073,741,824 = 2^30.
Finally, the default initial capacity of the HashMap is 16. As the number of elements in the HashMap increases, the capacity is expanded. The load factor is the measure that decides when to increase the capacity of the Map. The default load factor is 75% of the capacity.
In Oracle JDK 8, HashMap resizes when the size is > threshold (capacity * load factor). With capacity of 16 and default load factor of 0.75 , resizing (to capacity of 32 ) takes place when the 13 th entry is put.
The underlying capacity of the array has to be a power of 2 (which is limited to 2^30) When this size is reached the load factor is effectively ignored and array stops growing.
At this point the rate of collisions increases.
Given the hashCode() only has 32-bits it wouldn't make sense to grow much big that this in any case.
/**
* 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);
}
When the size exceeds Integer.MAX_VALUE it overflows.
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);
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With