How do I actually map a key to a specific array index?

This is the "magic" of the hash table, but it's actually pretty straightforward. You start with a fixed-size array (I usually call these "buckets"). To figure out where a key goes, you take the key's hash code—which in Java is provided by the hashCode() method—and constrain it to the size of your array using the modulo operator (%).

Here is a quick look at how I'd handle the index calculation. I use Math.abs() because hashCode() can return negative integers, and you can't have a negative array index.

int bucketIndex = Math.abs(key.hashCode()) % buckets.length;

One thing to keep in mind: if your array size is a prime number, you'll generally get a better distribution of keys, which means fewer collisions. It's a small detail, but it's the kind of thing that separates a "working" implementation from an "efficient" one.

What happens when two different keys end up at the same index?

In the real world, collisions are inevitable. Two different strings will eventually hash to the same index. The most common way to handle this is called "Separate Chaining." Instead of storing the value directly in the array, you store a linked list of entries at that index.

I usually define a small private Entry class to hold the key-value pair and a reference to the next entry in the chain. When you put a value, you check the list at that index. If the key already exists, you update the value. If it doesn't, you just tack a new entry onto the head of the list.

class Entry<K, V> {
    K key;
    V value;
    Entry<K, V> next;

    Entry(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

// Inside the put method:
int index = Math.abs(key.hashCode()) % buckets.length;
Entry<K, V> head = buckets[index];

while (head != null) {
    if (head.key.equals(key)) {
        head.value = value; // Update existing key
        return;
    }
    head = head.next;
}

// No existing key found, insert new entry at the front
Entry<K, V> newEntry = new Entry<>(key, value);
newEntry.next = buckets[index];
buckets[index] = newEntry;

How do I stop the table from slowing down as it fills up?

If you keep adding elements to a small array, your linked lists will get longer and longer. Eventually, your O(1) lookup time degrades into O(n), which defeats the whole purpose of using a hash table. To fix this, we use a "Load Factor"—typically 0.75.

Once the number of elements exceeds 75% of the array's capacity, you need to resize. But you can't just copy the array over. Because the index is calculated using % buckets.length, changing the length changes the index for every single item. You have to "rehash" every single element into a new, larger array.

private void resize() {
    Entry<K, V>[] oldBuckets = buckets;
    buckets = new Entry[oldBuckets.length * 2];
    size = 0; // Reset size because put() will increment it

    for (Entry<K, V> head : oldBuckets) {
        while (head != null) {
            put(head.key, head.value); // Re-insert into the new array
            head = head.next;
        }
    }
}

I'll admit, rehashing is expensive, but since it happens infrequently (logarithmically), the average cost per operation stays constant.

📋 Practical Task

Exercise: Building a Cached Employee Directory with Dynamic Resizing

You need to implement a custom EmployeeCache class from scratch that mimics a hash table. The cache should map an Employee ID (String) to an Employee Name (String).

Requirements:

• Implement a put(String id, String name) method that handles collisions using separate chaining.
• Implement a get(String id) method that returns the name or null if not found.
• Implement a resize() mechanism that triggers when the load factor reaches 0.75.
• Start with an initial bucket array size of 4.

Test Scenario: Insert 6 employees with IDs that you know (or suspect) will cause collisions. Verify that the resize() method is called and that you can still retrieve all 6 employees correctly after the table has expanded.