Design a hash map and hash set from scratch

01The design, in the six-step framework

1. Requirements and use cases

An easy prompt with a sharp purpose: the interviewer wants to see whether you understand the container you use every day, and whether you can keep a small class clean under follow-ups about load factor and resizing.

• A caller puts a key and value; an existing key's value is replaced.
• A caller gets a value by key, or a miss marker.
• A caller removes a key.
• Keys can be any object that defines hash and equality consistently.
• Operations stay O(1) on average as the map grows: the map resizes itself.
• A hash set is built on the same machinery with a trivial value.

Out of scope: ordering of iteration, thread safety, and weak references. Non-functional constraints: average O(1) for all three operations with a load factor kept under a stated threshold; memory within a small constant of the number of entries; and the collision strategy must be explainable in one sentence, so separate chaining is chosen over open addressing.

2. Core entities and relationships

• HashMap: the public object; owns the bucket array, the entry count and the load-factor policy.
• Bucket: a short list of entries whose keys hash to the same slot.
• Entry: a key and a value; equality of entries is equality of keys.
• HashSet: a thin wrapper that stores keys with a sentinel value.

The map composes its buckets, and each bucket composes its entries; nothing outside the map ever sees a bucket. The set is implemented by composition over a map, not by inheritance from it: a set is not a kind of map (it has no values), it merely uses one. That is the first instinct interviewers check under inheritance versus composition.

3. Interfaces and key methods

from typing import Generic, Hashable, Optional, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")


class HashMap(Generic[K, V]):
    def __init__(self, initial_buckets: int = 8, max_load: float = 0.75) -> None:
        """Bucket count is a power of two; resizes when size / buckets exceeds max_load."""

    def put(self, key: K, value: V) -> None:
        """Insert or replace."""

    def get(self, key: K) -> Optional[V]:
        """Value or None (use __contains__ to tell None-valued keys from misses)."""

    def remove(self, key: K) -> bool:
        """True if the key was present."""

    def __contains__(self, key: object) -> bool: ...
    def __len__(self) -> int: ...


class HashSet(Generic[K]):
    def add(self, key: K) -> None: ...
    def contains(self, key: K) -> bool: ...
    def remove(self, key: K) -> bool: ...

Invariants: every entry lives in the bucket at index hash(key) & (buckets − 1) for the current bucket count; no two entries in the map have equal keys; size equals the total number of entries across buckets; and after any put, size / len(buckets) <= max_load.

4. Design patterns and the choices behind them

Separate chaining over open addressing

The force is collisions. Chaining keeps a list per bucket: insert appends, remove deletes from a short list, and resizing is a rehash of every entry into a new array. Open addressing (probe the next slot) uses less memory and is cache-friendlier, but deletion needs tombstones and the probe sequence is where interview bugs live. For a one-hour design, chaining is the defensible choice and you should name the trade-off. This is the kind of call covered in trade-offs and over-engineering.

Power-of-two bucket counts

The force is cheap slot computation and simple doubling. With a power of two, the slot is a bitwise and instead of a modulo, and doubling keeps the property. Python's built-in hash can be negative; the mask handles that without an extra absolute value.

Why the load factor is 0.75

The force is the trade between memory and chain length. With uniform hashing, the expected chain length is the load factor itself, so at 0.75 a lookup inspects fewer than two entries on average, and the bucket array wastes at most a quarter of its slots. Pushing the threshold to 2 halves memory but doubles the expected scan; pulling it to 0.25 makes lookups a single entry but quadruples the array. Doubling on resize keeps the amortised cost of growth at O(1) per insert, because the total rehash work over n inserts is bounded by 2n. These three numbers are what an interviewer expects you to produce when asked "why that constant".

expected chain length = size / buckets = load factor; total rehash work for n inserts < 2n

Keys are hashable, and only hashable

The map asks nothing of keys beyond hash and equality, and it relies on their contract: equal keys must hash equal. If a caller mutates a key after inserting it, the entry becomes unreachable; that is the caller's bug, and saying so shows you know where the contract boundary is. The encapsulation rule for the class is that buckets never escape, so no caller can break the first invariant.

5. Core flow and code

Flow for put("k", 1) when the map holds 6 entries in 8 buckets with max_load 0.75:

1. Compute the slot from the hash and the mask; scan that bucket for an entry with an equal key.
2. None found: append a new Entry, increment size to 7.
3. 7 / 8 exceeds 0.75, so allocate 16 buckets and re-insert every entry by its new slot.

from dataclasses import dataclass
from typing import Generic, Hashable, List, Optional, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")


@dataclass
class Entry(Generic[K, V]):
    key: K
    value: V


class HashMap(Generic[K, V]):
    def __init__(self, initial_buckets: int = 8, max_load: float = 0.75) -> None:
        if initial_buckets < 1 or initial_buckets & (initial_buckets - 1):
            raise ValueError("initial_buckets must be a power of two")
        self.buckets: List[List[Entry[K, V]]] = [[] for _ in range(initial_buckets)]
        self.size = 0
        self.max_load = max_load

    def _slot(self, key: K) -> int:
        return hash(key) & (len(self.buckets) - 1)

    def _find(self, bucket: List[Entry[K, V]], key: K) -> Optional[Entry[K, V]]:
        for entry in bucket:
            if entry.key == key:
                return entry
        return None

    def put(self, key: K, value: V) -> None:
        bucket = self.buckets[self._slot(key)]
        entry = self._find(bucket, key)
        if entry is not None:
            entry.value = value
            return
        bucket.append(Entry(key, value))
        self.size += 1
        if self.size / len(self.buckets) > self.max_load:
            self._resize(len(self.buckets) * 2)

    def get(self, key: K) -> Optional[V]:
        entry = self._find(self.buckets[self._slot(key)], key)
        return None if entry is None else entry.value

    def remove(self, key: K) -> bool:
        bucket = self.buckets[self._slot(key)]
        for i, entry in enumerate(bucket):
            if entry.key == key:
                bucket[i] = bucket[-1]      # swap with last, then pop: O(1)
                bucket.pop()
                self.size -= 1
                return True
        return False

    def __contains__(self, key: object) -> bool:
        return self._find(self.buckets[self._slot(key)], key) is not None  # type: ignore[arg-type]

    def __len__(self) -> int:
        return self.size

    def _resize(self, new_count: int) -> None:
        old = self.buckets
        self.buckets = [[] for _ in range(new_count)]
        for bucket in old:
            for entry in bucket:
                self.buckets[self._slot(entry.key)].append(entry)


class HashSet(Generic[K]):
    def __init__(self) -> None:
        self.map: HashMap[K, None] = HashMap()

    def add(self, key: K) -> None:
        self.map.put(key, None)

    def contains(self, key: K) -> bool:
        return key in self.map

    def remove(self, key: K) -> bool:
        return self.map.remove(key)

    def __len__(self) -> int:
        return len(self.map)


if __name__ == "__main__":
    m: HashMap[str, int] = HashMap(initial_buckets=2)
    for i in range(20):
        m.put(f"k{i}", i)                     # forces several resizes
    assert len(m) == 20 and m.get("k7") == 7 and len(m.buckets) >= 32
    assert m.remove("k7") and "k7" not in m and len(m) == 19
    s: HashSet[int] = HashSet()
    s.add(3); s.add(3)
    assert len(s) == 1 and s.contains(3)

6. Extensions, concurrency and what interviewers probe

• Why not shrink? Shrinking on remove makes a workload that oscillates around the threshold resize constantly; if asked, shrink only when load drops below a quarter, with hysteresis.
• Worst case. All keys colliding make every operation O(n); the remedy in real libraries is turning long chains into trees or randomising the hash seed. Naming that shows depth without implementing it.
• Iteration order. Unspecified here; an insertion-ordered map adds a linked list through the entries, which is the same trick as the LRU cache.
• Thread safety. A single lock, or striped locks over bucket ranges; resizing must take every stripe, which is the subtle part.
• What to test first. Put-then-resize-then-get, as in the code, because a wrong rehash is invisible until the first lookup after growth.
• Common mistake. Using hash(key) % n with a negative hash in languages where modulo can be negative, and inheriting HashSet from HashMap so put leaks into the set's API.

02Where this question was reported

• LeetCode Discuss · LeetCode 706 (Easy), Google-tagged, freq 16.6; 705 Design HashSet freq 18.2