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: