Linear Probing Collision Technique

Linear Probing is a collision resolution technique used in open addressing hash tables. When a collision occurs (i.e., the calculated hash index is already occupied), Linear Probing searches for the next available slot by moving sequentially forward through the array.

Imagine you are trying to park your car in a parking lot. You drive to your designated spot, but it's taken. Instead of leaving, you simply drive to the very next spot, check if it's empty, and park there. If that one is also taken, you move to the next, and so on. That is exactly how Linear Probing works.

The Probing Sequence

The formula for Linear Probing is:

h'(key) = (h(key) + i) % Table_Size

Where:

• h(key) is the original hash function.
• i is the probe number (0, 1, 2, 3,...).
• % Table_Size ensures we wrap around to the beginning if we reach the end.

How Linear Probing Works?

Let's use a hash table of size 10 (m = 10) and the hash function h(key) = key % 10. Insert the following keys in this exact order: 12, 22, 32, 42, 52

Step 1: Initialize the Hash Table

We start with an empty table of size 10.

Index:  0  1  2  3  4  5  6  7  8  9
       [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]

Step 2: Insert Key 12

• Calculate hash: 12 % 10 = 2.
• Check index 2. It is empty.
• Insert 12 at index 2.

Index:  0  1  2  3  4  5  6  7  8  9
       [ ][ ][12][ ][ ][ ][ ][ ][ ][ ]

Step 3: Insert Key 22

• Calculate hash: 22 % 10 = 2.
• Check index 2. It is occupied (by 12). Collision!
• Probe forward: i = 1 → (2 + 1) % 10 = 3.
• Check index 3. It is empty.
• Insert 22 at index 3.

Index:  0  1  2  3  4  5  6  7  8  9
       [ ][ ][12][22][ ][ ][ ][ ][ ][ ]

Step 4: Insert Key 32

• Calculate hash: 32 % 10 = 2.
• Check index 2. Occupied (12). Probe i=1 → index 3. Occupied (22).
• Probe i=2 → (2 + 2) % 10 = 4. Index 4 is empty.
• Insert 32 at index 4.

Index:  0  1  2  3  4  5  6  7  8  9
       [ ][ ][12][22][32][ ][ ][ ][ ][ ]

Step 5: Insert Key 42

• Hash: 42 % 10 = 2.
• Check index 2 (occupied), 3 (occupied), 4 (occupied).
• Probe i=3 → (2 + 3) % 10 = 5. Index 5 is empty.
• Insert 42 at index 5.

Index:  0  1  2  3  4  5  6  7  8  9
       [ ][ ][12][22][32][42][ ][ ][ ][ ]

Step 6: Insert Key 52

• Hash: 52 % 10 = 2.
• Check index 2, 3, 4, 5 (all occupied).
• Probe i=4 → (2 + 4) % 10 = 6. Index 6 is empty.
• Insert 52 at index 6.

Final Hash Table

Index:  0  1  2  3  4  5  6  7  8  9
       [ ][ ][12][22][32][42][52][ ][ ][ ]

Observation: All keys formed a continuous cluster (Primary Clustering) from index 2 to 6.

Algorithm for Linear Probing

Insertion Algorithm

Algorithm: LinearProbeInsert(T, key)
Input:  T - Hash table of size m
        key - Key to insert
Output: None (or error if table is full)

Step 1: START
Step 2: index = h(key)          // Compute initial hash
Step 3: i = 0
Step 4: WHILE i < m DO
Step 5:     probe = (index + i) % m
Step 6:     IF T[probe] is empty THEN
Step 7:         T[probe] = key
Step 8:         RETURN (Success)
Step 9:     ELSE
Step 10:        i = i + 1
Step 11: END WHILE
Step 12: RETURN (Table Full Error)
Step 13: END

Search Algorithm

Algorithm: LinearProbeSearch(T, key)
Input:  T - Hash table of size m
        key - Key to search
Output: Index of the key if found, otherwise -1

Step 1: START
Step 2: index = h(key)
Step 3: i = 0
Step 4: WHILE i < m DO
Step 5:     probe = (index + i) % m
Step 6:     IF T[probe] == key THEN
Step 7:         RETURN probe
Step 8:     IF T[probe] is empty THEN
Step 9:         RETURN -1     // Key not present
Step 10:    i = i + 1
Step 11: END WHILE
Step 12: RETURN -1
Step 13: END

Note: In the search algorithm, if we encounter an empty slot, we can stop searching because, by the rules of linear probing, the key would have been placed in the first empty slot available. If it's not here, it doesn't exist.

Implementation in C Programming

#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10
#define EMPTY -1

int hashTable[TABLE_SIZE];

// Initialize hash table
void initialize() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = EMPTY;
    }
}

// Hash function
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// Insert using Linear Probing
void insert(int key) {
    int index = hashFunction(key);
    int i = 0;
    
    while (i < TABLE_SIZE) {
        int probe = (index + i) % TABLE_SIZE;
        
        if (hashTable[probe] == EMPTY) {
            hashTable[probe] = key;
            printf("Inserted %d at index %d\n", key, probe);
            return;
        }
        i++;
    }
    
    printf("Hash table is full! Could not insert %d\n", key);
}

// Search using Linear Probing
int search(int key) {
    int index = hashFunction(key);
    int i = 0;
    
    while (i < TABLE_SIZE) {
        int probe = (index + i) % TABLE_SIZE;
        
        if (hashTable[probe] == key) {
            return probe;  // Found
        }
        
        // If we find an empty slot, key is not present
        if (hashTable[probe] == EMPTY) {
            return -1;
        }
        i++;
    }
    return -1;  // Not found
}

// Display the table
void display() {
    printf("\nHash Table (Linear Probing):\n");
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("Index %d: %d\n", i, hashTable[i]);
    }
}

int main() {
    initialize();
    
    int keys[] = {12, 22, 32, 42, 52};
    int n = sizeof(keys) / sizeof(keys[0]);
    
    for (int i = 0; i < n; i++) {
        insert(keys[i]);
    }
    
    display();
    
    int key = 32;
    int result = search(key);
    if (result != -1) {
        printf("\nElement %d found at index %d.\n", key, result);
    } else {
        printf("\nElement %d not found.\n", key);
    }
    
    return 0;
}

Output:

Inserted 12 at index 2
Inserted 22 at index 3
Inserted 32 at index 4
Inserted 42 at index 5
Inserted 52 at index 6

Hash Table (Linear Probing):
Index 0: -1
Index 1: -1
Index 2: 12
Index 3: 22
Index 4: 32
Index 5: 42
Index 6: 52
Index 7: -1
Index 8: -1
Index 9: -1

Element 32 found at index 4.

Complexity Analysis

Time Complexity

• Average Case: When the load factor (α = n/m) is low (e.g., < 0.5), the probe sequence is short. The expected number of probes is approximately 1 / (1 - α).
• Worst Case: If the table is nearly full or a massive cluster forms, we might have to scan the entire table.

Space Complexity

• O(1) – The algorithm uses only a constant amount of extra memory (loop variables). The table itself is O(n).

Advantages of Linear Probing

1. Extremely Simple: Easy to understand and implement.
2. Cache Efficient: Because it scans sequential memory locations, it utilizes CPU caches very well.
3. No Extra Memory: Unlike chaining, it does not require pointers or linked list nodes.

Disadvantages of Linear Probing

1. Primary Clustering: This is the biggest drawback. Consecutive occupied slots form a cluster. The larger the cluster, the higher the probability that a new key hashing into that cluster will extend it. This causes performance to degrade significantly as the table fills up.
2. Deletion Complexity: Deleting a key is tricky. If you simply remove it (set to EMPTY), the search algorithm might stop early and incorrectly report that a key (which was inserted after the deleted key) is not found. We typically use special "deleted" markers.
3. Table Full: Insertion fails if the table becomes completely full.

When to Use Linear Probing?

• When the load factor will be kept low (typically α < 0.5).
• When cache performance is critical.
• When you have limited memory and don't want the overhead of linked lists.
• When the dataset is relatively small or static.

Practice Questions

1. A hash table has m=10 slots and uses the hash function h(k) = k mod  10. Insert the following keys into the hash table using linear probing: 12,22,32,42,52 Show the final hash table after all insertions.
2. A hash table with m = 7 slots has the following keys inserted using linear probing: 10,20,15,25,35 The hash function is h(k) = k mod  7.
   1. Find the position of the key 25.
   2. Determine the number of probes required to search for 15.
3. A hash table of size m=5 uses the hash function h(k) = k mod  5. Insert the keys: 21,26,31,16,35,41
   1. Show the final hash table after all insertions.
   2. How many collisions occurred in total?