Cracking The Coding Interview Together – Problem 7.12: Hash Table

If you ask any software engineer to name a data structure that offers constant-time average operations, the instant answer is almost always the Hash Table. We rely on key-value lookups everywhere—from high-performance local caches to object relational mapping libraries and database indexing engine layers. However, the promise of true O(1) lookup performance relies on an elegant mathematical abstraction masking a messy physical reality.

Under the hood, physical computer memory is a contiguous linear array of bytes. But the universe of possible keys we want to store—strings, UUIDs, complex domain objects—is practically infinite. When we compress an infinite domain of keys into a finite array of buckets, two distinct keys will inevitably map to the exact same array index. This fundamental conflict is known as a hash collision.

How we handle collisions determines whether our Hash Table remains a blistering O(1) lookup engine or degrades into a sluggish O(N) linear scan. In this article, we are going to roll up our sleeves and build a production-grade, generic Hash Table from scratch using Separate Chaining. Along the way, we will dissect load factors, resizing strategies, dynamic bucket rehashing, and real-world system considerations.

Problem Statement

Design and implement a generic Hash Table data structure from scratch using Separate Chaining for collision handling. Your implementation should support key-value pair storage and expose the following public API operations:

• put(K key, V value): Inserts a key-value pair into the table. If the key already exists, updates its associated value.
• get(K key): Retrieves the value mapped to the given key, or returns null if the key does not exist.
• remove(K key): Removes the key-value pair associated with the key and returns its value (or null if absent).
• size(): Returns the total count of key-value pairs stored in the table.

Operational Requirement: The table must automatically resize (rehash) itself when the ratio of stored elements to total buckets exceeds a predefined load factor threshold (e.g., 0.75), preserving average O(1) operation bounds.

Analyze the Problem Together

Before writing a single line of code, we need to carefully weigh our architectural options for handling collisions. When two keys yield the same bucket index, we primarily have two paths forward: Open Addressing or Separate Chaining.

We are selecting Separate Chaining because of its flexibility and clean separation of concerns. In our architecture, the primary backing array contains head pointers to linked lists of key-value entries.

Here comes our crucial "Aha!" realization: Separate chaining alone does not guarantee O(1) lookup times! If we fix our array capacity to 16 buckets and insert 1,000,000 keys, average bucket length grows to 62,500 entries. Every lookup would turn into a 62,500-step linear search! To protect our constant-time operations, we must maintain a low ratio between elements ($N$) and bucket capacity ($C$). This ratio is called the Load Factor ($ \alpha = N / C$). Whenever $\alpha$ exceeds a threshold like 0.75, we must double our capacity and rehash all elements.

Questions for the Interviewer

When tasked with designing a core data structure in a system design or technical coding interview, always ask clarifying engineering questions to refine your scope:

1. How should we handle null keys or null values?
   Clarification: Java's standard HashMap allows one null key, whereas Hashtable prohibits nulls entirely. For clarity, we will disallow null keys in our implementation.
2. What hashing function should we rely on?
   Clarification: We can leverage Java's native Object.hashCode() method, but we must account for negative integer values returned by raw hash algorithms.
3. Do we need thread-safety or concurrent access guarantees?
   Clarification: We will focus on single-threaded correctness first, and then discuss lock-granularity and concurrency patterns in our architectural summary.
4. What initial capacity and load factor threshold should we target?
   Clarification: Standard production defaults are an initial capacity of 16 buckets and a target load factor of 0.75.

Think About the Solution

Let's map out our object model and architectural design step-by-step.

Core Components

• HashNode<K, V>: A private static inner class representing a key-value entry node. Each node stores K key, V value, the calculated int hash, and a HashNode<K, V> next pointer to form the bucket's collision chain.
• Bucket Array: An internal array HashNode<K, V>[] buckets initialized to default initial capacity (16).
• Index Mapping Logic: To convert a raw key hash into a valid array index safely, we strip the sign bit and apply modulo arithmetic: (key.hashCode() & 0x7fffffff) % capacity. Alternatively, using power-of-two capacities allows bitwise masking: hash & (capacity - 1).
• Dynamic Rehash Engine: A private resize() method triggered when size >= capacity * loadFactor. It allocates a new array with double the capacity and re-inserts every node into its updated bucket index.

Key Edge Cases to Guard Against

• Updating values for existing keys without creating redundant nodes.
• Removing nodes at the very head of a bucket chain versus middle/tail nodes.
• Handling hash code collisions for distinct non-equal keys mapping to identical bucket indices.
• Rehashing empty buckets safely during map expansion.

Write Code and Explain

Here is our complete, production-ready Java implementation of a Hash Table with separate chaining:

package com.devlearnings.datastructures;

import java.util.Objects;

/**
 * A custom Hash Table implementation using Separate Chaining for collision resolution.
 *
 * @param <K> Key type
 * @param <V> Value type
 */
public class MyHashTable<K, V> {

    // Private inner node representing a key-value pair in a collision chain
    private static class HashNode<K, V> {
        final K key;
        V value;
        final int hash;
        HashNode<K, V> next;

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

    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private HashNode<K, V>[] buckets;
    private int capacity;
    private int size;
    private final float loadFactor;

    @SuppressWarnings("unchecked")
    public MyHashTable(int initialCapacity, float loadFactor) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("Initial capacity must be greater than zero.");
        }
        if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Load factor must be a positive float.");
        }
        this.capacity = initialCapacity;
        this.loadFactor = loadFactor;
        this.size = 0;
        this.buckets = (HashNode<K, V>[]) new HashNode[capacity];
    }

    public MyHashTable() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Maps key hash code to a valid array bucket index.
     */
    private int getBucketIndex(K key) {
        int hashCode = key.hashCode();
        // Mask out sign bit to prevent negative indices
        return (hashCode & 0x7fffffff) % capacity;
    }

    /**
     * Associates the specified value with the specified key in this hash table.
     */
    public void put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("Null keys are not supported.");
        }

        int bucketIndex = getBucketIndex(key);
        int hash = key.hashCode();
        HashNode<K, V> head = buckets[bucketIndex];

        // Step 1: Search if key already exists in the chain
        HashNode<K, V> current = head;
        while (current != null) {
            if (current.hash == hash && Objects.equals(current.key, key)) {
                current.value = value; // Update existing value
                return;
            }
            current = current.next;
        }

        // Step 2: Insert new node at the head of the chain (O(1) insertion)
        HashNode<K, V> newNode = new HashNode<>(key, value, hash);
        newNode.next = head;
        buckets[bucketIndex] = newNode;
        size++;

        // Step 3: Trigger dynamic resizing if load factor threshold is breached
        if ((float) size / capacity >= loadFactor) {
            resize();
        }
    }

    /**
     * Returns the value mapped to the specified key, or null if absent.
     */
    public V get(K key) {
        if (key == null) return null;

        int bucketIndex = getBucketIndex(key);
        int hash = key.hashCode();
        HashNode<K, V> current = buckets[bucketIndex];

        while (current != null) {
            if (current.hash == hash && Objects.equals(current.key, key)) {
                return current.value;
            }
            current = current.next;
        }

        return null;
    }

    /**
     * Removes the key-value pair for the given key.
     */
    public V remove(K key) {
        if (key == null) return null;

        int bucketIndex = getBucketIndex(key);
        int hash = key.hashCode();
        HashNode<K, V> current = buckets[bucketIndex];
        HashNode<K, V> previous = null;

        while (current != null) {
            if (current.hash == hash && Objects.equals(current.key, key)) {
                if (previous != null) {
                    previous.next = current.next;
                } else {
                    buckets[bucketIndex] = current.next; // Removing head
                }
                size--;
                return current.value;
            }
            previous = current;
            current = current.next;
        }

        return null;
    }

    /**
     * Doubles the internal bucket capacity and re-hashes all existing entries.
     */
    @SuppressWarnings("unchecked")
    private void resize() {
        int oldCapacity = capacity;
        HashNode<K, V>[] oldBuckets = buckets;

        this.capacity = oldCapacity * 2;
        this.buckets = (HashNode<K, V>[]) new HashNode[capacity];
        this.size = 0; // Will be incremented during re-insertion

        for (int i = 0; i < oldCapacity; i++) {
            HashNode<K, V> head = oldBuckets[i];
            while (head != null) {
                // Re-insert into expanded bucket array
                put(head.key, head.value);
                head = head.next;
            }
        }
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

Code Walkthrough

1. Index Calculation (getBucketIndex): Bitwise masking with 0x7fffffff strips out the signed negative bit from the key's native integer hash. Applying the modulo operator bounded by current array capacity yields a safe array index.
2. Prepend Insertion Strategy (put): When adding a new node, we insert it at the head of the bucket's linked list in $O(1)$ time rather than traversing to the end of the list.
3. Singly Linked Removal Logic (remove): We maintain a previous tracking reference as we traverse down the chain. If the target entry resides at the bucket head (previous == null), we update the array slot pointer directly; otherwise, we unlink the node by routing previous.next = current.next.
4. Dynamic Expansion (resize): When the element count crosses capacity * loadFactor, we allocate an array of double the size and re-process every node. This redistributes chain elements across the wider index space.

Time & Space Complexity

Let's analyze the time and space metrics for our data structure:

• Put Operation:
  • Average Case: $O(1)$ amortized time. Searching a short collision chain is $O(1)$ assuming uniform distribution. Resizing costs $O(N)$ when triggered, but amortizes across $N$ prior operations to $O(1)$.
  • Worst Case: $O(N)$ if all keys produce identical hash codes and map to a single bucket chain.
• Get Operation:
  • Average Case: $O(1)$ time.
  • Worst Case: $O(N)$ full chain scan.
• Remove Operation:
  • Average Case: $O(1)$ time.
  • Worst Case: $O(N)$ full chain scan.
• Space Complexity: $O(N + C)$ where $N$ is total key-value entries and $C$ is array bucket capacity. Each entry node incurs small fixed object heap allocation overhead.

Why This Problem Matters (The Senior Perspective)

Understanding native hash table construction is essential for high-level system architecture and performance engineering. Consider these production insights:

Java 8+ Optimization: Red-Black Trees (Treeification)

In standard Java 8 java.util.HashMap, when a single bucket linked list exceeds 8 nodes (and total table capacity is at least 64), Java dynamically converts that specific collision chain from a singly linked list into a balanced Red-Black Tree. This optimization elevates worst-case runtime from $O(N)$ down to $O(\log N)$, neutralizing performance degradation from poor key hash distributions.

Denial of Service Attacks (HashDoS)

Without balanced tree fallback mechanisms, bad actors can exploit predictable hash algorithms by issuing thousands of HTTP request parameters specifically crafted to produce matching hash codes. This triggers $O(N^2)$ algorithmic complexity on the server, spiking CPU usage to 100% and taking down application nodes. Modern languages employ randomized hash seeds to mitigate this vulnerability.

Concurrency & Locks

Our implementation is non-thread-safe. In high-throughput distributed systems, wrapping the entire table in a single global lock (like legacy Hashtable) introduces severe lock contention. Modern frameworks use lock striping (e.g., ConcurrentHashMap), applying fine-grained atomic Compare-And-Swap (CAS) instructions or individual bucket locks to allow simultaneous reads and writes across different buckets.

Final Thoughts

Building a Hash Table from scratch demystifies one of computer science's most important abstraction layers. By combining an indexed backing array with separate chaining linked lists and dynamic rehashing, we maintain constant-time lookup guarantees even as data sets grow.

Next Challenge for You: How would you extend our implementation to support JDK 8's dynamic treeification? Try replacing `HashNode` with a binary tree node structure once chain lengths exceed a fixed threshold!

Keep coding, keep building, and we'll see you in the next installment of The Dev Learnings!