- The simplest approach to resolve a collision is linear probing. In this technique, if a value is already stored at a location generated by h(k), it means collision occurred then we do a sequential search to find the empty location.
- Here the idea is to place a value in the next available position. Because in this approach searches are performed sequentially so it’s known as linear probing.
- Here array or hash table is considered circular because when the last slot reached an empty location not found then the search proceeds to the first location of the array.

**Clustering is a major drawback of linear probing.**

Below is a hash function that calculates the next location. If the location is empty then store value otherwise find the next location.

Following hash function is used to resolve the collision in:**h(k, i) = [h(k) + i] mod m**

Where

**m** = size of the hash table,**h(k) = (k mod m)**,**i** = the probe number that varies from **0 to m–1**.

Therefore, for a given key k, the first location is generated by **[h(k) + 0]** mod m, the first time i=0.

If the location is free, the value is stored at this location. If value successfully** stores** then probe count is 1 means location is founded on the first go.

If location is not free then second probe generates the address of the location given by **[h(k) + 1]mod m**.

Similarly, if the generated location is occupied, then subsequent probes generate the address as **[h(k) + 2]mod m**, **[h(k) + 3]mod m**, **[h(k) + 4]mod m**, **[h(k) + 5]mod m**, and so on, until a free location is found.

**Probes is a count to find the free location for each value to store in the hash table.**

## Linear Probing Example

Insert the following sequence of keys in the hash table

**{9, 7, 11, 13, 12, 8}**

Use linear probing technique for collision resolution

h(k, i) = [h(k) + i] mod m

h(k) = 2k + 5

m=10

**Solution**:

**Step 01**:

First Draw an empty hash table of Size 10.

The possible range of hash values will be [0, 9].

**Step 02:**

Insert the given keys one by one in the hash table.

First Key to be inserted in the hash table = 9.

h(k) = 2k + 5

h(9) = 2*9 + 5 = 23

h(k, i) = [h(k) + i] mod m

h(9, 0) = [23 + 0] mod 10 = 3

So, key 9 will be inserted at index 3 of the hash table

**Step 03:**

Next Key to be inserted in the hash table = 7.

h(k) = 2k + 5

h(7) = 2*7 + 5 = 19

h(k, i) = [h(k) + i] mod m

h(7, 0) = [19 + 0] mod 10 = 9

So, key 7 will be inserted at index 9 of the hash table

**Step 04:**

Next Key to be inserted in the hash table = 11.

h(k) = 2k + 5

h(11) = 2*11 + 5 = 27

h(k, i) = [h(k) + i] mod m

h(11, 0) = [27 + 0] mod 10 = 7

So, key 11 will be inserted at index 7 of the hash table

**Step 05:**

Next Key to be inserted in the hash table = 13.

h(k) = 2k + 5

h(13) = 2*13 + 5 = 31

h(k, i) = [h(k) + i] mod m

h(13, 0) = [31 + 0] mod 10 = 1

So, key 13 will be inserted at index 1 of the hash table

**Step 06:**

Next key to be inserted in the hash table = 12.

h(k) = 2k + 5

h(12) = 2*12 + 5 = 27

h(k, i) = [h(k) + i] mod m

h(12, 0) = [27 + 0] mod 10 = 7

Here Collision has occurred because **index 7** is already filled.

Now we will increase **i by 1**.

h(12, 1) = [27 + 1] mod 10 = 8

So, key 12 will be inserted at index 8 of the hash table.

**Step 07:**

Next key to be inserted in the hash table = 8.

h(k) = 2k + 5

h(8) = 2*8 + 5 = 21

h(k, i) = [h(k) + i] mod m

h(8, 0) = [21 + 0] mod 10 = 1

Here Collision has occurred because **index 1** is already filled.

Now we will increase i by 1 now i become 1.

h(k) = 2k + 5

h(8) = 2*8 + 5 = 21

h(k, i) = [h(k) + i] mod m

h(8, 0) = [21 + 1] mod 10 = 2

index 2 is vacant so 8 will be inserted at index 2.

This is how the linear probing collision resolution technique works.

Share On :