Tag hashing in C

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

Type	Description	Example
Hash Set	Collection of unique keys	unordered_set (C++), HashSet (Java)
Hash Map	Key-value pairs with unique keys	unordered_map (C++), HashMap (Java), dict (Python)

When NOT to Use Hashing

Scenario	Better Choice
Need sorted data with search/insert/delete	Self-balancing BST
Prefix search on string keys	Trie
Need floor/ceiling operations	Self-balancing BST
Range queries	Sorted array / segment tree

Components of Hashing

Component	Description
Key	The input (string, integer, etc.)
Hash Function	Maps key → index in [0, tableSize - 1]
Hash Table	Array storing values at hash indices

Key Hashing Concepts

Concept	Description
Hash Function	Mathematical formula mapping key to index
Collision	Two keys map to the same index
Collision Resolution	Chaining, open addressing, etc.
Load Factor (α)	n / m (entries / table size)
Rehashing	Resizing table when load factor is high

Complexity Comparison

Data Structure	Search	Insert	Delete
Array (unsorted)	O(n)	O(1)	O(n)
Linked List	O(n)	O(1)	O(n)
Balanced BST	O(log n)	O(log n)	O(log n)
Hash Table	O(1) avg	O(1) avg	O(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

Strategy	Description
Separate Chaining	Each bucket holds a linked list of entries
Linear Probing	On collision, try (h(k) + i) % m for i = 1, 2, ...
Quadratic Probing	Try (h(k) + i²) % m
Double Hashing	Use 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.