How a HashMap works under the hood

The Interview Question

Interviewer: "You use HashMaps constantly in your code. Walk me through what actually happens when you call map.put(key, value) and then map.get(key). How does a HashMap find the right value in O(1) time, and what happens when two keys hash to the same bucket?"

This question tests whether you understand the data structure you use most often. The interviewer wants to hear about hash functions, bucket arrays, collision resolution, and resizing. A senior candidate should also mention treeification (Java 8+), load factors, and thread safety.

What to Clarify Before Answering

You: "Before I walk through the internals, a few scoping questions..."

• "Are we discussing the general concept, or a specific implementation like Java's HashMap or Python's dict?"
• "Should I cover thread safety and concurrent variants, or just the single-threaded case?"
• "Do you want me to compare separate chaining vs open addressing, or focus on one approach?"
• "Should I include the resizing mechanism and amortized analysis?"

Why this matters: HashMap implementations vary significantly across languages. Java uses separate chaining with treeification. Python uses open addressing with perturbation. C++ unordered_map uses chaining with linked lists. Scoping the answer lets you go deep on the right variant.

The 30-Second Answer

A HashMap stores key-value pairs in a bucket array. When you insert a key, the HashMap computes a hash code (an integer derived from the key), then maps it to a bucket index using modular arithmetic (hash % arrayLength). The value is stored in that bucket. On lookup, it repeats the same computation to jump directly to the correct bucket in O(1) time. When two keys map to the same bucket (a collision), the HashMap resolves it using either separate chaining (a linked list or tree at each bucket) or open addressing (probing to find the next empty slot). When the ratio of entries to buckets (the load factor) exceeds a threshold (typically 0.75), the HashMap resizes by doubling the array and rehashing all entries, keeping the amortized cost of insertion at O(1).

The Architecture Overview

The diagram shows the full path of a HashMap operation. Every put, get, or remove starts with computing a hash, mapping it to a bucket index, and then handling whatever is in that bucket. If the bucket is empty, the operation is trivial. If it contains existing entries, we need collision resolution.

I will now walk through each layer in detail, starting with the hash function itself.

Hash Function Internals

The hash function is the foundation of the entire data structure. A good hash function distributes keys uniformly across buckets. A bad one clusters keys into a few buckets, degrading O(1) lookups to O(n).

What hashCode() Actually Computes

In Java, every object has a hashCode() method that returns a 32-bit integer. The default implementation uses the object's memory address, but most classes override it:

// String.hashCode() in Java
int hashCode() {
  int h = 0;
  for (char c : value) {
    h = 31 * h + c;    // Polynomial rolling hash
  }                      // "abc" -> 31^2*97 + 31*98 + 99 = 96354
  return h;
}

The multiplier 31 is chosen because:

• It is an odd prime, reducing collision probability
• 31 * h can be optimized by the JIT compiler to (h << 5) - h (a shift and subtract), which is faster than multiplication

The Spread Function (Secondary Hash)

Raw hash codes often have patterns in their low bits (especially for sequential integers or short strings). Java's HashMap applies a spread function to mix the high bits into the low bits:

// Java HashMap's spread function
static int hash(Object key) {
  int h = key.hashCode();
  return h ^ (h >>> 16);    // XOR high 16 bits into low 16 bits
}

This is critical because the bucket index uses only the low bits (hash & (capacity - 1) when capacity is a power of 2). Without the spread, keys whose hash codes differ only in high bits would all land in the same bucket.

From Hash to Bucket Index

The bucket index is computed using bitwise AND instead of modulo:

int index = hash & (capacity - 1);   // Equivalent to hash % capacity
                                      // Only works when capacity is power of 2

This is why HashMap always uses power-of-2 capacities (16, 32, 64, ...). Bitwise AND is a single CPU instruction, while modulo requires division. For billions of lookups, this matters.

Collision Resolution: Separate Chaining

When two different keys produce the same bucket index, we have a collision. Java's HashMap (and most implementations) uses separate chaining: each bucket holds a linked list of entries.

The Linked List Phase

When a collision occurs:

1. The new entry is added to the head of the linked list at that bucket
2. On lookup, the HashMap walks the list, comparing keys using .equals() for each node
3. On deletion, the HashMap removes the matching node from the list

// Simplified Node structure in Java HashMap
class Node<K,V> {
  final int hash;       // Cached hash (avoid recomputing)
  final K key;
  V value;
  Node<K,V> next;      // Linked list pointer
}

// Lookup within a bucket
Node<K,V> getNode(int hash, Object key) {
  Node<K,V> node = table[hash & (capacity - 1)];
  while (node != null) {
    if (node.hash == hash &&                    // Fast hash comparison first
        (node.key == key || key.equals(node.key))) {  // Then full equality
      return node;
    }
    node = node.next;
  }
  return null;
}

Notice the optimization: the HashMap compares hash values first (a cheap integer comparison) before calling .equals() (which may be expensive for complex objects). This short-circuits most comparisons in a chain.

Treeification: When Lists Become Trees

In Java 8+, when a single bucket's linked list grows to 8 or more entries, the HashMap converts it to a red-black tree. This changes worst-case lookup within a bucket from O(n) to O(log n).

The untreeify threshold is 6 (not 8) to prevent thrashing between list and tree modes. This two-threshold approach is a classic hysteresis pattern.

For treeification to work, keys must implement Comparable. If they do not, the tree falls back to comparing hash codes and uses identity as a tiebreaker. This is why implementing Comparable on your key objects improves HashMap performance in edge cases.

Collision Resolution: Open Addressing

The alternative to separate chaining is open addressing, where all entries live directly in the bucket array. When a collision occurs, the HashMap probes forward through the array to find the next empty slot. Python's dict uses this approach.

Linear Probing

The simplest form: if bucket i is occupied, try i+1, then i+2, and so on.

// Linear probing insert
void put(K key, V value) {
  int index = hash(key) & (capacity - 1);
  while (table[index] != null) {
    if (table[index].key.equals(key)) {
      table[index].value = value;   // Update existing
      return;
    }
    index = (index + 1) & (capacity - 1);  // Wrap around
  }
  table[index] = new Entry(key, value);
  size++;
}

Linear probing has excellent cache locality because it accesses consecutive memory addresses (the CPU prefetcher loves this). But it suffers from primary clustering: long runs of occupied slots form clusters that grow larger over time, increasing probe sequences.

Quadratic Probing and Double Hashing

To reduce clustering, quadratic probing uses offsets of 1, 4, 9, 16... instead of 1, 2, 3, 4:

index = (original + i * i) & (capacity - 1)    // Quadratic

Double hashing uses a second hash function to choose the step size:

step = 1 + (hash2(key) % (capacity - 1))       // Second hash
index = (original + i * step) & (capacity - 1)  // Double hash

Double hashing eliminates clustering almost entirely but loses cache locality because probes jump to non-adjacent memory.

Deletion in Open Addressing: The Tombstone Problem

Deletion in open addressing is trickier than in chaining. You cannot simply empty a slot, because subsequent lookups might stop probing too early (thinking they hit an empty slot when the entry they want is further along the probe chain).

The solution is tombstones (also called sentinel markers). When you delete an entry, you replace it with a special DELETED marker. During lookup, DELETED slots are treated as occupied (keep probing). During insertion, DELETED slots can be reused.

// Deletion with tombstones
void remove(K key) {
  int index = hash(key) & (capacity - 1);
  while (table[index] != null) {
    if (table[index] != DELETED && table[index].key.equals(key)) {
      table[index] = DELETED;       // Tombstone marker
      size--;
      return;
    }
    index = (index + 1) & (capacity - 1);
  }
}

The downside: tombstones accumulate over time. A map with many insertions and deletions fills up with DELETED markers that slow down probing without contributing to the load factor. Some implementations trigger a full rehash when tombstone density gets too high, compacting the table.

Robin Hood Hashing

Robin Hood hashing is my favorite variant. On insertion, if the new key has traveled farther from its home bucket than the existing key at the current slot, they swap. This ensures all keys are roughly equidistant from their home buckets, making the worst case much better.

// Robin Hood insertion (simplified)
void insert(K key, V value) {
  int index = hash(key) & (capacity - 1);
  int distance = 0;
  Entry entry = new Entry(key, value);
  
  while (table[index] != null) {
    int existingDist = probeDistance(table[index], index);
    if (distance > existingDist) {
      swap(entry, table[index]);    // "Rob from the rich"
      distance = existingDist;      // Continue with displaced entry
    }
    index = (index + 1) & (capacity - 1);
    distance++;
  }
  table[index] = entry;
}

Load Factor and Dynamic Resizing

A HashMap cannot keep adding entries forever without degrading. The load factor is the ratio of entries to bucket array capacity. When it exceeds a threshold, the HashMap resizes.

The Resize Trigger

Java's HashMap uses a default load factor of 0.75. When size > capacity * 0.75, the HashMap doubles its capacity and rehashes every entry.

Why 0.75? It is a balance between space and time:

• Load factor 0.5: Fewer collisions, but wastes 50% of memory
• Load factor 0.75: Good balance, chains average ~1.5 entries
• Load factor 1.0: Maximum density, but collision chains lengthen significantly

The Rehash Process

Resizing is the most expensive HashMap operation. Every entry must be reinserted into the new, larger array:

// Simplified resize
void resize() {
  int newCapacity = capacity * 2;
  Node[] newTable = new Node[newCapacity];
  
  for (Node node : table) {
    while (node != null) {
      Node next = node.next;
      int newIndex = node.hash & (newCapacity - 1);  // Recompute index
      node.next = newTable[newIndex];                  // Prepend to new bucket
      newTable[newIndex] = node;
      node = next;
    }
  }
  table = newTable;
  capacity = newCapacity;
}

Amortized O(1) Analysis

A single resize copies all N entries, costing O(n). But resizes happen exponentially less frequently as the map grows. The amortized cost per insertion:

• Insert entries 1-12: no resize, cost = O(1) each
• Insert entry 13: resize from 16 to 32, copies 12 entries, cost = O(n) once
• Insert entries 14-24: no resize, cost = O(1) each
• Insert entry 25: resize from 32 to 64, copies 24 entries

Total cost for N insertions: N (insertions) + N/2 + N/4 + N/8 + ... (resize copies) = N + N = 2N = O(n) total, or O(1) amortized per insertion.

This is the same amortized argument used for dynamic arrays (ArrayList, Python lists, Go slices).

Thread Safety and ConcurrentHashMap

Standard HashMap is not thread-safe. Two threads calling put() simultaneously can corrupt the internal structure, causing infinite loops (in Java 7's linked list implementation), lost updates, or unpredictable behavior.

What Goes Wrong Without Synchronization

In Java 7, concurrent resizes could create a circular linked list in a bucket. Thread A is halfway through moving entries to the new array when Thread B starts its own resize. The linked list pointers get crossed, creating a cycle. Any subsequent get() that hits this bucket enters an infinite loop, consuming 100% CPU on that thread.

Java 8 fixed this specific bug by not reversing the linked list order during resize. But concurrent modification can still cause lost updates and size counter corruption.

ConcurrentHashMap: Lock Striping

Java's ConcurrentHashMap provides thread-safe access without locking the entire map. The key insight is lock striping: instead of one lock for the whole map, it uses one lock per bucket (or per segment in older versions).

// ConcurrentHashMap put (simplified, Java 8+)
V put(K key, V value) {
  int hash = spread(key.hashCode());
  int index = hash & (capacity - 1);
  
  synchronized (getBucketLock(index)) {    // Lock only this bucket
    // Insert or update within this bucket
    // Other threads can still access other buckets
  }
  
  if (size.incrementAndGet() > threshold) {
    // Cooperative resize: multiple threads help rehash
    helpTransfer();
  }
}

Key design choices in Java's ConcurrentHashMap:

• Lock per bucket: Only the bucket being modified is locked. Reads are lock-free (using volatile reads).
• CAS for size counter: The entry count uses LongAdder (internally striped counters) to avoid contention on a single counter.
• Cooperative resizing: When a resize is triggered, all threads that encounter the resize-in-progress state help move buckets, spreading the work across threads.

Real Implementation Walk-Through

Java HashMap (Separate Chaining + Treeification)

Java's HashMap is the most commonly asked about in interviews:

The put() path in Java HashMap:

1. Compute hash = key.hashCode() ^ (key.hashCode() >>> 16)
2. Find bucket: index = hash & (capacity - 1)
3. If bucket is empty, insert new Node
4. If bucket is a linked list, walk it. If key exists, update value. If not, append.
5. If list length reaches 8 and capacity >= 64, convert to TreeNode (red-black tree)
6. If list length reaches 8 and capacity < 64, resize instead of treeifying
7. Increment size. If size > capacity * loadFactor, resize (double capacity, rehash)

Python dict (Open Addressing + Compact Layout)

Python's dict implementation is quite different from Java:

• Uses open addressing with a hash table index array and a separate compact entries array
• Probing uses perturbation: next_index = (5 * index + 1 + perturb) % capacity; perturb >>= 5
• Load factor threshold: 2/3 (approximately 0.67)
• No treeification (open addressing does not use chains)

The compact layout (introduced in Python 3.6) separates the hash table indices from the entries, saving ~25% memory and preserving insertion order as a side effect. This is why Python dicts maintain insertion order (guaranteed since Python 3.7).

// Python dict structure (simplified)
struct PyDictObject {
  int[] indices;       // Sparse array: maps hash -> entry position
  Entry[] entries;     // Dense array: stores (hash, key, value) in insertion order
}

// Lookup
int lookup(key) {
  int hash = hash(key);
  int index = hash % len(indices);
  int perturb = hash;
  
  while (indices[index] != EMPTY) {
    int entry_pos = indices[index];
    if (entries[entry_pos].hash == hash && 
        entries[entry_pos].key == key) {
      return entry_pos;
    }
    index = (5 * index + 1 + perturb) % len(indices);
    perturb >>= 5;     // Perturbation decays: uses all hash bits over time
  }
  return NOT_FOUND;
}

What Happens When Things Break

Performance Characteristics

Memory overhead per entry (Java HashMap):

• Each Node object: 32 bytes (hash, key ref, value ref, next pointer, object header)
• Plus the key and value objects themselves
• Bucket array: 4-8 bytes per slot (reference)
• At load factor 0.75: ~25% of buckets are empty (wasted array space)

Total memory for 1 million entries: approximately 48-64 MB (depending on key/value sizes and JVM settings).

How This Compares to Alternatives

I use HashMap as the default choice for key-value storage. I switch to TreeMap only when I need sorted iteration or range queries (subMap, headMap, tailMap). I use LinkedHashMap when access order matters (LRU eviction is a common use case). ConcurrentHashMap is the only option when the map is shared across threads.

For high-performance systems, I also consider off-heap maps (like Chronicle Map) when GC pressure from millions of entries becomes a bottleneck, or primitive-specialized maps (like Eclipse Collections or Koloboke) when keys/values are primitive types and autoboxing overhead matters.

Cache Performance: Why HashMap Layout Matters

At the hardware level, HashMap performance depends heavily on CPU cache behavior. I find this the most underappreciated aspect of HashMap design.

Separate chaining scatters Node objects across the heap. Each node is a separate Java object allocated wherever the GC places it. Following node.next pointers causes cache misses because consecutive nodes are rarely in adjacent memory. For a chain of length 4, you might have 4 cache misses (each costing ~100ns on a modern CPU).

Open addressing stores entries directly in a contiguous array. Probing consecutive slots (linear probing) accesses adjacent memory, which the CPU prefetcher predicts and pre-loads. This is why open addressing with linear probing can be 2-3x faster than chaining for small to medium maps, despite having higher collision rates.

This is why Google's absl::flat_hash_map (C++) and Rust's HashMap chose open addressing variants. They prioritize cache performance for modern CPUs where memory latency dominates.

Interview Cheat Sheet

• When asked about hash functions: "hashCode() produces a 32-bit integer. Java's HashMap applies a spread function (XOR high bits into low bits) to reduce clustering. The bucket index is computed with hash & (capacity - 1), which requires power-of-2 capacity."
• When asked about collisions: "Java uses separate chaining. Each bucket is a linked list. In Java 8+, lists with 8+ entries are converted to red-black trees for O(log n) worst-case lookup."
• When asked about open addressing: "Python's dict uses open addressing with perturbation-based probing. Each probe step incorporates more bits of the hash. No separate linked lists, everything lives in the array."
• When asked about load factor: "Default is 0.75 in Java. When exceeded, the array doubles and all entries are rehashed. Amortized insertion cost is still O(1) because resizes are exponentially less frequent."
• When asked about thread safety: "HashMap is not thread-safe. ConcurrentHashMap uses lock striping (one lock per bucket) and CAS operations for the size counter. Reads are lock-free."
• When asked about worst case: "If all keys hash to the same bucket, HashMap degrades to O(n). Treeification improves this to O(log n). The real fix is a better hash function."
• When asked about memory: "Each Java HashMap entry costs ~32 bytes for the Node object alone. Pre-size the map if you know the expected size to avoid unnecessary resizes."
• When asked about equals and hashCode contract: "If two objects are equal (a.equals(b)), they must have the same hashCode. The reverse is not required but desired. Violating this contract causes entries to be lost in the HashMap."
• When asked about Robin Hood hashing: "On collision, if the inserting key has probed farther than the resident key, they swap. This equalizes probe distances and improves worst-case lookup for open addressing."

Test Your Understanding

Step-by-Step: Tracing a put() and get() in Java

Let me walk through a concrete example to make this tangible. We start with an empty HashMap (capacity 16, load factor 0.75, threshold 12).

Step 1: map.put("alice", 42)

1. Compute hash: "alice".hashCode() returns 92903807
2. Spread: 92903807 ^ (92903807 >>> 16) = 92903807 ^ 1417 = 92905134
3. Bucket index: 92905134 & 15 = 14 (binary: last 4 bits of hash)
4. Bucket 14 is empty. Create a new Node(hash=92905134, key="alice", value=42, next=null)
5. Place it in table[14]. Size becomes 1.

Step 2: map.put("bob", 77)

1. Compute hash: "bob".hashCode() returns 97442
2. Spread: 97442 ^ (97442 >>> 16) = 97442 ^ 1 = 97443
3. Bucket index: 97443 & 15 = 3
4. Bucket 3 is empty. Create new Node. Size becomes 2.

Step 3: map.put("charlie", 99) (assume collision, also maps to bucket 14)

1. Compute hash and bucket index: lands on bucket 14
2. Bucket 14 is occupied (by "alice"). Walk the chain: compare hash values, then .equals()
3. "charlie" != "alice", and node.next is null, so append to the chain
4. Bucket 14 now has: alice -> charlie. Size becomes 3.

Step 4: map.get("charlie")

1. Compute hash and bucket index: bucket 14
2. First node is "alice". Hash matches? Check. Key equals "charlie"? No.
3. Follow node.next. Second node is "charlie". Hash matches? Check. Key equals "charlie"? Yes.
4. Return value: 99

This two-step comparison (hash first, then equals) is the key optimization. In a chain of 100 entries, most can be eliminated by the cheap integer hash comparison without calling the potentially expensive .equals() method.

Quick Recap

1. A HashMap maps keys to bucket indices using a hash function and modular arithmetic (hash & (capacity - 1) for power-of-2 capacities).
2. Java's HashMap applies a spread function (XOR high 16 bits into low 16 bits) to reduce collisions from hash codes with patterns in their low bits.
3. Separate chaining stores collisions in linked lists per bucket. Java 8+ converts lists to red-black trees at 8 entries for O(log n) worst-case lookup.
4. Open addressing (used by Python's dict) stores all entries in the array and probes forward on collision. Robin Hood hashing improves fairness by swapping entries that have probed unequally.
5. The load factor (default 0.75 in Java) triggers a resize when exceeded. Resizing doubles the array and rehashes all entries, but amortized cost per insertion remains O(1).
6. HashMap is not thread-safe. ConcurrentHashMap uses lock striping (one lock per bucket) and CAS-based size counting for high-concurrency access.
7. The equals/hashCode contract is fundamental: equal objects must have the same hash code. Violating this causes silent data loss in HashMaps.
8. Pre-sizing the HashMap to the expected entry count avoids unnecessary resizes and GC pressure during bulk insertions.

Related Concepts

• Red-black trees: The self-balancing BST used for treeification in Java HashMap buckets. Understanding their O(log n) guarantees explains worst-case HashMap behavior.
• Consistent hashing: A different hashing strategy used in distributed systems (not data structures) to minimize key redistribution when nodes are added or removed.
• Bloom filters: A probabilistic data structure that uses multiple hash functions. Understanding how hash functions distribute keys applies directly.
• LRU caches: LinkedHashMap is the foundation for LRU cache implementations. The connection between HashMap and caching is a common interview thread.
• Hash flooding and SipHash: Understanding adversarial inputs and randomized hash functions connects data structure design to security engineering.