Building a hash table with separate chaining in Python

A hash table is one of those deceptively simple data structures that quietly powers everything from database indexing to caching layers in web frameworks. In Australia, where software engineers at Atlassian in Sydney and Canva in Surry Hills build tools relied on by millions, understanding how a hash table behaves under the hood is genuinely useful. The structure offers average-case constant time for inserts, lookups and deletes, but reaching that performance hinges on how collisions are handled. Separate chaining is the friendliest approach for learners because it sidesteps the clustering problems that plague open addressing schemes.

The core idea is straightforward. Feed a key into a hash function, take the resulting integer modulo the number of buckets, and store the key-value pair at that index. When two keys hash to the same bucket, keep both by chaining them together using a linked list, or in Python, a list of tuples or a small custom linked list class. This approach degrades gracefully as the load factor climbs, and Python's built-in dict is essentially a refined version of the same idea.

For newcomers exploring algorithmic problem solving on platforms such as LeetCode, or for students sitting algorithms courses at the University of Melbourne or UNSW, building a hash table from scratch clarifies why average-case O(1) is not the same as worst-case O(n). It also surfaces the practical decisions that production engineers wrestle with: how big to make the table, when to resize, and how to write a fair hash function for string keys.

Readers who want a broader tour of data structures and Python implementations can wander over to the hello ML community blog, which collects tutorials on trees, sorting algorithms and interview-style problems. The article ahead focuses narrowly on separate chaining, walking through design decisions and showing every line of code along the way.

Understanding hash functions and bucket placement

A hash function takes arbitrary input, such as a string, an integer or a tuple, and produces an integer that we can reduce modulo the table size. Python's built-in hash() for strings uses a SipHash variant with a per-process random seed to defeat hash flooding attacks. Writing your own table usually does not need that level of defence, but understanding the principle matters. A simple deterministic scheme for strings is to start with a prime multiplier such as 31 or 5381 and accumulate character codes as you iterate.

The modulo step distributes keys across buckets, and the choice of bucket count influences collision frequency. A power of two is convenient for masking, but it makes the hash function's lower bits disproportionately important, which can lead to clustering. Many production implementations vary bucket count between sizes related to powers of two, three and five to avoid pathological inputs. For a teaching implementation, starting with a fixed prime such as 11 or 53 keeps the maths easy to reason about.

When two keys hash to the same bucket, separate chaining stores them in a linked list attached to that slot. Each lookup walks the list and compares the full key for equality, since different keys can share a hash. This is why mutable objects cannot be hashed reliably in Python. List equality is value-based but list hashing raises a TypeError on purpose, preserving the contract that equal keys must produce equal hashes.

Designing the class and choosing the bucket type

The skeleton of our class needs three instance variables: the bucket array, the current count of items, and a load factor threshold. The bucket array is typically a Python list where each element holds either an empty marker or a chain of entries. Chains can be implemented as plain lists of tuples, which is the simplest route for a teaching project, or as a small custom linked list class if you want to rehearse pointer manipulation.

For an Australian student juggling coursework and part-time work, the list-of-tuples approach is appealing because it stays under fifty lines of code. The trade-off is that deleting a key requires scanning and rebuilding the slice, an O(k) operation where k is the chain length. A linked list lets you splice out a node in O(1) once you locate it, which is closer to what the standard library does for very large chains.

The constructor should accept an initial capacity and a load factor upper bound, defaulting to 8 and 0.75. We also want a method called _resize that doubles the capacity and rehashes every existing key. Choosing 0.75 as the default mirrors CPython and Java's HashMap, striking a reasonable balance between memory overhead and collision risk. The internal _bucket_index helper computes the slot by modding the hash by capacity, and a guard against non-power-of-two capacities keeps the code robust if you later switch to bit masking.

Implementing insert, lookup and delete

Insertion is the workhorse operation. Compute the bucket index, walk the chain, and either overwrite the value if the key exists or append a new tuple. The size counter increments only when a new entry is created, which keeps the load factor meaningful and protects against accidentally growing the table from repeated updates to the same key.

class HashTable:
    def __init__(self, capacity=8, load_factor=0.75):
        self.capacity = capacity
        self.load_factor = load_factor
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]

    def put(self, key, value):
        idx = self._bucket_index(key)
        bucket = self.buckets[idx]
        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 * self.load_factor:
            self._resize()

Lookup follows the same path without the mutation. Returning a sentinel such as a custom _Missing singleton avoids the classic bug where a stored value of None is mistaken for an absent key. Many HashMap implementations in Java and elsewhere have shipped this exact bug over the years, so reading the canonical fix before writing your own saves an arvo of debugging.

Deletion walks the chain to find the matching tuple, pops it from the list and decrements the size counter. The slot stays an empty list rather than None, which keeps the bucket array type uniform and avoids special-casing in _bucket_index. Performance test paths at REA Group in Richmond have shown that uniform slot types simplify JIT optimisations for similar dictionary-heavy workloads, a reminder that even tiny consistency choices matter at scale.

Resizing, load factor and rehashing

Resizing is the operation that most casual implementations skip, and that omission is what separates a toy from a usable hash table. When the load factor crosses the threshold, allocate a new bucket array of double the capacity and reinsert every key. Reinserting forces the hash to recompute under the new modulus, so keys that previously collided may end up in different slots.

The amortised cost of doubling is O(1) per insert across the table's lifetime. Each entry gets rehashed at most log n times across n insertions, which is what gives the structure its constant amortised performance. Skipping the resize step turns average-case O(1) into worst-case O(n) once the chains grow long, which is exactly the failure mode that hash flooding attacks exploit.

A subtle refinement is to shrink the table when deletions drop the load factor below a lower threshold such as 0.2. Many production libraries skip shrinking to avoid resize churn, but a teaching implementation benefits from exposing both directions. Engineers benchmarking scraping pipelines at Xero in Melbourne often disable shrinking on hot paths because session caches churn for hours without dropping below a stable size.

Time and space complexity at a glance

A comparison of common strategies helps frame where separate chaining sits relative to its peers. The table below summarises the trade-offs between separate chaining and the three main open addressing schemes.

Strategy	Average insert	Worst-case insert	Memory overhead	Cache friendliness
Separate chaining	O(1 + α)	O(n)	High (extra pointers or lists)	Moderate
Linear probing	O(1 + α)	O(n)	Low	Excellent
Quadratic probing	O(1 + α)	O(n)	Low	Good
Double hashing	O(1 + α)	O(n)	Low	Moderate

Here α is the load factor, which is the ratio of stored entries to bucket slots. Separate chaining tolerates α above 1 without performance collapse, whereas open addressing requires α to stay below roughly 0.7 to remain practical. That headroom is why chaining is the default in many teaching languages and in C++'s unordered_map.

For readers comparing implementations across languages, the hello ML team has published companion pieces on balanced BSTs and tries that discuss similar trade-off tables. The patterns repeat across data structures. Amortised guarantees rely on occasional expensive operations such as resize or rotation being rare enough to be averaged out across thousands of calls.

Practical applications and an Australian flavour

Hash tables underpin countless systems that Australians interact with daily. Search-as-you-type on realestate.com.au uses a hash-backed index of suburb names so that typing "Mordialloc" returns results after the first three letters. Atlassian's Jira caches project metadata in hash structures to render dashboards in under a hundred milliseconds, and Canva uses them to look up design templates by ID when serving billions of rendered images each quarter.

Algorithms courses at QUT in Brisbane and RMIT in Melbourne frequently set hash table labs around building a small symbol table for a toy expression evaluator. The exercise surfaces real bugs: forgetting to handle the empty-string key, mishandling negative hash values from Python's hash(), or forgetting to rehash after a resize. Catching those issues in a controlled lab is far cheaper than chasing them in production.

Practitioner's notes on separate chaining

Tips that keep a custom hash table well-behaved:

• Use a load factor threshold between 0.6 and 0.8 to balance memory and collisions.
• Resize by doubling capacity when the threshold is reached and rehash every key.
• Store the key alongside the value to enable equality checks and safe deletion.
• Avoid hashing mutable objects, since updates change the hash and orphan entries.
• Test with adversarial inputs, including sorted keys and strings that differ only in trailing whitespace.

Patterns where chaining shines and when to reach for an alternative:

• Web session caches where keys arrive in unpredictable order and chains stay short.
• Symbol tables in compilers where insert and lookup dominate the workload.
• Small embedded libraries that cannot afford complex probing logic.
• Scenarios with strong locality of reference, where open addressing outperforms chaining.
• Applications needing bounded memory, since chaining can grow beyond α equals 1.
• Code running on hardware without a fast allocator, where chain node allocation is expensive.

The hands-on nature of building a hash table from scratch rewards persistence, and the small class above extends neatly into a complete interview-ready portfolio piece. From caching HTTP responses on a Tasmanian weather API to powering fast lookup for Melbourne tram timetables, the data structure appears wherever engineers need constant-time access keyed by arbitrary strings, integers or tuples.