javaHashMap expansion details and example code

  • 2020-06-07 04:36:12
  • OfStack

HashMap capacity


When size of HashMap is greater than or equal to (capacity * load factor), it will trigger the capacity enlargement operation, which is a costly operation.

Why expand the capacity? The default capacity of HashMap is 16. As elements are added to HashMap, the probability of hash conflicts is higher and the linked list for each bucket is longer.

This affects the performance of the query because each time the linked list is traversed, the object is compared for equality,1 until the element is found.

In order to improve query performance, only the capacity can be enlarged, hash conflicts can be reduced, and the key of elements can be distributed as evenly as possible.

Expand the basic points

The default value of the load factor is 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

The default value for capacity is 16

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //  Is equal to the 16

HashMap provides a construction parameter that specifies the capacity and load factor at creation time.

 public HashMap(int initialCapacity, float loadFactor)

By default, if size1 of HashMap is greater than or equal to 16*0.75=12,

Each Entry(or bucket) expands when it has at least one element in it.

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

When you expand, you double the capacity of the container

 resize(2 * table.length);

To enlarge, you need to recalculate the index of the array

1. Reallocate a new Entry array
2. Recalculate the index of the original element in the new array (resource-consuming)

Thank you for reading, I hope to help you, thank you for your support to this site!

Related articles: