Hashing & Collision Resolution

Hash tables, the underlying structure for dictionaries and sets, offer near-constant time average performance for insertions, deletions, and lookups. This efficiency relies on a hash function that maps keys to specific memory locations, or buckets. However, different keys can sometimes map to the same bucket, a scenario known as a hash collision. Effectively managing these collisions is critical for maintaining the hash table's performance and correctness.

The Hash Function's Role

At its core, a hash function takes an input key and returns a fixed-size integer, the hash value. This hash value is then typically modulated by the number of available buckets (e.g., hash_value % num_buckets) to produce an array index. A well-designed hash function aims to distribute keys uniformly across the available buckets, minimizing the chance of multiple keys mapping to the same location. The function must also be deterministic, always returning the same hash value for the same input key.

pythonPython's Built-in `hash()` Function

💡 Hash Function Properties

An ideal hash function exhibits determinism (same input, same output), uniformity (distributes keys evenly), and speed (computes quickly). It should also have an avalanche effect, where a small change in input drastically changes the hash output.

The Inevitability of Collisions

A hash collision occurs when two different keys produce the same hash value, or more commonly, map to the same bucket index after the modulo operation. Collisions are mathematically unavoidable in any system where the number of possible keys is greater than the number of available buckets (the pigeonhole principle). Even with a perfect hash function, the probability of collisions increases rapidly as more items are added to the table, a phenomenon often illustrated by the Birthday Paradox.

Check Your Understanding

Why are hash collisions considered inevitable in practical hash table implementations?

Collision Resolution: Separate Chaining

Separate chaining is one of the most straightforward and widely used collision resolution techniques. When a collision occurs, instead of trying to find another slot in the main array, each bucket in the hash table points to a data structure, typically a linked list (or sometimes a balanced binary search tree for very large chains). All key-value pairs that hash to the same index are stored in this list. To retrieve an item, the hash function locates the correct bucket, then the linked list is traversed to find the specific key.

pythonImplementing Separate Chaining

✨ Chaining Pros & Cons

Chaining is simple to implement and handles high load factors gracefully, as it can always add more items to a chain. Deletions are also straightforward. However, it requires extra space for pointers (in true linked lists) and can degrade to $O(N)$ performance in the worst case if all keys hash to the same bucket, forming a single long list.

Collision Resolution: Open Addressing

Open addressing is an alternative strategy where all key-value pairs are stored directly within the hash table array itself. When a collision occurs, the algorithm probes for an alternative empty slot in the table. This probing continues until an empty slot is found for insertion, or the key is found during a lookup. The main challenge with open addressing is designing an effective probing sequence to avoid clustering and ensure efficient access.

Linear Probing

Linear probing is the simplest form of open addressing. If the initial hash index is occupied, it checks the next slot, then the next, and so on, wrapping around the table if necessary. The probe sequence is $h(key)$ , $(h(key) + 1) \% M$ , $(h(key) + 2) \% M$ , and so forth, where $M$ is the table size. While easy to implement, linear probing suffers from primary clustering, where long contiguous blocks of occupied slots form, increasing average probe length.

pythonImplementing Linear Probing

⚠️ Primary Clustering

Linear probing's main drawback is primary clustering. If many keys hash to the same initial region, they form long contiguous blocks. Subsequent insertions into this block require longer probe sequences, and the block tends to grow, exacerbating the problem. This significantly degrades performance, especially at higher load factors.

Try It Yourself

Modify the LinearProbingHashTable to track the number of probes required for each insertion. Add a probe_counts list to the class and append the probe count after each successful insertion. Then, print the average probe count after all insertions.

python

class LinearProbingHashTable:
    def __init__(self, capacity):
        self.capacity = capacity
        self.table = [None] * self.capacity
        self.size = 0
        # Add probe_counts list here

def _get_index(self, key):
        return hash(key) % self.capacity

def insert(self, key, value):
        if self.size == self.capacity:
            raise Exception("Hash table is full")

index = self._get_index(key)
        initial_index = index
        probes = 0 # Initialize probe counter

while self.table[index] is not None:
            k, v = self.table[index]
            if k == key:
                self.table[index] = (key, value)
                # Decide if you want to count probes for updates
                return
            index = (index + 1) % self.capacity
            probes += 1 # Increment probe counter
            if index == initial_index:
                raise Exception("Hash table is full or cannot find slot")

self.table[index] = (key, value)
        self.size += 1
        # Append probes to probe_counts here

def get(self, key):
        index = self._get_index(key)
        initial_index = index

while self.table[index] is not None:
            k, v = self.table[index]
            if k == key:
                return v
            index = (index + 1) % self.capacity
            if index == initial_index:
                break
        raise KeyError(f"Key '{key}' not found")

def display(self):
        for i, item in enumerate(self.table):
            print(f"Bucket {i}: {item}")

# Example Usage
ht_lp = LinearProbingHashTable(7)
keys_values = [('apple', 10), ('banana', 20), ('cherry', 30), ('date', 40), ('elderberry', 50), ('fig', 60), ('grape', 70)]
for k, v in keys_values:
    ht_lp.insert(k, v)

print("--- Linear Probing Table ---")
ht_lp.display()

# Calculate and print average probes here

Check Your Understanding

Which collision resolution strategy is generally preferred when memory overhead for pointers is a concern?

Quadratic Probing

To mitigate primary clustering, quadratic probing uses a non-linear probing sequence. If the initial hash index $h(key)$ is occupied, it checks $h(key) + 1^2$ , then $h(key) + 2^2$ , then $h(key) + 3^2$ , and so on, all modulo $M$ . The probe sequence is $h(key)$ , $(h(key) + 1^2) \% M$ , $(h(key) + 2^2) \% M$ , $(h(key) + 3^2) \% M$ , etc. This spreads out colliding keys more effectively than linear probing. However, it can suffer from secondary clustering, where keys that initially hash to the same index follow the same quadratic probe sequence.

pythonImplementing Quadratic Probing

💡 Secondary Clustering

While quadratic probing avoids primary clustering, it can still suffer from secondary clustering. This occurs when multiple keys hash to the same initial index and then follow the exact same quadratic probe sequence. This means they still collide with each other along their entire probe path, leading to similar performance degradation as primary clustering for those specific keys.

Double Hashing

Double hashing is considered one of the best open addressing techniques. It uses two independent hash functions: $h_1(key)$ for the initial index and $h_2(key)$ for the step size. The probe sequence is $h_1(key)$ , $(h_1(key) + h_2(key)) \% M$ , $(h_1(key) + 2 \cdot h_2(key)) \% M$ , $(h_1(key) + 3 \cdot h_2(key)) \% M$ , and so on. Since the step size $h_2(key)$ varies for each key, it virtually eliminates both primary and secondary clustering, leading to a more uniform distribution of probes and better performance.

pythonImplementing Double Hashing

Collision Resolution Strategies Comparison

Feature	Separate Chaining	Linear Probing	Quadratic Probing	Double Hashing
Mechanism	Linked list at each bucket	Next available slot (+1)	Next available slot ( $+i^2$ )	Next available slot ( $+i \cdot h_2(key)$ )
Clustering Type	None (within table)	Primary Clustering	Secondary Clustering	Minimal Clustering
Memory Usage	Higher (pointers for lists)	Lower (no pointers)	Lower (no pointers)	Lower (no pointers)
Deletion Complexity	Easy	Difficult (requires marking as 'deleted')	Difficult (requires marking as 'deleted')	Difficult (requires marking as 'deleted')
Performance at High Load	Degrades gracefully	Degrades quickly	Degrades moderately	Degrades gracefully (best open addressing)
Best Use Case	General purpose, high load factors	Simple, low load factors	Moderate load factors, avoids primary clustering	High performance, avoids most clustering

A summary of common collision resolution techniques and their trade-offs.

Load Factor and Rehashing

The load factor ( $\alpha$ ) of a hash table is the ratio of the number of items stored ( $N$ ) to the number of available buckets ( $M$ ), i.e., $\alpha = N/M$ . A high load factor means more items per bucket on average, increasing the likelihood and impact of collisions. To maintain performance, hash tables dynamically resize (or rehash) when the load factor exceeds a certain threshold (e.g., 0.7 for open addressing, 1.0 for chaining). Rehashing involves creating a new, larger table and re-inserting all existing key-value pairs using the new table's capacity. This is an $O(N)$ operation but amortized over many insertions, it keeps average performance near $O(1)$ .

Hash Table Insertion Process with Collision Resolution and Rehashing

Loading diagram...

This flowchart illustrates the steps involved in inserting a key-value pair, including how collisions are handled and when rehashing is triggered to maintain performance.

Qualities of an Effective Hash Function

The choice of hash function significantly impacts a hash table's performance. An effective hash function should exhibit several key qualities:

Uniformity: It should distribute keys as evenly as possible across all buckets to minimize collisions. A perfectly uniform hash function would map each key to a unique bucket.
Determinism: For a given key, the hash function must always produce the same hash value. This is non-negotiable for consistent lookups.
Speed: The function must compute hash values quickly. A slow hash function negates the $O(1)$ average time complexity benefits of hash tables.
Avalanche Effect: A small change in the input key (e.g., changing one character in a string) should result in a drastically different hash value. This helps prevent secondary clustering and ensures good distribution even for similar keys.

Key Takeaways

Hash functions map keys to array indices (buckets), but collisions (multiple keys mapping to the same bucket) are inevitable.
Separate chaining resolves collisions by storing key-value pairs in a linked list at each bucket, offering graceful degradation at high load factors.
Open addressing strategies (linear, quadratic, double hashing) store all items directly in the table, probing for the next available slot upon collision.
Linear probing suffers from primary clustering, while quadratic probing mitigates this but can still encounter secondary clustering.
Double hashing uses a second hash function for the probe step size, effectively eliminating most clustering and providing excellent performance.
The load factor ( $\alpha = N/M$ ) dictates hash table efficiency; exceeding a threshold triggers rehashing (resizing) to a larger table.
A good hash function is uniform, deterministic, fast, and exhibits an avalanche effect to ensure optimal hash table performance.

← All lessons in Data Structures: Dictionaries & Sets