Collision resolution techniques for hash tables

Collisions in Hashing - Rob Edwards
🔗
Click here to suggest a better video
Click here to view videos suggested by visitors

In the introductory article on hasing and hash tables, we discussed how a hash function can be used to map any string or an object to a number/index. This index can be used to locate data in the storage array. As long as each string/object is mapped to a unique index everything works fine. But what if the hash function returns the same number/index for two different strings?

For example, if the hash function is a simple one which maps a to 1, b to 2, c to 3 and so on. If the string contains multiple characters, let’s say the hash function adds the values of all characters in the string. For the string “ab”, the hash value will be 1 + 2 which is 3. Also for the string “ba”, the hash value will be 2 + 1 which is 3!.

So the hash function we chose has decided that the index for the key “ab” is same as the index for the string “ba”. This is termed as hash collision and can result in data being overwritten for two different objects.

To handle scenarios like these, we use different hashing collision resolution techniques to identify the correct location and prevent overwriting the data corresponding to another key.

Below are some of the hashing collision techniques:

Collision Resolution By Separate Chaining

In this method, the actual data is stored in a linked list present at the hashed index location. So if two different keys have the same hashed index, both of them will be added to a linked list present at that index. Read More

Collision Resolution By Open Addressing

In this method, if the slot corresponding to the key where the object needs to be stored is filled, the next unfilled slot is used to store the data. While retrieving the object, we start from the index where it should ideally be stored and move ahead until we find the object or an empty slot. Read More