No argument constructor …

In Java is a good practice to initialize the initial capacity of collections and maps.

Many developers (me included) have the habit to declare a new Collection or Map using the no argument constructor, e.g.:

Map exampleMap = new HashMap();

With this instruction Java initializes a new HashMap object with the attribute loadFactor at 0.75 and the DEFAULT_INITIAL_CAPACITY at 16.

The HashMap stores internally his values in an array of HashMap$Node objects (at least until when the size doesn’t become too big).

The initialization doesn’t create yet the array, it will be instantiated only with the first insert in the map (e.g. using put), Java will create the internal array with something like: Node<K,V>[] tab = (Node<K,V>[])new Node[16].

… it will grow

Every time an entry is added into the Map, the HashMap instance checks that the number of values contained in the bucket array is not more than his capacity multiplied the load factor (default at 0.75). In our case : 16 (capacity) * 0.75 (load factor) = 12 (threshold).

What happens when the 13th value is inserted in the array? The number of entries in the array is more than the threshold and the HashMap instance calls the method: final Node<K,V>[] resize().

This method creates a new array of Node with a capacity of the current store (16) * 2: (Node<K,V>[])new Node[32]

The values of the current bucket array are ‘transferred’ in the new array, the new threshold is also multiplied * 2.

The table shows how the the size of the bucket array grows adding new entries.

The rehashing done in resize() requires computational power and should be avoided if possible.

# of inserts .put(K,V) resize() calls bucket array size Threshold
0 0 null 0
1 1 16 12
13 2 32 24
25 3 64 48
49 4 128 96
97 5 256 192
193 6 512 384
385 7 1 024 768
769 8 2 048 1 536
1 537 9 4 096 3 072
98 305 15 262 144 196 608

defining the initial size in the constructor

You have a defined number or entries or you know what should be the number of values that the map will contain, then it’s recommended to set thee ‘initial capacity’ accordingly.

Example you will have 100 entries and not one more? new HashMap(100) will generate a bucket array of only 100 nodes without the need of rehashing during the insert.

If the initial capacity is defined using the constructor the size of the threshold is calculated using the following algorithm:

/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

… the result is 128.

If your map won’t grow more than the initial size, there won’t be rehashing of your data.

This solution is optimal if you know the maximum size of the HashMap.

General tip from the code source

The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations.

If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

JDK version used for the tests

OpenJDK version 11.0.1