Linear probing is a simple way to deal with collisions in a hash table. A collision happens when two items should go in the same spot. Imagine a parking lot where each car has a specific spot. If a car finds its spot taken, it moves down the line to find the next open one. That’s linear probing!
Let’s say we have 5 parking spots for cars numbered 1 to 5. Car 3 arrives and parks in spot 3. Then car 8 arrives. Spot 8 is outside our lot, so we loop back and start from spot 1, finding spot 3 taken. We check spot 4, and it’s open, so car 8 parks there. This way, all cars find a spot using linear probing.
Important Point on Linear Probing
- 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.
How Linear Probing Works?
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.
Challenges and Solutions in Linear Probing
- Clustering: One issue with linear probing is clustering, where a bunch of occupied spots clump together, slowing down the insertion and search processes. To minimize clustering, the table should have enough empty spots and use a good hash function that spreads items evenly.
- Infinite Loops: If the table gets full, linear probing could get stuck in an infinite loop. Ensuring the table never gets completely full or implementing a resizing mechanism can prevent this.
Real-world Example of Linear Probing
Imagine a classroom with lockers numbered 1 to 100, where students’ locker numbers are their birthdays modulo 100. If two students have the same birthday, the second student to arrive checks the next locker until finding an empty one.
For example, if two students have their birthday on January 1st (assuming it simplifies to locker number 1), and locker 1 is taken, the second student checks locker 2, 3, and so on, until they find an empty locker.
Efficiency and Use Cases of Linear Probing
Linear probing shines in situations where quick insertion and lookup times are critical, and the dataset does not frequently approach the hash table’s capacity. It’s used in various applications, from language interpreters and compilers to databases and caching systems.
Similar Reads
-
Multiplications of Two variable polynomial
Polynomial multiplication is a common operation in algebra, used in areas such as scientific computing, engineering simulations, and symbolic algebra… -
Subtraction of Two-Variable Polynomial in C
Polynomials with two variables are common in engineering, graphics, and scientific computation. While addition is frequently discussed, subtraction is equally… -
Explain the Addition of Two variable polynomial
Polynomials are fundamental in mathematics, and their use extends into computer science, engineering, physics, and more. While single-variable polynomials are… -
Reverses the Doubly Circular Linked List
Algorithm to Reverse a Doubly Circular Linked List Check if the List is Empty or Has Only One Node: If… -
Algorithm and Program in C to traverse Doubly Circular Linked List
A doubly circular linked list is a special type of linked list in which every node is connected to both… -
Polynomial representation Using Array
Polynomials are fundamental mathematical expressions used extensively in various fields. Representing them efficiently in programming is crucial for calculations and… -
Multiplication of Single Variable Polynomial : Algorithm and Program
Multiplication of single-variable polynomials is a fundamental operation in polynomial algebra. The process involves multiplying each term of one polynomial… -
Subtraction of Single variable Polynomial : Algorithm and Program
Subtracting single-variable polynomials involves reducing each corresponding term of the polynomials from each other. This process is similar to addition,… -
Addition of Single variable Polynomial : Program and Algorithm
The addition of single-variable polynomials is a fundamental concept in algebra, often encountered in mathematics and computer science. Let's break… -
Polynomial Representation Using Linked List
Polynomial representation using linked lists is a critical concept in computer science and mathematics. In this guide, we explore how…