Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

Building a HashMap

4 min read

You'll learn to

-Implement put, get, delete and contains with separate chaining
-Explain load factor, and see in an experiment what skipping the resize costs
-Explain why hashmap operations are described as average-case O(1)

This chapter assembles the last chapter's pieces into a complete, working HashMap: a fixed array of buckets, the hash-and-modulo step to choose one, and a short linear scan inside that one bucket to handle whatever collisions land there.

An Analogy: A Coat Check With Numbered Hooks

A coat check has a row of hooks. When you hand over a coat, the attendant turns your name into a hook number and hangs the coat there. To get it back, they turn your name into the same number and look at that hook. If two coats end up on one hook, the attendant checks the tags on that hook only. If one hook is crowded, they add more hooks and re-hang everything. That is a hashmap.

The Bucket Array

A list of buckets, each an empty list ready to hold (key, value) pairs

class HashMap:
    def __init__(self, capacity=8):
        self._capacity = capacity
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0

    def _bucket_index(self, key):
        return hash(key) % self._capacity

put, get, delete, and contains

put, get, delete, contains, size, and load_factor, continuing the HashMap class

    def put(self, key, value):
        index = self._bucket_index(key)
        bucket = self._buckets[index]
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[i] = (key, value)     # overwrite an existing key
                return
        bucket.append((key, value))          # new key - append to the chain
        self._size += 1
        if self.load_factor() > 0.75:
            self._resize()

    def get(self, key):
        bucket = self._buckets[self._bucket_index(key)]
        for existing_key, value in bucket:
            if existing_key == key:
                return value
        raise KeyError(key)

    def delete(self, key):
        bucket = self._buckets[self._bucket_index(key)]
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                del bucket[i]
                self._size -= 1
                return
        raise KeyError(key)

    def contains(self, key):
        bucket = self._buckets[self._bucket_index(key)]
        return any(existing_key == key for existing_key, _ in bucket)

    def size(self):
        return self._size

    def load_factor(self):
        return self._size / self._capacity

Every one of put, get, delete and contains has the same two-step shape: hash the key once to find the right bucket (O(1)), then scan only that one bucket instead of the whole table. As long as buckets stay short, that scan costs almost nothing, which is why the overall operation is described as average-case O(1). Not because there is no scanning, but because the scan only ever touches a tiny slice of the data.

Load Factor & Resizing

Load factor is the number of stored entries divided by the number of buckets, which is effectively the average chain length. As it climbs past about 0.7 to 0.75, buckets routinely hold several entries, and the per-bucket scan stops being negligible. Real hashmaps, including Python's own dict, watch the load factor and, past a threshold, allocate a larger bucket array (commonly double the old size) and rehash every key into it. That rehashing pass is O(n), but it happens only occasionally. Spread across all the puts that led up to it, it barely dents the average-case O(1).

The full HashMap class, assembled and demonstrated end to end

class HashMap:
    def __init__(self, capacity=8):
        self._capacity = capacity
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0

    def _bucket_index(self, key):
        return hash(key) % self._capacity

    def put(self, key, value):
        index = self._bucket_index(key)
        bucket = self._buckets[index]
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[i] = (key, value)     # overwrite an existing key
                return
        bucket.append((key, value))          # new key - append to the chain
        self._size += 1
        if self.load_factor() > 0.75:
            self._resize()

    def get(self, key):
        bucket = self._buckets[self._bucket_index(key)]
        for existing_key, value in bucket:
            if existing_key == key:
                return value
        raise KeyError(key)

    def delete(self, key):
        bucket = self._buckets[self._bucket_index(key)]
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                del bucket[i]
                self._size -= 1
                return
        raise KeyError(key)

    def contains(self, key):
        bucket = self._buckets[self._bucket_index(key)]
        return any(existing_key == key for existing_key, _ in bucket)

    def size(self):
        return self._size

    def load_factor(self):
        return self._size / self._capacity

    def _resize(self):
        old_buckets = self._buckets
        self._capacity *= 2
        self._buckets = [[] for _ in range(self._capacity)]
        self._size = 0
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)   # re-hash every key into the larger table

h = HashMap(capacity=4)
for i in range(6):
    h.put(f"key{i}", i * 10)   # crosses load factor 0.75 partway through, triggering a resize

print(f"size={h.size()}, capacity={h._capacity}, load_factor={h.load_factor():.2f}")
print(h.get("key3"))
print(h.contains("key5"), h.contains("key99"))
h.delete("key0")
print(h.contains("key0"))

class HashMap:
    def __init__(self, capacity=8):
        self._capacity = capacity
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0

def _bucket_index(self, key):
        return hash(key) % self._capacity

def put(self, key, value):
        index = self._bucket_index(key)
        bucket = self._buckets[index]
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[i] = (key, value)     # overwrite an existing key
                return
        bucket.append((key, value))          # new key - append to the chain
        self._size += 1
        if self.load_factor() > 0.75:
            self._resize()

def get(self, key):
        bucket = self._buckets[self._bucket_index(key)]
        for existing_key, value in bucket:
            if existing_key == key:
                return value
        raise KeyError(key)

def delete(self, key):
        bucket = self._buckets[self._bucket_index(key)]
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                del bucket[i]
                self._size -= 1
                return
        raise KeyError(key)

def contains(self, key):
        bucket = self._buckets[self._bucket_index(key)]
        return any(existing_key == key for existing_key, _ in bucket)

def size(self):
        return self._size

def load_factor(self):
        return self._size / self._capacity

def _resize(self):
        old_buckets = self._buckets
        self._capacity *= 2
        self._buckets = [[] for _ in range(self._capacity)]
        self._size = 0
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)   # re-hash every key into the larger table

h = HashMap(capacity=4)
for i in range(6):
    h.put(f"key{i}", i * 10)   # crosses load factor 0.75 partway through, triggering a resize

print(f"size={h.size()}, capacity={h._capacity}, load_factor={h.load_factor():.2f}")
print(h.get("key3"))
print(h.contains("key5"), h.contains("key99"))
h.delete("key0")
print(h.contains("key0"))

The experiment below shows why that resize is worth its cost. It puts 1,000 keys into a table that starts with 8 buckets, once with no resizing and once with doubling. Compare the longest chain and the average number of comparisons needed to find a key.

Press Run: without resizing, finding a key walks about 63 entries on average, with resizing about 1

def build(keys, resize):
    capacity = 8
    buckets = [[] for _ in range(capacity)]
    size = 0
    for key in keys:
        buckets[key % capacity].append(key)              # hash-and-modulo, kept simple: the key itself is the hash
        size += 1
        if resize and size / capacity > 0.75:             # load factor too high: double and re-hash everything
            capacity *= 2
            bigger = [[] for _ in range(capacity)]
            for bucket in buckets:
                for k in bucket:
                    bigger[k % capacity].append(k)
            buckets = bigger
    return buckets, capacity

def average_comparisons(buckets):                         # finding a key means walking its chain up to that key
    total, count = 0, 0
    for bucket in buckets:
        for position, _ in enumerate(bucket, start=1):
            total += position
            count += 1
    return total / count

keys = [i * 7 + 3 for i in range(1000)]
for resize in (False, True):
    buckets, capacity = build(keys, resize)
    longest = max(len(b) for b in buckets)
    label = "doubles when load factor > 0.75" if resize else "never resizes (stays at 8 buckets)"
    print(f"{label:36} capacity {capacity:>5}, longest chain {longest:>3}, average comparisons to find a key {average_comparisons(buckets):.1f}")

def build(keys, resize):
    capacity = 8
    buckets = [[] for _ in range(capacity)]
    size = 0
    for key in keys:
        buckets[key % capacity].append(key)              # hash-and-modulo, kept simple: the key itself is the hash
        size += 1
        if resize and size / capacity > 0.75:             # load factor too high: double and re-hash everything
            capacity *= 2
            bigger = [[] for _ in range(capacity)]
            for bucket in buckets:
                for k in bucket:
                    bigger[k % capacity].append(k)
            buckets = bigger
    return buckets, capacity

def average_comparisons(buckets):                         # finding a key means walking its chain up to that key
    total, count = 0, 0
    for bucket in buckets:
        for position, _ in enumerate(bucket, start=1):
            total += position
            count += 1
    return total / count

keys = [i * 7 + 3 for i in range(1000)]
for resize in (False, True):
    buckets, capacity = build(keys, resize)
    longest = max(len(b) for b in buckets)
    label = "doubles when load factor > 0.75" if resize else "never resizes (stays at 8 buckets)"
    print(f"{label:36} capacity {capacity:>5}, longest chain {longest:>3}, average comparisons to find a key {average_comparisons(buckets):.1f}")

Load factor and average chain length

~0.5 entries per bucket (fast)

Load factor 0.5

~4 entries per bucket (4x slower gets)

Load factor 4.0 (never resized)

Python's real dict is far more optimized than this: it uses open addressing instead of chaining, and has kept insertion order since Python 3.7. But the average-case O(1), resize-on-load-factor idea built here is the same mental model underneath every hashmap you will reach for.

Interview Signal is part of Pro

See a real weak answer next to a real strong one for this exact topic.

Quiz is part of Pro

Test what you just read with a short quiz, and bank the XP.

Ready to Build This?

Level 4: HashMap from Scratch asks you to implement exactly this, a HashMap class with put, get, delete, contains, size, and load_factor, using separate chaining for collision resolution. Build it directly from the class above.

Hash Functions & Collisions Singly Linked Lists

Discussion0

Join the Discussion

No comments yet. Be the first to start the thread!