How does HashMap work internally in Java?

A HashMap is an array of buckets. When you call put(key, value):

1. Java calls key.hashCode() and spreads the bits of the hash.
2. The bucket index is found from the hash and the array length (the default size is 16).
3. If the bucket is empty, the entry is stored there. If not, Java walks the bucket and uses equals() to find the same key. If it finds one, the value is replaced, if not the new entry is added.
4. When the number of entries goes above capacity x load factor (0.75), the array is doubled and the entries are moved (rehashing).
5. When one bucket gets long (8 or more entries, and the table has 64 or more buckets), the linked list becomes a balanced tree, so the search stays fast.

So the keys need a good hashCode() and a matching equals(). Even with a very bad hash code the map still gives right answers, only slow:

import java.util.HashMap;
import java.util.Map;

public class Main {
    static class BadKey {
        final int id;
        BadKey(int id) { this.id = id; }
        @Override public int hashCode() { return 1; }                     // all keys in one bucket
        @Override public boolean equals(Object o) { return o instanceof BadKey b && b.id == id; }
    }

    public static void main(String[] args) {
        Map<BadKey, String> map = new HashMap<>();
        for (int i = 0; i < 1000; i++) {
            map.put(new BadKey(i), "value" + i);
        }
        System.out.println(map.size());
        System.out.println(map.get(new BadKey(777)));
    }
}

See Java HashMap.

• Previous Interview Question
• Next Interview Question

---

Tutorials
No Content Found.

Exercises & Assignments
No Content Found.

Interview Questions & Answers
No Content Found.