🗂️ Hash Tables Fundamentals

🎯 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 or slots, from which the desired value can be found. Ideal hash tables provide O(1) average-time lookup, insertion, and deletion.

Average: O(1) | Worst-case: O(n) | Space: O(n)

The Magic of Hash Tables

Core Idea: Transform a key (string, number, object) into an integer index using a hash function. Use that index to store/find the value in an array. When two keys hash to the same index, we handle the collision.

Analogy: Like a library where every book has a call number (hash) that tells you exactly which shelf (bucket) to look in. Multiple books can share a shelf (collision), and you search within that shelf.

📌 O(1) Average Operations📌 Key-Value Pairs📌 Hash Function📌 Collision Handling

# Python Dictionary (Hash Table)
hash_table = {}  # or dict()

# Insertion - O(1) average
hash_table["apple"] = 5
hash_table["banana"] = 3
hash_table["cherry"] = 8

# Lookup - O(1) average
print(hash_table["apple"])  # 5

# Deletion - O(1) average
del hash_table["banana"]

# Check existence - O(1)
if "cherry" in hash_table:
    print("Found!")

# Iteration
for key, value in hash_table.items():
    print(f"{key}: {value}")

🔢 Hash Functions

🎯 Converting Keys to Indices

A hash function takes a key and returns an integer (hash code). Good hash functions are:

Deterministic: Same key always produces same hash
Uniform: Distributes keys evenly across buckets
Fast to compute: O(1) or O(len(key))
Minimizes collisions: Different keys map to different indices

# Simple hash functions

# 1. For integers - often use modulo
def int_hash(key, table_size):
    return key % table_size

# 2. For strings - polynomial rolling hash
def string_hash(s, table_size):
    hash_val = 0
    for i, char in enumerate(s):
        hash_val = (hash_val * 31 + ord(char)) % table_size
    return hash_val

# 3. Python's built-in hash()
print(hash("apple"))  # Large integer (varies by run)
print(hash(42))

# 4. Java-style hash for strings
def java_string_hash(s):
    hash_val = 0
    for char in s:
        hash_val = hash_val * 31 + ord(char)
    return hash_val

"apple" → hash("apple") = 123456 → index = 123456 % 10 = 6

"banana" → hash("banana") = 789012 → index = 789012 % 10 = 2

"cherry" → hash("cherry") = 345678 → index = 345678 % 10 = 8

💥 Collision Resolution

🎯 When Two Keys Map to Same Index

Collisions are inevitable (pigeonhole principle). Two main strategies:

Chaining (Separate Chaining): Each bucket stores a linked list (or other structure) of key-value pairs
Open Addressing: When a collision occurs, probe to find another empty slot

Why Collisions Happen

If a hash table has 10 buckets and you store 1000 items, many items must share buckets. Good hash functions distribute evenly, but collisions are unavoidable. The load factor (n/m) determines collision probability.

🔗 Chaining (Separate Chaining)

🎯 Linked Lists in Buckets

Each bucket contains a linked list (or array) of entries. On lookup, hash to bucket, then search the list. Insertion adds to the front (O(1)).

Advantages: Simple, handles many collisions well, never runs out of space
Disadvantages: Extra memory for pointers, poor cache locality

# Separate Chaining Implementation
class HashTableChaining:
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.table = [[] for _ in range(capacity)]
        self.size = 0
    
    def _hash(self, key):
        return hash(key) % self.capacity
    
    def put(self, key, value):
        index = self._hash(key)
        bucket = self.table[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update
                return
        bucket.append((key, value))  # Insert
        self.size += 1
    
    def get(self, key):
        index = self._hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        raise KeyError(key)
    
    def remove(self, key):
        index = self._hash(key)
        bucket = self.table[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return

🚪 Open Addressing

🎯 Probing for Empty Slots

All entries stored directly in the array. On collision, probe sequentially (or with a pattern) until an empty slot is found.

Linear Probing: Check i+1, i+2, ... (clustering problem)
Quadratic Probing: Check i+1², i+2², i+3², ... (reduces clustering)
Double Hashing: Use second hash function for probe step

# Linear Probing Implementation
class HashTableLinearProbing:
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.keys = [None] * capacity
        self.values = [None] * capacity
        self.size = 0
    
    def _hash(self, key):
        return hash(key) % self.capacity
    
    def put(self, key, value):
        index = self._hash(key)
        while self.keys[index] is not None and self.keys[index] != key:
            index = (index + 1) % self.capacity
        if self.keys[index] is None:
            self.size += 1
        self.keys[index] = key
        self.values[index] = value
    
    def get(self, key):
        index = self._hash(key)
        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.capacity
        raise KeyError(key)

⏱️ Time & Space Complexities

🎯 Performance Analysis

Average Case (good hash, low load factor): O(1) for insert, lookup, delete
Worst Case (all keys collide): O(n) for all operations
Space Complexity: O(n) + overhead for empty buckets
Load Factor α = n/m: Ideal α between 0.5 and 0.75

Expected Collisions

With uniform hashing, expected number of keys per bucket ≈ α. Expected lookup time = O(1 + α). When α is constant, operations are O(1) average.

💻 Multiple Implementations

# 1. Python dict (production quality)
hash_map = {}
hash_map["key"] = "value"

# 2. Java HashMap style using __slots__ for memory efficiency
class HashMapOptimized:
    __slots__ = ('capacity', 'table', 'size')
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.table = [None] * capacity
        self.size = 0
    
    def _index(self, key):
        return hash(key) & (self.capacity - 1)  # Power of 2 optimization
    
    def __setitem__(self, key, value):
        idx = self._index(key)
        if self.table[idx] is None:
            self.table[idx] = []
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        self.table[idx].append((key, value))
        self.size += 1
    
    def __getitem__(self, key):
        idx = self._index(key)
        if self.table[idx]:
            for k, v in self.table[idx]:
                if k == key:
                    return v
        raise KeyError(key)

# 3. Using default values
from collections import defaultdict
dd = defaultdict(int)  # default 0 for missing keys
dd["counter"] += 1

📈 Resizing & Load Factor

🎯 Growing the Hash Table

When load factor exceeds threshold (typically 0.75), the hash table resizes (usually doubles capacity) and rehashes all entries. This is O(n) but amortized O(1) per insertion.

Python dict: Resizes when 2/3 full
Java HashMap: Load factor 0.75
Resize cost: All keys must be rehashed (expensive but rare)

def _resize(self):
    old_table = self.table
    self.capacity *= 2
    self.table = [[] for _ in range(self.capacity)]
    self.size = 0
    for bucket in old_table:
        for key, value in bucket:
            self.put(key, value)  # Rehash each entry

✨ Perfect Hashing

🎯 No Collisions (Static Keys)

For a fixed set of keys (static dictionary), we can create a perfect hash function with no collisions. Minimal perfect hashing maps n keys to n slots with no collisions and no empty slots.

Applications: Compilers (keyword lookup), static symbol tables
Examples: gperf, CMPH library

🦆 Cuckoo Hashing

🎯 O(1) Worst-Case Lookup

Cuckoo hashing uses two hash functions and two tables. On insertion, if both slots are occupied, the existing key is "kicked out" to its alternate location. Lookup checks only two positions (O(1) worst-case).

class CuckooHash:
    def __init__(self, capacity=100):
        self.capacity = capacity
        self.table1 = [None] * capacity
        self.table2 = [None] * capacity
    
    def hash1(self, key):
        return hash(key) % self.capacity
    
    def hash2(self, key):
        return (hash(key) // self.capacity) % self.capacity
    
    def insert(self, key, value, count=0):
        if count > self.capacity:
            self._rehash()
            return self.insert(key, value)
        pos1 = self.hash1(key)
        if self.table1[pos1] is None:
            self.table1[pos1] = (key, value)
            return
        # Kick out existing key
        old_key, old_val = self.table1[pos1]
        self.table1[pos1] = (key, value)
        self.insert(old_key, old_val, count + 1)

⚖️ Comparison with Other DS

vs Array: Hash table provides O(1) lookup by key (vs O(1) by index). Better for sparse key spaces.
vs Balanced BST: BST provides O(log n) operations and ordered iteration. Hash table is faster but unordered.
vs Linked List: Hash table is dramatically faster for search.
vs Trie: Tries are better for prefix search (autocomplete), hash tables for exact match.

🌍 Real-World Applications

Database Indexing: Hash indexes for fast point lookups
Caches: Memcached, Redis, CPU caches (associative memory)
Symbol Tables: Compilers, interpreters, assemblers
Routing Tables: IP to network interface mapping
Password Storage: Hash of password (with salt)
Bloom Filters: Probabilistic hash-based data structure
Count-Min Sketch: Frequency estimation

💪 Classic Hash Table Problems

Two Sum: Use hash map to find complement in O(n)
First Non-Repeating Character: Count frequencies
Group Anagrams: Hash by sorted string
Longest Consecutive Sequence: O(n) using hash set
LRU Cache: Hash map + doubly linked list
Subarray Sum Equals K: Prefix sum with hash map

# Two Sum - O(n) using hash map
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# First Non-Repeating Character
def first_non_repeating(s):
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    for i, char in enumerate(s):
        if freq[char] == 1:
            return i
    return -1

📝 Interview Patterns

🎯 When to Use Hash Tables

Counting frequencies: Use dict to count occurrences
Lookup/check existence: Set or dict for O(1) membership
Two-pass algorithms: Build map in first pass, query in second
Removing duplicates: Use set to track seen elements
Sliding window with character counts: Hash map of frequencies

# Frequency Counter Pattern
def frequency_counter(arr):
    freq = {}
    for item in arr:
        freq[item] = freq.get(item, 0) + 1
    return freq

# Set for deduplication
def remove_duplicates(arr):
    return list(set(arr))

# Hash Map for caching (Memoization)
def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]