What happens when HashMap or HashSet maximum capacity is reached?

Question

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:

• What happens when we try to insert 2,147,483,647 + 1 element in the HashMap/HashSet?
• Is there an error thrown?
• If yes, which error? If not what happens to the HashMap/HashSet, its already existing elements and the new element?

If someone is blessed with access to a machine with say 16GB memory, you can try it out practically. :)

Solution

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

Comments

[Bhushan]

Can you explain why it is limited to 2^30, I mean where does 30 come from? And why it cannot become 31, 32...?

[Vishy]

Arrays are limited to a size to a signed 32-bit number. This is a historical restriction which is hard to fix to allow signed long sizes unfortunately. The maximum signed int value is 2^31-1. However the size of the array has to be a power of two (due to the way HashMap works) and this is one too few, so the largest power 2 it can be is 2^30. Given hashCode has only 2^32 possible values, having much more than this is rather pointless in any case. ;)

[Vishy]

I work with larger collections including hash maps and use a 64-bit size/length and 64-bit hashCode for these reasons.

[Bhushan]

so you mean you can store more than 2,147,483,647 items in the hashmap? if yes, how do you do that? i would like to know.

[Vishy]

You can store values in a HashMap, but the size will be wrong. However what I use is a map which uses a hash, or a hash map in the generic sense. The problem you have with such a hash map is the shear size of it. Say you want to store 256 bytes for the key, the value and any over head. That's 512 GB for a single collection, more than the size of your memory and possible more than the free space of one drive. (Using SSDs can be up to 1000x faster than using a HDD for random access)

[Vishy]

To do this I use memory mapped byte buffers. Many of them, because unfortunately they suffer from the same int size limit that arrays do. If you want to use powers of two for sizes, you have the same 2^30 limit for each memory mapping.

[Geek]

@PeterLawrey "This method is called automatically when the * number of keys in this map reaches its threshold." Who decides when the number of keys reaches threshold and what is the calculation for threshold ?

[Vishy]

@Geek the threshold is the "load factor" passed in the constructor * the capacity. See the last line of resize()

[Geek]

@PeterLawrey +1 for the folow up.