Implementing Hash Maps with Chaining

Hello! Welcome to the first lesson of our new module, "Implementing Core Data Structures."

In the previous module, we focused on writing production-quality Python, culminating in a lesson that mapped your deep expertise in Rust's concurrency model to Python's threading and asyncio frameworks.

Today, we shift gears to a fundamental topic often encountered in software engineering interviews: building core data structures from scratch. This lesson directly addresses the learning outcome: Implement a hash map from scratch using chaining for collision resolution.

Building a hash map is a classic exercise that tests your understanding of data structures, algorithms, and trade-offs. For a role at a company like Anthropic, demonstrating a solid grasp of these fundamentals is just as important as your experience with large-scale systems.

In this lesson, we will:

1. Review the core principles of hash maps: hashing, buckets, and collisions.
2. Explore separate chaining as a collision resolution strategy.
3. Implement a HashTable class in Python from the ground up, with put, get, and remove operations.
4. Discuss the design trade-offs involved in our implementation choices.

Let's begin!

1. The Core Idea of a Hash Map

At its heart, a hash map (or hash table) is a data structure designed for fast key-value lookups, aiming for an average time complexity of O(1). It achieves this by cleverly using an array and a special function.

To get a clear overview of the concepts, let's watch a video that explains the problem hash maps solve and how they work at a high level.

As the video explains, the three core components are:

1. An Array: The underlying storage for our data. We'll use a Python list. Each slot in this list is often called a bucket.
2. A Hash Function: A function that converts a key of an arbitrary type into an integer hash code. We'll use Python's built-in hash() function.
3. A Collision Resolution Strategy: A method to handle cases where two different keys map to the same bucket index.

2. Collision Resolution with Separate Chaining

Collisions are a fact of life with hash maps. The pigeonhole principle guarantees that if you have more keys than available buckets, at least one bucket must contain more than one key. How we manage this is crucial.

There are two primary strategies:

• Open Addressing: When a collision occurs, we probe for the next empty slot in the array itself (e.g., linear probing).
• Closed Addressing (or Separate Chaining): We embrace the collision and store all keys that map to the same bucket together in a separate data structure within that bucket.

This lesson focuses on separate chaining. Each bucket in our array will point to another data structure—classically a linked list—that holds all the key-value pairs that have hashed to that index.

This image provides a great visual for the concept:

The logic for any operation (get, put, remove) becomes a two-step process:

1. Hash the key to find the correct bucket index.
2. Search through the data structure within that bucket to find, update, or remove the specific key.

Let's watch one more short video that demonstrates this chaining mechanism, which will set us up perfectly for our implementation.

3. Implementing a Hash Map from Scratch

Now, let's apply these concepts to build our own HashTable class. We'll do this incrementally, just as you might in an interview setting. Your background in Rust, where data structures like HashMap are built with generics and traits, provides a strong conceptual foundation. The structure we'll build, list[deque[tuple[K, V]]], is a direct Python parallel to the Vec<Vec<(K, V)>> structure described in the Rust hash table implementation you can find in the resource "Implement Hash Table in Rust | Implement Data Structures in ...".

Step 1: The Class Structure

First, let's define the skeleton of our HashTable. It needs an initializer that sets up the buckets. We'll use collections.deque as our linked list implementation for the buckets, as it's a highly optimized doubly-linked list provided by Python's standard library. For clarity, we'll also define a Pair using typing.NamedTuple to hold our key-value pairs.

from collections import deque
from typing import NamedTuple, Any

class Pair(NamedTuple):
    key: Any
    value: Any

class HashTable:
    def __init__(self, capacity: int = 8):
        if capacity < 1:
            raise ValueError("Capacity must be a positive number")
        self._capacity = capacity



        # A list of deques, where each deque is a bucket for chaining
        self._buckets = [deque() for _ in range(capacity)]

    def _get_bucket_index(self, key: Any) -> int:
        """Calculates the bucket index for a given key."""



        # Use Python's built-in hash() and the modulo operator
        return hash(key) % self._capacity

Key Points:

• We initialize _buckets as a list of empty deque objects. Each deque will store the Pair objects that collide at that index.
• The _get_bucket_index helper method encapsulates the hashing logic. A key must be hashable to be used in our hash table, which generally means it must be immutable. We'll explore this more in a later lesson.

Step 2: Implementing __setitem__ (Put/Insert)

The __setitem__ dunder method allows us to use the table[key] = value syntax. The logic must handle both new insertions and updates to existing keys.

# Add this method to your HashTable class

def __setitem__(self, key: Any, value: Any):
    """Inserts a key-value pair or updates the value of an existing key."""
    bucket_index = self._get_bucket_index(key)
    bucket = self._buckets[bucket_index]




    # Check if the key already exists in the bucket
    for i, pair in enumerate(bucket):
        if pair.key == key:



            # Update the existing pair
            bucket[i] = Pair(key, value)
            return




    # If the key is new, append it to the bucket
    bucket.append(Pair(key, value))

This implementation follows our two-step process: find the bucket, then iterate through it. If a matching key is found, we replace the Pair object; otherwise, we add a new one.

Step 3: Implementing __getitem__ (Get)

This method enables the value = table[key] syntax. It's similar to __setitem__ but retrieves a value and raises a KeyError if the key is not found, mimicking Python's built-in dict.

# Add this method to your HashTable class

def __getitem__(self, key: Any) -> Any:
    """Retrieves the value associated with a key."""
    bucket_index = self._get_bucket_index(key)
    bucket = self._buckets[bucket_index]




    # Search for the key in the bucket
    for pair in bucket:
        if pair.key == key:
            return pair.value




    # If the key is not found after checking the whole bucket
    raise KeyError(key)

Step 4: Implementing __delitem__ (Remove)

Finally, __delitem__ implements the del table[key] syntax. It finds the item and removes it from the deque.

# Add this method to your HashTable class

def __delitem__(self, key: Any):
    """Removes a key-value pair from the hash table."""
    bucket_index = self._get_bucket_index(key)
    bucket = self._buckets[bucket_index]
    



    # We need to find the pair to remove it.
    # A deque does not have a simple remove-by-value, so we rebuild it.
    for i, pair in enumerate(bucket):
        if pair.key == key:
            del bucket[i]
            return




    # If the key is not found
    raise KeyError(key)

Note on deque deletion: The del bucket[i] operation on a deque is O(N) where N is the length of the deque. While appends are O(1), indexed access and deletion are not. For the small number of items expected in a bucket (if our hash function is good), this is acceptable.

4. Code and Trade-offs

Here is the complete HashTable class so far:

from collections import deque
from typing import NamedTuple, Any

class Pair(NamedTuple):
    key: Any
    value: Any

class HashTable:
    def __init__(self, capacity: int = 8):
        if capacity < 1:
            raise ValueError("Capacity must be a positive number")
        self._capacity = capacity
        self._buckets = [deque() for _ in range(capacity)]

    def _get_bucket_index(self, key: Any) -> int:
        return hash(key) % self._capacity

    def __setitem__(self, key: Any, value: Any):
        bucket_index = self._get_bucket_index(key)
        bucket = self._buckets[bucket_index]
        for i, pair in enumerate(bucket):
            if pair.key == key:
                bucket[i] = Pair(key, value)
                return
        bucket.append(Pair(key, value))

    def __getitem__(self, key: Any) -> Any:
        bucket_index = self._get_bucket_index(key)
        bucket = self._buckets[bucket_index]
        for pair in bucket:
            if pair.key == key:
                return pair.value
        raise KeyError(key)

    def __delitem__(self, key: Any):
        bucket_index = self._get_bucket_index(key)
        bucket = self._buckets[bucket_index]
        for i, pair in enumerate(bucket):
            if pair.key == key:
                del bucket[i]
                return
        raise KeyError(key)
        
    def __str__(self):
        """A simple string representation for printing."""
        pairs = []
        for bucket in self._buckets:
            for pair in bucket:
                pairs.append(f"{repr(pair.key)}: {repr(pair.value)}")
        return "{" + ", ".join(pairs) + "}"

Let's discuss the trade-offs, a key focus for your learning:

• Chaining vs. Open Addressing:

  • Simplicity: Chaining is generally easier to implement, especially for deletion. Deleting from a linearly probed hash table requires "tombstone" markers to avoid breaking search chains, which adds complexity.
  • Performance Degradation: Chaining's performance degrades more gracefully. As the table fills, the linked lists simply get longer. Open addressing can suffer from clustering, where long runs of occupied slots form, causing lookups to devolve into a linear search over a large portion of the array.
  • Memory and Cache Performance: Open addressing stores all data directly in the main array, which can lead to better cache locality and performance if the table is not too full. Chaining requires pointer-chasing, which can be less cache-friendly.

• deque vs. list for Buckets:

  • We chose deque because it's conceptually a linked list, providing O(1) appends.
  • A Python list also offers O(1) amortized appends. However, removing an element from the start or middle of a list is an O(N) operation, whereas it is also O(N) for a deque. So for this specific implementation, the performance difference is minor, but deque better represents the classic "linked list" model of chaining.

Conclusion

Congratulations! You have successfully implemented a functional hash map from scratch using separate chaining. This exercise solidifies your understanding of one of the most important data structures in computer science.

Key Takeaways:

• A hash map is built from three components: an array (buckets), a hash function, and a collision resolution strategy.
• Separate chaining resolves collisions by storing all entries that hash to the same index in a separate data structure (like a deque or linked list) within that bucket.
• The core operations (__setitem__, __getitem__, __delitem__) all follow a two-step pattern: hash the key to find the bucket, then perform a linear search within that bucket.
• The implementation choices, such as chaining vs. open addressing, come with important trade-offs in complexity, memory usage, and performance characteristics.

Next Lesson

Our current implementation has a major limitation: its capacity is fixed. If we add too many items, the buckets will grow long, and performance will degrade from O(1) towards O(N).

In our next lesson, we will solve this by implementing a critical feature: Extend the hash map to support dynamic resizing based on a load factor, analyzing performance trade-offs. This will bring our implementation much closer to what you'd find in a production-ready library.