Linear Probing: Simple Open Addressing Technique Explained with Examples

Linear Probing is one of the simplest and most widely used techniques for resolving collisions in hash tables using open addressing. When two keys are mapped to the same index in a hash table, instead of storing data in linked lists (like in separate chaining), linear probing places the item in the next nearest empty slot by sequentially scanning the table. This makes it efficient, easy to implement, and cache-friendly.

Table of Contents

What is Linear Probing?

A hash table is a data structure that maps keys to values using a hash function. Collisions occur when multiple keys map to the same index. Linear probing resolves this issue by checking subsequent slots linearly until an empty space is found.

For example:

Hash function maps a key to index i.
If slot i is occupied, check i+1.
If i+1 is also occupied, check i+2.
Continue this process until an empty slot is found.

Linear Probing Example

Let’s say we have a hash table of size 7 and we want to insert keys [50, 700, 76, 85, 92, 73] using h(key) = key % 7.

Step-by-step insertion:

50 % 7 = 1 → Place 50 at index 1.
700 % 7 = 0 → Place 700 at index 0.
76 % 7 = 6 → Place 76 at index 6.
85 % 7 = 1 → Index 1 is occupied → check index 2 → Place 85 at index 2.
92 % 7 = 1 → Index 1 is occupied → check index 2 (again occupied) → check index 3 → Place 92 at index 3.
73 % 7 = 3 → Index 3 is occupied → check index 4 → Place 73 at index 4.

Advantages of Linear Probing

Cache-friendly since data is stored in consecutive slots.
Easy to implement compared to separate chaining.
No extra memory is required for pointers or linked lists.

Disadvantages of Linear Probing

Primary Clustering: Collisions tend to create large blocks of filled slots, increasing the chance of further collisions.
May require multiple probes before finding an empty slot, slowing insertions and searches when the table load is high.

Python Implementation of Linear Probing


class LinearProbingHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return key % self.size

    def insert(self, key):
        index = self.hash_function(key)
        start_index = index  # remember start to avoid infinite loop

        while self.table[index] is not None:
            index = (index + 1) % self.size
            if index == start_index:  # full table
                raise Exception("Hash Table is full")

        self.table[index] = key

    def search(self, key):
        index = self.hash_function(key)
        start_index = index

        while self.table[index] is not None:
            if self.table[index] == key:
                return index
            index = (index + 1) % self.size
            if index == start_index:
                break
        return None

    def display(self):
        for i, val in enumerate(self.table):
            print(f"{i}: {val}")

# Example usage
ht = LinearProbingHashTable(7)
for k in [50, 700, 76, 85, 92, 73]:
    ht.insert(k)

ht.display()

Sample Output:

0: 700
1: 50
2: 85
3: 92
4: 73
5: None
6: 76

Interactive Visualization of Linear Probing

Here’s a simple way to visualize probing steps while searching for 92 in the example table:

Performance Analysis

Efficiency of linear probing depends on load factor (α = number of elements / table size):

For low load factors (α < 0.5), searching and inserting is very efficient (close to O(1)).
As α approaches 1, performance degrades due to clustering.
In the worst case, an operation may take O(n) when the table is nearly full.

When to Use Linear Probing?

Linear probing is ideal when:

You need a compact, memory-efficient hash table.
Cache locality is important for performance.
You can keep the load factor under 0.7 through resizing or rehashing.

Conclusion

Linear probing is a simple, efficient, and cache-friendly collision resolution technique for hash tables. It works by checking slots sequentially until an empty one is found, making it straightforward to implement. While it has the drawback of clustering under high load factors, it remains a popular choice due to its speed and simplicity in practice.

By understanding this technique with clear examples and Python implementation, you now have the knowledge to apply linear probing effectively in your data structures and algorithm projects.