What is Linear Probing: Explanation and Example

Linear probing is a method used in hash tables to resolve collisions by checking the next available slot in a sequence. When a collision occurs, it moves step-by-step through the table until it finds an empty spot to store the data.

How It Works

Imagine you have a row of mailboxes, each with a number. When you want to put a letter in a mailbox, you use a formula to pick which mailbox to use. Sometimes, two letters want the same mailbox. This is called a collision.

Linear probing solves this by checking the next mailbox in order, one by one, until it finds an empty one. It’s like if your mailbox is full, you just move to the next mailbox until you find a free spot.

This way, all data is stored in the hash table without losing any, but it can slow down if many collisions happen because it has to check multiple spots.

Example

This example shows how linear probing inserts values into a hash table when collisions occur.

python

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

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

        self.table[index] = key

    def __str__(self):
        return str(self.table)

# Create a hash table of size 5
hash_table = LinearProbingHashTable(5)

# Insert keys
hash_table.insert(1)  # Goes to index 1
hash_table.insert(6)  # Collision at 1, goes to 2
hash_table.insert(11) # Collision at 1 and 2, goes to 3

print(hash_table)

Output

[None, 1, 6, 11, None]

When to Use

Linear probing is useful when you want a simple and fast way to handle collisions in hash tables. It works well when the table is not too full, so there are fewer collisions.

It is commonly used in situations like caching, databases, and memory management where quick data lookup is important. However, if the table gets crowded, performance can drop because many slots may need to be checked.

Key Points

• Linear probing handles collisions by checking the next slot sequentially.
• It keeps data in the hash table without losing entries.
• Performance decreases if the table is nearly full due to clustering.
• Simple to implement and efficient for low load factors.

Key Takeaways

Linear probing resolves hash collisions by searching the next available slot in order.

It is simple and effective when the hash table has low occupancy.

Performance can degrade due to clustering when many collisions occur.

Ideal for fast lookups in applications like caching and databases.