Hash Map Internals: How Hash Tables Really Work

---

What is a Hash Map?

A hash map (or hash table) is a data structure that maps keys to values using a hash function. The hash function converts a key into an array index (bucket), allowing average O(1) lookups, insertions, and deletions.

The core idea is simple:

1. Given a key, compute hash(key) % table_size to get a bucket index.
2. Store the key-value pair in that bucket.
3. On lookup, compute the same hash and go directly to the bucket.

The challenge is handling collisions — when two different keys hash to the same bucket.

---

Hash Functions

What Makes a Good Hash Function?

A good hash function should:

• Distribute keys uniformly across buckets (minimize clustering)
• Be deterministic — same key always produces the same hash
• Be fast to compute
• Minimize collisions — different keys should rarely hash to the same value

Common Hash Functions

def hash_division(key, table_size):
    """Simple division method: h(k) = k mod m."""
    return key % table_size

def hash_multiplication(key, table_size):
    """Multiplication method (Knuth's)."""
    A = 0.6180339887  # (sqrt(5) - 1) / 2
    return int(table_size * ((key * A) % 1))

def hash_string(s, table_size):
    """Polynomial rolling hash for strings."""
    h = 0
    base = 31
    for ch in s:
        h = (h * base + ord(ch)) % table_size
    return h

Python’s Built-in hash()

Python uses different hash functions depending on the type:

• Integers: The hash of a small integer is the integer itself.
• Strings: SipHash (cryptographic, collision-resistant).
• Tuples: Combines hashes of elements.

# Python's hash is randomized per process for strings (security)
print(hash(42))        # 42
print(hash("hello"))   # Different each run
print(hash((1, 2, 3))) # Depends on element hashes

---

Collision Resolution: Separate Chaining

Separate chaining stores a linked list (or other collection) at each bucket. When a collision occurs, the new element is appended to the list.

class HashMapChaining:
    """Hash map using separate chaining for collision resolution."""
    
    def __init__(self, initial_capacity=16, load_factor_threshold=0.75):
        self.capacity = initial_capacity
        self.load_factor_threshold = load_factor_threshold
        self.size = 0
        self.buckets = [[] for _ in range(self.capacity)]
    
    def _hash(self, key):
        """Compute bucket index for the given key."""
        return hash(key) % self.capacity
    
    def put(self, key, value):
        """Insert or update a key-value pair."""
        idx = self._hash(key)
        
        # Check if key already exists
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, value)
                return
        
        # Key not found, append
        self.buckets[idx].append((key, value))
        self.size += 1
        
        # Check load factor and rehash if needed
        if self.size / self.capacity > self.load_factor_threshold:
            self._rehash()
    
    def get(self, key, default=None):
        """Retrieve value for the given key."""
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        return default
    
    def remove(self, key):
        """Remove a key-value pair. Returns True if found."""
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx].pop(i)
                self.size -= 1
                return True
        return False
    
    def _rehash(self):
        """Double the capacity and rehash all elements."""
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)
    
    def __contains__(self, key):
        return self.get(key) is not None
    
    def __len__(self):
        return self.size
    
    def __repr__(self):
        items = []
        for bucket in self.buckets:
            for k, v in bucket:
                items.append(f"{k}: {v}")
        return "{" + ", ".join(items) + "}"


# Usage
hm = HashMapChaining()
hm.put("apple", 1)
hm.put("banana", 2)
hm.put("cherry", 3)
print(hm.get("banana"))    # 2
print("apple" in hm)       # True
hm.remove("banana")
print(hm.get("banana"))    # None
print(f"Size: {len(hm)}")  # 2

---

Collision Resolution: Open Addressing

In open addressing, all elements are stored directly in the table array. When a collision occurs, we probe (search for) the next available slot.

Linear Probing

class HashMapLinearProbing:
    """Hash map using open addressing with linear probing."""
    
    EMPTY = object()     # Sentinel for empty slots
    DELETED = object()   # Sentinel for deleted slots (tombstone)
    
    def __init__(self, initial_capacity=16, load_factor_threshold=0.5):
        self.capacity = initial_capacity
        self.load_factor_threshold = load_factor_threshold
        self.size = 0
        self.keys = [self.EMPTY] * self.capacity
        self.values = [None] * self.capacity
    
    def _hash(self, key):
        return hash(key) % self.capacity
    
    def _probe(self, key):
        """Find the slot for this key (existing or empty)."""
        idx = self._hash(key)
        first_deleted = -1
        
        for _ in range(self.capacity):
            if self.keys[idx] is self.EMPTY:
                # Empty slot: key doesn't exist
                return first_deleted if first_deleted != -1 else idx
            elif self.keys[idx] is self.DELETED:
                if first_deleted == -1:
                    first_deleted = idx
            elif self.keys[idx] == key:
                return idx
            
            idx = (idx + 1) % self.capacity  # Linear probe
        
        return first_deleted if first_deleted != -1 else -1
    
    def put(self, key, value):
        idx = self._probe(key)
        if idx == -1:
            self._rehash()
            idx = self._probe(key)
        
        is_new = self.keys[idx] is self.EMPTY or self.keys[idx] is self.DELETED
        self.keys[idx] = key
        self.values[idx] = value
        
        if is_new:
            self.size += 1
            if self.size / self.capacity > self.load_factor_threshold:
                self._rehash()
    
    def get(self, key, default=None):
        idx = self._hash(key)
        for _ in range(self.capacity):
            if self.keys[idx] is self.EMPTY:
                return default
            if self.keys[idx] == key:
                return self.values[idx]
            idx = (idx + 1) % self.capacity
        return default
    
    def remove(self, key):
        idx = self._hash(key)
        for _ in range(self.capacity):
            if self.keys[idx] is self.EMPTY:
                return False
            if self.keys[idx] == key:
                self.keys[idx] = self.DELETED  # Tombstone
                self.values[idx] = None
                self.size -= 1
                return True
            idx = (idx + 1) % self.capacity
        return False
    
    def _rehash(self):
        old_keys = self.keys
        old_values = self.values
        self.capacity *= 2
        self.keys = [self.EMPTY] * self.capacity
        self.values = [None] * self.capacity
        self.size = 0
        
        for i in range(len(old_keys)):
            if old_keys[i] is not self.EMPTY and old_keys[i] is not self.DELETED:
                self.put(old_keys[i], old_values[i])
    
    def __len__(self):
        return self.size


# Usage
hm = HashMapLinearProbing()
for i in range(100):
    hm.put(f"key_{i}", i * 10)

print(hm.get("key_42"))    # 420
print(hm.get("key_99"))    # 990
print(len(hm))             # 100

Quadratic Probing

Instead of probing (h + 1), (h + 2), (h + 3), ... we probe (h + 1), (h + 4), (h + 9), ...:

def quadratic_probe(self, key):
    idx = self._hash(key)
    i = 0
    while True:
        slot = (idx + i * i) % self.capacity
        if self.keys[slot] is self.EMPTY or self.keys[slot] == key:
            return slot
        i += 1

Quadratic probing avoids the primary clustering problem of linear probing, where consecutive occupied slots form long chains.

Double Hashing

Use a second hash function to determine the probe step:

def double_hash_probe(self, key):
    h1 = hash(key) % self.capacity
    h2 = 1 + (hash(key) % (self.capacity - 1))  # Must be non-zero
    
    i = 0
    while True:
        slot = (h1 + i * h2) % self.capacity
        if self.keys[slot] is self.EMPTY or self.keys[slot] == key:
            return slot
        i += 1

---

Load Factor and Rehashing

The load factor alpha = n / m (number of elements / table size) determines performance:

Load Factor	Chaining Avg Probe	Linear Probing Avg Probe
0.25	1.25	1.17
0.50	1.50	1.50
0.75	1.75	2.50
0.90	1.90	5.50
0.95	1.95	10.50

For chaining, average chain length = alpha, so lookups take O(1 + alpha).

For linear probing, performance degrades rapidly above alpha = 0.75.

Rehashing (doubling the table and reinserting all elements) is triggered when the load factor exceeds a threshold. While a single rehash takes O(n), it happens infrequently enough that the amortized cost per insertion remains O(1).

def analyze_load_factor():
    """Demonstrate how load factor affects collision rate."""
    import random
    
    for load in [0.25, 0.50, 0.75, 0.90]:
        table_size = 1000
        n = int(table_size * load)
        
        buckets = [0] * table_size
        for _ in range(n):
            idx = random.randint(0, table_size - 1)
            buckets[idx] += 1
        
        collisions = sum(1 for b in buckets if b > 1)
        max_chain = max(buckets)
        empty = sum(1 for b in buckets if b == 0)
        
        print(f"Load={load:.2f}: collisions={collisions}, "
              f"max_chain={max_chain}, empty_buckets={empty}")

analyze_load_factor()

---

How Python’s dict Works

Python’s dict uses open addressing with a custom probing scheme:

1. Table size is always a power of 2.
2. Hash function: SipHash for strings, identity for small ints.
3. Probing: A perturbation-based scheme that uses the full hash value (not just hash % size).
4. Load factor threshold: 2/3 (approximately 0.67).
5. Compact dict (Python 3.6+): Separates the hash table from the insertion-order list, saving memory and preserving insertion order.

import sys

# Python dict memory usage
d = {}
print(f"Empty dict: {sys.getsizeof(d)} bytes")  # ~64 bytes

for i in range(100):
    d[i] = i
print(f"100-element dict: {sys.getsizeof(d)} bytes")  # ~4192 bytes

# dict preserves insertion order (guaranteed since Python 3.7)
d = {"c": 3, "a": 1, "b": 2}
print(list(d.keys()))  # ['c', 'a', 'b']

Python’s Probe Sequence

# Simplified version of CPython's probe sequence
def python_probe(hash_val, table_size):
    """Simulate Python's perturbation-based probing."""
    PERTURB_SHIFT = 5
    perturb = hash_val
    idx = hash_val % table_size
    
    indices = [idx]
    for _ in range(10):
        perturb >>= PERTURB_SHIFT
        idx = (5 * idx + perturb + 1) % table_size
        indices.append(idx)
    
    return indices

# Shows that the probe sequence visits many different parts of the table
print(python_probe(42, 32))

---

Robin Hood Hashing

Robin Hood hashing is an open addressing variant that reduces the variance of probe lengths. The idea: when inserting, if the current element has traveled fewer steps from its home slot than the element already there, swap them (steal from the rich, give to the poor).

class RobinHoodHashMap:
    """Hash map using Robin Hood hashing."""
    
    EMPTY = object()
    
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.keys = [self.EMPTY] * capacity
        self.values = [None] * capacity
        self.distances = [0] * capacity  # How far each element is from home
    
    def _hash(self, key):
        return hash(key) % self.capacity
    
    def put(self, key, value):
        if self.size / self.capacity > 0.5:
            self._rehash()
        
        idx = self._hash(key)
        dist = 0
        
        while True:
            if self.keys[idx] is self.EMPTY:
                self.keys[idx] = key
                self.values[idx] = value
                self.distances[idx] = dist
                self.size += 1
                return
            
            if self.keys[idx] == key:
                self.values[idx] = value
                return
            
            # Robin Hood: if current element is "richer" (shorter distance),
            # swap and continue inserting the displaced element
            if self.distances[idx] < dist:
                # Swap
                key, self.keys[idx] = self.keys[idx], key
                value, self.values[idx] = self.values[idx], value
                dist, self.distances[idx] = self.distances[idx], dist
            
            idx = (idx + 1) % self.capacity
            dist += 1
    
    def get(self, key, default=None):
        idx = self._hash(key)
        dist = 0
        
        while True:
            if self.keys[idx] is self.EMPTY:
                return default
            if self.keys[idx] == key:
                return self.values[idx]
            # If we've probed further than this element's distance,
            # the key doesn't exist (Robin Hood invariant)
            if self.distances[idx] < dist:
                return default
            
            idx = (idx + 1) % self.capacity
            dist += 1
    
    def _rehash(self):
        old_keys = self.keys
        old_values = self.values
        self.capacity *= 2
        self.keys = [self.EMPTY] * self.capacity
        self.values = [None] * self.capacity
        self.distances = [0] * self.capacity
        self.size = 0
        
        for i in range(len(old_keys)):
            if old_keys[i] is not self.EMPTY:
                self.put(old_keys[i], old_values[i])


# Usage
rh = RobinHoodHashMap()
for i in range(50):
    rh.put(f"key_{i}", i)

print(rh.get("key_25"))  # 25
print(rh.get("key_49"))  # 49
print(rh.get("missing")) # None

The key benefit: Robin Hood hashing gives very low variance in probe lengths. The maximum probe length is O(log n) with high probability, compared to O(log n / log log n) expected for linear probing.

---

Time Complexity Analysis

Operation	Average	Worst Case	Amortized (with rehashing)
Insert	O(1)	O(n)	O(1)
Lookup	O(1)	O(n)	O(1)
Delete	O(1)	O(n)	O(1)

The worst case O(n) happens when all keys hash to the same bucket. With a good hash function, this is extremely unlikely.

When O(1) Becomes O(n)

# Adversarial example: all keys hash to same bucket
class BadHash:
    def __init__(self, val):
        self.val = val
    def __hash__(self):
        return 42  # Everything hashes to 42!
    def __eq__(self, other):
        return isinstance(other, BadHash) and self.val == other.val

# This creates a hash table that degrades to a linked list
d = {}
for i in range(1000):
    d[BadHash(i)] = i
# Lookups are now O(n)

---

Chaining vs Open Addressing: When to Use Which

Feature	Chaining	Open Addressing
Load factor	Can exceed 1.0	Must stay below ~0.75
Memory	Extra pointers	No extra pointers
Cache performance	Poor (linked list)	Good (array)
Deletion	Simple	Needs tombstones
Implementation	Simpler	More complex
Used by	Java HashMap	Python dict, Rust HashMap

---

Practice Problems

1. Design HashMap (LeetCode 706) — Implement basic put, get, remove.
2. Two Sum (LeetCode 1) — Classic hash map application.
3. Group Anagrams (LeetCode 49) — Hash map with sorted string keys.
4. LRU Cache (LeetCode 146) — Hash map + doubly linked list.
5. Longest Consecutive Sequence (LeetCode 128) — Hash set for O(n) solution.
6. Subarray Sum Equals K (LeetCode 560) — Prefix sum + hash map.

---

Key Takeaways

• Hash maps achieve average O(1) operations by computing a bucket index directly from the key.
• Separate chaining stores collisions in linked lists; open addressing probes for the next empty slot.
• The load factor determines performance; rehashing keeps it low at the cost of occasional O(n) resizes.
• Python’s dict uses open addressing with perturbation-based probing and a 2/3 load factor threshold.
• Robin Hood hashing reduces probe length variance by swapping elements during insertion.
• Always use a good hash function to ensure uniform distribution; a bad hash degrades everything to O(n).