Hard java coding

How do you implement your own HashMap?

The 30 second answer

I'd use an array of buckets, where each bucket is a linked list of nodes holding the key, its hash and the value. To find a bucket I mix the hash code's high bits into the low bits and mask with the array length, which is a power of two. Put either updates a matching key or adds a node. When size passes three quarters of the capacity, I double the array and rehash. Lookups are constant time on average.

The interviewer wants three things: buckets, collision handling and resizing. I keep the types concrete (String keys, int values) so the code stays short and the ideas stay visible.

Buckets. The map is an array of buckets. A key's bucket index comes from its hashCode(). Java's own HashMap first spreads the hash with h ^ (h >>> 16), so the high bits affect the index too. Then it masks with length - 1, which works because the table length is always a power of two.

Collisions. Two keys can land in the same bucket, so each bucket is a linked list. Lookups compare the stored hash first, which is cheap, and then call equals. This is why the hashCode and equals contract matters: equal objects must have equal hash codes, or get looks in the wrong bucket.

Resizing. When size passes capacity times the load factor (0.75 by default), I double the array and move every node to its new bucket. The HashMap Javadoc describes 0.75 as "a good tradeoff between time and space costs".

import java.util.Objects;

public class StringIntMap {
    private static final class Node {
        final String key;
        final int hash;
        int value;
        Node next;
        Node(String key, int hash, int value, Node next) {
            this.key = key; this.hash = hash; this.value = value; this.next = next;
        }
    }

    private Node[] table = new Node[16];
    private int size;

    private static int hash(String key) {
        int h = Objects.hashCode(key);
        return h ^ (h >>> 16);              // mix high bits into the low bits
    }

    private static int indexFor(int hash, int length) {
        return hash & (length - 1);         // length is a power of two
    }

    public Integer get(String key) {
        int h = hash(key);
        for (Node n = table[indexFor(h, table.length)]; n != null; n = n.next) {
            if (n.hash == h && Objects.equals(n.key, key)) return n.value;
        }
        return null;
    }

    public void put(String key, int value) {
        int h = hash(key);
        int i = indexFor(h, table.length);
        for (Node n = table[i]; n != null; n = n.next) {
            if (n.hash == h && Objects.equals(n.key, key)) { n.value = value; return; }
        }
        table[i] = new Node(key, h, value, table[i]);
        if (++size > table.length * 3 / 4) resize();   // load factor 0.75
    }

    public boolean remove(String key) {
        int h = hash(key);
        int i = indexFor(h, table.length);
        Node prev = null;
        for (Node n = table[i]; n != null; prev = n, n = n.next) {
            if (n.hash == h && Objects.equals(n.key, key)) {
                if (prev == null) table[i] = n.next; else prev.next = n.next;
                size--;
                return true;
            }
        }
        return false;
    }

    private void resize() {
        Node[] old = table;
        table = new Node[old.length * 2];
        for (Node head : old) {
            for (Node n = head; n != null; ) {
                Node next = n.next;
                int i = indexFor(n.hash, table.length);
                n.next = table[i];
                table[i] = n;
                n = next;
            }
        }
    }

    public int size() { return size; }
}
StringIntMap m = new StringIntMap();
m.put("Aa", 1);
m.put("BB", 2);                 // "Aa" and "BB" have the same hashCode
System.out.println(m.get("Aa") + " " + m.get("BB"));   // 1 2

Complexity. get, put and remove are O(1) on average, given a hash function that spreads keys well. A resize is O(n), but it happens rarely enough that put is still O(1) amortized.

Follow-ups to expect.

  • What does the real HashMap do differently? In the OpenJDK 21 source, the defaults are an initial capacity of 16 and a load factor of 0.75. A bucket with 8 or more nodes becomes a red-black tree (TREEIFY_THRESHOLD = 8), but only once the table has at least 64 buckets (MIN_TREEIFY_CAPACITY = 64). Below that, the map resizes instead. This caps the worst case for a crowded bucket at O(log n) instead of O(n).
  • Is it thread-safe? No. Two threads calling put at the same time can lose an update. For shared state I use ConcurrentHashMap.
  • What if a key is mutated after insertion? If its hash code changes, the node sits in the wrong bucket and get can't find it. Keys should be immutable.
Sources (3)
  1. HashMap Javadoc (Java 21)docs.oracle.com
  2. OpenJDK 21 source: HashMap.javagithub.com
  3. Object.hashCode and equals contract (Java 21)docs.oracle.com