Learning JavaScript Data Structures and Algorithms - Third Edition

Linear probing

Another technique of collision resolution is linear probing. It is called linear because the collision is handled in a way the values will be stored directly in the table, not in a separate data structure.

When we try to add a new element, if the position of the hash is already occupied, then we will try position +1. If position +1 is occupied, then we will try position + 2, and so on, until we find a free position in the hash table. Let's imagine we have a hash table with some values already in it and we want to add a new key and value. We calculate the hash for this new key and we check whether the position for the hash is already occupied. If it is not occupied, we add the value in the correct position. If it is occupied, ...