Demystifying HashMap: Internals of Hashing, Collisions, and Resizing

1. The Core Structure: Buckets and Nodes

At its heart, a HashMap is surprisingly simple: it's an array of "buckets". When you create a new HashMap(), Java allocates an array in memory with a default capacity of 16.

Each key-value pair you insert is wrapped in an object. Prior to Java 8, this was an Entry class. Since Java 8, it's called a Node. Each Node object holds four key pieces of information:

• The key's hash code (int hash)
• The key itself (final K key)
• The value (V value)
• A pointer to the next node in the same bucket (Node<K,V> next)

This next pointer is the key to collision handling—it allows HashMap to form a linked list within a single bucket.

For a concise written overview of these components, you can refer to the first section of the article "How HashMap Works Internally After Java 8?".

2. The put() Operation: Hashing and Collision Handling

When you call map.put(key, value), HashMap performs a sequence of operations to place your data in the correct bucket. This process is the key to understanding HashMap.

To see this process in action, let's watch a video that walks through it step-by-step.

Let's break down that process in detail, as you would in an interview.

Step 1: Calculate the Key's Hash
HashMap first gets the hash code from the key by calling key.hashCode(). However, it doesn't use this value directly. To protect against poorly implemented hashCode() functions and to ensure better distribution, HashMap applies its own internal hash() function:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

The expression (h = key.hashCode()) ^ (h >>> 16) is a clever trick. It performs a bitwise XOR between the original hash code and the same hash code right-shifted by 16 bits. This effectively mixes the higher-order bits with the lower-order bits, spreading out the hash values more evenly and reducing the chance of collisions.

Step 2: Calculate the Bucket Index
Next, HashMap must map this hash value to an index in its internal array. It does this with another efficient bitwise operation:
int index = (n - 1) & hash;
Here, n is the capacity of the array (e.g., 16). Because the capacity is always a power of two, (n-1) results in a bitmask (e.g., 15 is 00001111 in binary). The & operation is a very fast way to compute the remainder (like hash % n), ensuring the index is always within the array's bounds.

Step 3: Handle the Bucket
HashMap now has the target bucket index.

• If the bucket is empty: It creates a new Node and places it at that index. The operation is complete.

• If the bucket is NOT empty (a collision): The HashMap must check if it's adding a new key or updating an existing one. It traverses the linked list at that bucket, and for each Node it finds, it performs two checks:

  1. Does the new key's hash match the existing node's hash?
  2. If the hashes match, does key.equals(existingNode.key) return true?

  If both are true, it means the key already exists. HashMap updates the value in that node and the operation is done. If it reaches the end of the list without finding a match, it appends the new Node to the end of the linked list.

3. Java 8 Enhancement: Treeification

In older versions of Java, a large number of collisions in one bucket could degrade performance significantly. If many keys mapped to the same bucket, the linked list would become very long. Retrieving an element from this long list would take O(n) time, defeating the purpose of a HashMap.

Java 8 introduced a major optimization called treeification.

• If the number of nodes in a single bucket reaches a certain threshold (specifically, TREEIFY_THRESHOLD, which defaults to 8), the linked list is converted into a self-balancing Red-Black Tree.

This dramatically improves worst-case performance. Searching for an element in a balanced tree takes O(log n) time, which is a massive improvement over the O(n) of a long linked list.

This conversion only happens if the map's total capacity is also large enough (at least MIN_TREEIFY_CAPACITY, which is 64). If the map is still small, it will prioritize resizing the whole map over treeifying a single bucket.

4. Resizing: How a HashMap Grows

A HashMap can't just keep adding nodes to its buckets indefinitely. As the map fills up, the probability of collisions increases. To maintain its performance, the HashMap resizes itself.

Resizing is triggered based on two parameters:

• Capacity: The current length of the internal array (e.g., 16).
• Load Factor: A measure of how full the map is allowed to get before it's resized. The default is 0.75.

The threshold for resizing is calculated as capacity * loadFactor.
For a default HashMap, the threshold is 16 * 0.75 = 12. This means when you add the 13th element, the HashMap will trigger a resize.

The Resizing Process:

1. A new array is created with double the capacity of the old one (e.g., 16 -> 32).
2. All existing entries from the old array are iterated over and re-hashed into the new, larger array. Their bucket index is recalculated based on the new capacity.

This rehashing process is computationally expensive, which is why it's a good performance practice to initialize your HashMap with an appropriate capacity if you know roughly how many elements it will hold.

// Good practice if you expect ~1000 items
Map<String, User> userMap = new HashMap<>(1500); // Prevents multiple resizes

5. hashCode() and equals() in Action

To truly grasp when hashCode() and equals() are called, there's no substitute for seeing it live. The following video provides a brilliant coding demonstration that's perfect for interview preparation.

This demonstration makes it crystal clear:

• hashCode() is called on every put and get to find the bucket.
• equals() is only called when a collision occurs—that is, when HashMap finds an existing node in the target bucket with the same hash.

Conclusion

You have now deconstructed one of the most important data structures in the Java ecosystem. Understanding HashMap internals is a hallmark of a proficient Java developer and a common expectation in demanding technical interviews.

Key Takeaways:

• Structure: A HashMap is an array of buckets, where each bucket holds nodes in a linked list or a Red-Black Tree.
• Hashing: The put(key, value) operation calculates a bucket index using key.hashCode(), an internal hash() function, and a bitwise & operation with the array's capacity.
• Collisions: When multiple keys map to the same bucket, their nodes are stored together. The equals() method is used to differentiate them.
• Performance: For a well-distributed set of keys, operations are O(1) on average. In the worst-case scenario of many collisions, Java 8's treeification ensures O(log n) performance.
• Resizing: The map automatically doubles its capacity and rehashes all entries when its size exceeds the capacity * loadFactor threshold.

In our next lesson, we will build on this knowledge to compare and contrast HashMap, LinkedHashMap, TreeMap, and ConcurrentHashMap. We'll analyze their specific use cases, performance trade-offs, and how they differ in ordering and thread-safety.