Skip to main content

Selected Questions

🧠 How HashMap Works Internally in Java​

The HashMap in Java is one of the most widely used data structures for storing key-value pairs. While its API is simple to use, understanding how it works internally can significantly help when dealing with performance-critical applications.

Initial Structure​

When we create a new HashMap in Java, for example:

Map<String, Object> map = new HashMap<>();

The JVM internally allocates:

  • Initial capacity of 16 buckets (i.e., array size = 16).

  • Load factor of 0.75, which defines the threshold for resizing the map (i.e., 16 × 0.75 = 12, so resizing occurs after 12 entries).

Each bucket can hold multiple entries and is implemented as a linked list (or a balanced tree if it gets too long in Java 8+).

Inserting an Entry: put(key, value)​

When you use the put method:

hashMap.put("key", value);

Here’s what happens step by step:

Step: 1. Hash Code Calculation​

The JVM calculates the hash code of the key:

int hashCode = key.hashCode();

This hash code is an integer and may not directly correspond to an index in the bucket array.

Step: 2. Bucket Index Calculation​

The JVM then computes the index of the bucket where the entry should go using the following formula:

index = hashCode & (arrayLength - 1)

This ensures that the index is within bounds (i.e., between 0 and length-1), and it helps distribute the entries uniformly.

Step: 3. Handling the Entry in the Bucket​

Now that the index is determined, the JVM checks the corresponding bucket.

✅ No Hash Collision​

If the bucket is empty, the key-value pair is inserted as the first node in a singly linked list.

⚠️ Hash Collision Occurs​

If another entry is already present in the bucket (i.e., hash collision):

  • The JVM traverses the linked list in that bucket.

  • It compares the existing keys using the equals() method:

    key.equals(existingKey)
🔁 If key exists (duplicate key):​

The value of the existing node is replaced with the new value.

If key does not exist:​

A new node is appended to the end of the linked list in the bucket.

Treeification (Java 8+)​

If the number of entries in a bucket exceeds a certain threshold (usually 8), the linked list is converted into a Red-Black Tree to improve performance from O(n) to O(log n).

Load Factor and Resizing​

Once the number of stored entries exceeds the capacity × loadFactor threshold (e.g., 12 for capacity 16 with a load factor of 0.75):

  • The HashMap is resized to double its previous capacity (e.g., 16 → 32).
  • All existing entries are rehashed and redistributed into the new buckets.

Summary:

StepDescription
1.Compute key’s hashCode()
2.Derive bucket index: hash & (length - 1)
3.Insert into bucket: as a node in a list/tree
4.On collision: check equals(), replace or append
5.Resize if load factor exceeds threshold

Representation of How HashMap.put Works Internally in Java​

Conclusion​

The internal working of HashMap.put() in Java reveals how efficiently Java handles key-value storage through hashing, collision resolution, and dynamic resizing. Understanding these steps — from calculating the hash and determining the bucket index to managing collisions and converting to trees — helps developers write more optimized and predictable code.

Whether you're preparing for interviews or aiming to improve performance in real-world applications, a deep knowledge of HashMap internals equips you with the right foundation to choose and use data structures wisely in Java.