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 2Complexity. 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
putat the same time can lose an update. For shared state I useConcurrentHashMap. - What if a key is mutated after insertion? If its hash code changes, the node sits in the wrong bucket and
getcan't find it. Keys should be immutable.
Sources (3)
- HashMap Javadoc (Java 21)docs.oracle.com
- OpenJDK 21 source: HashMap.javagithub.com
- Object.hashCode and equals contract (Java 21)docs.oracle.com