Hash Table with Chaining

1. The Core Architecture

As we discussed, separate chaining resolves collisions by placing all key-value pairs that hash to the same index into a linked list at that index.

Our implementation will have three main components:

1. HashNode<K, V>: A class representing a single node in our linked lists. It will hold the key, the value, and a reference to the next node.
2. A Bucket Array: This will be an ArrayList where each element acts as a "bucket." Each bucket will store the head of a linked list.
3. The MyHashMap<K, V> class: This will orchestrate everything, managing the bucket array and providing methods like put, get, and remove.

Here is a visual representation of what we're about to build:

2. A Step-by-Step Implementation Guide

The best way to understand how a hash map works is to build one. The following video provides an excellent, detailed walkthrough of creating a hash map in Java. We will follow its structure, and I will provide key code snippets and explanations along the way.

Step 1: Defining the HashNode and MyHashMap Structure

Based on the video, let's define our core classes. We'll use generics <K, V> to make our hash map type-safe, just like Java's standard HashMap.

The HashNode Class: This will be a private inner class because it's only relevant to our hash map's internal implementation.

// A node of the linked list chain
private class HashNode<K, V> {
    K key;
    V value;
    HashNode<K, V> next; // Reference to the next node in the chain

    public HashNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

The MyHashMap Class Structure: This is the main class. It will contain the bucket array and essential properties like the number of buckets (capacity) and the number of entries (size).

import java.util.ArrayList;

public class MyHashMap<K, V> {
    // bucketArray stores the heads of the linked lists
    private ArrayList<HashNode<K, V>> bucketArray;

    // The current capacity of the bucket array
    private int numBuckets;

    // The current number of key-value pairs in the map
    private int size;

    // Constructor
    public MyHashMap() {
        bucketArray = new ArrayList<>();
        numBuckets = 10; // Initial capacity
        size = 0;

        // Create empty chains (buckets)
        for (int i = 0; i < numBuckets; i++) {
            bucketArray.add(null);
        }
    }
    // ... methods will go here
}

As the video explains, initializing the ArrayList with nulls is crucial. It ensures that we can immediately use bucketArray.set(index, ...) without getting an IndexOutOfBoundsException.

Step 2: The Hash Function (getBucketIndex)

We need a private helper function to convert a key into an index for our bucketArray. This function encapsulates the two-step process:

1. Get the integer hashCode from the key object.
2. Compress this hash code into a valid index within the bounds of our numBuckets.

// This implements the hash function to find an index for a key
private int getBucketIndex(K key) {
    int hashCode = key.hashCode();
    // The modulo operator compresses the hash code to a valid index
    int index = hashCode % numBuckets;
    
    // hashCode() can be negative. We need a positive index.
    // Math.abs() can cause issues if hashCode is Integer.MIN_VALUE.
    // A safer way is to handle negative results directly.
    index = index < 0 ? index * -1 : index;

    return index;
}

Step 3: Implementing the get() Method

To retrieve a value, we first hash the key to find the correct bucket and then traverse the linked list in that bucket to find the exact key.

Here's the logic for the get(K key) method:

1. Find the index for the key using getBucketIndex().
2. Get the head of the linked list at that index.
3. Traverse the list. For each node, check if its key .equals() the key you're searching for.
4. If a match is found, return the node's value.
5. If you reach the end of the list without a match, the key isn't in the map, so return null.

public V get(K key) {
    int bucketIndex = getBucketIndex(key);
    HashNode<K, V> head = bucketArray.get(bucketIndex);

    // Search for the key in the chain
    while (head != null) {
        if (head.key.equals(key)) {
            return head.value;
        }
        head = head.next;
    }

    // If key not found
    return null;
}

This highlights the famous hashCode() and equals() contract in Java. For a custom object to work correctly as a key in a HashMap, you must override both methods: if two objects are equal according to .equals(), they must have the same hashCode().

Step 4: Implementing the put() Method

Adding a key-value pair follows a similar logic, with two possible outcomes:

1. If the key already exists, we update its value.
2. If the key is new, we add a new node to the front of the linked list in the appropriate bucket.

Here is the implementation of put(K key, V value):

public void put(K key, V value) {
    int bucketIndex = getBucketIndex(key);
    HashNode<K, V> head = bucketArray.get(bucketIndex);

    // Check if key is already present
    while (head != null) {
        if (head.key.equals(key)) {
            head.value = value; // Update the value and return
            return;
        }
        head = head.next;
    }

    // If key not found, insert it at the head of the chain
    size++;
    head = bucketArray.get(bucketIndex);
    HashNode<K, V> newNode = new HashNode<>(key, value);
    newNode.next = head; // New node points to the old head
    bucketArray.set(bucketIndex, newNode); // Bucket now points to the new node
}

3. Keeping Performance High: Rehashing

Our hash map works, but what happens if we add many elements? The linked lists will get longer, and our get() and put() operations will slow down from $O(1)$ towards $O(N)$. To prevent this, we introduce the concept of a load factor and rehashing.

• Load Factor: A measure of how full the hash table is.
  $\text{Load Factor}(\lambda )=\frac{\text{size}}{\text{numBuckets}}=\frac{\text{Number of entries}}{\text{Total number of buckets}}$
• Rehashing: When the load factor exceeds a certain threshold (e.g., 0.7), we create a new, larger bucket array (usually doubling the size) and re-insert all existing entries into it. This redistributes the entries and keeps the chains short.

To implement rehashing, we modify our put() method. After adding a new element, we check the load factor.

public void put(K key, V value) {
    // ... (logic from before to find/update or add new node)

    // Insert key in chain (same as before)
    size++;
    // ... (rest of the insertion logic) ...

    // If load factor goes beyond threshold, then double hash table size
    if ((1.0 * size) / numBuckets >= 0.7) {
        rehash();
    }
}

private void rehash() {
    System.out.println("Rehashing, size: " + size + ", numBuckets: " + numBuckets);
    ArrayList<HashNode<K, V>> temp = bucketArray;
    bucketArray = new ArrayList<>();
    numBuckets = 2 * numBuckets;
    size = 0; // The put method will increment this again
    for (int i = 0; i < numBuckets; i++) {
        bucketArray.add(null);
    }

    for (HashNode<K, V> headNode : temp) {
        while (headNode != null) {
            // Re-insert every node into the new, larger bucket array
            put(headNode.key, headNode.value);
            headNode = headNode.next;
        }
    }
}

Important Note: In the rehash method, when we iterate through the old nodes, we call our existing put() method. The put() method will automatically calculate the new correct index for each key based on the doubled numBuckets and place it in the new bucketArray.

For a complete, well-commented code example, you can also refer to this article. It presents the same logic in a textual format.

Conclusion

Congratulations! You've just walked through the complete implementation of a hash map using separate chaining, a fundamental data structure. This is a significant milestone that moves you from being a user of hash maps to understanding how they are built.

Key Takeaways:

• A hash map is built on an array of buckets, where each bucket is the head of a linked list to handle collisions.
• The process involves a HashNode for the list, a getBucketIndex function to map keys to array indices, and the core get() and put() methods.
• Proper key comparison requires using the .equals() method, relying on the equals() and hashCode() contract.
• To maintain $O(1)$ average performance, the hash map monitors its load factor and performs rehashing (resizing and re-inserting all elements) when it gets too full.

Preview of the Next Lesson:
Now that you have a deep understanding of how hash maps work internally, you're perfectly equipped to wield them effectively. In the next lesson, we will focus on applying hash maps to solve common interview problems, such as "Two Sum" and "Subarray Sum Equals K," leveraging the power of constant-time lookups to create highly efficient solutions.