When people first start talking about hash tables, they often fall into the trap of thinking the hash function is a magic wand that tells the computer exactly which index to use. They assume that hash("username") returns a neat little number like 4 or 12, and we just pop that value straight into an array. It seems intuitive, but if you try to actually code it that way, your program will crash almost immediately.

The 'Magic Index' Fallacy

Let's look at why that intuition fails. If you open a Python REPL and type hash("my_key"), you aren't going to get a small index. You're going to get something like -742839104723948102. Now, try to use that as an index for a list of size 10: my_list[-742839104723948102]. You'll get an IndexError instantly. The hash function's job isn't to find a slot; its job is to turn an arbitrary piece of data into a large, unique-ish integer. It's up to us to map that giant number down to a range our array can actually handle.

Taming the Hash with Modulo and Chaining

To bridge the gap between a massive hash integer and a small array, we use the modulo operator (%). By taking hash(key) % array_size, we force that giant number into a range from 0 to array_size - 1. I'll be honest: this is where things get messy. Because we are squeezing a near-infinite number of possible keys into a small number of slots, two different keys will eventually result in the same index. This is called a collision.

The most reliable way to handle this is "Separate Chaining." Instead of storing the value directly at the index, we store a small list (a "bucket") at that index. If two keys land on the same spot, they just both live in that bucket as key-value pairs. When you want to retrieve a value, you go to the bucket and do a quick linear search for the specific key. It sounds inefficient, but as long as your array is reasonably sized, these buckets stay tiny.

Building the Actual Engine

Here is how I would implement this. Notice that I'm initializing the table with a fixed size. In a production environment, you'd resize the table when it gets too full, but for our purposes, we'll keep the size static to focus on the mechanics of hashing and chaining.

class SimpleHashTable:
    def __init__(self, capacity=10):
        self.capacity = capacity
        # Create a list of empty lists (our buckets)
        self.table = [[] for _ in range(self.capacity)]

    def _get_index(self, key):
        # This is the critical step: mapping the hash to our array size
        return hash(key) % self.capacity

    def put(self, key, value):
        index = self._get_index(key)
        bucket = self.table[index]
        
        # Check if the key already exists in the bucket to update it
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        
        # Otherwise, append the new key-value pair to the bucket
        bucket.append((key, value))

    def get(self, key):
        index = self._get_index(key)
        bucket = self.table[index]
        
        for k, v in bucket:
            if k == key:
                return v
        
        raise KeyError(f"Key '{key}' not found in hash table")

# Example usage:
my_store = SimpleHashTable(5)
my_store.put("email", "dev@example.com")
my_store.put("username", "python_pro")
print(my_store.get("email")) # Output: dev@example.com

If you look closely at the put method, we aren't just blindly adding data. We have to scan the bucket first. If we didn't, we'd end up with duplicate keys in the same bucket, and get would always return the oldest version of the data rather than the most recent update.

📋 Practical Task

Implementing a Custom DNS Cache with Collision Handling

In this exercise, you will build a specialized version of a hash table designed to act as a DNS (Domain Name System) cache. Your goal is to create a class DNSCache that maps domain names (e.g., "google.com") to IP addresses (e.g., "142.250.190.46").

Requirements:

• Initialize the cache with a fixed capacity of 8 slots.
• Implement a set_entry(domain, ip) method that handles collisions using separate chaining.
• Implement a resolve(domain) method that returns the IP address if it exists, or the string "NXDOMAIN" (Non-Existent Domain) if the domain is not found.
• Include a debug_print() method that prints the entire internal table structure so you can see exactly which domains ended up in which buckets.

Test Case: Add at least 12 different domains to your cache. Because your capacity is only 8, you must trigger collisions. Use debug_print() to verify that some buckets contain multiple domain-IP pairs.