Visualizing Hash Table Collisions: Linear vs. Quadratic Probing

Understanding Hash Table Collisions

Hash tables are a fundamental data structure offering (ideally) constant time complexity for insertion, deletion, and lookup operations. However, this ideal scenario relies on a perfect hash function, which is often unattainable in practice. When two different keys hash to the same index, a collision occurs. Resolving these collisions efficiently is crucial for maintaining good performance.

This post will explore two common collision resolution techniques: linear probing and quadratic probing, and visualize their effects.

Linear Probing

Linear probing is the simplest collision resolution technique. When a collision occurs at index i, we linearly probe subsequent indices (i+1, i+2, i+3, and so on, wrapping around to the beginning of the table if necessary) until an empty slot is found.

Algorithm:

• Calculate the initial hash index: h(key) % table_size.
• If the slot at the index is empty, insert the key.
• If the slot is occupied, probe the next slot: (h(key) + 1) % table_size.
• Repeat until an empty slot is found or the entire table has been probed.

Visualization:

Imagine a table of size 10. Let's insert the keys 12, 22, 32, and 42, assuming a simple hash function h(key) = key (modulo 10 for table size).

• 12 goes to index 2.
• 22 goes to index 2. Collision! Probe index 3. Insert 22 at index 3.
• 32 goes to index 2. Collision! Probe index 3. Collision! Probe index 4. Insert 32 at index 4.
• 42 goes to index 2. Collision! Probe index 3. Collision! Probe index 4. Collision! Probe index 5. Insert 42 at index 5.

Disadvantages:

• Primary Clustering: Consecutive blocks of occupied slots tend to form, increasing the probe length for subsequent insertions. As you can see above, slots 2-5 are filled contiguously.
• This clustering degrades performance.

Improve your coding skills, check out Data Structures and Algorithms

Quadratic Probing

Quadratic probing attempts to address primary clustering by using a quadratic function to determine the probe sequence. Instead of linearly probing, we probe indices (i + 1^2) % table_size, (i + 2^2) % table_size, (i + 3^2) % table_size, and so on.

Algorithm:

• Calculate the initial hash index: h(key) % table_size.
• If the slot at the index is empty, insert the key.
• If the slot is occupied, probe the next slot using the quadratic function: (h(key) + j^2) % table_size, where j starts at 1 and increments.
• Repeat until an empty slot is found or the entire table has been probed.

Visualization:

Using the same table of size 10 and keys 12, 22, 32, and 42:

• 12 goes to index 2.
• 22 goes to index 2. Collision! Probe index (2 + 1^2) % 10 = 3. Insert 22 at index 3.
• 32 goes to index 2. Collision! Probe index (2 + 1^2) % 10 = 3. Collision! Probe index (2 + 2^2) % 10 = 6. Insert 32 at index 6.
• 42 goes to index 2. Collision! Probe index (2 + 1^2) % 10 = 3. Collision! Probe index (2 + 2^2) % 10 = 6. Collision! Probe index (2 + 3^2) % 10 = 11 % 10 = 1. Insert 42 at index 1.

Notice how the keys are more spread out compared to linear probing, mitigating primary clustering.

Advantages:

• Reduces primary clustering compared to linear probing.

Disadvantages:

• Secondary Clustering: If two keys hash to the same index, their probe sequence will be the same. This is known as secondary clustering.
• Not guaranteed to find an empty slot if the table is more than half full. This is often solved by ensuring the table size is prime.

Choosing the Right Probing Technique

Both linear and quadratic probing have their pros and cons. Linear probing is simpler to implement but suffers from primary clustering. Quadratic probing reduces primary clustering but introduces secondary clustering. The choice depends on the specific application and the expected distribution of keys.

For more advanced techniques and deeper insights on data structures and algorithms, visit our educational resources: DSA Cheat Sheet, Core Subjects and Roadmap.

Further Learning:

• Consider exploring other collision resolution techniques like separate chaining.
• Experiment with different hash functions and analyze their impact on collision rates.
• Explore Mock Interviews for practice.
• Get Resume Review.
• Start Mentorship for guidance.
• Check Flashcards to prep.