Collisions in Hash Tables

In the previous sections, we took a look at how hash tables can help us store a lot of keys in a way that makes it easy to look up any required key. However, we also encountered a problem where multiple keys had the same hash value, also known as a collision. In Exercise 13, Basic Dictionary for Integers, we handled this issue by simply rewriting the key and retaining the latest key corresponding to a given hash value. However, this does not allow us to store all the keys. In the following subtopics, we shall take a look at a couple of approaches that help us overcome this problem and allow us to retain all of our key values in the hash table.

Close Addressing – Chaining

So far, we've only been storing a single element for any hash value. If we already have an element for a particular hash value, we have no option but to discard either the new value or the old value. The method of chaining is one way we can retain both values. In this method, instead of...