Collision Resolution Techniques and Load Factor Analysis

1. The Core Idea: Hashing and Collisions

At its heart, hashing is a simple idea. We use a hash function, $h(k)$, to compute an index in an array (called a hash table) for a given key $k$. In an ideal world, every key would map to a unique index. For example, a common hash function is the division method: $h(k)=k(\mathrm{mod}m)$, where $m$ is the size of the hash table.

The problem arises when two different keys map to the same index. This is called a collision. For instance, if our table size $m=10$ and we want to store keys 6 and 26, both would map to index 6 ($6(\mathrm{mod}10)=6$ and $26(\mathrm{mod}10)=6$). We can't store both in the same slot. How we handle this is the central topic of this lesson.

To start, let's solidify this foundational concept of hashing and collisions.

All collision resolution techniques fall into two broad categories: Separate Chaining (also called closed addressing) and Open Addressing.

2. Strategy 1: Separate Chaining

Separate chaining is an intuitive and popular method for handling collisions. The idea is to not store the elements directly in the hash table slots. Instead, each slot in the table acts as a head pointer to a linked list. All keys that hash to the same index are simply added to that index's linked list.

• Insertion: To insert a key, you compute its hash index and insert it into the linked list at that position. For $O(1)$ insertion, you can simply add the new node at the head of the list.
• Search/Deletion: To search for or delete a key, you compute its hash index, which directs you to the correct linked list. You then perform a standard linear search on that list to find or remove the element.

The performance of separate chaining is determined by the load factor, $\alpha$, defined as:

where $n$ is the number of keys stored and $m$ is the number of slots in the hash table. For separate chaining, it's perfectly acceptable for $\alpha$ to be greater than 1.

The average length of a chain is $\alpha$. Therefore, the average time for an unsuccessful search is $O(\alpha )$, and for a successful search, it's approximately $O(1+\alpha /2)$. Assuming a good hash function that distributes keys uniformly, if we keep $\alpha$ as a small constant (e.g., by making the table size $m$ proportional to the number of keys $n$), the average search time becomes $O(1)$.

Let's walk through a detailed example to see exactly how this works.

3. Strategy 2: Open Addressing

Open addressing takes a different approach. All keys are stored directly inside the hash table. If a collision occurs at index $j$, we probe for another empty slot in the table according to a fixed rule.

For open addressing, the load factor $\alpha =n/m$ must be less than or equal to 1. As $\alpha$ gets close to 1, the table fills up, and finding an empty slot can become very slow.

The probe sequence is generated by a function of the form:

where $h^{\prime }(k)$ is the initial hash function, $i$ is the probe attempt number (starting from $i=0$), and $f(i)$ is the function that distinguishes the different open addressing techniques.

3.1. Linear Probing

This is the simplest form of open addressing. The probe function is $f(i)=i$. If the initial slot $h^{\prime }(k)$ is occupied, we try $h^{\prime }(k)+1$, then $h^{\prime }(k)+2$, and so on, wrapping around the table if necessary, until we find an empty slot.

• Problem: Primary Clustering: Linear probing suffers from a problem where long runs of occupied slots tend to build up. When a new key hashes to anywhere in this cluster, it has to traverse to the end of the cluster to be inserted, further lengthening it. This significantly degrades performance.
• Deletion: Deletion is tricky. If we simply remove an element from a slot, it might break the "chain" for a subsequent probe sequence. For example, if we inserted keys A, B, C where A and B hashed to index 10 and C hashed to 11, B would be placed at 11 and C at 12. If we then delete B from slot 11, a search for C would fail, as the probe would stop at the now-empty slot 11. To solve this, we mark deleted slots with a special "tombstone" or "deleted" marker. A new element can be inserted into a deleted slot, but a search probe must continue past it.

Let's see how linear probing works, including the crucial detail of handling deletions.

3.2. Quadratic Probing

To alleviate the primary clustering problem of linear probing, we can use a non-linear probe sequence. In quadratic probing, the probe function is quadratic, typically $f(i)=i^2$. If the initial slot $h^{\prime }(k)$ is occupied, we check $h^{\prime }(k)+1$, then $h^{\prime }(k)+4$, then $h^{\prime }(k)+9$, and so on.

• Advantage: Keys that hash to the same location will not necessarily follow the same probe sequence if other keys have already occupied the primary probe slots. This helps mitigate primary clustering.
• Disadvantage: It can lead to secondary clustering, where keys that hash to the same initial slot do follow the same alternative probe sequence. Also, it is not guaranteed to find an empty slot even if one exists, unless the table size $m$ is a prime number and the load factor $\alpha$ is kept below 0.5.

3.3. Double Hashing (Briefly)

Double hashing is one of the best open addressing methods available. It uses a second hash function, $h_2(k)$, to determine the step size for the probe sequence: $f(i)=i\cdot h_2(k)$.

This means that keys hashing to the same initial location will likely have different probe sequences because their step sizes (determined by $h_2$) will be different. This effectively eliminates both primary and secondary clustering. The main drawback is the extra computational cost of a second hash function. The syllabus only requires you to be aware of it, so we won't go into a full example.

4. Performance Analysis and Comparison

The performance of open addressing is highly sensitive to the load factor $\alpha$. The expected number of probes for an operation is approximately $O(1/(1-\alpha ))$. You can see that as $\alpha$ approaches 1 (the table becomes full), the denominator approaches 0, and the number of probes skyrockets. This is in contrast to separate chaining, where performance degrades more gracefully as $O(1+\alpha )$.

Let's summarize the trade-offs between these methods.

Here is a summary table for your quick reference:

Conclusion

In this lesson, we explored hashing, a technique that provides the potential for $O(1)$ average-time complexity for dictionary operations. We saw that this performance hinges on effectively managing collisions.

Key Takeaways:

• Hashing maps keys to table indices; collisions occur when different keys map to the same index.
• Separate Chaining resolves collisions by storing keys in linked lists at each index. Its performance, $O(1+\alpha )$, degrades linearly with the load factor $\alpha =n/m$.
• Open Addressing resolves collisions by probing for the next available slot within the table itself. Its performance is critically dependent on the load factor, approximately $O(1/(1-\alpha ))$, and $\alpha$ must be less than 1.
• Linear Probing ($f(i)=i$) is simple and cache-friendly but suffers from primary clustering.
• Quadratic Probing ($f(i)=i^2$) mitigates primary clustering but can cause secondary clustering.
• Load Factor ($\alpha$) is the single most important parameter for analyzing hash table performance. For GATE, you must be comfortable with how it affects both chaining and open addressing.

This lesson concludes our module on Data Structures. We've built a solid foundation that will be indispensable for the next, and most heavily-weighted, part of your preparation: Algorithms. In our upcoming lessons, we will start by formalizing the language of algorithm analysis with Asymptotic Notation, mastering Big-O, Big-$\Omega$, and Big-$\Theta$ to precisely describe and compare algorithm efficiency.