DSA Designing a Hash Map

The problem

Design a Hash Map asks for a storage structure built from scratch. The structure stores pairs of a key and a value. Keys are words in this article, and values are numbers.

Three operations define the design. Put stores a pair or replaces the value of an existing key. Get returns the value for a key or None when the key is absent. Remove deletes a pair and reports whether the key was present.

The test is one fixed script of operations. The same script runs on every design in this article. A real dict runs beside the script as the reference answer.

script = [
    ("put", "ant", 1), ("put", "bee", 2), ("put", "cat", 3),
    ("put", "dog", 4), ("put", "elk", 5), ("put", "fox", 6),
    ("put", "gnu", 7), ("put", "cat", 30), ("remove", "bee", None),
    ("get", "cat", None), ("get", "bee", None), ("get", "owl", None),
]
for op, key, value in script:
    print(op, key, value)

The script holds seven new keys and one update. The update writes cat again with a new value. The last three gets test a present key, a removed key, and a key that never existed.

Intuition: one long list of pairs

The first design stores every pair in one list. Put appends to the list. Get walks the list from the start until the key matches.

The design is correct. Its cost is the trap. A key near the end pays for almost every pair stored before it, on every single lookup.

pairs = [("ant", 1), ("bee", 2), ("cat", 3), ("dog", 4),
         ("elk", 5), ("fox", 6), ("gnu", 7)]

def find(pairs, key):
    checks = 0
    for k, v in pairs:
        checks += 1
        if k == key:
            return v, checks
    return None, checks

print("get gnu:", find(pairs, "gnu"))
print("get ant:", find(pairs, "ant"))
print("get owl:", find(pairs, "owl"))

The last key costs seven checks. A missing key also costs seven checks, because only a full walk proves absence. Doubling the stored pairs doubles both costs.

Brute force: the list design, working and counted

The naive design wraps the list in three small functions. An update first walks the list to find the old pair. A counter totals the pair checks across the whole script.

script = [
    ("put", "ant", 1), ("put", "bee", 2), ("put", "cat", 3),
    ("put", "dog", 4), ("put", "elk", 5), ("put", "fox", 6),
    ("put", "gnu", 7), ("put", "cat", 30), ("remove", "bee", None),
    ("get", "cat", None), ("get", "bee", None), ("get", "owl", None),
]
pairs = []
checks = 0
real = {}
verdicts = []
for op, key, value in script:
    if op == "put":
        found = False
        for i, (k, v) in enumerate(pairs):
            checks += 1
            if k == key:
                pairs[i] = (key, value)
                found = True
                break
        if not found:
            pairs.append((key, value))
        real[key] = value
        verdicts.append(True)
    elif op == "remove":
        hit = False
        for i, (k, v) in enumerate(pairs):
            checks += 1
            if k == key:
                del pairs[i]
                hit = True
                break
        verdicts.append(hit == (key in real))
        real.pop(key, None)
    else:
        got = None
        for k, v in pairs:
            checks += 1
            if k == key:
                got = v
                break
        verdicts.append(got == real.get(key))
print("checks passed:", sum(verdicts), "of", len(verdicts))
print("pair checks in total:", checks)
print("stored pairs:", len(pairs))

Every verdict matches the reference dict. The design passes the script. It still spends dozens of pair checks on twelve operations, and the count grows with every stored pair.

The optimal solution: buckets chosen by a hash, with a resize rule

A hash is a calculation that turns a key into a number. The number modulo the bucket count picks one bucket, and a bucket is a short list that holds the pairs sent to it.

A lookup walks only its own bucket chain. The load factor is the pair count divided by the bucket count. A put that pushes the load factor past 0.75 doubles the buckets and places every pair again.

class MiniMap:
    def __init__(self):
        self.capacity = 4
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0

    def _hash(self, key):
        total = 0
        for ch in key:
            total = total * 31 + ord(ch)
        return total % self.capacity

    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        for key, value in old:
            self.buckets[self._hash(key)].append((key, value))

    def put(self, key, value):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1
        if self.size / self.capacity > 0.75:
            self._resize()

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

    def remove(self, key):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return True
        return False

mini = MiniMap()
real = {}
script = [
    ("put", "ant", 1), ("put", "bee", 2), ("put", "cat", 3),
    ("put", "dog", 4), ("put", "elk", 5), ("put", "fox", 6),
    ("put", "gnu", 7), ("put", "cat", 30), ("remove", "bee", None),
    ("get", "cat", None), ("get", "bee", None), ("get", "owl", None),
]
results = []
for op, key, value in script:
    if op == "put":
        mini.put(key, value)
        real[key] = value
        results.append(True)
    elif op == "remove":
        results.append(mini.remove(key) == (key in real))
        real.pop(key, None)
    else:
        results.append(mini.get(key) == real.get(key))
print("checks passed:", sum(results), "of", len(results))
print("size:", mini.size, "capacity:", mini.capacity)
print("cat:", mini.get("cat"))

All twelve checks pass again. Seven inserts cross the load limit twice, so the capacity doubles twice and ends at 16. The update of cat replaces its value without growing the size.

Walkthrough: the first puts, step by step

The walk runs the opening puts of the script. Each line shows the bucket a key lands in, the size, and the capacity after the put.

class MiniMap:
    def __init__(self):
        self.capacity = 4
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0

    def _hash(self, key):
        total = 0
        for ch in key:
            total = total * 31 + ord(ch)
        return total % self.capacity

    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        for key, value in old:
            self.buckets[self._hash(key)].append((key, value))

    def put(self, key, value):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1
        if self.size / self.capacity > 0.75:
            self._resize()

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

    def remove(self, key):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return True
        return False

mini = MiniMap()
for key, value in [("ant", 1), ("bee", 2), ("cat", 3), ("dog", 4), ("elk", 5)]:
    before = mini.capacity
    mini.put(key, value)
    note = "resized" if mini.capacity != before else ""
    print("put", key, "- size", mini.size, "capacity", mini.capacity, note)
print("chains:", [len(b) for b in mini.buckets])

The fourth put crosses the limit of three pairs in four buckets. The table doubles to eight buckets before the fifth put. The chain lengths show the pairs spread across the buckets instead of piling into one list.

Complexity

A list get walks up to n pairs for n stored pairs, so its time is O(n). A bucket get walks one short chain, so its average time stays O(1) while the resize rule keeps chains short.

Both designs store every pair once, so their space is O(n). The bucket design also stores its bucket lists, which add one slot per bucket.

for n in [7, 14, 28]:
    list_checks = n * (n + 1) // 2
    print("pairs", n, "- list checks for all gets:", list_checks, " gets:", n)

Fetching every key once from the list costs a triangular count of checks. That count roughly quadruples when the pairs double. The bucket design pays a short chain walk per get instead.

Edge cases and pitfalls

Updating a key must not grow the size. A put that skips the search first would store the same key twice. The later copy would then shadow the earlier one in some buckets and break gets.

Forgetting the resize is the slow failure. Chains grow with the pair count, and the design slides back toward the list cost. Removing a missing key must also leave the size untouched.

class MiniMap:
    def __init__(self):
        self.capacity = 4
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0

    def _hash(self, key):
        total = 0
        for ch in key:
            total = total * 31 + ord(ch)
        return total % self.capacity

    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        for key, value in old:
            self.buckets[self._hash(key)].append((key, value))

    def put(self, key, value):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1
        if self.size / self.capacity > 0.75:
            self._resize()

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

    def remove(self, key):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return True
        return False

mini = MiniMap()
print("get from empty:", mini.get("ant"))
print("remove from empty:", mini.remove("ant"))
mini.put("cat", 3)
mini.put("cat", 30)
print("after update, size:", mini.size, "cat:", mini.get("cat"))
print("remove missing:", mini.remove("owl"), "size:", mini.size)
print("remove present:", mini.remove("cat"), "size:", mini.size)
print("get after remove:", mini.get("cat"))

The empty map answers cleanly. The update keeps the size at one. The failed remove changes nothing, and the successful remove leaves no trace of the key.