Hash Table

What is a Hash Table?

A hash table (also called hash map or dictionary) is a data structure that maps keys to values using a hash function. The hash function converts a key into an array index, enabling near-instant lookup, insertion, and deletion.

Think of a hash table like a library catalog â€” instead of searching every shelf, you look up the book's code and go directly to the right shelf.

How Hashing Works

Hash function â€” converts key to an integer index: index = hash(key) % tableSize
Store â€” place value at that index in the array
Retrieve â€” compute hash again to find the index instantly
Collision handling â€” when two keys hash to the same index

Operation	Average	Worst Case
Search	O(1)	O(n) â€” all keys collide
Insert	O(1)	O(n)
Delete	O(1)	O(n)

Hash Table â€” Built-in and Custom Implementation

#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int main() {
    // unordered_map â€” hash map, O(1) average
    unordered_map<string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"]   = 87;
    scores["Carol"] = 92;

    // Access
    cout << "Alice: " << scores["Alice"] << endl;  // 95

    // Check existence
    if (scores.count("Bob")) cout << "Bob exists" << endl;
    if (scores.find("Dave") == scores.end()) cout << "Dave not found" << endl;

    // Iterate
    for (auto& [name, score] : scores) {
        cout << name << ": " << score << endl;
    }

    // Erase
    scores.erase("Bob");
    cout << "Size: " << scores.size() << endl;  // 2

    // unordered_set â€” hash set
    unordered_set<int> seen;
    seen.insert(1); seen.insert(2); seen.insert(1);  // duplicates ignored
    cout << "Set size: " << seen.size() << endl;  // 2

    // Application: frequency count
    string text = "hello world hello";
    unordered_map<string, int> freq;
    // (split by space and count)

    return 0;
}

import java.util.*;

public class HashTableDemo {
    public static void main(String[] args) {
        // HashMap â€” hash map, O(1) average
        HashMap<String, Integer> scores = new HashMap<>();
        scores.put("Alice", 95);
        scores.put("Bob",   87);
        scores.put("Carol", 92);

        // Access
        System.out.println("Alice: " + scores.get("Alice"));  // 95

        // Check existence
        System.out.println(scores.containsKey("Bob"));    // true
        System.out.println(scores.containsValue(92));     // true

        // getOrDefault â€” safe access
        int dave = scores.getOrDefault("Dave", 0);
        System.out.println("Dave: " + dave);  // 0

        // Iterate
        for (Map.Entry<String, Integer> e : scores.entrySet()) {
            System.out.println(e.getKey() + ": " + e.getValue());
        }

        // Remove
        scores.remove("Bob");

        // HashSet
        HashSet<Integer> seen = new HashSet<>();
        seen.add(1); seen.add(2); seen.add(1);
        System.out.println("Set: " + seen);  // [1, 2]

        // Application: Two Sum
        int[] arr = {2, 7, 11, 15};
        int target = 9;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int complement = target - arr[i];
            if (map.containsKey(complement)) {
                System.out.println("[" + map.get(complement) + ", " + i + "]");
            }
            map.put(arr[i], i);
        }
    }
}

# Python dict â€” built-in hash map
scores = {"Alice": 95, "Bob": 87, "Carol": 92}

# Access
print("Alice:", scores["Alice"])  # 95
print("Dave:", scores.get("Dave", 0))  # 0 (default)

# Check existence
print("Bob" in scores)   # True
print("Dave" in scores)  # False

# Iterate
for name, score in scores.items():
    print(f"{name}: {score}")

# Update and delete
scores["Alice"] = 98
del scores["Bob"]
print("Size:", len(scores))  # 2

# set â€” hash set
seen = {1, 2, 3, 1, 2}  # duplicates removed
print("Set:", seen)  # {1, 2, 3}

# Counter â€” frequency map
from collections import Counter, defaultdict

text = "hello world hello"
freq = Counter(text.split())
print(freq)  # Counter({'hello': 2, 'world': 1})
print("Most common:", freq.most_common(1))  # [('hello', 2)]

# defaultdict â€” no KeyError
graph = defaultdict(list)
graph[0].append(1)
graph[0].append(2)
print(dict(graph))  # {0: [1, 2]}

# Application: Two Sum â€” O(n)
def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

// JavaScript Map â€” hash map with any key type
const scores = new Map();
scores.set("Alice", 95);
scores.set("Bob",   87);
scores.set("Carol", 92);

// Access
console.log("Alice:", scores.get("Alice"));  // 95
console.log("Has Bob:", scores.has("Bob"));  // true

// Iterate
for (const [name, score] of scores) {
    console.log(`${name}: ${score}`);
}

// Delete
scores.delete("Bob");
console.log("Size:", scores.size);  // 2

// Object as hash map (string keys only)
const obj = { Alice: 95, Bob: 87 };
console.log(obj["Alice"]);  // 95
console.log("Alice" in obj);  // true

// Set â€” hash set
const seen = new Set([1, 2, 3, 1, 2]);
console.log("Set:", [...seen]);  // [1, 2, 3]
seen.add(4);
seen.delete(1);

// Application: Two Sum â€” O(n)
function twoSum(nums, target) {
    const map = new Map();
    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]

// Frequency count
function wordFreq(text) {
    const freq = new Map();
    for (const word of text.split(' ')) {
        freq.set(word, (freq.get(word) || 0) + 1);
    }
    return freq;
}
console.log([...wordFreq("hello world hello")]);
// [['hello', 2], ['world', 1]]

Previous Next

Hash Table

What is a Hash Table?

How Hashing Works

Ready to Level Up Your Skills?