Hash Tables: How to Explain Them in an Interview (2026)

A hash table is a data structure that stores key → value pairs by turning each key into an index with a hash function. The index points to a bucket where the value lives. This simple idea lets you look up, insert, or delete an item in average‑case constant time, O(1).

How a Hash Table Works

1. Hash Function – Takes a key (string, integer, etc.) and returns an integer. The integer is reduced modulo the table size to produce a bucket index.
2. Buckets – Each slot in the underlying array holds either a single entry or a collection of entries that share the same index.
3. Collision Resolution – When two keys map to the same bucket, the table must store both. The two most common strategies are:
   • Chaining – Each bucket holds a linked list (or dynamic array) of entries. Insertion appends to the list; lookup scans the list.
   • Open Addressing – The table probes other slots (linear, quadratic, double hashing) until an empty slot is found.

The choice of hash function and collision strategy determines both average and worst‑case performance.

Trade‑offs to Discuss

In most interview settings, candidates are expected to know that chaining is conceptually easier, while open addressing can be faster in practice due to cache effects.

Concrete Example

Imagine you need a phone‑book lookup where the key is a person's name and the value is their phone number. You decide on a simple hash: sum the ASCII codes of the characters and take modulo 10 (so the table has 10 buckets).

class SimpleHashTable:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key):
        return sum(ord(c) for c in key) % self.size

    def set(self, key, value):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        raise KeyError(key)

If you add "Alice" and "Bob", both may land in bucket 3 because their ASCII sums happen to be congruent modulo 10. The list in bucket 3 now holds two entries; a lookup scans at most two items.

Typical Interview Questions

1. Define a hash table in one sentence. “A hash table stores key‑value pairs by mapping each key to an array index using a hash function.”
2. What is the purpose of a hash function? Explain determinism, uniform distribution, and the modulo operation.
3. How do you handle collisions? Compare chaining vs. open addressing, mention pros/cons.
4. What is the load factor and why does it matter? Load factor = n / m (entries / buckets). When it exceeds a threshold (often 0.7), performance degrades and a resize is triggered.
5. What is the worst‑case time complexity? O(n) if all keys hash to the same bucket (degenerate case).
6. How would you design a hash function for strings? Discuss rolling hash, multiplication method, or built‑in language hash with modulo.
7. Explain resizing: when and how it works. Resize when load factor crosses a threshold; allocate a larger array and re‑hash every entry.
8. When would you prefer a tree map over a hash table? When you need ordered iteration or guaranteed O(log n) bounds.

A 60‑Second Spoken Answer

“A hash table is a structure that stores key‑value pairs by converting the key into an array index with a hash function. The function should be deterministic and spread keys uniformly, typically by taking the key’s numeric representation modulo the table size. Collisions happen when two keys map to the same index; we resolve them either by chaining—keeping a linked list in each bucket—or by open addressing, probing other slots until we find an empty one. In the average case, lookups, inserts, and deletes are O(1), but the worst case degrades to O(n) if many keys collide. The load factor, defined as the number of entries divided by bucket count, guides when we resize the table to keep performance stable. In practice, chaining is easier to reason about, while open addressing can be faster due to better cache locality. Understanding these trade‑offs lets you choose the right variant for the problem at hand.”

Practicing this answer aloud with Call Assistant can help you keep the timing tight and ensure you stay on topic.

How to Practice This

1. Write the answer on paper – Draft the one‑sentence definition, then expand to the full explanation. Remove any filler.
2. Record a 60‑second version – Use a phone or Call Assistant’s voice‑capture feature; listen for pacing and clarity.
3. Simulate follow‑up questions – Have a friend ask about collisions, load factor, or resizing. Answer verbally, referring back to your core explanation.

---

FAQ

1. Q: What makes a good hash function? A: It must be deterministic, fast to compute, and distribute keys uniformly across buckets. Simple modulo works for integers; for strings, combine character codes with a multiplier to avoid patterns.
2. Q: Why does open addressing have better cache performance? A: All entries reside in a contiguous array, so probing accesses nearby memory locations, reducing cache misses compared to following pointers in linked lists.
3. Q: When should I choose chaining over open addressing? A: If you expect many insertions and deletions, or if you need to store more elements than the initial bucket count without frequent resizing, chaining is simpler and more robust.
4. Q: How does resizing affect performance? A: Resizing is an O(n) operation because every entry must be re‑hashed into the new larger array. However, it happens infrequently (when the load factor crosses a threshold), so the amortized cost remains constant.