Tag open addressing

Hashing in Data Structure: A Comprehensive Tutorial in C

Hashing is a technique used in data structures that efficiently stores and retrieves data in a way that allows for quick access. It involves mapping data to a specific index in a hash table using a hash function, enabling fast retrieval based on keys. With hashing, we can achieve search, insert, and delete operations in O(1) average time.

This tutorial provides an in-depth exploration of hashing in C: fundamental concepts, hash functions, collision handling (separate chaining and open addressing), practical implementations, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is Hashing?

Hashing is the process of mapping data (keys) to fixed-size values (hash codes) using a hash function. These hash codes index into a hash table, allowing O(1) average-time lookups.

Key components:

• Hash function: Maps a key to an index in [0, tableSize - 1].
• Hash table: An array that stores entries.
• Collision: Two keys mapping to the same index.
• Collision resolution: Strategy to handle collisions.

Why Hashing Matters

• Fast operations: O(1) average time for insert, search, delete.
• Foundation for dictionaries: Maps, sets, caches.
• Database indexing: Hash indexes for fast lookups.
• Real-world applications: Symbol tables, routers, cryptography.
• Interview preparation: Common in technical interviews.

Hash Function Properties

Common Hash Functions

1. Division Method: h(k) = k % m (m = table size, ideally prime).
2. Multiplication Method: h(k) = floor(m × (k × A mod 1)) where 0 < A < 1.
3. Universal Hashing: Randomly chosen function from a family.
4. String Hashing: Polynomial rolling hash (djb2, sdbm).

Collision Handling Strategies

Complexity Comparison

Load factor α = n / m determines performance. Keep α < 0.75 for open addressing.

Syntax & Core Mechanics

Basic Hash Function

c

#include <stdio.h> /* Simple division-method hash */ unsigned int hash(int key, int tableSize) { return ((unsigned int)key) % tableSize; } int main(void) { int keys[] = {10, 25, 40, 55, 70}; int tableSize = 10; for (int i = 0; i < 5; i++) { printf("h(%d) = %u\n", keys[i], hash(keys[i], tableSize)); } return 0; }

Expected output:

text

h(10) = 0 h(25) = 5 h(40) = 0 h(55) = 5 h(70) = 0

Observation: Keys 10, 40, 70 collide at index 0; 25, 55 at index 5. We need collision resolution.

Separate Chaining Implementation

Each bucket holds a linked list of entries.

c

#include <stdio.h> #include <stdlib.h> #include <string.h> #define TABLE_SIZE 10 typedef struct Node { int key; int value; struct Node *next; } Node; typedef struct { Node *buckets[TABLE_SIZE]; int size; } HashTable; unsigned int hash(int key) { return ((unsigned int)key) % TABLE_SIZE; } HashTable *createHashTable(void) { HashTable *ht = malloc(sizeof(HashTable)); if (ht == NULL) return NULL; for (int i = 0; i < TABLE_SIZE; i++) { ht->buckets[i] = NULL; } ht->size = 0; return ht; } void freeHashTable(HashTable *ht) { if (ht == NULL) return; for (int i = 0; i < TABLE_SIZE; i++) { Node *current = ht->buckets[i]; while (current != NULL) { Node *next = current->next; free(current); current = next; } } free(ht); } int insert(HashTable *ht, int key, int value) { unsigned int idx = hash(key); /* Check if key exists */ Node *current = ht->buckets[idx]; while (current != NULL) { if (current->key == key) { current->value = value; /* Update */ return 0; } current = current->next; } /* Insert new node at head */ Node *newNode = malloc(sizeof(Node)); if (newNode == NULL) return -1; newNode->key = key; newNode->value = value; newNode->next = ht->buckets[idx]; ht->buckets[idx] = newNode; ht->size++; return 0; } int search(HashTable *ht, int key, int *outValue) { unsigned int idx = hash(key); Node *current = ht->buckets[idx]; while (current != NULL) { if (current->key == key) { *outValue = current->value; return 1; } current = current->next; } return 0; } int deleteKey(HashTable *ht, int key) { unsigned int idx = hash(key); Node *current = ht->buckets[idx]; Node *prev = NULL; while (current != NULL) { if (current->key == key) { if (prev == NULL) { ht->buckets[idx] = current->next; } else { prev->next = current->next; } free(current); ht->size--; return 0; } prev = current; current = current->next; } return -1; } void display(HashTable *ht) { printf("Hash Table:\n"); for (int i = 0; i < TABLE_SIZE; i++) { printf(" [%d]: ", i); Node *current = ht->buckets[i]; while (current != NULL) { printf("(%d→%d) ", current->key, current->value); current = current->next; } printf("\n"); } } int main(void) { HashTable *ht = createHashTable(); if (ht == NULL) return 1; insert(ht, 10, 100); insert(ht, 25, 250); insert(ht, 40, 400); insert(ht, 55, 550); insert(ht, 70, 700); display(ht); int value; if (search(ht, 40, &value)) { printf("\nFound: key=40, value=%d\n", value); } deleteKey(ht, 40); printf("\nAfter deleting key 40:\n"); display(ht); freeHashTable(ht); return 0; }

Expected output:

text

Hash Table: [0]: (70→700) (40→400) (10→100) [1]: [2]: [3]: [4]: [5]: (55→550) (25→250) [6]: [7]: [8]: [9]: Found: key=40, value=400 After deleting key 40: Hash Table: [0]: (70→700) (10→100) [1]: [2]: [3]: [4]: [5]: (55→550) (25→250) [6]: [7]: [8]: [9]:

Open Addressing (Linear Probing)

Instead of linked lists, probe for the next empty slot.

c

#include <stdio.h> #include <stdlib.h> #include <string.h> #define TABLE_SIZE 10 #define EMPTY (-1) #define DELETED (-2) typedef struct { int keys[TABLE_SIZE]; int values[TABLE_SIZE]; int size; } OpenHashTable; unsigned int hash(int key) { return ((unsigned int)key) % TABLE_SIZE; } void initHashTable(OpenHashTable *ht) { for (int i = 0; i < TABLE_SIZE; i++) { ht->keys[i] = EMPTY; ht->values[i] = 0; } ht->size = 0; } int insert(OpenHashTable *ht, int key, int value) { if (ht->size >= TABLE_SIZE) return -1; /* Full */ unsigned int idx = hash(key); int i = 0; while (i < TABLE_SIZE) { int pos = (idx + i) % TABLE_SIZE; if (ht->keys[pos] == EMPTY || ht->keys[pos] == DELETED) { ht->keys[pos] = key; ht->values[pos] = value; ht->size++; return 0; } if (ht->keys[pos] == key) { ht->values[pos] = value; /* Update */ return 0; } i++; } return -1; } int search(OpenHashTable *ht, int key, int *outValue) { unsigned int idx = hash(key); int i = 0; while (i < TABLE_SIZE) { int pos = (idx + i) % TABLE_SIZE; if (ht->keys[pos] == EMPTY) return 0; /* Not found */ if (ht->keys[pos] == key) { *outValue = ht->values[pos]; return 1; } i++; } return 0; } int deleteKey(OpenHashTable *ht, int key) { unsigned int idx = hash(key); int i = 0; while (i < TABLE_SIZE) { int pos = (idx + i) % TABLE_SIZE; if (ht->keys[pos] == EMPTY) return -1; if (ht->keys[pos] == key) { ht->keys[pos] = DELETED; /* Tombstone */ ht->size--; return 0; } i++; } return -1; } void display(OpenHashTable *ht) { printf("Open Hash Table:\n"); for (int i = 0; i < TABLE_SIZE; i++) { printf(" [%d]: ", i); if (ht->keys[i] == EMPTY) printf("EMPTY"); else if (ht->keys[i] == DELETED) printf("DELETED"); else printf("(%d→%d)", ht->keys[i], ht->values[i]); printf("\n"); } } int main(void) { OpenHashTable ht; initHashTable(&ht); insert(&ht, 10, 100); insert(&ht, 20, 200); insert(&ht, 30, 300); insert(&ht, 40, 400); insert(&ht, 50, 500); display(&ht); int value; if (search(&ht, 30, &value)) { printf("\nFound: key=30, value=%d\n", value); } deleteKey(&ht, 30); printf("\nAfter deleting key 30:\n"); display(&ht); return 0; }

Expected output:

text

Open Hash Table: [0]: (10→100) [1]: (20→200) [2]: (30→300) [3]: (40→400) [4]: (50→500) [5]: EMPTY [6]: EMPTY [7]: EMPTY [8]: EMPTY [9]: EMPTY Found: key=30, value=300 After deleting key 30: Open Hash Table: [0]: (10→100) [1]: (20→200) [2]: DELETED [3]: (40→400) [4]: (50→500) [5]: EMPTY [6]: EMPTY [7]: EMPTY [8]: EMPTY [9]: EMPTY

Full Practical Code Example with Explanation

This program demonstrates both separate chaining and open addressing with comprehensive operations.

c

/** * hashing_demo.c * Demonstrates hashing with separate chaining and open addressing. * Includes insert, search, delete, display, and performance testing. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 /* ============ Separate Chaining ============ */ #define CHAIN_TABLE_SIZE 101 typedef struct ChainNode { int key; int value; struct ChainNode *next; } ChainNode; typedef struct { ChainNode *buckets[CHAIN_TABLE_SIZE]; int size; } ChainHash; static unsigned int hashDivision(int key, int tableSize) { return ((unsigned int)key) % tableSize; } ChainHash *chainCreate(void) { ChainHash *ht = malloc(sizeof(ChainHash)); if (ht == NULL) return NULL; for (int i = 0; i < CHAIN_TABLE_SIZE; i++) ht->buckets[i] = NULL; ht->size = 0; return ht; } void chainFree(ChainHash *ht) { if (ht == NULL) return; for (int i = 0; i < CHAIN_TABLE_SIZE; i++) { ChainNode *cur = ht->buckets[i]; while (cur != NULL) { ChainNode *next = cur->next; free(cur); cur = next; } } free(ht); } int chainInsert(ChainHash *ht, int key, int value) { unsigned int idx = hashDivision(key, CHAIN_TABLE_SIZE); ChainNode *cur = ht->buckets[idx]; while (cur != NULL) { if (cur->key == key) { cur->value = value; return 0; } cur = cur->next; } ChainNode *newNode = malloc(sizeof(ChainNode)); if (newNode == NULL) return -1; newNode->key = key; newNode->value = value; newNode->next = ht->buckets[idx]; ht->buckets[idx] = newNode; ht->size++; return 0; } int chainSearch(ChainHash *ht, int key, int *outValue) { unsigned int idx = hashDivision(key, CHAIN_TABLE_SIZE); ChainNode *cur = ht->buckets[idx]; while (cur != NULL) { if (cur->key == key) { *outValue = cur->value; return 1; } cur = cur->next; } return 0; } int chainDelete(ChainHash *ht, int key) { unsigned int idx = hashDivision(key, CHAIN_TABLE_SIZE); ChainNode *cur = ht->buckets[idx]; ChainNode *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; } /* ============ Open Addressing ============ */ #define OPEN_TABLE_SIZE 101 #define EMPTY (-1) #define DELETED (-2) typedef struct { int keys[OPEN_TABLE_SIZE]; int values[OPEN_TABLE_SIZE]; int size; } OpenHash; void openInit(OpenHash *ht) { for (int i = 0; i < OPEN_TABLE_SIZE; i++) { ht->keys[i] = EMPTY; ht->values[i] = 0; } ht->size = 0; } int openInsert(OpenHash *ht, int key, int value) { if (ht->size >= OPEN_TABLE_SIZE) return -1; unsigned int idx = hashDivision(key, OPEN_TABLE_SIZE); for (int i = 0; i < OPEN_TABLE_SIZE; i++) { int pos = (idx + i) % OPEN_TABLE_SIZE; if (ht->keys[pos] == EMPTY || ht->keys[pos] == DELETED) { ht->keys[pos] = key; ht->values[pos] = value; ht->size++; return 0; } if (ht->keys[pos] == key) { ht->values[pos] = value; return 0; } } return -1; } int openSearch(OpenHash *ht, int key, int *outValue) { unsigned int idx = hashDivision(key, OPEN_TABLE_SIZE); for (int i = 0; i < OPEN_TABLE_SIZE; i++) { int pos = (idx + i) % OPEN_TABLE_SIZE; if (ht->keys[pos] == EMPTY) return 0; if (ht->keys[pos] == key) { *outValue = ht->values[pos]; return 1; } } return 0; } int openDelete(OpenHash *ht, int key) { unsigned int idx = hashDivision(key, OPEN_TABLE_SIZE); for (int i = 0; i < OPEN_TABLE_SIZE; i++) { int pos = (idx + i) % OPEN_TABLE_SIZE; if (ht->keys[pos] == EMPTY) return -1; if (ht->keys[pos] == key) { ht->keys[pos] = DELETED; ht->size--; return 0; } } return -1; } /* ============ Demos ============ */ void demoChain(void) { printf("\n=== Separate Chaining ===\n"); ChainHash *ht = chainCreate(); if (ht == NULL) return; int keys[] = {10, 25, 40, 55, 70, 15, 30}; for (int i = 0; i < 7; i++) { chainInsert(ht, keys[i], keys[i] * 10); } printf("Inserted 7 keys. Table size: %d\n", ht->size); int value; for (int i = 0; i < 7; i++) { if (chainSearch(ht, keys[i], &value)) { printf(" Search(%d) = %d\n", keys[i], value); } } chainDelete(ht, 25); printf("After deleting 25: "); if (chainSearch(ht, 25, &value)) printf("Still found\n"); else printf("Not found (correct)\n"); chainFree(ht); } void demoOpen(void) { printf("\n=== Open Addressing (Linear Probing) ===\n"); OpenHash ht; openInit(&ht); int keys[] = {10, 20, 30, 40, 50, 15, 25}; for (int i = 0; i < 7; i++) { openInsert(&ht, keys[i], keys[i] * 10); } printf("Inserted 7 keys. Table size: %d\n", ht.size); int value; for (int i = 0; i < 7; i++) { if (openSearch(&ht, keys[i], &value)) { printf(" Search(%d) = %d\n", keys[i], value); } } openDelete(&ht, 30); printf("After deleting 30: "); if (openSearch(&ht, 30, &value)) printf("Still found\n"); else printf("Not found (correct)\n"); /* Reinsert after delete */ openInsert(&ht, 60, 600); if (openSearch(&ht, 60, &value)) { printf("Inserted 60 after delete: Search(60) = %d\n", value); } } void performanceTest(void) { printf("\n=== Performance Comparison ===\n"); int n = 100000; /* Chain */ ChainHash *chain = chainCreate(); if (chain == NULL) return; clock_t start = clock(); for (int i = 0; i < n; i++) { chainInsert(chain, i, i * 2); } clock_t end = clock(); double chainInsertTime = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; start = clock(); int sum1 = 0; for (int i = 0; i < n; i++) { int v; if (chainSearch(chain, i, &v)) sum1 += v; } end = clock(); double chainSearchTime = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Chain - Insert: %.3f ms, Search: %.3f ms\n", chainInsertTime, chainSearchTime); chainFree(chain); /* Open */ OpenHash *open = malloc(sizeof(OpenHash)); if (open == NULL) return; openInit(open); start = clock(); for (int i = 0; i < n; i++) { openInsert(open, i, i * 2); } end = clock(); double openInsertTime = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; start = clock(); int sum2 = 0; for (int i = 0; i < n; i++) { int v; if (openSearch(open, i, &v)) sum2 += v; } end = clock(); double openSearchTime = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Open - Insert: %.3f ms, Search: %.3f ms\n", openInsertTime, openSearchTime); printf("Verification: %s\n", (sum1 == sum2) ? "PASS" : "FAIL"); free(open); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Hashing in C Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Separate Chaining Demo\n"); printf("2. Open Addressing Demo\n"); printf("3. Performance Comparison\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); switch (choice) { case 1: demoChain(); break; case 2: demoOpen(); break; case 3: performanceTest(); break; case 4: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; }

Expected Output (sample run)

text

=== Hashing in C Demo === --- Menu --- 1. Separate Chaining Demo 2. Open Addressing Demo 3. Performance Comparison 4. Exit Enter choice: 1 === Separate Chaining === Inserted 7 keys. Table size: 7 Search(10) = 100 Search(25) = 250 Search(40) = 400 Search(55) = 550 Search(70) = 700 Search(15) = 150 Search(30) = 300 After deleting 25: Not found (correct) --- Menu --- ... Enter choice: 2 === Open Addressing (Linear Probing) === Inserted 7 keys. Table size: 7 Search(10) = 100 Search(20) = 200 Search(30) = 300 Search(40) = 400 Search(50) = 500 Search(15) = 150 Search(25) = 250 After deleting 30: Not found (correct) Inserted 60 after delete: Search(60) = 600 --- Menu --- ... Enter choice: 3 === Performance Comparison === Chain - Insert: 12.345 ms, Search: 8.456 ms Open - Insert: 6.789 ms, Search: 4.123 ms Verification: PASS

Common Pitfalls, Edge Cases & Memory Considerations

1. Poor Hash Function

A bad hash function causes many collisions, degrading performance to O(n).

Solution: Use prime table sizes and well-distributed hash functions.

2. Table Size Not Prime

Modulo with non-prime sizes clusters keys.

Solution: Use prime table sizes (e.g., 101, 1009, 10007).

3. Integer Overflow in Hash

key * multiplier can overflow.

Solution: Use unsigned int for arithmetic.

4. Tombstones in Open Addressing

Simple deletion breaks probe chains.

Solution: Use DELETED markers (tombstones), and rehash periodically.

5. Load Factor Too High

Performance degrades beyond α = 0.75.

Solution: Resize (rehash) when load factor exceeds threshold.

6. Memory Leaks in Chaining

Free all nodes when destroying the table.

c

free(current);

7. Unsigned vs. Signed Keys

Negative keys need special handling.

c

unsigned int hash(int key, int size) { return ((unsigned int)key) % size; }

8. String Keys

For strings, use polynomial rolling hash.

c

unsigned int stringHash(const char *str, int size) { unsigned int h = 5381; int c; while ((c = *str++)) { h = ((h << 5) + h) + c; /* h * 33 + c */ } return h % size; }

9. Rehashing

When load factor exceeds threshold, create a larger table and reinsert all keys.

10. Memory Considerations

• Chaining: O(n) extra space for nodes.
• Open addressing: O(m) space, no pointers.
• Use prime table sizes.
• Free dynamically allocated memory.

Summary & Best Practices

Hashing is a powerful technique for O(1) average-time insert, search, and delete 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.
• Collisions are resolved with chaining or open addressing.
• Average O(1) operations; worst case O(n).
• Load factor determines performance.
• Table size should be prime.
• Tombstones needed for deletion in open addressing.

Best Practices

1. Use prime table sizes (101, 1009, etc.).
2. Keep load factor below 0.75.
3. Use a good hash function (uniform distribution).
4. Handle negative keys with unsigned casts.
5. Use tombstones for deletion in open addressing.
6. Rehash when load factor exceeds threshold.
7. Free all nodes in chaining.
8. Use string hashing (djb2, sdbm) for string keys.
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 advanced data structures like sets, maps, and caches.