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]:

Key	Index
15	1
11	4
27	6
8	1 (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

Operation	Time Complexity
Search	O(1 + α)
Insert	O(1 + α)
Delete	O(1 + α)

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

Two Variants

Variant	Description
Simple Chaining	Fixed number of buckets; no resizing
Chaining with Rehashing	Doubles 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.