Day 2: Implement a Custom Chained Hash Map to Eliminate Key Collisions

The Problem: The Cost of Simple Arrays

In Day 1, you built an array-backed key-value store. It worked by mapping a key to an index using a simple hash function. But you likely noticed a fatal flaw: if two keys hash to the same index, the second one overwrites the first. In systems engineering, we call this a collision.

If you use a simple array for storage, you are forced to choose between two evils: a massive, memory-wasting array to keep collisions rare, or a small array that corrupts your data the moment two keys happen to produce the same hash. Real-world systems like Redis (in its dict implementation) or Java’s own HashMap solve this using Separate Chaining. Instead of storing the value directly in the array, we store a pointer to a linked list (a "bucket") that holds all entries sharing that same hash.

The Architecture: Buckets and Nodes

We are moving from a flat array to an array of heads. Each index in our array now points to a Node object. If a collision occurs, we simply append a new Node to the end of the existing chain at that index.

The Core Mechanism

When you perform a put(key, value), the system calculates the index, traverses the linked list at that index to see if the key already exists (to update it), and if not, appends a new node.

public class Node {
    final String key;
    String value;
    Node next;

    public Node(String key, String value) {
        this.key = key;
        this.value = value;
    }
}

This structure is a foundational trade-off. By chaining, we trade a small amount of memory (for the next pointers) for the ability to handle an arbitrary number of keys without data loss.

The Production Stakes: The Collision Attack

Why does this matter beyond simple correctness? In 2011, researchers demonstrated a Hash Denial of Service (DoS) attack. By crafting thousands of keys that all hashed to the same bucket, they turned a $O(1)$ lookup time into a $O(n)$ time. The CPU usage spiked to 100% as the system traversed long linked lists, effectively taking down the service. While we won't implement randomized hash seeding today, understanding that your hash map is a performance-critical data structure is the first step toward building resilient systems.

The Failure Demo: Observing the Overwrite

In our previous array-based system, if we inserted key1 (hash 5) and key2 (hash 5), key2 would silently delete key1. Today, you will break the system by forcing a collision and observing that both values persist.

Implementation Logic

Your put method must now handle the chain:

public void put(String key, String value) {
    int index = hash(key) % table.length;
    Node head = table[index];
    // Traverse to find existing key
    for (Node x = head; x != null; x = x.next) {
        if (x.key.equals(key)) {
            x.value = value; // Update
            return;
        }
    }
    // No match, prepend new node to the bucket
    table[index] = new Node(key, value, head);
}

Scaling Up

At a hyperscale level, we don't just use linked lists. Once a bucket exceeds a certain length (often 8), Java’s HashMap converts the linked list into a Red-Black Tree. This keeps lookups at $O(log n)$ even under heavy collision scenarios. For our AstraKV, we are sticking to linked lists to master the pointer mechanics before we introduce tree-based complexities in later modules.

Assignment

1. 1.Extend your AstraKV engine: Replace your String[] storage with a Node[] array.

2. 2.Implement Collision Handling: Update your put and get methods to traverse the linked list at the calculated index.

3. 3.Verify: Create a test case that inserts two keys with the same hash (e.g., keys that result in the same index via a custom mock hash function) and ensure both are retrievable.

Solution Hints

• Use a hash() function that returns a fixed value for testing purposes to guarantee a collision.

• Ensure your get() method follows the same traversal logic as put().

• If you find that get() returns null for the second key, you likely forgot to check the next pointers in the chain.