HashMap Internal Working Java | Fresher Interview

Direct Answer

A HashMap stores entries in an array of buckets. It spreads the key's hashCode() and uses the table size to select a bucket. Collisions begin as a linked list. In typical Java 8+ implementations, a bin can become a red-black tree near 8 entries only when the table has at least 64 buckets; otherwise the table grows. Average get and put are O(1). Tree bins improve many severe collisions, but pathological equal-hash keys can still require a broader search.

Deep Dive & Architecture

A Java HashMap uses a power-of-two bucket array. When a key is inserted, Java gets its hashCode(), mixes the high and low bits, and uses (capacity - 1) & hash to choose a bucket. This calculation is fast, but different keys can still land in the same bucket.

Inside a bucket, HashMap checks both the stored hash and key equality. Two keys with the same hash remain separate when equals() returns false; equal keys update the existing value. This is why equal keys must return the same hash code.

Small example

With capacity 16, integer keys 1 and 17 both have lower four bits equal to 0001, so they initially share bucket 1. A lookup goes to that bucket and compares keys until it finds the requested one.

The default load factor is 0.75. Once the number of entries passes the threshold, the table grows and entries are redistributed. Heavy collisions begin as a linked list. In Java 8+, a sufficiently large bin can become a red-black tree; treeification normally requires at least eight entries in the bin and a table capacity of at least 64, otherwise HashMap prefers resizing.

Well-distributed hashes give average O(1) get and put. A tree bin limits a heavily collided bucket to O(log m), where m is that bucket's size.

Code Example

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);     // hashCode("apple") -> bucket index
map.put("apple", 2);     // same key: equals() true -> overwrites to 2
System.out.println(map.get("apple"));   // 2

// Custom key MUST override hashCode AND equals or lookups fail:
record Point(int x, int y) {}        // record auto-generates both
Map<Point, String> grid = new HashMap<>();
grid.put(new Point(1, 2), "A");
System.out.println(grid.get(new Point(1, 2)));  // "A" - found

A new object with the same fields finds the entry only because hashCode/equals agree.

Common Mistakes & Pitfalls

• Calling HashMap always O(1): O(1) is the expected average with useful hash distribution.
• Claiming treeification makes every worst case O(log n): tree bins help, but pathological indistinguishable keys can still require more work.
• Ignoring the capacity condition: a crowded bin in a small table normally triggers resize before treeification.
• Mutable keys: changing fields used by equals or hashCode after insertion can make an entry unreachable.
• Assuming order: HashMap does not promise iteration order.