Related data structures: Hashtable, Array

##### Linear Probing

This method resolves the problem by probing or searching through alternative locations in the probe sequence until the target or an unused slot is found.

When two records demand for the same location in the hash table, the collision can be solved by placing second record linearly down wherever an empty location is found. Lookups are performed in the same way (by searching the table sequentially starting at the position given by the hash function) until finding a cell with a matching key or an empty cell. Because linear probing is especially sensitive to unevenly distributed hash values, it is important to combine it with a high-quality hash function that does not produce such irregularities.

Consider the following hash table.

Index Data
0
1 131
2 21
3 31
4 4
5 5
6 61
7 7
8 8
9

Given the hash table on the left, if the first number which is to be placed is 131 then 131 % 10 equals to 1. The remainder is 1, so the hash key is 1. That means we are supposed to place the record at index 1.

Next number is 21 which also gives hash key = 1 as 21 % 10 = 1. But 131 is already placed at index 1. That means collision has occurred. We will now apply linear probing.

In this method, we will search the place for number 21 from location of 131. In this case we can place the number 21 at index 2. Then if 31 has to be stored, it can be stored at index 3. Similarly, 61 can be stored at 6 because number 4 and 5 are stored before 61.
This technique makes the search operation efficient, as we have to search only limited list to obtain the desired number.

Example hashtable implementation holding maximum 10 student records.