Hash Table with Separate Chaining

1. From Keys to Array Indices: The Idea of Hashing

Imagine you have a large collection of key-value pairs (like a phonebook with names and numbers). If you stored them in a simple list, finding a person's number would require searching through the list one by one, which is an O(n) operation.

A hash table speeds this up dramatically. The core idea is to use a special function, called a hash function, to convert any given key into an integer index. This index tells us exactly where in an underlying array (or list in Python) to store the corresponding value.

Key → Hash Function → Array Index

For example, if we have an array of size 10, a simple hash function for integer keys could be hash(key) = key % 10.

• To store the pair (key=23, value='apple'), we compute 23 % 10 = 3. So, 'apple' goes into index 3 of our array.
• To search for key 23, we just compute the hash 23 % 10 = 3 and look directly at index 3. This is an O(1) operation!

But what happens if we then want to store (key=13, value='banana')? We compute 13 % 10 = 3. Now two different keys want to occupy the same slot. This is called a collision.

2. Collision Resolution with Separate Chaining

A good hash function minimizes collisions, but we must have a strategy to handle them when they occur. The most intuitive strategy is Separate Chaining.

Instead of storing a single value at each array index, we store a data structure that can hold multiple key-value pairs. The simplest choice for this is a linked list.

When a collision occurs, we simply add the new key-value pair to the linked list at that array index.

To understand this concept visually and see how it works step-by-step, the following video provides a clear, language-independent explanation.

3. Implementing a Hash Table in Python

Now, let's translate this idea into Python code. For simplicity and to leverage Python's built-in features, we can use a standard Python list at each index instead of building a formal linked list from scratch. Each "bucket" in our hash table will be a list containing (key, value) tuples.

Our HashTable class will look like this:

• __init__(self, size): Initializes an array (a list of empty lists) of a given size.
• _get_hash(self, key): A private method to compute the array index for a given key.
• __setitem__(self, key, value): For inserting or updating a value (used like my_table[key] = value).
• __getitem__(self, key): For retrieving a value (used like my_table[key]).
• __delitem__(self, key): For deleting a key-value pair (used like del my_table[key]).

The following video from the codebasics channel provides an excellent walkthrough of building this exact class. We'll use it as our guide.

Putting It All Together: The Code

Here is the complete Python code for our HashTable class, inspired by the video. Note how each method first calculates the hash to find the correct "bucket" (the list at that index) and then performs a simple linear search within that small list.

class HashTable:
    def __init__(self, size=10):
        self.size = size
        # Initialize the table with empty lists at each index
        self.table = [[] for _ in range(self.size)]

    def _get_hash(self, key):
        # A simple hash function using Python's built-in hash()
        return hash(key) % self.size

    def __setitem__(self, key, value):
        """Inserts or updates a key-value pair."""
        h = self._get_hash(key)
        found = False
        
        # Search the chain (the list at the hashed index)
        for idx, element in enumerate(self.table[h]):
            # If key is found, update the value and exit
            if len(element) == 2 and element[0] == key:
                self.table[h][idx] = (key, value)
                found = True
                break
        
        # If key was not found, append the new (key, value) pair
        if not found:
            self.table[h].append((key, value))

    def __getitem__(self, key):
        """Retrieves the value for a given key."""
        h = self._get_hash(key)
        
        # Search the chain for the key
        for element in self.table[h]:
            if element[0] == key:
                return element[1] # Return the value
        
        # If the key is not found after searching the chain
        raise KeyError(key)

    def __delitem__(self, key):
        """Deletes a key-value pair."""
        h = self._get_hash(key)
        
        # Search the chain for the element to delete
        for idx, element in enumerate(self.table[h]):
            if element[0] == key:
                # Remove the (key, value) tuple from the list
                del self.table[h][idx]
                return
        
        # If the key is not found after searching the chain
        raise KeyError(key)

# --- Let's test our Hash Table ---
t = HashTable()

# Insert some values
t['march 6'] = 120
t['march 8'] = 67
t['march 9'] = 4
t['march 17'] = 459 # This will likely cause a collision with 'march 6'

print("Internal state of the table after insertions:")
print(t.table)

# Retrieve a value
print("\nValue for 'march 6':", t['march 6'])    # Should be 120
print("Value for 'march 17':", t['march 17'])  # Should be 459

# Update a value
t['march 6'] = 78
print("\nUpdated value for 'march 6':", t['march 6']) # Should be 78

# Delete a value
del t['march 17']
print("\nInternal state after deleting 'march 17':")
print(t.table)

# Try to access a deleted key (will raise KeyError)
try:
    print(t['march 17'])
except KeyError:
    print("\nCorrectly raised KeyError for 'march 17'.")

[
  [('apple', 1), ('grape', 3)],  # Index 0
  [('banana', 2)],              # Index 1
  [],                           # Index 2
  [('fig', 4)],                  # Index 3
  []                            # Index 4
]

4. Performance Considerations

• Best/Average Case: If your hash function distributes keys evenly, the chains (lists) at each index will be very short. Finding an element becomes an O(1) operation: one hash calculation and a search through a tiny list.
• Worst Case: If you have a terrible hash function that maps every key to the same index, your hash table degenerates into a single long linked list. In this scenario, insertion, search, and deletion all become O(n) operations, as you have to traverse the entire list. This is why a good hash function is so important!

Conclusion

Excellent work! You have now implemented one of the most important data structures in computer science. Hash tables are a brilliant example of a space-time tradeoff: we use extra memory (the array) to gain a huge speed advantage for accessing data.

Key Takeaways:

• A hash table maps keys to array indices using a hash function for fast lookups.
• Collisions occur when multiple keys map to the same index.
• Separate Chaining is a collision resolution strategy where each array slot points to a list (or other collection) of all key-value pairs that hashed to that index.
• With a good hash function, the average time complexity for insert, search, and delete is O(1).
• The worst-case time complexity is O(n), which occurs when many keys collide.

Preview of the Next Lesson:

We will continue our journey through core data structures by looking at another specialized tree structure. In the next lesson, you will implement a heap and use it to build a priority queue. Heaps are essential for efficiently managing and retrieving items with the highest (or lowest) priority, a common requirement in many algorithms and systems.