Hash Tables Data Structure — Complete Guide

What is a Hash Table?

A Hash Table (or Hash Map) is a data structure that implements an associative array abstract data type, mapping Keys to Values. It uses a Hash Function to compute an index into an array of buckets/slots, from which the desired value can be found in O(1) Average Time Complexity.

Key ("apple") ──→ [ Hash Function ] ──→ Index (4) ──→ Bucket [4]: "Fruit"
Key ("carrot") ──→ [ Hash Function ] ──→ Index (1) ──→ Bucket [1]: "Vegetable"

Hash Functions & Collision Resolution

A Collision occurs when two distinct keys hash to the exact same array index.

1. Separate Chaining (Linked List Buckets)

Each bucket in the array stores a pointer to a Linked List (or dynamic array) of all key-value pairs that hash to that index.

Index 2: [ ("cat", 1) ] ──→ [ ("act", 4) ] ──→ Null

2. Open Addressing

All key-value pairs are stored directly in the table array. When a collision occurs, probe for an alternative empty slot:

• Linear Probing: Check (hash + 1), (hash + 2), (hash + 3)...
• Quadratic Probing: Check (hash + 1²), (hash + 2²), (hash + 3²)...
• Double Hashing: Use a second hash function hash2(key) to determine jump step size.

Load Factor & Rehashing

Load Factor (α) = Total Elements (n) / Table Capacity (k) When α exceeds a threshold (typically 0.75), the Hash Table automatically allocates a new array of double size and rehashes all existing key-value pairs into the new table.

Solved Problem 1: Two Sum 🟢 Easy

Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

javascript
function twoSum(nums, target) {
    const map = new Map(); // key: number, value: index

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (map.has(complement)) {
            return [map.get(complement), i];
        }

        map.set(nums[i], i);
    }

    return [];
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

Time: O(N) | Space: O(N)

Solved Problem 2: Group Anagrams 🟡 Medium

Problem: Given an array of strings strs, group the anagrams together.

javascript
function groupAnagrams(strs) {
    const map = new Map();

    for (const str of strs) {
        // Character count array key for 26 lowercase English letters
        const count = new Array(26).fill(0);
        for (const char of str) {
            count[char.charCodeAt(0) - 97]++;
        }
        
        const key = count.join('#'); // Unique key representation

        if (!map.has(key)) map.set(key, []);
        map.get(key).push(str);
    }

    return Array.from(map.values());
}

Time: O(N × K) where N is number of strings, K is max string length | Space: O(N × K)

Frequently Asked Questions

Q: What is the worst-case time complexity of a Hash Table?
A: O(N). If all keys hash to the exact same index (a malicious Hash DoS attack or poor hash function), Chaining degrades to a single Linked List scan of N elements.

Q: How does ES6 Map differ from plain JavaScript Object?
A: ES6 Map allows keys of any data type (objects, functions, primitives), maintains insertion order, and provides built-in .size property. JS Object keys are limited to Strings and Symbols.