Collision Resolution By Open Addressing

Open Addressing - Rob Edwards
Click here to suggest a better video
Click here to view videos suggested by visitors

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. Below is a sample illustration of how a hash table implementing open addressing looks (source: wikipedia):

In the above example, both “John Smith” and “Sandra Dee” are mapped to the same index “152”. But by the time the data of “Sandra Dee” is about to be stored, the slot at index “152” is already filled with data of “John Smith”. So the data of “Sandra Dee” is stored in the next available slot “153”.

TODO: Add more info about liner/quadratic probing and double hashing.