Introduction to linear probing

Now that we know how a hash table is implemented using separate chaining and its advantages and disadvantages, we look at another popular collision resolution scheme called linear probing. One major disadvantage of separate chaining schemes is that the table size is not limited. Because the chain data structure is scattered(non-contiguous) throughout the memory, it does not benefit from the locality of reference.

In the linear probing scheme, the internal array stores the key-value pair. The size of the internal array limits the size of the hash table. Because the array is a contiguous memory, it has performance benefits due to the locality of reference.