Linear Probing in Hash Tables in C: Complete Guide

Linear Probing in Hash Tables in C: A Comprehensive Tutorial

Linear Probing is the simplest and most widely used Open Addressing collision resolution technique. When a collision occurs, the algorithm probes the next slot in the table linearly until it finds an empty, deleted, or matching slot. All elements are stored directly in the hash table itself, requiring no auxiliary linked lists.

This tutorial provides an in-depth exploration of Linear Probing in C: fundamental concepts, insertion, search, deletion with tombstones, rehashing, complexity analysis, complete implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is Linear Probing?

Linear Probing is an Open Addressing strategy where, on collision at index h(k), we check h(k) + 1, h(k) + 2, … (modulo table size) until we find a suitable slot.

Probe sequence: (h(k) + i) % m for i = 0, 1, 2, ..., m-1

Why Linear Probing?

• No extra memory: All elements are stored directly in the table.
• Cache-friendly: Sequential probing has excellent cache locality.
• Simple to implement: No linked lists or pointers needed.
• Fast for low load factors: α < 0.7 yields O(1) average operations.

Key Concepts

Concept	Description
Open Addressing	All keys stored in the table itself
Probe	Sequence of slots examined on collision
Load Factor (α)	n / m (entries / table size)
Tombstone	Marker for deleted slot
Clustering	Adjacent occupied slots form a cluster
Rehashing	Resizing table when α exceeds threshold

The Tombstone Problem

Simply clearing a deleted slot would break probe chains. Instead, mark the slot with a tombstone (a special value indicating deletion). Searches continue past tombstones; insertions may reuse them.

Example issue without tombstones:

text

Insert 1, 11, 21 with h(k) = k % 10: [1]: 1, [2]: 11, [3]: 21 Delete 11 (clear slot): [1]: 1, [2]: EMPTY, [3]: 21 Search 21 → hits EMPTY at [2], stops, reports "not found" (BUG!)

With tombstone:

text

Delete 11 (mark as DELETED): [1]: 1, [2]: DELETED, [3]: 21 Search 21 → passes [2] tombstone, finds 21 at [3] ✓

Complexity Analysis

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

Worst case occurs when many collisions cluster keys (primary clustering).

Linear Probing vs Chaining

Aspect	Linear Probing	Chaining
Memory	No pointers; table-only	Extra pointer per entry
Cache	Excellent locality	Poor for long chains
Load factor	Must stay < 1	Can exceed 1
Deletion	Requires tombstones	Direct node removal
Clustering	Primary clustering	None
Performance	Degrades fast near α = 1	Degrades linearly

---

Syntax & Core Mechanics

Slot States

c

#define EMPTY (-1) #define DELETED (-2)

We use sentinel keys to mark empty and deleted slots.

Basic Structure

c

typedef struct { int *keys; /* Keys array */ int *values; /* Values array */ int *states; /* EMPTY, DELETED, or OCCUPIED (0/1) */ int capacity; int size; } HashTable;

Alternative: Use a single sentinel key DELETED (e.g., -1) with the slot’s key field.

c

typedef struct { int key; /* -1 = empty, -2 = deleted */ int value; } Slot; typedef struct { Slot *slots; int capacity; int size; } HashTable;

Insertion Algorithm

1. Compute idx = h(key).
2. Probe: pos = (idx + i) % m for i = 0, 1, ....
3. If slots[pos].key == EMPTY or DELETED: insert; if it was EMPTY, increment size.
4. If slots[pos].key == key: update value.
5. Continue until inserted or full.

Search Algorithm

1. Compute idx = h(key).
2. Probe: pos = (idx + i) % m.
3. If slots[pos].key == key: found.
4. If slots[pos].key == EMPTY: stop (key absent).
5. If slots[pos].key == DELETED: continue probing.
6. Stop after examining all slots.

Deletion Algorithm

1. Find the key via probe.
2. Replace with DELETED marker (tombstone).
3. Decrement size.

Rehashing

When load factor > threshold (typically 0.7):

1. Double capacity (choose prime).
2. Create new slot array (all EMPTY).
3. Reinsert all non-empty, non-deleted entries.

---

Full Practical Code Example with Explanation

This program implements a complete hash table using linear probing with tombstones and rehashing.

c

/** * linear_probing.c * Complete hash table implementation using linear probing. * Supports insert, search, delete, rehashing, and display. */ #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.7 /* Slot in the hash table */ typedef struct { int key; /* EMPTY, DELETED, or a valid key */ int value; } Slot; /* Hash table using linear probing */ typedef struct { Slot *slots; int capacity; int size; /* Number of live entries */ int deletedCount; } HashTable; /* Find next prime >= n */ static int nextPrime(int n) { if (n <= 2) return 2; if (n % 2 == 0) n++; while (1) { int isPrime = 1; for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) { isPrime = 0; break; } } if (isPrime) return n; n += 2; } } /* Hash function */ static unsigned int hashIndex(int key, int capacity) { return ((unsigned int)key) % (unsigned int)capacity; } /* Create a hash table with given initial capacity */ HashTable *createHashTable(int initialCapacity) { HashTable *ht = malloc(sizeof(HashTable)); if (ht == NULL) return NULL; int capacity = nextPrime(initialCapacity); ht->slots = malloc(capacity * sizeof(Slot)); if (ht->slots == NULL) { free(ht); return NULL; } for (int i = 0; i < capacity; i++) { ht->slots[i].key = EMPTY; ht->slots[i].value = 0; } ht->capacity = capacity; ht->size = 0; ht->deletedCount = 0; return ht; } void freeHashTable(HashTable *ht) { if (ht == NULL) return; free(ht->slots); free(ht); } /* Rehash: grow table and reinsert entries */ static int rehash(HashTable *ht) { int oldCapacity = ht->capacity; Slot *oldSlots = ht->slots; int newCapacity = nextPrime(oldCapacity * 2); Slot *newSlots = malloc(newCapacity * sizeof(Slot)); if (newSlots == NULL) return -1; for (int i = 0; i < newCapacity; i++) { newSlots[i].key = EMPTY; newSlots[i].value = 0; } ht->slots = newSlots; ht->capacity = newCapacity; ht->size = 0; ht->deletedCount = 0; for (int i = 0; i < oldCapacity; i++) { if (oldSlots[i].key != EMPTY && oldSlots[i].key != DELETED) { int key = oldSlots[i].key; int value = oldSlots[i].value; unsigned int idx = hashIndex(key, newCapacity); for (int j = 0; j < newCapacity; j++) { int pos = (int)((idx + (unsigned int)j) % (unsigned int)newCapacity); if (newSlots[pos].key == EMPTY) { newSlots[pos].key = key; newSlots[pos].value = value; ht->size++; break; } } } } free(oldSlots); return 0; } /* Insert or update key-value pair */ 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 idx = hashIndex(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = (int)((idx + (unsigned int)i) % (unsigned int)ht->capacity); if (ht->slots[pos].key == key) { ht->slots[pos].value = value; /* Update */ 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; /* Table full */ } /* Search for a key; returns 1 if found */ int search(HashTable *ht, int key, int *outValue) { unsigned int idx = hashIndex(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = (int)((idx + (unsigned int)i) % (unsigned int)ht->capacity); if (ht->slots[pos].key == EMPTY) { return 0; /* Not found */ } if (ht->slots[pos].key == key) { *outValue = ht->slots[pos].value; return 1; } /* Continue past DELETED slots */ } return 0; } /* Delete a key; returns 0 on success */ int deleteKey(HashTable *ht, int key) { unsigned int idx = hashIndex(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = (int)((idx + (unsigned int)i) % (unsigned int)ht->capacity); if (ht->slots[pos].key == EMPTY) { return -1; /* Not found */ } if (ht->slots[pos].key == key) { ht->slots[pos].key = DELETED; ht->deletedCount++; ht->size--; return 0; } } return -1; } /* Display the table */ void display(const HashTable *ht) { double lf = (double)ht->size / ht->capacity; printf("Hash Table (size=%d, capacity=%d, deleted=%d, load=%.2f):\n", 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 demoBasicOperations(void) { printf("\n=== Basic Linear Probing Demo ===\n"); HashTable *ht = createHashTable(10); if (ht == NULL) return; int keys[] = {1, 2, 3, 22, 42}; int n = sizeof(keys) / sizeof(keys[0]); for (int i = 0; i < n; i++) { insert(ht, keys[i], keys[i] * 10); } display(ht); int value; printf("\nSearch 3: "); if (search(ht, 3, &value)) printf("%d\n", value); else printf("not found\n"); printf("Search 22: "); if (search(ht, 22, &value)) printf("%d\n", value); else printf("not found\n"); printf("Search 100: "); if (search(ht, 100, &value)) printf("%d\n", value); else printf("not found\n"); printf("\nDeleting 2...\n"); deleteKey(ht, 2); display(ht); printf("\nAfter delete, search 22: "); if (search(ht, 22, &value)) printf("%d (past tombstone)\n", value); else printf("not found\n"); printf("Insert 12 (reuses DELETED slot)...\n"); insert(ht, 12, 120); display(ht); freeHashTable(ht); } static void demoRehashing(void) { printf("\n=== Rehashing Demo ===\n"); HashTable *ht = createHashTable(5); if (ht == NULL) return; for (int i = 0; i < 15; i++) { int key = (i * 7 + 3) % 100; insert(ht, key, key * 10); if (i == 4 || i == 9) { printf("\nAfter %d inserts:\n", i + 1); display(ht); } } printf("\nFinal table:\n"); display(ht); freeHashTable(ht); } /* Read integer safely */ 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("=== Linear Probing Hash Table Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Basic Operations Demo\n"); printf("2. Rehashing Demo\n"); printf("3. Interactive Hash Table\n"); printf("4. 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) { demoBasicOperations(); } else if (choice == 2) { demoRehashing(); } else if (choice == 3) { HashTable *ht = createHashTable(10); 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 == 4) { printf("Exiting.\n"); return EXIT_SUCCESS; } else { printf("Invalid choice.\n"); } } return EXIT_SUCCESS; }

Explanation of the Code

1. Slot — Stores key and value; sentinel keys mark EMPTY and DELETED.
2. HashTable — Contains slots array, capacity, size, and deleted count.
3. hashIndex — Division-method hash with unsigned cast.
4. nextPrime — Finds next prime ≥ n for capacity.
5. createHashTable — Allocates and initializes all slots to EMPTY.
6. insert — Probes linearly; updates existing key, reuses DELETED, or inserts at EMPTY.
7. search — Probes until key found or EMPTY encountered; passes over DELETED.
8. deleteKey — Replaces slot with DELETED tombstone.
9. rehash — Doubles capacity, reinserts live entries.
10. display — Prints each slot’s state.

Expected Output (sample run)

text

=== Basic Linear Probing Demo === Hash Table (size=5, capacity=11, deleted=0, load=0.45): [ 0]: (22 → 220) [ 1]: (1 → 10) [ 2]: (2 → 20) [ 3]: (3 → 30) [ 4]: (42 → 420) [ 5]: EMPTY [ 6]: EMPTY [ 7]: EMPTY [ 8]: EMPTY [ 9]: EMPTY [10]: EMPTY Search 3: 30 Search 22: 220 Search 100: not found Deleting 2... Hash Table (size=4, capacity=11, deleted=1, load=0.36): [ 0]: (22 → 220) [ 1]: (1 → 10) [ 2]: DELETED [ 3]: (3 → 30) [ 4]: (42 → 420) ... After delete, search 22: 220 (past tombstone) Insert 12 (reuses DELETED slot)... Hash Table (size=5, capacity=11, deleted=0, load=0.45): [ 0]: (22 → 220) [ 1]: (1 → 10) [ 2]: (12 → 120) [ 3]: (3 → 30) [ 4]: (42 → 420) ...

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Infinite Probe Loop

If the table is full and no tombstone exists, probing never terminates.

c

for (int i = 0; i < ht->capacity; i++) { ... } /* Bounded loop */

Solution: Always bound the probe loop by capacity.

2. Tombstone Accumulation

Frequent deletes fill the table with tombstones, degrading performance.

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

3. Wrong Load Factor

Using only size / capacity ignores tombstones.

Solution: Use (size + deleted) / capacity for rehash decisions.

4. Search Stops at DELETED

Searches must continue past DELETED slots.

c

if (slots[pos].key == EMPTY) return 0; /* Stop */ if (slots[pos].key == key) return 1; /* Found */ /* else continue past DELETED */

5. Table Size Not Prime

Non-prime sizes cause clustering.

Solution: Use nextPrime.

6. Unbounded Rehashing

Rehashing in a loop can cause infinite recursion.

Solution: Rehash once per insert, not recursively.

7. Deleting from Empty Table

Guard against size == 0 before deleting.

8. Negative Keys

Cast to unsigned int before modulo.

9. Rehashing During Insert

Ensure rehash happens before computing the initial probe index.

10. Memory Considerations

• Table memory: capacity × sizeof(Slot).
• No pointers per entry — memory efficient.
• Rehashing doubles temporary memory.
• Free the slots array on destruction.

---

Summary & Best Practices

Linear Probing is a straightforward Open Addressing strategy with excellent cache locality. Handling tombstones and rehashing correctly is essential for maintaining O(1) average performance.

Key Takeaways

• Probe sequence: (h(k) + i) % m.
• Use tombstones for deletion.
• Bound probe loops by capacity.
• Rehash when (size + deleted) / capacity > 0.7.
• Use prime table sizes.
• Complexity: O(1) average; O(n) worst.

Best Practices

1. Use prime table sizes for better distribution.
2. Bound probe loops by capacity to avoid infinite loops.
3. Track tombstones and rehash when they accumulate.
4. Continue search past DELETED slots.
5. Rehash when load factor exceeds 0.7.
6. Cast keys to unsigned before modulo.
7. Prefer linear probing for cache-friendly workloads.
8. Consider quadratic probing or double hashing for lower clustering.
9. Free the slots array on cleanup.
10. Profile for large datasets to tune thresholds.

By mastering linear probing, you’ll implement efficient in-place hash maps without pointer overhead, ideal for cache-sensitive applications.