Quadratic Probing Collision Technique

Quadratic Probing is a collision resolution technique used in open addressing hash tables. When a collision occurs, instead of checking the next sequential slot (like linear probing), Quadratic Probing checks slots at quadratic intervals.

Think of it like this: You arrive at a parking spot and it's taken. Instead of checking the very next spot, you check spots that are increasingly far away: 1 spot away, then 4 spots away, then 9 spots away, then 16 spots away, and so on. 

This helps to distribute keys more evenly and reduces the clustering problem found in linear probing.

The Probing Sequence

The formula for Quadratic Probing is: 

h'(key) = (h(key) + c1*i + c2*i²) % Table_Size

The most common and simplest form uses c1 = 0 and c2 = 1:

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

Where:

• h(key) is the original hash function.
• i is the probe number (0, 1, 2, 3,...).
• i² is the quadratic increment (0, 1, 4, 9, 16, 25,...).

How Quadratic 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 89, 18, 49, 58, 79

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 89

• Calculate hash: 89 % 10 = 9.
• Check index 9. It is empty.
• Insert 89 at index 9.

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

Step 3: Insert Key 18

• Calculate hash: 18 % 10 = 8.
• Check index 8. It is empty.
• Insert 18 at index 8.

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

Step 4: Insert Key 49 (Collision Occurs!)

• Calculate hash: 49 % 10 = 9.
• Check index 9. It is occupied (by 89). Collision!
• Probe Sequence (using i²):
  • i = 1: (9 + 1²) % 10 = (9 + 1) % 10 = 0. Check index 0. It is empty.
• Insert 49 at index 0.

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

Step 5: Insert Key 58 (Collision Occurs!)

• Calculate hash: 58 % 10 = 8.
• Check index 8. It is occupied (by 18). Collision!
• Probe Sequence:
  • i = 1: (8 + 1²) % 10 = 9. Index 9 is occupied (by 89).
  • i = 2: (8 + 2²) % 10 = (8 + 4) % 10 = 12 % 10 = 2. Index 2 is empty.
• Insert 58 at index 2.

Index:  0   1   2  3  4  5  6  7   8   9
       [49][ ][58][ ][ ][ ][ ][ ][18][89]

Step 6: Insert Key 79 (Collision Occurs!)

• Calculate hash: 79 % 10 = 9.
• Check index 9. It is occupied (by 89). Collision!
• Probe Sequence:
  • i = 1: (9 + 1²) % 10 = 0. Index 0 is occupied (by 49).
  • i = 2: (9 + 2²) % 10 = (9 + 4) % 10 = 13 % 10 = 3. Index 3 is empty.
• Insert 79 at index 3.

Final Hash Table

Index:  0  1  2  3  4  5  6  7  8  9
       [49][ ][58][79][ ][ ][ ][ ][18][89]

Observation: Notice how the keys are now more spread out compared to linear probing. Instead of forming one large cluster at indices 8 and 9, they are distributed across indices 0, 2, 3, 8, and 9.

Algorithm for Quadratic Probing

Insertion Algorithm

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

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 or No Empty Slot Found)
Step 13: END

Search Algorithm

Algorithm: QuadraticProbeSearch(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

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 Quadratic Probing
void insert(int key) {
    int index = hashFunction(key);
    int i = 0;
    
    while (i < TABLE_SIZE) {
        int probe = (index + i * i) % TABLE_SIZE;
        
        if (hashTable[probe] == EMPTY) {
            hashTable[probe] = key;
            printf("Inserted %d at index %d (i=%d)\n", key, probe, i);
            return;
        }
        i++;
    }
    
    printf("Hash table is full or no suitable slot! Could not insert %d\n", key);
}

// Search using Quadratic Probing
int search(int key) {
    int index = hashFunction(key);
    int i = 0;
    
    while (i < TABLE_SIZE) {
        int probe = (index + i * 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 (Quadratic Probing):\n");
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("Index %d: %d\n", i, hashTable[i]);
    }
}

int main() {
    initialize();
    
    int keys[] = {89, 18, 49, 58, 79};
    int n = sizeof(keys) / sizeof(keys[0]);
    
    for (int i = 0; i < n; i++) {
        insert(keys[i]);
    }
    
    display();
    
    int key = 58;
    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 89 at index 9 (i=0)
Inserted 18 at index 8 (i=0)
Inserted 49 at index 0 (i=1)
Inserted 58 at index 2 (i=2)
Inserted 79 at index 3 (i=2)

Hash Table (Quadratic Probing):
Index 0: 49
Index 1: -1
Index 2: 58
Index 3: 79
Index 4: -1
Index 5: -1
Index 6: -1
Index 7: -1
Index 8: 18
Index 9: 89

Element 58 found at index 2.

Complexity Analysis

Time Complexity

Explanation: Similar to linear probing, the average case depends on the load factor (α = n/m). With a low load factor, the expected number of probes is approximately 1 / (1 - α).

Space Complexity

• O(1) – Only constant extra memory is used.

Advantages of Quadratic Probing

1. Reduces Primary Clustering: Unlike linear probing, quadratic probing jumps over slots, breaking up large clusters.
2. Better Distribution: Keys are spread more evenly across the table.
3. Simple to Implement: Almost as easy as linear probing.
4. Cache Efficient: Still uses an array, so it has good cache performance (though not as good as linear probing due to non-sequential access).

Disadvantages of Quadratic Probing

1. Secondary Clustering: Keys that hash to the same initial index will follow the same probe sequence (i.e., they will visit the same set of slots). This is called secondary clustering. It's less severe than primary clustering but still exists.
2. May Not Find an Empty Slot: Unlike linear probing, quadratic probing does not guarantee to find an empty slot even if the table is not completely full. It may cycle through a limited set of slots and miss empty ones.
3. Table Size Restriction: To guarantee that the entire table is probed, the table size m must be a prime number and the load factor must be less than 0.5 (in some variations, m must be a power of 2 with certain conditions).

The Table Size Problem

The probe sequence in quadratic probing might not cover all slots. For example, with m = 8, the sequence for i = 0, 1, 2, 3,... might only visit indices 0, 1, 4, 1, 0, 1, 4,... (repeating). This means many slots will never be checked, causing insertion to fail even if the table has free space.

Solution: Use a prime number for the table size. With a prime m, the quadratic probing sequence will visit at least half the slots (for i < m/2), and if m is prime and α < 0.5, we are guaranteed to find an empty slot if one exists.

When to Use Quadratic Probing?

• When you want to avoid primary clustering.
• When the load factor will be kept low (α < 0.5).
• When you have a prime table size.
• When you prefer open addressing over chaining.

Practice Questions

1. Insert the following keys into a hash table of size 10 using quadratic probing 45, 25, 35, 15, 55
   1. Use the hash function: h(key) = key % 10
   2. Show the status of the hash table after each insertion.
2. Given the following keys: 17, 29, 41, 55, 68
   1. Use a hash table of size 11
   2. Hash function: h(key) = key % 11
   3. Use quadratic probing to resolve collisions
   4. Show final hash table and explain steps.
3. A hash table has size 13 and uses quadratic probing. Insert the following keys: 18, 41, 22, 44, 59, 32
   1. Use hash function: h(key) = key % 13
   2. What index does each key go into?
   3. Are there any keys that cannot be inserted if the table is half full? Why?