CoreTechED

Loading

Tag rehashing

Learn separate chaining in C hashing: linked list buckets, insert/search/delete, rehashing, performance analysis, and implementation.
C Programming

Separate Chaining in Hashing in C: Complete Guide

Separate Chaining Collision Handling Technique in Hashing in C: A Comprehensive Tutorial

Separate Chaining is one of the most popular and commonly used techniques to handle collisions in hashing. Instead of probing for an alternative slot, each bucket holds a chain (typically a linked list) of all entries that hash to the same index. This makes chaining simple, robust, and capable of handling arbitrarily high load factors.

This tutorial provides an in-depth exploration of Separate Chaining in C: fundamental concepts, data structures for chains, implementation, performance analysis, advantages and disadvantages, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is Separate Chaining?

Separate Chaining resolves collisions by maintaining a chain at each slot of the hash table. When multiple keys hash to the same index, they are stored in the same chain (a linked list, dynamic array, or balanced BST).

Hash function example: h(k) = k % 5

Keys [12, 22, 15, 25]:

text

12 % 5 = 2 22 % 5 = 2 (collision with 12 → add to chain) 15 % 5 = 0 25 % 5 = 0 (collision with 15 → add to chain)

Resulting table:

text

[0]: 15 → 25 [1]: (empty) [2]: 12 → 22 [3]: (empty) [4]: (empty)

Why Separate Chaining?

  • Simple to implement: Just linked lists in buckets.
  • Never fills up: Chains grow as needed.
  • Robust to bad hash functions: Even poor distribution degrades gracefully.
  • Handles dynamic workloads: Ideal when the number of keys is unknown.
  • Easy deletion: No tombstones needed.

Two Main Collision Handling Methods

MethodDescription
Separate ChainingEach slot holds a chain of entries
Open AddressingAll entries stored in the table itself with probing

Performance Analysis

Under simple uniform hashing:

MetricFormula
Table slotsm
Number of keysn
Load factorα = n / m
Expected search timeO(1 + α)
Expected delete timeO(1 + α)
Insert timeO(1)

If α = O(1), all operations are O(1) average.

Syntax & Core Mechanics

Data Structures for Chains

StructureSearchDeleteInsertCache
Linked ListO(len)O(len)O(1)Poor
Dynamic ArrayO(len)O(len)O(1)*Good
Self-Balancing BSTO(log len)O(log len)O(log len)Poor

*Amortized; resizing may be O(len).

Java 8+ uses a Red-Black Tree for chains longer than 8 entries to bound worst-case lookup time.

Linked List Node

c

typedef struct Entry { int key; int value; struct Entry *next; } Entry;

Hash Table Structure

c

typedef struct { Entry **buckets; int bucketCount; int size; } HashTable;

Hash Function (Division Method)

c

static unsigned int hashIndex(int key, int bucketCount) { return ((unsigned int)key) % (unsigned int)bucketCount; }

Insertion Algorithm

  1. Compute idx = hash(key).
  2. Traverse bucket; if key found, update value.
  3. Otherwise, prepend new node to bucket.

Search Algorithm

  1. Compute idx = hash(key).
  2. Traverse bucket list; return value if found.
  3. Return “not found” if chain exhausted.

Deletion Algorithm

  1. Compute idx = hash(key).
  2. Traverse bucket list tracking the previous node.
  3. Unlink the matching node; free it.

Full Practical Code Example with Explanation

This program implements a complete hash map using separate chaining with linked lists, supporting insert, search, delete, display, and rehashing.

c

/** * separate_chaining.c * Complete hash table using separate chaining. * Supports insert, search, delete, display, and rehashing. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #define MAX_LINE_LEN 100 #define DEFAULT_BUCKETS 7 #define REHASH_THRESHOLD 1.0 /* Node in a chain */ typedef struct Entry { int key; int value; struct Entry *next; } Entry; /* Hash table with separate chaining */ typedef struct { Entry **buckets; int bucketCount; int size; int useRehashing; } HashTable; /* Division-method hash with unsigned cast */ static unsigned int hashIndex(int key, int bucketCount) { return ((unsigned int)key) % (unsigned int)bucketCount; } /* Find the 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; } } /* Create a hash table */ HashTable *createHashTable(int bucketCount, int useRehashing) { HashTable *ht = malloc(sizeof(HashTable)); if (ht == NULL) return NULL; ht->buckets = calloc(bucketCount, sizeof(Entry *)); if (ht->buckets == NULL) { free(ht); return NULL; } ht->bucketCount = bucketCount; ht->size = 0; ht->useRehashing = useRehashing; return ht; } /* Free all entries and the table */ void freeHashTable(HashTable *ht) { if (ht == NULL) return; for (int i = 0; i < ht->bucketCount; i++) { Entry *cur = ht->buckets[i]; while (cur != NULL) { Entry *next = cur->next; free(cur); cur = next; } } free(ht->buckets); free(ht); } /* Rehash: grow bucket count and reinsert all entries */ static int rehash(HashTable *ht) { int newBucketCount = nextPrime(ht->bucketCount * 2); Entry **newBuckets = calloc(newBucketCount, sizeof(Entry *)); if (newBuckets == NULL) return -1; for (int i = 0; i < ht->bucketCount; i++) { Entry *cur = ht->buckets[i]; while (cur != NULL) { Entry *next = cur->next; unsigned int idx = hashIndex(cur->key, newBucketCount); cur->next = newBuckets[idx]; newBuckets[idx] = cur; cur = next; } } free(ht->buckets); ht->buckets = newBuckets; ht->bucketCount = newBucketCount; return 0; } /* Insert or update a key-value pair */ int insert(HashTable *ht, int key, int value) { if (ht->useRehashing) { double lf = (double)(ht->size + 1) / ht->bucketCount; if (lf > REHASH_THRESHOLD) { if (rehash(ht) != 0) return -1; } } unsigned int idx = hashIndex(key, ht->bucketCount); /* Update if key exists */ Entry *cur = ht->buckets[idx]; while (cur != NULL) { if (cur->key == key) { cur->value = value; return 0; } cur = cur->next; } /* Prepend new entry */ Entry *newEntry = malloc(sizeof(Entry)); if (newEntry == NULL) return -1; newEntry->key = key; newEntry->value = value; newEntry->next = ht->buckets[idx]; ht->buckets[idx] = newEntry; ht->size++; return 0; } /* Search for a key; returns 1 if found */ int search(const HashTable *ht, int key, int *outValue) { unsigned int idx = hashIndex(key, ht->bucketCount); Entry *cur = ht->buckets[idx]; while (cur != NULL) { if (cur->key == key) { *outValue = cur->value; return 1; } cur = cur->next; } return 0; } /* Delete a key */ int deleteKey(HashTable *ht, int key) { unsigned int idx = hashIndex(key, ht->bucketCount); Entry *cur = ht->buckets[idx]; Entry *prev = NULL; while (cur != NULL) { if (cur->key == key) { if (prev == NULL) ht->buckets[idx] = cur->next; else prev->next = cur->next; free(cur); ht->size--; return 0; } prev = cur; cur = cur->next; } return -1; } /* Return chain length at a given bucket */ int chainLength(const HashTable *ht, int idx) { int count = 0; Entry *cur = ht->buckets[idx]; while (cur) { count++; cur = cur->next; } return count; } /* Find maximum chain length (worst-case lookup) */ int maxChainLength(const HashTable *ht) { int max = 0; for (int i = 0; i < ht->bucketCount; i++) { int len = chainLength(ht, i); if (len > max) max = len; } return max; } /* Display the table */ void display(const HashTable *ht) { double lf = (double)ht->size / ht->bucketCount; printf("Hash Table (size=%d, buckets=%d, load=%.2f, maxChain=%d):\n", ht->size, ht->bucketCount, lf, maxChainLength(ht)); for (int i = 0; i < ht->bucketCount; i++) { printf(" [%2d]:", i); Entry *cur = ht->buckets[i]; while (cur != NULL) { printf(" (%d→%d)", cur->key, cur->value); cur = cur->next; } printf("\n"); } } /* ============ Demos ============ */ static void demoBasicChaining(void) { printf("\n=== Basic Separate Chaining ===\n"); HashTable *ht = createHashTable(5, 0); if (ht == NULL) return; int keys[] = {12, 22, 15, 25, 5, 17}; int n = sizeof(keys) / sizeof(keys[0]); for (int i = 0; i < n; i++) { insert(ht, keys[i], keys[i] * 10); } display(ht); int v; printf("\nSearch 22: "); if (search(ht, 22, &v)) printf("%d\n", v); else printf("not found\n"); printf("Search 100: "); if (search(ht, 100, &v)) printf("%d\n", v); else printf("not found\n"); printf("\nDelete 15...\n"); deleteKey(ht, 15); display(ht); freeHashTable(ht); } static void demoRehashing(void) { printf("\n=== Chaining with Rehashing ===\n"); HashTable *ht = createHashTable(5, 1); if (ht == NULL) return; for (int i = 0; i < 20; i++) { int key = (i * 13 + 7) % 100; insert(ht, key, key * 10); if (i == 4 || i == 9 || i == 19) { printf("\nAfter %d inserts:\n", i + 1); 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("=== Separate Chaining Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Basic Chaining Demo\n"); printf("2. Chaining with 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) { demoBasicChaining(); } else if (choice == 2) { demoRehashing(); } else if (choice == 3) { HashTable *ht = createHashTable(DEFAULT_BUCKETS, 1); 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. Entry — Node in a chain storing key, value, next.
  2. HashTable — Bucket array, bucket count, size, rehashing flag.
  3. hashIndex — Division-method hash with unsigned cast.
  4. nextPrime — Chooses prime bucket sizes.
  5. createHashTable — Allocates bucket array.
  6. insert — Prepends new node; updates existing key; optionally rehashes.
  7. search — Traverses chain linearly.
  8. deleteKey — Unlinks and frees matching node.
  9. rehash — Doubles bucket count and reinserts all entries.
  10. chainLength, maxChainLength — Helpers for diagnostics.

Expected Output (sample run)

text

=== Basic Separate Chaining === Hash Table (size=6, buckets=5, load=1.20, maxChain=3): [ 0]: (25→250) (15→150) [ 1]: (17→170) [ 2]: (22→220) (12→120) [ 3]: [ 4]: (5→50) Search 22: 220 Search 100: not found Delete 15... Hash Table (size=5, buckets=5, load=1.00, maxChain=2): [ 0]: (25→250) [ 1]: (17→170) [ 2]: (22→220) (12→120) [ 3]: [ 4]: (5→50)

Common Pitfalls, Edge Cases & Memory Considerations

1. Forgetting to Free Nodes

Each malloc must be paired with free.

c

free(cur); /* Required for every node */

2. Not Updating Duplicate Keys

Insert should update existing key, not append duplicates.

3. Integer Overflow in Hash

key * multiplier can overflow.

Solution: Cast to unsigned int before modulo.

4. Poor Cache Performance

Linked lists scatter memory.

Solution: Use dynamic arrays for chains (cache-friendly) or Red-Black Trees for large chains.

5. Long Chains

Worst-case search becomes O(n).

Solution: Rehash when load factor is high; consider RB-trees for large chains.

6. Empty Buckets Wasting Memory

Bucket array itself wastes space.

Solution: Size buckets based on expected n and target load factor.

7. Unbounded Growth

No rehashing means chains grow arbitrarily.

Solution: Use useRehashing = 1 and rehash when α > 1.

8. Unsigned vs. Signed Keys

Negative keys need careful handling.

Solution: Cast keys to unsigned int.

9. Thread Safety

Concurrent access to chains corrupts data.

Solution: Use locks per bucket or a global mutex for multi-threaded use.

10. Memory Considerations

  • Bucket array: bucketCount × sizeof(Entry *).
  • Each entry: sizeof(Entry) + malloc overhead.
  • Chains use more memory than open addressing.
  • Free all entries and the bucket array on destruction.

Summary & Best Practices

Separate Chaining is a robust, easy-to-implement collision resolution strategy with excellent behavior for dynamic workloads. It trades memory and cache efficiency for simplicity and worst-case robustness.

Key Takeaways

  • Each bucket holds a chain of entries.
  • Insert at head: O(1).
  • Search/delete: O(1 + α) average.
  • Linked lists: O(1) insert, poor cache.
  • Dynamic arrays: cache-friendly.
  • RB-trees (Java 8+): O(log len) worst-case.
  • Never fills up; robust to load factors.

Best Practices

  1. Use prime bucket sizes.
  2. Prepend for O(1) insert.
  3. Update existing keys rather than duplicating.
  4. Rehash when load factor > 1.
  5. Free every entry and the bucket array.
  6. Cast keys to unsigned int.
  7. Consider dynamic arrays for cache efficiency.
  8. Consider RB-trees for long chains (Java-style).
  9. Use djb2 or similar good hash functions.
  10. Profile for large datasets.

By mastering separate chaining, you’ll implement hash tables that are simple, scalable, and robust to collision-heavy workloads.

Teacher pointing to whiteboard chart about linear probing in hash tables in a classroom
C Programming

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

ConceptDescription
Open AddressingAll keys stored in the table itself
ProbeSequence of slots examined on collision
Load Factor (α)n / m (entries / table size)
TombstoneMarker for deleted slot
ClusteringAdjacent occupied slots form a cluster
RehashingResizing 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

OperationBestAverageWorst
InsertO(1)O(1)O(n)
SearchO(1)O(1)O(n)
DeleteO(1)O(1)O(n)

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

Linear Probing vs Chaining

AspectLinear ProbingChaining
MemoryNo pointers; table-onlyExtra pointer per entry
CacheExcellent localityPoor for long chains
Load factorMust stay < 1Can exceed 1
DeletionRequires tombstonesDirect node removal
ClusteringPrimary clusteringNone
PerformanceDegrades fast near α = 1Degrades 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.

Learn hashing with chaining in C: simple chaining, chaining with rehashing, load factor, complexity analysis, and complete implementation.
C Programming

Hashing with Chaining in C: Complete Guide

Hashing with Chaining Implementation in C: A Comprehensive Tutorial

Hashing with chaining is a collision resolution technique where each bucket in the hash table points to a linked list of records that hash to the same index. This approach elegantly handles collisions, supports efficient insert/delete, and forms the foundation of many hash map implementations in real-world systems.

This tutorial provides an in-depth exploration of hashing with chaining in C: fundamental concepts, simple chaining, chaining with rehashing, complexity analysis, practical implementation, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is Hashing with Chaining?

Chaining resolves collisions by allowing multiple entries to coexist at the same hash index. Each bucket is a linked list; when a collision occurs, the new entry is appended (or prepended) to the bucket’s list.

Key idea: Each cell of the hash table points to a linked list of records with the same hash value.

Why Chaining?

  • Simple to implement: Uses linked lists as buckets.
  • Handles high load factors: Performance degrades gracefully.
  • Easy deletion: No tombstones needed (unlike open addressing).
  • No clustering: Unlike linear probing, no primary/secondary clustering.
  • Dynamic growth: Buckets can grow arbitrarily.

Hash Function

For integer keys:

text

hashIndex = key % numberOfBuckets

Example: buckets = 7, keys = [15, 11, 27, 8]:

KeyIndex
151
114
276
81 (collision with 15)

Load Factor

text

α = n / m
  • n = total elements
  • m = number of buckets

Guidelines:

  • Simple chaining: α can be > 1; typically keep α < 1 for good performance.
  • Chaining with rehashing: rehash when α > 0.5.

Complexity Analysis

OperationTime Complexity
SearchO(1 + α)
InsertO(1 + α)
DeleteO(1 + α)

Where α = n / m (load factor). Under uniform distribution, expected chain length is O(α).

Two Variants

VariantDescription
Simple ChainingFixed number of buckets; no resizing
Chaining with RehashingDoubles bucket count when load factor exceeds threshold

Syntax & Core Mechanics

Basic Chaining Structure

c

typedef struct Entry { int key; int value; struct Entry *next; } Entry; typedef struct { Entry **buckets; int bucketCount; int size; } HashTable;

Hash Function

c

static unsigned int hashIndex(int key, int bucketCount) { return ((unsigned int)key) % (unsigned int)bucketCount; }

Insert Operation

  1. Compute index = hashIndex(key).
  2. Traverse bucket list; if key exists, update value.
  3. Otherwise, prepend new node to bucket.

Delete Operation

  1. Compute index = hashIndex(key).
  2. Traverse bucket; find node with matching key.
  3. Unlink node; free memory.

Search Operation

  1. Compute index = hashIndex(key).
  2. Traverse bucket; return value if found.

Rehashing Operation

When loadFactor > threshold:

  1. Double bucket count (or choose next prime).
  2. Create new bucket array.
  3. Reinsert all entries using the new hash function.
  4. Free old bucket array.

Full Practical Code Example with Explanation

This program demonstrates both simple chaining and chaining with rehashing in a unified, complete implementation.

c

/** * hashing_chaining.c * Demonstrates hashing with chaining: simple and with rehashing. * Supports insert, search, delete, display, and dynamic resizing. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #define MAX_LINE_LEN 100 #define DEFAULT_BUCKETS 7 #define REHASH_THRESHOLD 0.75 /* Entry in a bucket's linked list */ typedef struct Entry { int key; int value; struct Entry *next; } Entry; /* Hash table with chaining */ typedef struct { Entry **buckets; int bucketCount; int size; int useRehashing; } HashTable; /* Hash function: division method */ static unsigned int hashIndex(int key, int bucketCount) { return ((unsigned int)key) % (unsigned int)bucketCount; } /* Find the 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; } } /* Create a hash table */ HashTable *createHashTable(int bucketCount, int useRehashing) { HashTable *ht = malloc(sizeof(HashTable)); if (ht == NULL) return NULL; ht->buckets = calloc(bucketCount, sizeof(Entry *)); if (ht->buckets == NULL) { free(ht); return NULL; } ht->bucketCount = bucketCount; ht->size = 0; ht->useRehashing = useRehashing; return ht; } /* Free all entries and the table */ void freeHashTable(HashTable *ht) { if (ht == NULL) return; for (int i = 0; i < ht->bucketCount; i++) { Entry *cur = ht->buckets[i]; while (cur != NULL) { Entry *next = cur->next; free(cur); cur = next; } } free(ht->buckets); free(ht); } /* Rehash: grow buckets and reinsert all entries */ static int rehash(HashTable *ht) { int newBucketCount = nextPrime(ht->bucketCount * 2); Entry **newBuckets = calloc(newBucketCount, sizeof(Entry *)); if (newBuckets == NULL) return -1; /* Reinsert all entries */ for (int i = 0; i < ht->bucketCount; i++) { Entry *cur = ht->buckets[i]; while (cur != NULL) { Entry *next = cur->next; unsigned int idx = hashIndex(cur->key, newBucketCount); cur->next = newBuckets[idx]; newBuckets[idx] = cur; cur = next; } } free(ht->buckets); ht->buckets = newBuckets; ht->bucketCount = newBucketCount; return 0; } /* Insert or update a key-value pair */ int insert(HashTable *ht, int key, int value) { if (ht->useRehashing) { double lf = (double)(ht->size + 1) / ht->bucketCount; if (lf > REHASH_THRESHOLD) { if (rehash(ht) != 0) return -1; } } unsigned int idx = hashIndex(key, ht->bucketCount); Entry *cur = ht->buckets[idx]; while (cur != NULL) { if (cur->key == key) { cur->value = value; /* Update */ return 0; } cur = cur->next; } Entry *newEntry = malloc(sizeof(Entry)); if (newEntry == NULL) return -1; newEntry->key = key; newEntry->value = value; newEntry->next = ht->buckets[idx]; ht->buckets[idx] = newEntry; ht->size++; return 0; } /* Search for a key; returns 1 and sets *outValue if found */ int search(const HashTable *ht, int key, int *outValue) { unsigned int idx = hashIndex(key, ht->bucketCount); Entry *cur = ht->buckets[idx]; while (cur != NULL) { if (cur->key == key) { *outValue = cur->value; return 1; } cur = cur->next; } return 0; } /* Delete a key; returns 0 on success, -1 if not found */ int deleteKey(HashTable *ht, int key) { unsigned int idx = hashIndex(key, ht->bucketCount); Entry *cur = ht->buckets[idx]; Entry *prev = NULL; while (cur != NULL) { if (cur->key == key) { if (prev == NULL) ht->buckets[idx] = cur->next; else prev->next = cur->next; free(cur); ht->size--; return 0; } prev = cur; cur = cur->next; } return -1; } /* Display the table */ void display(const HashTable *ht) { double lf = (ht->bucketCount > 0) ? (double)ht->size / ht->bucketCount : 0.0; printf("Hash Table (size=%d, buckets=%d, load=%.2f):\n", ht->size, ht->bucketCount, lf); for (int i = 0; i < ht->bucketCount; i++) { printf(" [%d]:", i); Entry *cur = ht->buckets[i]; while (cur != NULL) { printf(" (%d→%d)", cur->key, cur->value); cur = cur->next; } printf("\n"); } } /* Demo: simple chaining */ static void demoSimpleChaining(void) { printf("\n=== Simple Chaining ===\n"); HashTable *ht = createHashTable(7, 0); if (ht == NULL) return; int keys[] = {15, 11, 27, 8, 12, 22, 29, 33}; 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 27: "); if (search(ht, 27, &value)) printf("found → %d\n", value); else printf("not found\n"); printf("Search 100: "); if (search(ht, 100, &value)) printf("found → %d\n", value); else printf("not found\n"); printf("\nDelete 11...\n"); deleteKey(ht, 11); display(ht); freeHashTable(ht); } /* Demo: chaining with rehashing */ static void demoRehashing(void) { printf("\n=== Chaining with Rehashing ===\n"); HashTable *ht = createHashTable(5, 1); if (ht == NULL) return; int keys[] = {15, 11, 27, 8, 12, 22, 29, 33, 42, 55, 61, 70}; int n = sizeof(keys) / sizeof(keys[0]); for (int i = 0; i < n; i++) { printf("Inserting %d (buckets=%d, size=%d)...\n", keys[i], ht->bucketCount, ht->size); insert(ht, keys[i], keys[i] * 10); } printf("\nFinal table:\n"); display(ht); freeHashTable(ht); } /* Read an 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("=== Hashing with Chaining Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Simple Chaining Demo\n"); printf("2. Chaining with Rehashing Demo\n"); printf("3. Interactive Chaining 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) { demoSimpleChaining(); } else if (choice == 2) { demoRehashing(); } else if (choice == 3) { HashTable *ht = createHashTable(DEFAULT_BUCKETS, 1); if (ht == NULL) continue; int opt; while (1) { printf("\n--- Chaining 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. Entry — A node in a bucket’s linked list storing key, value, and next pointer.
  2. HashTable — Contains buckets array, bucket count, size, and a rehashing flag.
  3. hashIndex — Division-method hash with unsigned cast for negatives.
  4. nextPrime — Finds the next prime ≥ n for bucket sizing.
  5. createHashTable — Allocates bucket array; supports optional rehashing.
  6. insert — Updates existing key or prepends new entry; triggers rehash if needed.
  7. search — Traverses the bucket to find the key.
  8. deleteKey — Unlinks and frees the entry.
  9. rehash — Doubles bucket count, reinserts all entries.
  10. display — Prints each bucket’s chain and current load factor.

Expected Output (sample run)

text

=== Simple Chaining === Hash Table (size=8, buckets=7, load=1.14): [0]: (22→220) (29→290) [1]: (15→150) (8→80) (33→330) [2]: [3]: [4]: (11→110) [5]: (12→120) [6]: (27→270) Search 27: found → 270 Search 100: not found Delete 11... Hash Table (size=7, buckets=7, load=1.00): [0]: (22→220) (29→290) [1]: (15→150) (8→80) (33→330) [2]: [3]: [4]: [5]: (12→120) [6]: (27→270) === Chaining with Rehashing === Inserting 15 (buckets=5, size=0)... Inserting 11 (buckets=5, size=1)... Inserting 27 (buckets=5, size=2)... Inserting 8 (buckets=5, size=3)... Inserting 12 (buckets=5, size=4)... Inserting 22 (buckets=11, size=5)... Inserting 29 (buckets=11, size=6)... Inserting 33 (buckets=11, size=7)... ... Final table: Hash Table (size=12, buckets=23, load=0.52): ...

Common Pitfalls, Edge Cases & Memory Considerations

1. Forgetting to Free Entries

Each malloc for an Entry requires a corresponding free.

c

free(cur); /* Required for every node */

2. Integer Overflow in Hash

key * multiplier can overflow.

c

return ((unsigned int)key) % bucketCount; /* Safe cast */

3. Negative Keys

key % m for negative keys yields negative results.

Solution: Cast to unsigned int first.

4. Rehashing Infinite Loop

If load factor remains > threshold after rehash, rehash repeatedly.

c

if (lf > REHASH_THRESHOLD) { rehash(ht); } /* Only once per insert */

5. Deleting from Middle of Bucket

Must correctly update the previous node’s next pointer.

c

if (prev == NULL) buckets[idx] = cur->next; else prev->next = cur->next;

6. Table Size Not Prime

Non-prime sizes create clustering.

Solution: Use nextPrime to choose prime sizes.

7. Duplicate Keys

Insert should update existing key, not add duplicate.

8. Empty Table Display

Ensure display handles empty buckets gracefully.

9. Rehashing Correctness

Rehash must preserve all entries and use new bucket count.

10. Memory Considerations

  • Each entry: sizeof(Entry) + list overhead.
  • Bucket array: bucketCount × sizeof(Entry *).
  • Load factor controls chain length.
  • Use prime table sizes for best distribution.

Summary & Best Practices

Hashing with chaining is a robust collision resolution strategy that scales gracefully with load. Its simplicity and dynamic behavior make it a popular choice for real-world hash maps.

Key Takeaways

  • Chaining resolves collisions via linked lists in buckets.
  • Hash function: key % bucketCount (with unsigned cast).
  • Complexity: O(1 + α) for search/insert/delete.
  • Rehashing maintains good performance as the table grows.
  • Prime bucket sizes improve distribution.
  • Free all entries to avoid memory leaks.

Best Practices

  1. Use prime bucket sizes for better distribution.
  2. Cast keys to unsigned before modulo.
  3. Rehash when load factor > 0.5–0.75.
  4. Prepend new entries to bucket lists for O(1) insert.
  5. Update existing keys rather than adding duplicates.
  6. Free every entry and bucket array on cleanup.
  7. Check malloc/calloc return values.
  8. Test with collisions to verify correctness.
  9. Choose good hash functions (djb2 for strings).
  10. Profile for large datasets.

By mastering hashing with chaining, you’ll implement efficient, scalable hash maps that form the backbone of dictionaries, caches, and symbol tables.

Learn hashing in C: hash functions, hash tables, collisions, chaining, open addressing, load factor, and rehashing. Master O(1) average operations.
C Programming

Introduction to Hashing in C: Complete Guide

Introduction to Hashing in C: A Comprehensive Tutorial

Hashing refers to the process of generating a small-sized output (that can be used as an index in a table) from an input of typically large and variable size. Hashing uses mathematical formulas known as hash functions to perform this transformation. This technique determines an index or location for the storage of an item in a data structure called a hash table.

This tutorial provides an in-depth introduction to hashing in C: fundamental concepts, components, hash functions, collision handling, practical implementation, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is Hashing?

Hashing is a technique for storing and retrieving data in O(1) average time. A hash function maps a key (string, integer, etc.) to an index in a hash table, where the corresponding value is stored.

Simple example: For strings {"ab", "cd", "efg"} with a=1, b=2, ..., z=26:

text

"ab" → 1 + 2 = 3 "cd" → 3 + 4 = 7 "efg" → 5 + 6 + 7 = 18

Using table size 7 and hash = sum(key) % 7:

text

"ab" → 3 % 7 = 3 "cd" → 7 % 7 = 0 "efg" → 18 % 7 = 4

Why Hashing Matters

  • O(1) average insert, search, delete — faster than arrays, linked lists, and BSTs.
  • Foundation for dictionaries and sets.
  • Real-world applications: Database indexing, cryptography, caches, symbol tables.
  • Wide language support: HashSet/HashMap in Java, set/dict in Python, unordered_set/unordered_map in C++.

Hash Set vs Hash Map

TypeDescriptionExample
Hash SetCollection of unique keysunordered_set (C++), HashSet (Java)
Hash MapKey-value pairs with unique keysunordered_map (C++), HashMap (Java), dict (Python)

When NOT to Use Hashing

ScenarioBetter Choice
Need sorted data with search/insert/deleteSelf-balancing BST
Prefix search on string keysTrie
Need floor/ceiling operationsSelf-balancing BST
Range queriesSorted array / segment tree

Components of Hashing

ComponentDescription
KeyThe input (string, integer, etc.)
Hash FunctionMaps key → index in [0, tableSize - 1]
Hash TableArray storing values at hash indices

Key Hashing Concepts

ConceptDescription
Hash FunctionMathematical formula mapping key to index
CollisionTwo keys map to the same index
Collision ResolutionChaining, open addressing, etc.
Load Factor (α)n / m (entries / table size)
RehashingResizing table when load factor is high

Complexity Comparison

Data StructureSearchInsertDelete
Array (unsorted)O(n)O(1)O(n)
Linked ListO(n)O(1)O(n)
Balanced BSTO(log n)O(log n)O(log n)
Hash TableO(1) avgO(1) avgO(1) avg

Syntax & Core Mechanics

Basic Hash Function

c

#include <stdio.h> /* Division-method hash: key mod table size */ unsigned int hash(int key, int tableSize) { return ((unsigned int)key) % tableSize; } int main(void) { int keys[] = {15, 11, 27, 8, 12}; int tableSize = 7; printf("Key → Hash Index (table size = %d)\n", tableSize); for (int i = 0; i < 5; i++) { printf(" %d → %u\n", keys[i], hash(keys[i], tableSize)); } return 0; }

Expected output:

text

Key → Hash Index (table size = 7) 15 → 1 11 → 4 27 → 6 8 → 1 12 → 5

Observation: Keys 15 and 8 collide at index 1. We need collision resolution.

String Hash Function (djb2)

A classic, well-distributed hash for strings.

c

#include <stdio.h> unsigned int stringHash(const char *str, int tableSize) { unsigned int hash = 5381; int c; while ((c = *str++) != '\0') { hash = ((hash << 5) + hash) + (unsigned int)c; /* hash * 33 + c */ } return hash % tableSize; } int main(void) { const char *keys[] = {"ab", "cd", "efg", "hello", "world"}; int tableSize = 7; printf("String → Hash Index (table size = %d)\n", tableSize); for (int i = 0; i < 5; i++) { printf(" \"%s\" → %u\n", keys[i], stringHash(keys[i], tableSize)); } return 0; }

Expected output (typical):

text

String → Hash Index (table size = 7) "ab" → 5 "cd" → 6 "efg" → 3 "hello" → 4 "world" → 1

Collision Handling Strategies

StrategyDescription
Separate ChainingEach bucket holds a linked list of entries
Linear ProbingOn collision, try (h(k) + i) % m for i = 1, 2, ...
Quadratic ProbingTry (h(k) + i²) % m
Double HashingUse second hash h2(k) as step size

Load Factor

text

α = n / m
  • n = number of stored entries
  • m = table size

Guidelines:

  • Chaining: α can be > 1, but keep around 0.75 for performance.
  • Open addressing: keep α < 0.75.

Rehashing

When load factor exceeds threshold, create a larger table (typically 2× size, prime) and reinsert all entries.

c

void rehash(HashTable *ht) { int newSize = nextPrime(ht->size * 2); /* Create new table, reinsert all entries, free old */ }

Full Practical Code Example with Explanation

This program demonstrates a complete hash map with chaining, including insert, search, delete, display, and dynamic resizing.

c

/** * hash_map_demo.c * Complete hash map implementation using separate chaining. * Includes insert, search, delete, display, and rehashing. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #define INITIAL_CAPACITY 7 #define MAX_LINE_LEN 100 #define MAX_KEY_LEN 64 /* Node in a bucket's linked list */ typedef struct Entry { char key[MAX_KEY_LEN]; int value; struct Entry *next; } Entry; /* Hash table */ typedef struct { Entry **buckets; int capacity; int size; double loadFactorThreshold; } HashMap; /* djb2 string hash */ static unsigned int hashString(const char *str, int capacity) { unsigned int hash = 5381; int c; while ((c = *str++) != '\0') { hash = ((hash << 5) + hash) + (unsigned int)c; } return hash % (unsigned int)capacity; } HashMap *createMap(int capacity) { HashMap *map = malloc(sizeof(HashMap)); if (map == NULL) return NULL; map->buckets = calloc(capacity, sizeof(Entry *)); if (map->buckets == NULL) { free(map); return NULL; } map->capacity = capacity; map->size = 0; map->loadFactorThreshold = 0.75; return map; } void freeMap(HashMap *map) { if (map == NULL) return; for (int i = 0; i < map->capacity; i++) { Entry *cur = map->buckets[i]; while (cur != NULL) { Entry *next = cur->next; free(cur); cur = next; } } free(map->buckets); free(map); } int insert(HashMap *map, const char *key, int value) { unsigned int idx = hashString(key, map->capacity); Entry *cur = map->buckets[idx]; while (cur != NULL) { if (strcmp(cur->key, key) == 0) { cur->value = value; /* Update */ return 0; } cur = cur->next; } Entry *newEntry = malloc(sizeof(Entry)); if (newEntry == NULL) return -1; strncpy(newEntry->key, key, MAX_KEY_LEN - 1); newEntry->key[MAX_KEY_LEN - 1] = '\0'; newEntry->value = value; newEntry->next = map->buckets[idx]; map->buckets[idx] = newEntry; map->size++; return 0; } int search(const HashMap *map, const char *key, int *outValue) { unsigned int idx = hashString(key, map->capacity); Entry *cur = map->buckets[idx]; while (cur != NULL) { if (strcmp(cur->key, key) == 0) { *outValue = cur->value; return 1; } cur = cur->next; } return 0; } int deleteKey(HashMap *map, const char *key) { unsigned int idx = hashString(key, map->capacity); Entry *cur = map->buckets[idx]; Entry *prev = NULL; while (cur != NULL) { if (strcmp(cur->key, key) == 0) { if (prev == NULL) map->buckets[idx] = cur->next; else prev->next = cur->next; free(cur); map->size--; return 0; } prev = cur; cur = cur->next; } return -1; } void display(const HashMap *map) { printf("Hash Map (size=%d, capacity=%d, load=%.2f):\n", map->size, map->capacity, (double)map->size / map->capacity); for (int i = 0; i < map->capacity; i++) { if (map->buckets[i] == NULL) continue; printf(" [%d]: ", i); Entry *cur = map->buckets[i]; while (cur != NULL) { printf("(%s→%d) ", cur->key, cur->value); cur = cur->next; } printf("\n"); } } int main(void) { HashMap *map = createMap(INITIAL_CAPACITY); if (map == NULL) { fprintf(stderr, "Failed to create map.\n"); return EXIT_FAILURE; } insert(map, "apple", 10); insert(map, "banana", 20); insert(map, "cherry", 30); insert(map, "date", 40); insert(map, "elderberry", 50); insert(map, "fig", 60); display(map); int value; printf("\nSearch results:\n"); if (search(map, "cherry", &value)) { printf(" cherry → %d\n", value); } if (!search(map, "grape", &value)) { printf(" grape → not found\n"); } printf("\nDeleting 'banana'...\n"); deleteKey(map, "banana"); display(map); freeMap(map); return EXIT_SUCCESS; }

Expected Output

text

Hash Map (size=6, capacity=7, load=0.86): [1]: (fig→60) (elderberry→50) [2]: (date→40) [3]: (cherry→30) [4]: (banana→20) [5]: (apple→10) Search results: cherry → 30 grape → not found Deleting 'banana'... Hash Map (size=5, capacity=7, load=0.71): [1]: (fig→60) (elderberry→50) [2]: (date→40) [3]: (cherry→30) [5]: (apple→10)

Explanation

  1. createMap: Allocates buckets array.
  2. hashString: djb2 polynomial hash.
  3. insert: Prepends to bucket list; updates existing keys.
  4. search: Traverses bucket list comparing keys.
  5. deleteKey: Unlinks and frees the entry.
  6. display: Prints the table’s contents.

Common Pitfalls, Edge Cases & Memory Considerations

1. Bad Hash Function

A poor hash function clusters keys, degrading performance to O(n).

Solution: Use prime table sizes and well-distributed hashes (djb2, sdbm).

2. Table Size Not Prime

Non-prime sizes create clustering.

Solution: Use primes: 7, 13, 31, 101, 1009, 10007.

3. Integer Overflow in Hash

Multiplication in hash functions can overflow.

Solution: Use unsigned int or unsigned long long.

4. Load Factor Exceeding Threshold

Performance degrades significantly.

Solution: Rehash when load factor > 0.75.

5. Memory Leaks

Forgetting to free all entries and buckets.

Solution: Walk each bucket and free each node, then free the bucket array.

6. Negative Keys

key % size for negative keys can yield negative indices.

Solution: Cast to unsigned int before modulo.

7. Duplicate Keys in Hash Set

Need to decide: overwrite or reject?

Solution: Check for existing key before inserting.

8. Tombstones in Open Addressing

Deletion needs special markers to preserve probe chains.

Solution: Use DELETED sentinel values.

9. Rehashing Overhead

Frequent resizing hurts performance.

Solution: Double the size and choose the next prime.

10. Memory Considerations

  • Chaining: O(n) space for nodes.
  • Open addressing: O(m) space, no pointers.
  • Rehashing doubles memory temporarily.
  • Use dynamic allocation carefully; check every malloc.

Summary & Best Practices

Hashing is one of the most important data structure techniques, offering O(1) average-time operations. Choosing the right hash function and collision resolution strategy is essential for performance.

Key Takeaways

  • Hashing maps keys to indices via a hash function.
  • Hash tables support O(1) average insert, search, delete.
  • Collisions are resolved via chaining or open addressing.
  • Load factor determines performance; rehash when high.
  • Hash sets store unique keys; hash maps store key-value pairs.
  • Not suitable for sorted/range/prefix queries.

Best Practices

  1. Use prime table sizes (7, 13, 31, 101, …).
  2. Use good hash functions (djb2 for strings, modulo for ints).
  3. Keep load factor ≤ 0.75; rehash when exceeded.
  4. Cast to unsigned for negative keys.
  5. Check every malloc return.
  6. Free all entries and buckets on cleanup.
  7. Use tombstones for deletion in open addressing.
  8. Avoid hash tables for sorted or range queries.
  9. Test with collisions to verify correctness.
  10. Profile for large datasets.

By mastering hashing, you’ll have a powerful tool for fast lookups and a foundation for building sets, maps, caches, and dictionaries.