Tag double hashing

Open Addressing Collision Handling Technique in Hashing in C: A Comprehensive Tutorial

Open Addressing is a collision handling technique where all elements are stored directly in the hash table itself. When a collision occurs, the algorithm probes for the next available slot in the table. Unlike chaining, no linked lists or extra nodes are used—everything lives in one contiguous array, giving excellent cache performance.

This tutorial provides an in-depth exploration of Open Addressing in C: fundamental concepts, three probing strategies (linear, quadratic, double hashing), full implementations, comparison with chaining, complexity analysis, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is Open Addressing?

Open Addressing (also called closed hashing) stores all elements in the hash table itself. When a collision occurs, we probe for the next slot using a probe sequence.

Key properties:

• Table size m must be ≥ number of keys n.
• No pointers or linked lists—everything in the table.
• Probing finds alternate slots on collision.
• Requires tombstones for deletion.

Why Open Addressing?

• Cache-friendly: Everything stored contiguously.
• Memory efficient: No pointer overhead.
• Simple deletion: With tombstones.
• Good for known workloads: When number of keys is predictable.

Core Operations

Operation	Description
Insert(k)	Probe until an empty slot is found; insert.
Search(k)	Probe until key found or empty slot reached.
Delete(k)	Mark slot as DELETED (tombstone); search continues past it.

Probe Function Types

Probing	Probe Sequence	Clustering
Linear Probing	(h(k) + i) % m	Primary
Quadratic Probing	(h(k) + i²) % m	Secondary
Double Hashing	(h(k) + i × h2(k)) % m	Minimal

Linear Probing

Sequential probing: (h(k) + 1) % m, (h(k) + 2) % m, …

• Best cache performance.
• Suffers from primary clustering: long contiguous runs of occupied slots.

Quadratic Probing

Probes: (h(k) + 1²) % m, (h(k) + 2²) % m, …

• Reduces primary clustering.
• Retains secondary clustering: keys with same initial hash follow identical probes.

Double Hashing

Probes: (h(k) + 1 × h2(k)) % m, (h(k) + 2 × h2(k)) % m, …

• Best distribution — reduces both primary and secondary clustering.
• Poor cache performance — jumps unpredictable.
• Requires a second hash function that never returns 0.

Performance Analysis

For load factor α = n / m (α < 1):

Operation	Expected Time
Search	< 1 / (1 - α)
Insert	< 1 / (1 - α)
Delete	< 1 / (1 - α)

At α = 0.5, expected probes ≈ 2; at α = 0.9, expected probes ≈ 10.

Open Addressing vs. Separate Chaining

Aspect	Open Addressing	Separate Chaining
Table size	Must be ≥ n	Any
Cache	Excellent	Poor
Clustering	Yes	No
Insert	Slight computation	O(1) prepend
Delete	Tombstones needed	Direct removal
Load factor	α < 1	Any
Pointer overhead	None	Per node
Best for	Known workloads	Dynamic workloads

---

Syntax & Core Mechanics

Slot States

c

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

Sentinel keys mark empty and deleted slots.

Basic Structure

c

typedef struct { int *keys; int *values; int capacity; int size; int deletedCount; } HashTable;

Probe Sequences

c

/* Linear Probing */ pos = (base + i) % capacity; /* Quadratic Probing */ pos = (base + i * i) % capacity; /* Double Hashing */ pos = (base + i * h2(key)) % capacity;

Second Hash Function (Double Hashing)

Must never return 0:

c

int h2(int key, int m) { return 1 + (key % (m - 1)); /* Ensures non-zero step */ }

Load Factor Threshold

Keep α < 0.7 for good performance; rehash when exceeded.

c

double lf = (double)(size + deletedCount) / capacity; if (lf > 0.7) rehash();

---

Full Practical Code Example with Explanation

This program demonstrates all three probing strategies with a unified hash table.

c

/** * open_addressing.c * Complete hash table using open addressing. * Supports linear, quadratic, and double hashing. */ #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 typedef enum { PROBE_LINEAR, PROBE_QUADRATIC, PROBE_DOUBLE } ProbeType; typedef struct { int *keys; int *values; int capacity; int size; int deletedCount; ProbeType probe; } HashTable; /* 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; } } /* Primary hash */ static unsigned int h1(int key, int m) { return ((unsigned int)key) % (unsigned int)m; } /* Secondary hash for double hashing (must never be 0) */ static unsigned int h2(int key, int m) { return 1u + ((unsigned int)key % (unsigned int)(m - 1)); } /* Compute probe index for iteration i */ static int probeAt(int base, int i, int key, int m, ProbeType type) { unsigned int idx; switch (type) { case PROBE_LINEAR: idx = ((unsigned int)base + (unsigned int)i) % (unsigned int)m; break; case PROBE_QUADRATIC: idx = ((unsigned int)base + (unsigned int)(i * i)) % (unsigned int)m; break; case PROBE_DOUBLE: idx = ((unsigned int)base + (unsigned int)i * h2(key, m)) % (unsigned int)m; break; default: return -1; } return (int)idx; } HashTable *createHashTable(int initialCapacity, ProbeType probe) { HashTable *ht = malloc(sizeof(HashTable)); if (ht == NULL) return NULL; int capacity = nextPrime(initialCapacity); ht->keys = malloc(capacity * sizeof(int)); ht->values = malloc(capacity * sizeof(int)); if (ht->keys == NULL || ht->values == NULL) { free(ht->keys); free(ht->values); free(ht); return NULL; } for (int i = 0; i < capacity; i++) { ht->keys[i] = EMPTY; ht->values[i] = 0; } ht->capacity = capacity; ht->size = 0; ht->deletedCount = 0; ht->probe = probe; return ht; } void freeHashTable(HashTable *ht) { if (ht == NULL) return; free(ht->keys); free(ht->values); free(ht); } /* Rehash: double capacity and reinsert all live entries */ static int rehash(HashTable *ht) { int oldCap = ht->capacity; int *oldKeys = ht->keys; int *oldValues = ht->values; int newCap = nextPrime(oldCap * 2); int *newKeys = malloc(newCap * sizeof(int)); int *newValues = malloc(newCap * sizeof(int)); if (newKeys == NULL || newValues == NULL) { free(newKeys); free(newValues); return -1; } for (int i = 0; i < newCap; i++) { newKeys[i] = EMPTY; newValues[i] = 0; } ht->keys = newKeys; ht->values = newValues; ht->capacity = newCap; ht->size = 0; ht->deletedCount = 0; for (int i = 0; i < oldCap; i++) { if (oldKeys[i] != EMPTY && oldKeys[i] != DELETED) { int key = oldKeys[i]; int value = oldValues[i]; int base = (int)h1(key, newCap); for (int j = 0; j < newCap; j++) { int pos = probeAt(base, j, key, newCap, ht->probe); if (newKeys[pos] == EMPTY) { newKeys[pos] = key; newValues[pos] = value; ht->size++; break; } } } } free(oldKeys); free(oldValues); return 0; } 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; } int base = (int)h1(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = probeAt(base, i, key, ht->capacity, ht->probe); if (ht->keys[pos] == key) { ht->values[pos] = value; return 0; } if (ht->keys[pos] == EMPTY || ht->keys[pos] == DELETED) { if (ht->keys[pos] == DELETED) ht->deletedCount--; ht->keys[pos] = key; ht->values[pos] = value; ht->size++; return 0; } } return -1; } int search(HashTable *ht, int key, int *outValue) { int base = (int)h1(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = probeAt(base, i, key, ht->capacity, ht->probe); if (ht->keys[pos] == EMPTY) return 0; if (ht->keys[pos] == key) { *outValue = ht->values[pos]; return 1; } } return 0; } int deleteKey(HashTable *ht, int key) { int base = (int)h1(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = probeAt(base, i, key, ht->capacity, ht->probe); if (ht->keys[pos] == EMPTY) return -1; if (ht->keys[pos] == key) { ht->keys[pos] = DELETED; ht->deletedCount++; ht->size--; return 0; } } return -1; } static const char *probeName(ProbeType t) { switch (t) { case PROBE_LINEAR: return "linear"; case PROBE_QUADRATIC: return "quadratic"; case PROBE_DOUBLE: return "double"; } return "unknown"; } 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", probeName(ht->probe), ht->size, ht->capacity, ht->deletedCount, lf); for (int i = 0; i < ht->capacity; i++) { printf(" [%2d]: ", i); if (ht->keys[i] == EMPTY) printf("EMPTY\n"); else if (ht->keys[i] == DELETED) printf("DELETED\n"); else printf("(%d → %d)\n", ht->keys[i], ht->values[i]); } } /* ============ Demos ============ */ static void demoLinear(void) { printf("\n=== Linear Probing ===\n"); HashTable *ht = createHashTable(7, PROBE_LINEAR); if (ht == NULL) return; int keys[] = {50, 70, 76, 85, 93}; for (int i = 0; i < 5; i++) insert(ht, keys[i], keys[i]); display(ht); int v; printf("\nSearch 76: "); if (search(ht, 76, &v)) printf("%d\n", v); else printf("not found\n"); printf("Delete 70...\n"); deleteKey(ht, 70); display(ht); freeHashTable(ht); } static void demoQuadratic(void) { printf("\n=== Quadratic Probing ===\n"); HashTable *ht = createHashTable(7, PROBE_QUADRATIC); if (ht == NULL) return; int keys[] = {22, 30, 50}; for (int i = 0; i < 3; i++) insert(ht, keys[i], keys[i]); display(ht); freeHashTable(ht); } static void demoDouble(void) { printf("\n=== Double Hashing ===\n"); HashTable *ht = createHashTable(7, PROBE_DOUBLE); if (ht == NULL) return; int keys[] = {27, 43, 692, 72}; for (int i = 0; i < 4; i++) insert(ht, keys[i], keys[i]); display(ht); freeHashTable(ht); } static void demoComparison(void) { printf("\n=== Probe Sequence Comparison ===\n"); int keys[] = {50, 70, 76, 85, 93}; HashTable *lin = createHashTable(11, PROBE_LINEAR); HashTable *quad = createHashTable(11, PROBE_QUADRATIC); HashTable *dbl = createHashTable(11, PROBE_DOUBLE); if (!lin || !quad || !dbl) { freeHashTable(lin); freeHashTable(quad); freeHashTable(dbl); return; } for (int i = 0; i < 5; i++) { insert(lin, keys[i], keys[i]); insert(quad, keys[i], keys[i]); insert(dbl, keys[i], keys[i]); } printf("Linear table:\n"); for (int i = 0; i < lin->capacity; i++) printf("%4d ", lin->keys[i]); printf("\n\nQuadratic table:\n"); for (int i = 0; i < quad->capacity; i++) printf("%4d ", quad->keys[i]); printf("\n\nDouble hashing table:\n"); for (int i = 0; i < dbl->capacity; i++) printf("%4d ", dbl->keys[i]); printf("\n"); freeHashTable(lin); freeHashTable(quad); freeHashTable(dbl); } 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("=== Open Addressing Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Linear Probing\n"); printf("2. Quadratic Probing\n"); printf("3. Double Hashing\n"); printf("4. Compare All Three\n"); printf("5. Interactive (Linear Probing)\n"); printf("6. 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) { demoLinear(); } else if (choice == 2) { demoQuadratic(); } else if (choice == 3) { demoDouble(); } else if (choice == 4) { demoComparison(); } else if (choice == 5) { HashTable *ht = createHashTable(11, PROBE_LINEAR); 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 == 6) { printf("Exiting.\n"); return EXIT_SUCCESS; } else { printf("Invalid choice.\n"); } } return EXIT_SUCCESS; }

Explanation of the Code

1. HashTable — Stores keys, values, capacity, size, deleted count, and probe type.
2. h1 — Primary division hash.
3. h2 — Secondary hash for double hashing; returns 1..m-1.
4. probeAt — Computes index for iteration i based on probe type.
5. insert — Probes until key matched or EMPTY/DELETED found.
6. search — Probes until key found or EMPTY encountered.
7. deleteKey — Replaces key with DELETED tombstone.
8. rehash — Grows capacity and reinserts live entries.

Expected Output (sample run)

text

=== Linear Probing === Hash Table (linear, size=5, capacity=7, deleted=0, load=0.71): [ 0]: (70 → 70) [ 1]: (50 → 50) [ 2]: (76 → 76) [ 3]: (85 → 85) [ 4]: (93 → 93) [ 5]: EMPTY [ 6]: EMPTY Search 76: 76 Delete 70... Hash Table (linear, size=4, capacity=7, deleted=1, load=0.57): [ 0]: DELETED [ 1]: (50 → 50) [ 2]: (76 → 76) [ 3]: (85 → 85) [ 4]: (93 → 93) [ 5]: EMPTY [ 6]: EMPTY === Quadratic Probing === Hash Table (quadratic, size=3, capacity=7, deleted=0, load=0.43): [ 0]: EMPTY [ 1]: (22 → 22) [ 2]: (30 → 30) [ 3]: EMPTY [ 4]: EMPTY [ 5]: (50 → 50) [ 6]: EMPTY === Double Hashing === Hash Table (double, size=4, capacity=7, deleted=0, load=0.57): ... === Probe Sequence Comparison === Linear table: 70 50 76 85 93 -1 -1 ... Quadratic table: -1 50 70 93 -1 76 85 ... Double hashing table: ...

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Infinite Probe Loop

Unbounded probing can loop forever if no empty slot exists.

Solution: Bound loop by capacity.

2. Quadratic Probing Not Visiting All Slots

Standard quadratic probing may miss slots if m is not prime and load is high.

Solution: Use prime table sizes; or use the modified formula from the previous tutorial.

3. Double Hashing with h2(k) = 0

If h2(k) returns 0, probing stalls.

Solution: Ensure h2(k) ∈ [1, m-1].

4. Forgetting Tombstones

Deleting by clearing breaks probe chains.

Solution: Use DELETED marker.

5. Load Factor Reaching 1

Table becomes full; insert fails.

Solution: Rehash when α > 0.7.

6. Primary Clustering (Linear)

Runs of occupied slots slow lookups.

Solution: Use quadratic or double hashing.

7. Secondary Clustering (Quadratic)

Keys with same initial hash follow identical probes.

Solution: Use double hashing.

8. Rehash Double-Counting

Not updating size and deletedCount correctly during rehash.

Solution: Reset counters at rehash start, then count entries as they are reinserted.

9. Negative Keys

key % m for negative keys yields negative indices.

Solution: Cast to unsigned int.

10. Memory Considerations

• Keys + values arrays: capacity × (sizeof(int) × 2).
• No pointers per entry — memory efficient.
• Rehash doubles memory temporarily.
• Free all arrays on cleanup.

---

Summary & Best Practices

Open Addressing is a memory-efficient, cache-friendly collision resolution strategy. Choosing the right probe sequence (linear, quadratic, double hashing) determines performance and clustering behavior.

Key Takeaways

• All entries stored in the table itself.
• Three probe strategies: linear, quadratic, double.
• Linear: best cache, primary clustering.
• Quadratic: middle ground, secondary clustering.
• Double: best distribution, poor cache.
• Deletion uses tombstones.
• Load factor α = n/m; keep below 0.7.
• Expected operations: O(1 / (1 - α)).

Best Practices

1. Use prime table sizes for better distribution.
2. Keep α ≤ 0.7; rehash proactively.
3. Use tombstones for deletion.
4. Bound probe loops by capacity.
5. Choose double hashing for minimal clustering.
6. Choose linear probing for cache-sensitive workloads.
7. Ensure h2(k) is never 0 in double hashing.
8. Track deletedCount to trigger rehash.
9. Cast keys to unsigned before modulo.
10. Profile with real workloads to pick the best strategy.

By mastering open addressing, you’ll implement memory-efficient, high-performance hash tables suitable for embedded systems, real-time applications, and cache-sensitive workloads.