Quadratic Probing in Hashing in C: Complete Guide

Quadratic Probing in Hashing in C: A Comprehensive Tutorial

Quadratic Probing is an Open Addressing collision resolution technique where, instead of probing linearly, we jump by quadratically increasing offsets. This reduces the primary clustering problem of linear probing, though it introduces a milder secondary clustering. It’s a widely used technique in high-performance hash tables.

This tutorial provides an in-depth exploration of Quadratic Probing in C: fundamental concepts, probe sequences, implementation, the modified formula for full table utilization, complexity analysis, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is Quadratic Probing?

Quadratic Probing is an open-addressing scheme where, on collision at index h(k), we probe slots at (h(k) + i²) % m for i = 0, 1, 2, ... until we find an empty or matching slot.

Probe sequence: (h(k) + 0²) % m, (h(k) + 1²) % m, (h(k) + 2²) % m, …

Why Quadratic Probing?

• Reduces primary clustering: Unlike linear probing, keys hashing to nearby slots don’t always collide.
• Better than linear probing: Distributes keys more uniformly in clustered regions.
• No extra memory: All keys stored in the table itself.
• Cache-friendly-ish: Jumps are still predictable but larger.

Probe Sequence Example

For hash function h(k) = k % 7 and keys [22, 30, 50]:

text

22 → 22 % 7 = 1 (place at index 1) 30 → 30 % 7 = 2 (place at index 2) 50 → 50 % 7 = 1 (collision!) Probe i=1: (1 + 1) % 7 = 2 (occupied) Probe i=2: (1 + 4) % 7 = 5 (empty → place at index 5)

Result: [_, 22, 30, _, _, 50, _]

Primary vs Secondary Clustering

Clustering	Description	Affects
Primary	Contiguous blocks of occupied slots	Linear probing
Secondary	Keys hashing to the same index follow identical probes	Quadratic probing

Quadratic probing eliminates primary clustering but retains secondary clustering.

The Full-Utilization Problem

With a standard quadratic probe (h(k) + i²) % m, the sequence may not visit all slots, especially if m is not prime. This can cause failed insertions even when empty slots exist.

Example: Table size 11 with keys [21, 10, 32, 43, 54, 65, 87, 76] fails to insert 87 and 76 with standard formula.

The Modified Probe Formula

For guaranteed full utilization, use this probe formula with m' = nextPowerOf2(m):

text

probe(k, i) = (h(k) + (i + i²) / 2) % m'

This produces the triangular number sequence: 0, 1, 3, 6, 10, 15, … which visits every slot exactly once when m' is a power of 2.

Complexity Analysis

Operation	Average	Worst
Insert	O(1)	O(n)
Search	O(1)	O(n)
Delete	O(1)	O(n)

At load factor α < 0.5, quadratic probing performs nearly as well as double hashing.

---

Syntax & Core Mechanics

Standard Quadratic Probing

c

/* Standard quadratic probe */ int probe = (hashValue + i * i) % tableSize;

Modified Quadratic Probing (Full Utilization)

c

/* Modified formula with next power of 2 */ int probe = (hashValue + (i + i * i) / 2) % nextPowerOf2(tableSize); if (probe >= tableSize) continue; /* Skip out-of-bounds */

Compute Next Power of 2

c

int nextPowerOf2(int n) { n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; n++; return n; }

Insertion Algorithm

1. Compute h = hash(key).
2. If table[h] is EMPTY, insert.
3. Else, probe i = 1, 2, ... with (h + i²) % m (or modified formula).
4. Stop when EMPTY slot found or all slots probed.

Deletion

Same tombstone approach as linear probing: mark slot as DELETED.

---

Full Practical Code Example with Explanation

This program demonstrates both standard and modified quadratic probing with a complete hash table.

c

/** * quadratic_probing.c * Demonstrates quadratic probing in hash tables. * Supports standard and modified probe sequences. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #define MAX_LINE_LEN 100 #define EMPTY (-1) #define DELETED (-2) #define REHASH_THRESHOLD 0.5 /* Slot in the hash table */ typedef struct { int key; int value; } Slot; /* Hash table using quadratic probing */ typedef struct { Slot *slots; int capacity; int size; int deletedCount; int useModified; } HashTable; /* Next power of 2 >= n */ static int nextPowerOf2(int n) { if (n <= 1) return 1; n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; n++; return n; } /* Hash function */ static unsigned int hashIndex(int key, int capacity) { return ((unsigned int)key) % (unsigned int)capacity; } /* Compute probe index for step i */ static int probeIndex(int baseIdx, int i, int capacity, int useModified) { int result; if (useModified) { int m = nextPowerOf2(capacity); result = (int)((unsigned int)(baseIdx + (i + i * i) / 2) % (unsigned int)m); } else { result = (int)((unsigned int)(baseIdx + i * i) % (unsigned int)capacity); } return result; } /* Create hash table */ HashTable *createHashTable(int initialCapacity, int useModified) { HashTable *ht = malloc(sizeof(HashTable)); if (ht == NULL) return NULL; ht->slots = malloc(initialCapacity * sizeof(Slot)); if (ht->slots == NULL) { free(ht); return NULL; } for (int i = 0; i < initialCapacity; i++) { ht->slots[i].key = EMPTY; ht->slots[i].value = 0; } ht->capacity = initialCapacity; ht->size = 0; ht->deletedCount = 0; ht->useModified = useModified; return ht; } void freeHashTable(HashTable *ht) { if (ht == NULL) return; free(ht->slots); free(ht); } /* Rehash: double capacity and reinsert all live entries */ static int rehash(HashTable *ht) { int oldCap = ht->capacity; Slot *oldSlots = ht->slots; int newCap = oldCap * 2 + 1; Slot *newSlots = malloc(newCap * sizeof(Slot)); if (newSlots == NULL) return -1; for (int i = 0; i < newCap; i++) { newSlots[i].key = EMPTY; newSlots[i].value = 0; } ht->slots = newSlots; ht->capacity = newCap; ht->size = 0; ht->deletedCount = 0; for (int i = 0; i < oldCap; i++) { if (oldSlots[i].key != EMPTY && oldSlots[i].key != DELETED) { int key = oldSlots[i].key; int value = oldSlots[i].value; unsigned int base = hashIndex(key, newCap); for (int i2 = 0; i2 < newCap; i2++) { int pos = probeIndex((int)base, i2, newCap, ht->useModified); if (pos >= newCap) continue; if (newSlots[pos].key == EMPTY) { newSlots[pos].key = key; newSlots[pos].value = value; ht->size++; break; } } } } free(oldSlots); return 0; } /* Insert or update */ int insert(HashTable *ht, int key, int value) { double lf = (double)(ht->size + ht->deletedCount) / ht->capacity; if (lf > REHASH_THRESHOLD) { if (rehash(ht) != 0) return -1; } unsigned int base = hashIndex(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = probeIndex((int)base, i, ht->capacity, ht->useModified); if (ht->useModified && pos >= ht->capacity) continue; if (ht->slots[pos].key == key) { ht->slots[pos].value = value; return 0; } if (ht->slots[pos].key == EMPTY || ht->slots[pos].key == DELETED) { if (ht->slots[pos].key == DELETED) ht->deletedCount--; ht->slots[pos].key = key; ht->slots[pos].value = value; ht->size++; return 0; } } return -1; } /* Search */ int search(const HashTable *ht, int key, int *outValue) { unsigned int base = hashIndex(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = probeIndex((int)base, i, ht->capacity, ht->useModified); if (ht->useModified && pos >= ht->capacity) continue; if (ht->slots[pos].key == EMPTY) return 0; if (ht->slots[pos].key == key) { *outValue = ht->slots[pos].value; return 1; } } return 0; } /* Delete */ int deleteKey(HashTable *ht, int key) { unsigned int base = hashIndex(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = probeIndex((int)base, i, ht->capacity, ht->useModified); if (ht->useModified && pos >= ht->capacity) continue; if (ht->slots[pos].key == EMPTY) return -1; if (ht->slots[pos].key == key) { ht->slots[pos].key = DELETED; ht->deletedCount++; ht->size--; return 0; } } return -1; } /* Display */ void display(const HashTable *ht) { double lf = (double)ht->size / ht->capacity; printf("Hash Table (%s, size=%d, capacity=%d, deleted=%d, load=%.2f):\n", ht->useModified ? "modified" : "standard", ht->size, ht->capacity, ht->deletedCount, lf); for (int i = 0; i < ht->capacity; i++) { printf(" [%2d]: ", i); if (ht->slots[i].key == EMPTY) printf("EMPTY\n"); else if (ht->slots[i].key == DELETED) printf("DELETED\n"); else printf("(%d → %d)\n", ht->slots[i].key, ht->slots[i].value); } } /* ============ Demos ============ */ static void demoStandard(void) { printf("\n=== Standard Quadratic Probing ===\n"); HashTable *ht = createHashTable(11, 0); if (ht == NULL) return; int keys[] = {50, 700, 76, 85, 92, 73, 101}; int n = sizeof(keys) / sizeof(keys[0]); for (int i = 0; i < n; i++) { insert(ht, keys[i], keys[i]); } display(ht); printf("\nSlots: "); for (int i = 0; i < ht->capacity; i++) { printf("%d ", ht->slots[i].key); } printf("\n"); freeHashTable(ht); } static void demoModified(void) { printf("\n=== Modified Quadratic Probing (Full Utilization) ===\n"); HashTable *ht = createHashTable(11, 1); if (ht == NULL) return; int keys[] = {21, 10, 32, 43, 54, 65, 87, 76}; int n = sizeof(keys) / sizeof(keys[0]); for (int i = 0; i < n; i++) { insert(ht, keys[i], keys[i]); } display(ht); printf("\nSlots: "); for (int i = 0; i < ht->capacity; i++) { printf("%d ", ht->slots[i].key); } printf("\n"); freeHashTable(ht); } static void demoOperations(void) { printf("\n=== Standard Operations ===\n"); HashTable *ht = createHashTable(11, 0); if (ht == NULL) return; insert(ht, 22, 220); insert(ht, 30, 300); insert(ht, 50, 500); insert(ht, 12, 120); display(ht); int value; printf("\nSearch 30: "); if (search(ht, 30, &value)) printf("%d\n", value); else printf("not found\n"); printf("Delete 30...\n"); deleteKey(ht, 30); display(ht); printf("\nSearch 50 (after delete): "); if (search(ht, 50, &value)) printf("%d\n", value); else printf("not found\n"); freeHashTable(ht); } static int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) return -1; errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) return -1; if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) return -1; *outValue = (int)val; return 0; } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Quadratic Probing in Hashing Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Standard Quadratic Probing\n"); printf("2. Modified Quadratic Probing (Full Utilization)\n"); printf("3. Operations Demo (Insert/Search/Delete)\n"); printf("4. Interactive Hash Table\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); if (choice == 1) { demoStandard(); } else if (choice == 2) { demoModified(); } else if (choice == 3) { demoOperations(); } else if (choice == 4) { HashTable *ht = createHashTable(11, 0); if (ht == NULL) continue; int opt; while (1) { printf("\n--- Interactive Hash Table ---\n"); printf("1. Insert\n2. Search\n3. Delete\n4. Display\n5. Back\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) break; opt = atoi(buffer); if (opt == 1) { int k, v; if (readInteger("Key: ", &k) == 0 && readInteger("Value: ", &v) == 0) { insert(ht, k, v); printf("Inserted (%d → %d)\n", k, v); } } else if (opt == 2) { int k, v; if (readInteger("Key: ", &k) == 0) { if (search(ht, k, &v)) printf("Found: %d → %d\n", k, v); else printf("Key %d not found\n", k); } } else if (opt == 3) { int k; if (readInteger("Key: ", &k) == 0) { if (deleteKey(ht, k) == 0) printf("Deleted %d\n", k); else printf("Key %d not found\n", k); } } else if (opt == 4) { display(ht); } else if (opt == 5) { break; } } freeHashTable(ht); } else if (choice == 5) { printf("Exiting.\n"); return EXIT_SUCCESS; } else { printf("Invalid choice.\n"); } } return EXIT_SUCCESS; }

Explanation

1. Slot — Stores key and value; sentinel keys mark EMPTY/DELETED.
2. probeIndex — Computes probe index for standard or modified quadratic probing.
3. nextPowerOf2 — Required by the modified formula for full utilization.
4. insert / search / deleteKey — Probe iteratively using probeIndex.
5. rehash — Doubles capacity when load factor exceeds 0.5.
6. display — Prints each slot and its state.

Expected Output (sample run)

text

=== Standard Quadratic Probing === Hash Table (standard, size=7, capacity=11, deleted=0, load=0.64): [ 0]: (73 → 73) [ 1]: EMPTY [ 2]: (101 → 101) [ 3]: EMPTY [ 4]: (92 → 92) [ 5]: EMPTY [ 6]: (50 → 50) [ 7]: (700 → 700) [ 8]: (85 → 85) [ 9]: EMPTY [10]: (76 → 76) Slots: 73 -1 101 -1 92 -1 50 700 85 -1 76 === Modified Quadratic Probing (Full Utilization) === Hash Table (modified, size=8, capacity=11, deleted=0, load=0.73): [ 0]: (10 → 10) [ 1]: (87 → 87) [ 2]: EMPTY [ 3]: EMPTY [ 4]: (32 → 32) [ 5]: EMPTY [ 6]: (54 → 54) [ 7]: (65 → 65) [ 8]: (76 → 76) [ 9]: (43 → 43) [10]: (21 → 21) Slots: 10 87 -1 -1 32 -1 54 65 76 43 21

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Probe Sequence Not Reaching All Slots

Standard quadratic probing may not visit every slot when m is not prime.

Solution: Use the modified formula with m' = nextPowerOf2(m).

2. Out-of-Bounds with Modified Formula

When m' > m, the computed index may exceed the table size.

c

if (pos >= ht->capacity) continue;

3. Infinite Probe Loop

Unbounded probing without finding an empty slot.

Solution: Bound the loop by capacity or nextPowerOf2(capacity).

4. Table Full (Even With Empty Slots)

Standard formula may fail to find an empty slot even when one exists.

Solution: Use the modified formula.

5. Tombstone Accumulation

Frequent deletes degrade performance.

Solution: Track deletedCount and trigger rehash when (size + deleted) / capacity > threshold.

6. Load Factor Too High

Quadratic probing degrades near α = 1.

Solution: Keep α < 0.5 and rehash proactively.

7. Secondary Clustering

Keys hashing to the same initial index follow identical probes.

Solution: Use double hashing for better distribution.

8. Rehash During Insert

Ensure rehash happens before computing the probe index.

9. Negative Keys

Cast to unsigned int before modulo.

10. Memory Considerations

• Table memory: capacity × sizeof(Slot).
• No pointer overhead.
• Rehashing doubles memory temporarily.
• Free slots array on cleanup.

---

Summary & Best Practices

Quadratic Probing reduces primary clustering compared to linear probing while remaining memory-efficient. For guaranteed full utilization, use the modified formula with a next power-of-2 table size.

Key Takeaways

• Probe sequence: (h(k) + i²) % m (standard) or (h(k) + (i + i²)/2) % m' (modified).
• Reduces primary clustering but retains secondary clustering.
• Standard formula may fail; modified formula guarantees full utilization.
• Keep load factor below 0.5.
• Deletion requires tombstones.
• Complexity: O(1) average; O(n) worst.

Best Practices

1. Use the modified formula with nextPowerOf2 for guaranteed full utilization.
2. Keep load factor < 0.5 for good performance.
3. Bound probe loops by table size or power-of-2 size.
4. Skip out-of-bounds indices in modified probing.
5. Use tombstones for deletion.
6. Rehash proactively when load factor exceeds threshold.
7. Cast keys to unsigned before modulo.
8. Consider double hashing for even better distribution.
9. Free the slots array on cleanup.
10. Test with high-collision keys to verify correctness.

By mastering quadratic probing, you’ll implement efficient in-place hash tables with better clustering behavior than linear probing.