How Does HashMap Work Internally in Java?

Expected Interview Answer

Step-by-Step Explanation

1. Step 1

   Compute the hash

   HashMap calls the key's hashCode and spreads the bits with an internal hash function to reduce collisions.

2. Step 2

   Find the bucket

   It maps the spread hash to an index using (n - 1) & hash, where n is the table length (a power of two).

3. Step 3

   Handle collisions

   Entries landing in the same bucket form a chain; put uses equals to detect and overwrite a matching key.

4. Step 4

   Treeify long buckets

   Since Java 8, a bucket with more than 8 nodes (in a table of at least 64) becomes a red-black tree for O(log n) lookups.

5. Step 5

   Resize when full

   When size exceeds capacity times load factor (0.75), capacity doubles and entries are rehashed into the larger table.

Code Example

import java.util.*;

public class HashMapInternals {
    static class Point {
        final int x, y;
        Point(int x, int y) { this.x = x; this.y = y; }

        // Both must be overridden together for HashMap to work correctly
        @Override public int hashCode() { return Objects.hash(x, y); }

        @Override public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Point)) return false;
            Point p = (Point) o;
            return x == p.x && y == p.y;
        }
    }

    public static void main(String[] args) {
        Map<Point, String> map = new HashMap<>();
        map.put(new Point(1, 2), "A");

        // Same field values -> same hashCode and equals -> found
        System.out.println(map.get(new Point(1, 2))); // A
        System.out.println(map.containsKey(new Point(3, 4))); // false
    }
}

Follow-up Questions

• What happens when two keys have the same hashCode but are not equal?
• How and when does a HashMap resize?
• What changed in HashMap between Java 7 and Java 8?
• Why must you override equals and hashCode together?
• How does HashMap differ from ConcurrentHashMap and Hashtable?