Separate Probing

Whenever a hash function results in a hash which has already been used, it results in a collision. There are two common techniques to resolve hash collisions, namely separate chaining and linear probing. I had a weird idea to combine both of them and creating a third technique called separate probing.

Separate Chaining

In separate chaining, we use linked lists to store the items. Whenever a hash function generates a hash which has already been used, we can simply put the element in the linked list corresponding to that hash. For example, in the diagram below B1, B4, and B8 result in the same hash, i.e. hash 0. Hence we store them sequentially in the linked list corresponding to hash 0.

Linear Probing

In linear probing, we use the next available position in the hash table in case of a collision. For example, B4 and B8 are stored immediately after B1, as they have the same hash. If the position is already occupied, we simply store it at the next available position.

Separate Probing/Linear Chaining

If we combine both of the above techniques, we can resolve collisions as follows. Whenever there is a collision, store the colliding key at the next available position. If the next position is occupied, store it as a linked list item at the last position. For example, in the above diagram, if there is an item B9 which results in the has 0, we will try to find out next available position. Since we run out of space at position 2, we will put B9 at the linked list at position 2, and so on.

While searching for an item, the existence of linked list at a position indicates the end of space for that hash, and we should proceed examining the linked list.

There is a gotcha here, and I am not yet quite sure of the best way around it. How do we differentiate between items having different hashes, when the available locations come to an end on the first pass? In other words, when we are at B8, how do we know B2 belongs to a different hash than 0? Something to think more about.