java HashMap Expansion Detailed Explanation and Example Code

HashMap Expansion

Preface:

HashMap's size is greater than or equal to(Capacity*Load Factor) will trigger the expansion operation, which is a costly operation.

Why do we need to expand?63;HashMap's default capacity is16, as more elements are added to the HashMap, the probability of hash conflicts is higher, and the corresponding list of each bucket will be longer,

This will affect query performance because each time it needs to traverse the list, compare the objects for equality, until the element is found.

To improve query performance, only expansion can be performed to reduce hash conflicts and make the distribution of element keys as even as possible.

Expansion Points

The default load factor is 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

The default capacity is16

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // =16

HashMap provides a constructor parameter that can specify the capacity and load factor when creating it.

 public HashMap(int initialCapacity, float loadFactor)

By default, once the size of HashMap is greater than or equal to16*0.75=12In other words,

An expansion will be performed when there is at least one element in each Entry (or bucket).

 if ((size >= threshold) && (null != table[bucketIndex])) {
      resize(2 * table.length);
      hash = (null != key) ? hash(key) : 0;
      bucketIndex = indexFor(hash, table.length);
}

The container capacity doubles when resizing

 resize(2 * table.length);

When resizing, the array index of the elements needs to be recalculated

1、allocate a new Entry array
2、recalculate the new index of the original element in the new array(Resource-intensive)

Thank you for reading, I hope it can help everyone, thank you for your support of this site!