CoreTechED

Loading

Tag data structures

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.

Explore hashing applications in C: password storage, file checksums, dictionaries, Bloom filters, load balancing, and symbol tables with code examples.
C Programming

Applications of Hashing in C: Complete Guide

Applications of Hashing in C: A Comprehensive Tutorial

Hashing is a technique that converts data of any size into a fixed-size value, known as a hash, which can be used for quick data retrieval and comparison. With average O(1) insert, search, and delete, hashing powers some of the most critical systems in computing — from securing passwords to routing internet traffic.

This tutorial explores hashing’s major applications in C: data integrity and security, database and search optimization, network and system infrastructure, and specialized processing. Each application is illustrated with practical C code.

Conceptual Introduction & Fundamentals

What is Hashing?

Hashing maps arbitrary-sized input (a key) to a fixed-size value (a hash) via a hash function. The hash serves as an index into a hash table, enabling O(1) average lookups.

Why Applications Matter

  • Ubiquity: Hashing powers databases, caches, security, networks.
  • Performance: Replaces O(n) or O(log n) operations with O(1) average.
  • Versatility: Applies to strings, integers, files, images.
  • Real-world impact: Every secure login, CDN, and compiler uses hashing.

Categories of Applications

CategoryPrimary Use
Data Integrity & SecurityPassword storage, checksums, blockchain
Database & SearchIndexing, dictionaries, Rabin-Karp
Network & SystemsLoad balancing, Bloom filters, routing
SpecializedImage hashing, symbol tables, graphics

Syntax & Core Mechanics

Application 1: Data Integrity & Security

1.1 Password Storage

Store non-reversible hash instead of plaintext.

c

#include <stdio.h> #include <string.h> #include <stdint.h> /* FNV-1a hash (for educational demo only; use bcrypt/scrypt/argon2 in production) */ uint64_t fnv1a(const char *str) { uint64_t hash = 1469598103934665603ULL; while (*str) { hash ^= (unsigned char)*str++; hash *= 1099511628211ULL; } return hash; } int main(void) { const char *password = "MySecret123"; uint64_t stored = fnv1a(password); printf("Stored hash: 0x%016llx\n", (unsigned long long)stored); /* Verify */ const char *attempt = "MySecret123"; if (fnv1a(attempt) == stored) { printf("Login successful\n"); } else { printf("Login failed\n"); } return 0; }

Expected output:

text

Stored hash: 0x... Login successful

Production note: Use bcrypt, scrypt, or Argon2 with salt for real password storage — FNV is not cryptographically secure.

1.2 File Comparison (Checksum)

c

#include <stdio.h> #include <stdint.h> uint64_t fileHash(const char *path) { FILE *fp = fopen(path, "rb"); if (fp == NULL) return 0; uint64_t hash = 1469598103934665603ULL; int c; while ((c = fgetc(fp)) != EOF) { hash ^= (unsigned char)c; hash *= 1099511628211ULL; } fclose(fp); return hash; } int main(void) { /* Create test file first */ FILE *fp = fopen("test.txt", "w"); if (fp != NULL) { fprintf(fp, "Hello, World!\n"); fclose(fp); } uint64_t h1 = fileHash("test.txt"); printf("File hash: 0x%016llx\n", (unsigned long long)h1); return 0; }

Expected output:

text

File hash: 0x...

Use case: Detect corruption; any single-bit change alters the hash.

1.3 Rabin-Karp String Search

Hash windows of text for fast substring search.

c

#include <stdio.h> #include <string.h> #define BASE 256 #define MOD 1000000007 long long hashString(const char *str, int len) { long long h = 0; for (int i = 0; i < len; i++) { h = (h * BASE + (unsigned char)str[i]) % MOD; } return h; } int rabinKarp(const char *text, const char *pattern) { int n = (int)strlen(text); int m = (int)strlen(pattern); if (m > n) return -1; long long patHash = hashString(pattern, m); long long textHash = hashString(text, m); /* Precompute BASE^(m-1) % MOD */ long long h = 1; for (int i = 0; i < m - 1; i++) h = (h * BASE) % MOD; for (int i = 0; i <= n - m; i++) { if (patHash == textHash) { if (strncmp(text + i, pattern, m) == 0) return i; } if (i < n - m) { textHash = (textHash - (unsigned char)text[i] * h) % MOD; if (textHash < 0) textHash += MOD; textHash = (textHash * BASE + (unsigned char)text[i + m]) % MOD; } } return -1; } int main(void) { const char *text = "The quick brown fox jumps over the lazy dog"; const char *pattern = "brown"; int idx = rabinKarp(text, pattern); if (idx >= 0) printf("Found \"%s\" at index %d\n", pattern, idx); else printf("Not found\n"); return 0; }

Expected output:

text

Found "brown" at index 10

Application 2: Database & Search Optimization

2.1 Dictionary / Associative Array

c

#include <stdio.h> #include <stdlib.h> #include <string.h> #define TABLE_SIZE 101 #define KEY_LEN 32 typedef struct Entry { char key[KEY_LEN]; int value; struct Entry *next; } Entry; typedef struct { Entry *buckets[TABLE_SIZE]; } Dict; static unsigned int hashString(const char *s) { unsigned int h = 5381; while (*s) h = ((h << 5) + h) + (unsigned char)*s++; return h % TABLE_SIZE; } void dictPut(Dict *d, const char *key, int value) { unsigned int idx = hashString(key); Entry *cur = d->buckets[idx]; while (cur) { if (strcmp(cur->key, key) == 0) { cur->value = value; return; } cur = cur->next; } Entry *e = malloc(sizeof(Entry)); if (e == NULL) return; strncpy(e->key, key, KEY_LEN - 1); e->key[KEY_LEN - 1] = '\0'; e->value = value; e->next = d->buckets[idx]; d->buckets[idx] = e; } int dictGet(Dict *d, const char *key, int *out) { unsigned int idx = hashString(key); Entry *cur = d->buckets[idx]; while (cur) { if (strcmp(cur->key, key) == 0) { *out = cur->value; return 1; } cur = cur->next; } return 0; } void dictFree(Dict *d) { for (int i = 0; i < TABLE_SIZE; i++) { Entry *cur = d->buckets[i]; while (cur) { Entry *next = cur->next; free(cur); cur = next; } } } int main(void) { Dict d = {0}; dictPut(&d, "apple", 10); dictPut(&d, "banana", 20); dictPut(&d, "cherry", 30); int v; if (dictGet(&d, "banana", &v)) printf("banana → %d\n", v); if (dictGet(&d, "grape", &v)) printf("grape → %d\n", v); else printf("grape not found\n"); dictFree(&d); return 0; }

Expected output:

text

banana → 20 grape not found

2.2 Frequency Counting

c

#include <stdio.h> #include <stdlib.h> void countFrequency(const int arr[], int n, int maxValue) { int *freq = calloc(maxValue + 1, sizeof(int)); if (freq == NULL) return; for (int i = 0; i < n; i++) freq[arr[i]]++; for (int i = 0; i <= maxValue; i++) { if (freq[i] > 0) printf(" %d → %d\n", i, freq[i]); } free(freq); } int main(void) { int arr[] = {1, 3, 5, 3, 2, 1, 5, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("Frequencies:\n"); countFrequency(arr, n, 5); return 0; }

Expected output:

text

Frequencies: 1 → 2 2 → 1 3 → 3 5 → 2

Application 3: Network & System Infrastructure

3.1 Bloom Filter (Membership Test)

c

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> #define BLOOM_SIZE 1024 /* bits */ #define NUM_HASHES 3 typedef struct { uint8_t bits[BLOOM_SIZE / 8]; } Bloom; static void bloomSet(Bloom *b, int bit) { b->bits[bit / 8] |= (uint8_t)(1u << (bit % 8)); } static int bloomGet(const Bloom *b, int bit) { return (b->bits[bit / 8] >> (bit % 8)) & 1u; } static unsigned int hash1(const char *s) { unsigned int h = 5381; while (*s) h = ((h << 5) + h) + (unsigned char)*s++; return h % BLOOM_SIZE; } static unsigned int hash2(const char *s) { unsigned int h = 0; while (*s) h = (h * 31) + (unsigned char)*s++; return h % BLOOM_SIZE; } static unsigned int hash3(const char *s) { unsigned int h = 7; while (*s) h = (h * 131) + (unsigned char)*s++; return h % BLOOM_SIZE; } void bloomAdd(Bloom *b, const char *key) { bloomSet(b, hash1(key)); bloomSet(b, hash2(key)); bloomSet(b, hash3(key)); } int bloomContains(const Bloom *b, const char *key) { return bloomGet(b, hash1(key)) && bloomGet(b, hash2(key)) && bloomGet(b, hash3(key)); } int main(void) { Bloom b = {{0}}; bloomAdd(&b, "apple"); bloomAdd(&b, "banana"); bloomAdd(&b, "cherry"); printf("apple: %s\n", bloomContains(&b, "apple") ? "maybe" : "no"); printf("banana: %s\n", bloomContains(&b, "banana") ? "maybe" : "no"); printf("grape: %s\n", bloomContains(&b, "grape") ? "maybe" : "no"); return 0; }

Expected output (typical):

text

apple: maybe banana: maybe grape: no

Key insight: Bloom filters never produce false negatives, only false positives.

3.2 Load Balancing (Consistent Hashing Skeleton)

c

#include <stdio.h> #include <string.h> #define NUM_SERVERS 4 const char *servers[NUM_SERVERS] = { "server-1", "server-2", "server-3", "server-4" }; unsigned int hashString(const char *s) { unsigned int h = 5381; while (*s) h = ((h << 5) + h) + (unsigned char)*s++; return h; } const char *routeRequest(const char *key) { unsigned int idx = hashString(key) % NUM_SERVERS; return servers[idx]; } int main(void) { const char *requests[] = {"user42", "session7", "cart9", "user7"}; int n = sizeof(requests) / sizeof(requests[0]); for (int i = 0; i < n; i++) { printf("%-10s → %s\n", requests[i], routeRequest(requests[i])); } return 0; }

Expected output (typical):

text

user42 → server-3 session7 → server-2 cart9 → server-1 user7 → server-4

Application 4: Specialized Processing

4.1 Symbol Table (Compiler Use Case)

Maps identifiers to metadata.

c

#include <stdio.h> #include <stdlib.h> #include <string.h> #define TABLE_SIZE 101 #define NAME_LEN 32 typedef enum { TYPE_INT, TYPE_FLOAT, TYPE_CHAR } VarType; typedef struct Symbol { char name[NAME_LEN]; VarType type; int scope; struct Symbol *next; } Symbol; typedef struct { Symbol *buckets[TABLE_SIZE]; } SymbolTable; static unsigned int hashName(const char *s) { unsigned int h = 5381; while (*s) h = ((h << 5) + h) + (unsigned char)*s++; return h % TABLE_SIZE; } void symAdd(SymbolTable *st, const char *name, VarType type, int scope) { unsigned int idx = hashName(name); Symbol *s = malloc(sizeof(Symbol)); if (s == NULL) return; strncpy(s->name, name, NAME_LEN - 1); s->name[NAME_LEN - 1] = '\0'; s->type = type; s->scope = scope; s->next = st->buckets[idx]; st->buckets[idx] = s; } Symbol *symFind(SymbolTable *st, const char *name) { unsigned int idx = hashName(name); Symbol *s = st->buckets[idx]; while (s) { if (strcmp(s->name, name) == 0) return s; s = s->next; } return NULL; } void symFree(SymbolTable *st) { for (int i = 0; i < TABLE_SIZE; i++) { Symbol *s = st->buckets[i]; while (s) { Symbol *next = s->next; free(s); s = next; } } } const char *typeName(VarType t) { switch (t) { case TYPE_INT: return "int"; case TYPE_FLOAT: return "float"; case TYPE_CHAR: return "char"; } return "unknown"; } int main(void) { SymbolTable st = {0}; symAdd(&st, "count", TYPE_INT, 0); symAdd(&st, "price", TYPE_FLOAT, 0); symAdd(&st, "initial", TYPE_CHAR, 1); Symbol *s = symFind(&st, "price"); if (s) printf("%s : %s (scope %d)\n", s->name, typeName(s->type), s->scope); symFree(&st); return 0; }

Expected output:

text

price : float (scope 0)

Full Practical Code Example with Explanation

This program combines multiple hashing applications in a single file-integrity and password manager demo.

c

/** * hashing_applications.c * Demonstrates hashing applications: password storage, * file checksums, frequency counting, and Bloom filters. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> #include <errno.h> #define MAX_LINE_LEN 100 #define BLOOM_SIZE 1024 #define NUM_HASHES 3 #define FNV_OFFSET 1469598103934665603ULL #define FNV_PRIME 1099511628211ULL /* FNV-1a hash */ uint64_t fnv1a(const char *str) { uint64_t h = FNV_OFFSET; while (*str) { h ^= (unsigned char)*str++; h *= FNV_PRIME; } return h; } /* Password demo */ void demoPassword(void) { printf("\n=== Password Storage ===\n"); const char *password = "MySecret123"; uint64_t stored = fnv1a(password); printf("Stored hash: 0x%016llx\n", (unsigned long long)stored); const char *attempts[] = {"MySecret123", "wrongpass", "MySecret124"}; for (int i = 0; i < 3; i++) { uint64_t h = fnv1a(attempts[i]); printf(" Attempt \"%s\": %s\n", attempts[i], (h == stored) ? "SUCCESS" : "FAIL"); } } /* File checksum demo */ uint64_t fileHash(const char *path) { FILE *fp = fopen(path, "rb"); if (fp == NULL) return 0; uint64_t h = FNV_OFFSET; int c; while ((c = fgetc(fp)) != EOF) { h ^= (unsigned char)c; h *= FNV_PRIME; } fclose(fp); return h; } void demoFileHash(void) { printf("\n=== File Checksum ===\n"); /* Create test file */ FILE *fp = fopen("demo.txt", "w"); if (fp == NULL) { perror("fopen"); return; } fprintf(fp, "Hello, hashing!\n"); fclose(fp); uint64_t h = fileHash("demo.txt"); printf("Hash of demo.txt: 0x%016llx\n", (unsigned long long)h); /* Modify file */ fp = fopen("demo.txt", "a"); if (fp == NULL) return; fprintf(fp, "Extra line.\n"); fclose(fp); uint64_t h2 = fileHash("demo.txt"); printf("After modification: 0x%016llx\n", (unsigned long long)h2); printf("Files match: %s\n", (h == h2) ? "YES" : "NO"); } /* Frequency counting */ void demoFrequency(void) { printf("\n=== Frequency Counting ===\n"); int arr[] = {1, 3, 5, 3, 2, 1, 5, 3}; int n = sizeof(arr) / sizeof(arr[0]); int maxV = 5; int *freq = calloc(maxV + 1, sizeof(int)); if (freq == NULL) return; for (int i = 0; i < n; i++) freq[arr[i]]++; for (int i = 0; i <= maxV; i++) { if (freq[i]) printf(" %d → %d\n", i, freq[i]); } free(freq); } /* Bloom filter */ typedef struct { uint8_t bits[BLOOM_SIZE / 8]; } Bloom; static unsigned int h1(const char *s) { unsigned int h = 5381; while (*s) h = ((h << 5) + h) + (unsigned char)*s++; return h % BLOOM_SIZE; } static unsigned int h2(const char *s) { unsigned int h = 0; while (*s) h = (h * 31) + (unsigned char)*s++; return h % BLOOM_SIZE; } static unsigned int h3(const char *s) { unsigned int h = 7; while (*s) h = (h * 131) + (unsigned char)*s++; return h % BLOOM_SIZE; } static void bloomSet(Bloom *b, int bit) { b->bits[bit / 8] |= (uint8_t)(1u << (bit % 8)); } static int bloomGet(const Bloom *b, int bit) { return (b->bits[bit / 8] >> (bit % 8)) & 1u; } void bloomAdd(Bloom *b, const char *k) { bloomSet(b, h1(k)); bloomSet(b, h2(k)); bloomSet(b, h3(k)); } int bloomHas(const Bloom *b, const char *k) { return bloomGet(b, h1(k)) && bloomGet(b, h2(k)) && bloomGet(b, h3(k)); } void demoBloom(void) { printf("\n=== Bloom Filter ===\n"); Bloom b = {{0}}; const char *inserted[] = {"apple", "banana", "cherry"}; for (int i = 0; i < 3; i++) bloomAdd(&b, inserted[i]); const char *tests[] = {"apple", "banana", "cherry", "grape", "kiwi"}; for (int i = 0; i < 5; i++) { printf(" %-8s: %s\n", tests[i], bloomHas(&b, tests[i]) ? "maybe" : "no"); } } int main(void) { printf("=== Applications of Hashing ===\n"); demoPassword(); demoFileHash(); demoFrequency(); demoBloom(); printf("\nDone.\n"); return 0; }

Expected Output (sample run)

text

=== Applications of Hashing === === Password Storage === Stored hash: 0x... Attempt "MySecret123": SUCCESS Attempt "wrongpass": FAIL Attempt "MySecret124": FAIL === File Checksum === Hash of demo.txt: 0x... After modification: 0x... Files match: NO === Frequency Counting === 1 → 2 2 → 1 3 → 3 5 → 2 === Bloom Filter === apple : maybe banana : maybe cherry : maybe grape : no kiwi : no Done.

Common Pitfalls, Edge Cases & Memory Considerations

1. Using Weak Hashes for Security

FNV/MD5/SHA-1 are unsuitable for password storage.

Solution: Use bcrypt, scrypt, or Argon2 with unique salts.

2. Bloom Filter False Negatives

Bloom filters must use all hash functions consistently; missing bits cause false negatives.

Solution: Always set/check all hash outputs; never partial.

3. Hash Table Memory Leaks

Forgetting to free bucket lists or arrays causes leaks.

Solution: Walk each bucket and free nodes before freeing the table.

4. Collision Attacks

Adversarial inputs can trigger worst-case collisions in weak hashes.

Solution: Use randomized seeds (SipHash, murmur with seed).

5. Load Factor Overflow

Ignoring load factor degrades to O(n).

Solution: Rehash when load factor > 0.75.

6. Integer Overflow in Hash Functions

Large multiplications overflow 32-bit int.

Solution: Use uint64_t or unsigned int.

7. File Handle Leaks

Not closing files after hashing.

Solution: Always fclose in all paths.

8. Bloom Filter Sizing

Too small a filter yields many false positives.

Solution: Size based on expected n and desired false-positive rate.

9. Unsalted Passwords

Identical passwords produce identical hashes.

Solution: Always use unique per-user salts.

10. Memory Considerations

  • Hash tables: O(n) entries + bucket array.
  • Bloom filters: O(m) bits, independent of n.
  • Frequency arrays: O(max value) space.
  • Free all dynamic allocations.

Summary & Best Practices

Hashing is one of the most versatile techniques in computing. From securing passwords to routing traffic and deduplicating images, its O(1) average operations enable modern software at scale.

Key Takeaways

  • Hashing powers security, databases, networks, and specialized systems.
  • Password storage must use salted, adaptive hashes (bcrypt/Argon2).
  • Bloom filters trade a small error rate for massive memory savings.
  • Consistent hashing enables stable load balancing.
  • Rabin-Karp uses rolling hashes for fast substring search.
  • Symbol tables map identifiers to metadata during compilation.

Best Practices

  1. Never store plaintext passwords; use salted adaptive hashes.
  2. Use cryptographic hashes (SHA-256) for integrity, not FNV.
  3. Choose table sizes as primes for even distribution.
  4. Rehash when load factor exceeds 0.75.
  5. Free all hash table nodes on cleanup.
  6. Use uint64_t for hash arithmetic to avoid overflow.
  7. Size Bloom filters based on expected elements and target false-positive rate.
  8. Use randomized seeds to prevent collision attacks.
  9. Close file handles after reading.
  10. Profile for large datasets.

Hashing’s blend of speed, simplicity, and versatility makes it an essential tool for every systems programmer.

Learn quadratic probing in C hash tables: standard and modified probe sequences, full utilization formula, and implementation with insert/search/delete.
C Programming

Quadratic Probing in Hashing in C: Complete Guide

Quadratic Probing in Hashing in C: A Comprehensive Tutorial

Quadratic Probing is an Open Addressing collision resolution technique where, instead of probing linearly, we jump by quadratically increasing offsets. This reduces the primary clustering problem of linear probing, though it introduces a milder secondary clustering. It’s a widely used technique in high-performance hash tables.

This tutorial provides an in-depth exploration of Quadratic Probing in C: fundamental concepts, probe sequences, implementation, the modified formula for full table utilization, complexity analysis, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is Quadratic Probing?

Quadratic Probing is an open-addressing scheme where, on collision at index h(k), we probe slots at (h(k) + i²) % m for i = 0, 1, 2, ... until we find an empty or matching slot.

Probe sequence: (h(k) + 0²) % m, (h(k) + 1²) % m, (h(k) + 2²) % m, …

Why Quadratic Probing?

  • Reduces primary clustering: Unlike linear probing, keys hashing to nearby slots don’t always collide.
  • Better than linear probing: Distributes keys more uniformly in clustered regions.
  • No extra memory: All keys stored in the table itself.
  • Cache-friendly-ish: Jumps are still predictable but larger.

Probe Sequence Example

For hash function h(k) = k % 7 and keys [22, 30, 50]:

text

22 → 22 % 7 = 1 (place at index 1) 30 → 30 % 7 = 2 (place at index 2) 50 → 50 % 7 = 1 (collision!) Probe i=1: (1 + 1) % 7 = 2 (occupied) Probe i=2: (1 + 4) % 7 = 5 (empty → place at index 5)

Result: [_, 22, 30, _, _, 50, _]

Primary vs Secondary Clustering

ClusteringDescriptionAffects
PrimaryContiguous blocks of occupied slotsLinear probing
SecondaryKeys hashing to the same index follow identical probesQuadratic probing

Quadratic probing eliminates primary clustering but retains secondary clustering.

The Full-Utilization Problem

With a standard quadratic probe (h(k) + i²) % m, the sequence may not visit all slots, especially if m is not prime. This can cause failed insertions even when empty slots exist.

Example: Table size 11 with keys [21, 10, 32, 43, 54, 65, 87, 76] fails to insert 87 and 76 with standard formula.

The Modified Probe Formula

For guaranteed full utilization, use this probe formula with m' = nextPowerOf2(m):

text

probe(k, i) = (h(k) + (i + i²) / 2) % m'

This produces the triangular number sequence: 0, 1, 3, 6, 10, 15, … which visits every slot exactly once when m' is a power of 2.

Complexity Analysis

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

At load factor α < 0.5, quadratic probing performs nearly as well as double hashing.

Syntax & Core Mechanics

Standard Quadratic Probing

c

/* Standard quadratic probe */ int probe = (hashValue + i * i) % tableSize;

Modified Quadratic Probing (Full Utilization)

c

/* Modified formula with next power of 2 */ int probe = (hashValue + (i + i * i) / 2) % nextPowerOf2(tableSize); if (probe >= tableSize) continue; /* Skip out-of-bounds */

Compute Next Power of 2

c

int nextPowerOf2(int n) { n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; n++; return n; }

Insertion Algorithm

  1. Compute h = hash(key).
  2. If table[h] is EMPTY, insert.
  3. Else, probe i = 1, 2, ... with (h + i²) % m (or modified formula).
  4. Stop when EMPTY slot found or all slots probed.

Deletion

Same tombstone approach as linear probing: mark slot as DELETED.

Full Practical Code Example with Explanation

This program demonstrates both standard and modified quadratic probing with a complete hash table.

c

/** * quadratic_probing.c * Demonstrates quadratic probing in hash tables. * Supports standard and modified probe sequences. */ #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.5 /* Slot in the hash table */ typedef struct { int key; int value; } Slot; /* Hash table using quadratic probing */ typedef struct { Slot *slots; int capacity; int size; int deletedCount; int useModified; } HashTable; /* Next power of 2 >= n */ static int nextPowerOf2(int n) { if (n <= 1) return 1; n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; n++; return n; } /* Hash function */ static unsigned int hashIndex(int key, int capacity) { return ((unsigned int)key) % (unsigned int)capacity; } /* Compute probe index for step i */ static int probeIndex(int baseIdx, int i, int capacity, int useModified) { int result; if (useModified) { int m = nextPowerOf2(capacity); result = (int)((unsigned int)(baseIdx + (i + i * i) / 2) % (unsigned int)m); } else { result = (int)((unsigned int)(baseIdx + i * i) % (unsigned int)capacity); } return result; } /* Create hash table */ HashTable *createHashTable(int initialCapacity, int useModified) { HashTable *ht = malloc(sizeof(HashTable)); if (ht == NULL) return NULL; ht->slots = malloc(initialCapacity * sizeof(Slot)); if (ht->slots == NULL) { free(ht); return NULL; } for (int i = 0; i < initialCapacity; i++) { ht->slots[i].key = EMPTY; ht->slots[i].value = 0; } ht->capacity = initialCapacity; ht->size = 0; ht->deletedCount = 0; ht->useModified = useModified; return ht; } void freeHashTable(HashTable *ht) { if (ht == NULL) return; free(ht->slots); free(ht); } /* Rehash: double capacity and reinsert all live entries */ static int rehash(HashTable *ht) { int oldCap = ht->capacity; Slot *oldSlots = ht->slots; int newCap = oldCap * 2 + 1; Slot *newSlots = malloc(newCap * sizeof(Slot)); if (newSlots == NULL) return -1; for (int i = 0; i < newCap; i++) { newSlots[i].key = EMPTY; newSlots[i].value = 0; } ht->slots = newSlots; ht->capacity = newCap; ht->size = 0; ht->deletedCount = 0; for (int i = 0; i < oldCap; i++) { if (oldSlots[i].key != EMPTY && oldSlots[i].key != DELETED) { int key = oldSlots[i].key; int value = oldSlots[i].value; unsigned int base = hashIndex(key, newCap); for (int i2 = 0; i2 < newCap; i2++) { int pos = probeIndex((int)base, i2, newCap, ht->useModified); if (pos >= newCap) continue; if (newSlots[pos].key == EMPTY) { newSlots[pos].key = key; newSlots[pos].value = value; ht->size++; break; } } } } free(oldSlots); return 0; } /* Insert or update */ 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 base = hashIndex(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = probeIndex((int)base, i, ht->capacity, ht->useModified); if (ht->useModified && pos >= ht->capacity) continue; if (ht->slots[pos].key == key) { ht->slots[pos].value = value; 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; } /* Search */ int search(const HashTable *ht, int key, int *outValue) { unsigned int base = hashIndex(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = probeIndex((int)base, i, ht->capacity, ht->useModified); if (ht->useModified && pos >= ht->capacity) continue; if (ht->slots[pos].key == EMPTY) return 0; if (ht->slots[pos].key == key) { *outValue = ht->slots[pos].value; return 1; } } return 0; } /* Delete */ int deleteKey(HashTable *ht, int key) { unsigned int base = hashIndex(key, ht->capacity); for (int i = 0; i < ht->capacity; i++) { int pos = probeIndex((int)base, i, ht->capacity, ht->useModified); if (ht->useModified && pos >= ht->capacity) continue; if (ht->slots[pos].key == EMPTY) return -1; if (ht->slots[pos].key == key) { ht->slots[pos].key = DELETED; ht->deletedCount++; ht->size--; return 0; } } return -1; } /* Display */ void display(const HashTable *ht) { double lf = (double)ht->size / ht->capacity; printf("Hash Table (%s, size=%d, capacity=%d, deleted=%d, load=%.2f):\n", ht->useModified ? "modified" : "standard", 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 demoStandard(void) { printf("\n=== Standard Quadratic Probing ===\n"); HashTable *ht = createHashTable(11, 0); if (ht == NULL) return; int keys[] = {50, 700, 76, 85, 92, 73, 101}; int n = sizeof(keys) / sizeof(keys[0]); for (int i = 0; i < n; i++) { insert(ht, keys[i], keys[i]); } display(ht); printf("\nSlots: "); for (int i = 0; i < ht->capacity; i++) { printf("%d ", ht->slots[i].key); } printf("\n"); freeHashTable(ht); } static void demoModified(void) { printf("\n=== Modified Quadratic Probing (Full Utilization) ===\n"); HashTable *ht = createHashTable(11, 1); if (ht == NULL) return; int keys[] = {21, 10, 32, 43, 54, 65, 87, 76}; int n = sizeof(keys) / sizeof(keys[0]); for (int i = 0; i < n; i++) { insert(ht, keys[i], keys[i]); } display(ht); printf("\nSlots: "); for (int i = 0; i < ht->capacity; i++) { printf("%d ", ht->slots[i].key); } printf("\n"); freeHashTable(ht); } static void demoOperations(void) { printf("\n=== Standard Operations ===\n"); HashTable *ht = createHashTable(11, 0); if (ht == NULL) return; insert(ht, 22, 220); insert(ht, 30, 300); insert(ht, 50, 500); insert(ht, 12, 120); display(ht); int value; printf("\nSearch 30: "); if (search(ht, 30, &value)) printf("%d\n", value); else printf("not found\n"); printf("Delete 30...\n"); deleteKey(ht, 30); display(ht); printf("\nSearch 50 (after delete): "); if (search(ht, 50, &value)) printf("%d\n", value); else printf("not found\n"); freeHashTable(ht); } 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("=== Quadratic Probing in Hashing Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Standard Quadratic Probing\n"); printf("2. Modified Quadratic Probing (Full Utilization)\n"); printf("3. Operations Demo (Insert/Search/Delete)\n"); printf("4. Interactive Hash Table\n"); printf("5. 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) { demoStandard(); } else if (choice == 2) { demoModified(); } else if (choice == 3) { demoOperations(); } else if (choice == 4) { HashTable *ht = createHashTable(11, 0); 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 == 5) { printf("Exiting.\n"); return EXIT_SUCCESS; } else { printf("Invalid choice.\n"); } } return EXIT_SUCCESS; }

Explanation

  1. Slot — Stores key and value; sentinel keys mark EMPTY/DELETED.
  2. probeIndex — Computes probe index for standard or modified quadratic probing.
  3. nextPowerOf2 — Required by the modified formula for full utilization.
  4. insert / search / deleteKey — Probe iteratively using probeIndex.
  5. rehash — Doubles capacity when load factor exceeds 0.5.
  6. display — Prints each slot and its state.

Expected Output (sample run)

text

=== Standard Quadratic Probing === Hash Table (standard, size=7, capacity=11, deleted=0, load=0.64): [ 0]: (73 → 73) [ 1]: EMPTY [ 2]: (101 → 101) [ 3]: EMPTY [ 4]: (92 → 92) [ 5]: EMPTY [ 6]: (50 → 50) [ 7]: (700 → 700) [ 8]: (85 → 85) [ 9]: EMPTY [10]: (76 → 76) Slots: 73 -1 101 -1 92 -1 50 700 85 -1 76 === Modified Quadratic Probing (Full Utilization) === Hash Table (modified, size=8, capacity=11, deleted=0, load=0.73): [ 0]: (10 → 10) [ 1]: (87 → 87) [ 2]: EMPTY [ 3]: EMPTY [ 4]: (32 → 32) [ 5]: EMPTY [ 6]: (54 → 54) [ 7]: (65 → 65) [ 8]: (76 → 76) [ 9]: (43 → 43) [10]: (21 → 21) Slots: 10 87 -1 -1 32 -1 54 65 76 43 21

Common Pitfalls, Edge Cases & Memory Considerations

1. Probe Sequence Not Reaching All Slots

Standard quadratic probing may not visit every slot when m is not prime.

Solution: Use the modified formula with m' = nextPowerOf2(m).

2. Out-of-Bounds with Modified Formula

When m' > m, the computed index may exceed the table size.

c

if (pos >= ht->capacity) continue;

3. Infinite Probe Loop

Unbounded probing without finding an empty slot.

Solution: Bound the loop by capacity or nextPowerOf2(capacity).

4. Table Full (Even With Empty Slots)

Standard formula may fail to find an empty slot even when one exists.

Solution: Use the modified formula.

5. Tombstone Accumulation

Frequent deletes degrade performance.

Solution: Track deletedCount and trigger rehash when (size + deleted) / capacity > threshold.

6. Load Factor Too High

Quadratic probing degrades near α = 1.

Solution: Keep α < 0.5 and rehash proactively.

7. Secondary Clustering

Keys hashing to the same initial index follow identical probes.

Solution: Use double hashing for better distribution.

8. Rehash During Insert

Ensure rehash happens before computing the probe index.

9. Negative Keys

Cast to unsigned int before modulo.

10. Memory Considerations

  • Table memory: capacity × sizeof(Slot).
  • No pointer overhead.
  • Rehashing doubles memory temporarily.
  • Free slots array on cleanup.

Summary & Best Practices

Quadratic Probing reduces primary clustering compared to linear probing while remaining memory-efficient. For guaranteed full utilization, use the modified formula with a next power-of-2 table size.

Key Takeaways

  • Probe sequence: (h(k) + i²) % m (standard) or (h(k) + (i + i²)/2) % m' (modified).
  • Reduces primary clustering but retains secondary clustering.
  • Standard formula may fail; modified formula guarantees full utilization.
  • Keep load factor below 0.5.
  • Deletion requires tombstones.
  • Complexity: O(1) average; O(n) worst.

Best Practices

  1. Use the modified formula with nextPowerOf2 for guaranteed full utilization.
  2. Keep load factor < 0.5 for good performance.
  3. Bound probe loops by table size or power-of-2 size.
  4. Skip out-of-bounds indices in modified probing.
  5. Use tombstones for deletion.
  6. Rehash proactively when load factor exceeds threshold.
  7. Cast keys to unsigned before modulo.
  8. Consider double hashing for even better distribution.
  9. Free the slots array on cleanup.
  10. Test with high-collision keys to verify correctness.

By mastering quadratic probing, you’ll implement efficient in-place hash tables with better clustering behavior than linear probing.

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.

Learn hashing in C: hash functions, separate chaining, open addressing, insert/search/delete, and collision handling. Master O(1) average operations.
C Programming

Hashing in Data Structure: Complete Guide in C

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

PropertyDescription
DeterministicSame key always produces same hash
FastO(1) computation
UniformKeys distribute evenly across table
Minimizes collisionsGood hash functions reduce clashes

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

StrategyDescriptionSpace
Separate ChainingEach bucket holds a linked listO(n)
Open AddressingProbe for next empty slotO(m)
Linear ProbingTry (h(k) + i) % m
Quadratic ProbingTry (h(k) + i²) % m
Double HashingUse second hash for step

Complexity Comparison

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

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.

Learn array reversal in C: temporary array, two pointers, single pointer, and recursive approaches. Master in-place reversal with O(1) space.
C Programming

Array Reverse in C: Complete Guide with Examples

Array Reverse in C: A Comprehensive Tutorial

Reversing an array means rearranging its elements such that the first element becomes the last, the second becomes the second-last, and so on. Array reversal is a fundamental operation used in string manipulation, palindrome checking, and many algorithmic problems. This tutorial explores multiple approaches to reversing an array in C, with a focus on efficiency and correctness.

This tutorial provides an in-depth exploration of array reversal in C: temporary array approach, two-pointer technique, single-pointer method, practical applications, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is Array Reversal?

Array reversal is the process of inverting the order of elements in an array. For an array arr of size n, the reversed array has arr[n-1] at position 0, arr[n-2] at position 1, and so on.

Example:

text

Original: [1, 4, 3, 2, 6, 5] Reversed: [5, 6, 2, 3, 4, 1]

Why Reverse an Array?

  • String reversal: Reverse characters in a string.
  • Palindrome checking: Compare array with its reverse.
  • Algorithm foundation: Rotations, permutations, and data manipulation.
  • Display purposes: Show data in reverse chronological order.
  • Matrix operations: Row/column reversal.

Approaches Overview

ApproachTime ComplexitySpace Complexity
Temporary arrayO(n)O(n)
Two pointersO(n)O(1)
Single pointerO(n)O(1)
RecursiveO(n)O(n) stack

Syntax & Core Mechanics

Approach 1: Temporary Array (Naive)

Creates a temporary array to store the reversed elements.

c

#include <stdio.h> #include <stdlib.h> void reverseArrayTemp(int arr[], int n) { /* Allocate temporary array */ int *temp = malloc(n * sizeof(int)); if (temp == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } /* Copy elements in reverse order */ for (int i = 0; i < n; i++) { temp[i] = arr[n - i - 1]; } /* Copy back to original array */ for (int i = 0; i < n; i++) { arr[i] = temp[i]; } free(temp); } int main(void) { int arr[] = {1, 4, 3, 2, 6, 5}; int n = sizeof(arr) / sizeof(arr[0]); reverseArrayTemp(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

5 6 2 3 4 1

Time: O(n), Space: O(n)

Approach 2: Two Pointers (Efficient)

Uses two pointers moving towards the center, swapping elements in place.

c

#include <stdio.h> void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void reverseArrayTwoPointers(int arr[], int n) { int left = 0; int right = n - 1; while (left < right) { swap(&arr[left], &arr[right]); left++; right--; } } int main(void) { int arr[] = {1, 4, 3, 2, 6, 5}; int n = sizeof(arr) / sizeof(arr[0]); reverseArrayTwoPointers(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

5 6 2 3 4 1

Time: O(n), Space: O(1)

Approach 3: Single Pointer (In-Place)

Iterates over the first half and swaps with the corresponding element from the end.

c

#include <stdio.h> void reverseArraySinglePointer(int arr[], int n) { for (int i = 0; i < n / 2; i++) { int temp = arr[i]; arr[i] = arr[n - i - 1]; arr[n - i - 1] = temp; } } int main(void) { int arr[] = {1, 4, 3, 2, 6, 5}; int n = sizeof(arr) / sizeof(arr[0]); reverseArraySinglePointer(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

5 6 2 3 4 1

Time: O(n), Space: O(1)

Approach 4: Recursive

c

#include <stdio.h> void reverseRecursive(int arr[], int left, int right) { if (left >= right) { return; /* Base case */ } /* Swap */ int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; /* Recurse */ reverseRecursive(arr, left + 1, right - 1); } void reverseArray(int arr[], int n) { reverseRecursive(arr, 0, n - 1); } int main(void) { int arr[] = {1, 4, 3, 2, 6, 5}; int n = sizeof(arr) / sizeof(arr[0]); reverseArray(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

5 6 2 3 4 1

Time: O(n), Space: O(n) stack

Full Practical Code Example with Explanation

This program demonstrates all array reversal approaches with timing and verification.

Program: Array Reversal Comparison

c

/** * array_reverse.c * Demonstrates multiple approaches to reverse an array. * Includes performance comparison and edge case handling. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ void reverseTempArray(int arr[], int n); void reverseTwoPointers(int arr[], int n); void reverseSinglePointer(int arr[], int n); void reverseRecursive(int arr[], int left, int right); void reverseRecursiveWrapper(int arr[], int n); void printArray(const int arr[], int n); int readInteger(const char *prompt, int *outValue); int arraysEqual(const int a[], const int b[], int n); void copyArray(const int src[], int dst[], int n); void demonstrateApproaches(void); void performanceComparison(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Array Reversal Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. Custom Array Reversal\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: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n; int method; if (readInteger("Enter array size (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements:\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } printf("\nOriginal array: "); printArray(arr, n); printf("\nSelect reversal method:\n"); printf("1. Temporary Array\n"); printf("2. Two Pointers\n"); printf("3. Single Pointer\n"); printf("4. Recursive\n"); printf("Enter method: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) break; method = atoi(buffer); switch (method) { case 1: reverseTempArray(arr, n); break; case 2: reverseTwoPointers(arr, n); break; case 3: reverseSinglePointer(arr, n); break; case 4: reverseRecursiveWrapper(arr, n); break; default: printf("Invalid method.\n"); continue; } printf("Reversed array: "); printArray(arr, n); break; } case 3: performanceComparison(); break; case 4: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Approach 1: Temporary array */ void reverseTempArray(int arr[], int n) { if (n <= 1) return; int *temp = malloc(n * sizeof(int)); if (temp == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } for (int i = 0; i < n; i++) { temp[i] = arr[n - i - 1]; } for (int i = 0; i < n; i++) { arr[i] = temp[i]; } free(temp); } /* Approach 2: Two pointers */ void reverseTwoPointers(int arr[], int n) { int left = 0; int right = n - 1; while (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } /* Approach 3: Single pointer */ void reverseSinglePointer(int arr[], int n) { for (int i = 0; i < n / 2; i++) { int temp = arr[i]; arr[i] = arr[n - i - 1]; arr[n - i - 1] = temp; } } /* Approach 4: Recursive */ void reverseRecursive(int arr[], int left, int right) { if (left >= right) return; int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; reverseRecursive(arr, left + 1, right - 1); } void reverseRecursiveWrapper(int arr[], int n) { if (n <= 1) return; reverseRecursive(arr, 0, n - 1); } /* Prints array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Compares two arrays */ int arraysEqual(const int a[], const int b[], int n) { for (int i = 0; i < n; i++) { if (a[i] != b[i]) return 0; } return 1; } /* Copies an array */ void copyArray(const int src[], int dst[], int n) { memcpy(dst, src, n * sizeof(int)); } /* Demonstrates all approaches with verification */ void demonstrateApproaches(void) { printf("\n=== All Reversal Approaches ===\n"); int original[] = {1, 4, 3, 2, 6, 5}; int n = sizeof(original) / sizeof(original[0]); int expected[] = {5, 6, 2, 3, 4, 1}; int arr[MAX_SIZE]; printf("Original: "); printArray(original, n); /* Method 1: Temporary array */ copyArray(original, arr, n); reverseTempArray(arr, n); printf("Temp Array: "); printArray(arr, n); printf(" Verification: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); /* Method 2: Two pointers */ copyArray(original, arr, n); reverseTwoPointers(arr, n); printf("Two Pointers: "); printArray(arr, n); printf(" Verification: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); /* Method 3: Single pointer */ copyArray(original, arr, n); reverseSinglePointer(arr, n); printf("Single Pointer:"); printArray(arr, n); printf(" Verification: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); /* Method 4: Recursive */ copyArray(original, arr, n); reverseRecursiveWrapper(arr, n); printf("Recursive: "); printArray(arr, n); printf(" Verification: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison ===\n"); int size = 100000; int *original = malloc(size * sizeof(int)); int *arr = malloc(size * sizeof(int)); if (original == NULL || arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); free(original); free(arr); return; } /* Initialize with random-ish data */ for (int i = 0; i < size; i++) { original[i] = i * 7 % 1000; } clock_t start, end; double timeTaken; /* Method 1: Temporary array */ copyArray(original, arr, size); start = clock(); reverseTempArray(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Temporary Array: %.3f ms\n", timeTaken); /* Method 2: Two pointers */ copyArray(original, arr, size); start = clock(); reverseTwoPointers(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Two Pointers: %.3f ms\n", timeTaken); /* Method 3: Single pointer */ copyArray(original, arr, size); start = clock(); reverseSinglePointer(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Single Pointer: %.3f ms\n", timeTaken); /* Method 4: Recursive */ copyArray(original, arr, size); start = clock(); reverseRecursiveWrapper(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Recursive: %.3f ms\n", timeTaken); free(original); free(arr); } /* Reads an integer safely */ 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; }

Explanation of Approaches

  1. Temporary Array: Simple but uses O(n) extra space.
  2. Two Pointers: In-place, O(1) space, most intuitive.
  3. Single Pointer: In-place, O(1) space, concise.
  4. Recursive: Elegant but uses O(n) stack space.

Expected Output (sample run)

text

=== Array Reversal Demo === --- Menu --- 1. Demonstrate All Approaches 2. Custom Array Reversal 3. Performance Comparison 4. Exit Enter choice: 1 === All Reversal Approaches === Original: [1, 4, 3, 2, 6, 5] Temp Array: [5, 6, 2, 3, 4, 1] Verification: PASS Two Pointers: [5, 6, 2, 3, 4, 1] Verification: PASS Single Pointer:[5, 6, 2, 3, 4, 1] Verification: PASS Recursive: [5, 6, 2, 3, 4, 1] Verification: PASS --- Menu --- ... Enter choice: 3 === Performance Comparison === Temporary Array: 0.412 ms Two Pointers: 0.285 ms Single Pointer: 0.278 ms Recursive: 0.521 ms

Common Pitfalls, Edge Cases & Memory Considerations

1. Off-by-One Errors

Incorrect loop bounds cause missed or double swaps.

c

for (int i = 0; i <= n / 2; i++) { // BUG: swaps middle element twice for odd n /* ... */ }

Solution: Use i < n / 2.

2. Integer Division for Odd Lengths

For odd-length arrays, the middle element stays in place.

c

/* n = 5: i goes 0, 1 (swaps pairs) */ /* Middle element at index 2 remains */

Solution: This is correct behavior; no special handling needed.

3. Empty Array

Reversing an empty array should do nothing.

c

int arr[] = {}; reverseArray(arr, 0); // No-op

Solution: Add if (n <= 1) return; at the start.

4. Single Element

A single-element array is already reversed.

c

int arr[] = {5}; reverseArray(arr, 1); // No change

5. Memory Leaks with Temporary Array

Forgetting to free the temporary array.

c

int *temp = malloc(n * sizeof(int)); /* ... */ /* Missing free(temp); */

Solution: Always free dynamically allocated memory.

6. Stack Overflow with Recursion

Deep recursion for large arrays causes stack overflow.

c

reverseRecursive(arr, 0, 999999); // Stack overflow

Solution: Use iterative approach for large arrays.

7. Const Arrays

Attempting to reverse a const array is a compile error.

c

void reverse(const int arr[], int n) { arr[0] = arr[n-1]; // Error: read-only }

Solution: Remove const if modification is intended.

8. Null Pointer

Passing NULL to reversal function crashes.

c

reverseArray(NULL, 5); // BUG

Solution: Check for NULL before processing.

9. Large Arrays on Stack

Large automatic arrays can overflow the stack.

c

void func(void) { int bigArray[1000000]; reverseArray(bigArray, 1000000); }

Solution: Use static or malloc for large arrays.

10. Memory Considerations

  • Temporary array approach uses O(n) extra space.
  • Two-pointer and single-pointer approaches use O(1) space.
  • Recursive uses O(n) stack space.
  • For large arrays, prefer in-place approaches.

Summary & Best Practices

Array reversal is a fundamental operation with multiple implementation approaches. The two-pointer and single-pointer methods are preferred for their O(1) space complexity.

Key Takeaways

  • Reversing an array swaps elements symmetrically.
  • Temporary array: O(n) time, O(n) space.
  • Two pointers: O(n) time, O(1) space.
  • Single pointer: O(n) time, O(1) space.
  • Recursive: O(n) time, O(n) stack space.
  • Middle element of odd-length array stays in place.

Best Practices

  1. Use the two-pointer or single-pointer approach for in-place reversal.
  2. Use the temporary array approach only when the original must be preserved.
  3. Handle empty and single-element arrays gracefully.
  4. Avoid recursion for large arrays to prevent stack overflow.
  5. Free dynamically allocated memory for temporary arrays.
  6. Validate input pointers before processing.
  7. Use size_t for array sizes.
  8. Test with odd and even lengths.
  9. Consider cache performance for very large arrays.
  10. Document whether the reversal is in-place.

By mastering array reversal, you’ll have a fundamental tool for string manipulation, algorithm design, and data processing.

Learn to generate all subarrays in C using iterative and recursive approaches. Master subarray algorithms with practical examples and memory management.
C Programming

Generating All Subarrays in C: Complete Guide

Generating All Subarrays in C: A Comprehensive Tutorial

Generating all subarrays of an array is a fundamental algorithmic problem that appears frequently in coding interviews and competitive programming. A subarray is a contiguous sequence of elements within an array. Understanding how to generate all subarrays efficiently is essential for solving problems involving ranges, sliding windows, and dynamic programming.

This tutorial provides an in-depth exploration of generating all subarrays in C: problem understanding, iterative and recursive approaches, practical implementation, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is a Subarray?

A subarray is a contiguous portion of an array. For an array of size n, there are n × (n + 1) / 2 possible subarrays.

Example:

text

Array: [1, 2, 3] Subarrays: [1], [1, 2], [1, 2, 3] [2], [2, 3] [3] Total: 3 × 4 / 2 = 6 subarrays

Subarray vs. Subsequence vs. Subset

ConceptDefinitionOrder Preserved?Contiguous?
SubarrayContiguous portionYesYes
SubsequenceNot necessarily contiguousYesNo
SubsetAny selectionNoNo

Why Generate All Subarrays?

  • Maximum subarray sum: Kadane’s algorithm foundation.
  • Sliding window problems: Subarray-based optimizations.
  • Range queries: Prefix sums and segment trees.
  • Interview preparation: Common coding problem.
  • Data analysis: Contiguous segment processing.

Number of Subarrays

For an array of size n:

  • Number of subarrays = n × (n + 1) / 2
  • For n = 3: 6 subarrays
  • For n = 4: 10 subarrays
  • For n = 5: 15 subarrays

Syntax & Core Mechanics

Approach 1: Iterative (Triple Nested Loops)

The most straightforward approach: fix starting index i, ending index j, and print elements from i to j.

Time complexity: O(n³)
Space complexity: O(1) for printing, O(n) for storing

c

#include <stdio.h> void printAllSubarrays(const int arr[], int n) { /* Fix starting index */ for (int i = 0; i < n; i++) { /* Fix ending index */ for (int j = i; j < n; j++) { /* Print subarray from i to j */ printf("["); for (int k = i; k <= j; k++) { printf("%d", arr[k]); if (k < j) printf(", "); } printf("]"); if (!(i == n - 1 && j == n - 1)) printf(", "); } } printf("\n"); } int main(void) { int arr[] = {1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("All subarrays:\n"); printAllSubarrays(arr, n); return 0; }

Expected output:

text

All subarrays: [1], [1, 2], [1, 2, 3], [2], [2, 3], [3]

Approach 2: Iterative (Optimized — Two Loops)

Instead of a third loop, extend the subarray incrementally.

Time complexity: O(n²)
Space complexity: O(1)

c

#include <stdio.h> void printAllSubarraysOptimized(const int arr[], int n) { for (int i = 0; i < n; i++) { printf("["); for (int j = i; j < n; j++) { printf("%d", arr[j]); if (j < n - 1) printf(", "); /* Print current subarray */ printf("]"); if (j < n - 1 || i < n - 1) printf(", "); if (j < n - 1) printf("["); } } printf("\n"); } int main(void) { int arr[] = {1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("All subarrays (optimized):\n"); printAllSubarraysOptimized(arr, n); return 0; }

Better implementation:

c

#include <stdio.h> void printAllSubarraysTwoLoops(const int arr[], int n) { int first = 1; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (!first) printf(", "); first = 0; printf("["); for (int k = i; k <= j; k++) { printf("%d", arr[k]); if (k < j) printf(", "); } printf("]"); } } printf("\n"); } int main(void) { int arr[] = {1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printAllSubarraysTwoLoops(arr, n); return 0; }

Expected output:

text

[1], [1, 2], [1, 2, 3], [2], [2, 3], [3]

Approach 3: Recursive

Use recursion to generate subarrays starting from each index.

c

#include <stdio.h> /* Recursively extend subarray from start to end */ void generateFromStart(const int arr[], int n, int start, int end, int current[], int currentSize, int *first) { if (end == n) return; /* Add current element to subarray */ current[currentSize] = arr[end]; /* Print current subarray */ if (!*first) printf(", "); *first = 0; printf("["); for (int i = 0; i <= currentSize; i++) { printf("%d", current[i]); if (i < currentSize) printf(", "); } printf("]"); /* Recursively extend */ generateFromStart(arr, n, start, end + 1, current, currentSize + 1, first); } /* Generate subarrays for each starting index */ void generateAll(const int arr[], int n, int start, int *first) { if (start == n) return; int current[100]; /* Buffer for current subarray */ generateFromStart(arr, n, start, start, current, 0, first); generateAll(arr, n, start + 1, first); } int main(void) { int arr[] = {1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); int first = 1; printf("All subarrays (recursive):\n"); generateAll(arr, n, 0, &first); printf("\n"); return 0; }

Expected output:

text

All subarrays (recursive): [1], [1, 2], [1, 2, 3], [2], [2, 3], [3]

Full Practical Code Example with Explanation

This program demonstrates all subarray generation approaches with a complete implementation using dynamic memory for storing subarrays.

Program: Subarray Generator and Analyzer

c

/** * subarray_generator.c * Generates all subarrays using iterative and recursive approaches. * Includes storage, display, and analysis of subarrays. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #define MAX_LINE_LEN 100 #define MAX_SUBARRAYS 1000 /* Structure to hold a subarray */ typedef struct { int *elements; int size; int startIndex; int endIndex; int sum; } Subarray; /* Structure to hold all subarrays */ typedef struct { Subarray *items; int count; int capacity; } SubarrayCollection; /* Function prototypes */ SubarrayCollection *createCollection(int capacity); void freeCollection(SubarrayCollection *collection); int addSubarray(SubarrayCollection *collection, const int arr[], int start, int end); void generateIterative(const int arr[], int n, SubarrayCollection *collection); void generateRecursiveHelper(const int arr[], int n, int start, int end, SubarrayCollection *collection); void generateRecursive(const int arr[], int n, SubarrayCollection *collection); void displaySubarrays(const SubarrayCollection *collection); void analyzeSubarrays(const SubarrayCollection *collection); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void displaySubarray(const Subarray *sub); int main(void) { int choice; char buffer[MAX_LINE_LEN]; int arr[MAX_LINE_LEN]; int n = 0; printf("=== Subarray Generator and Analyzer ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Enter Array\n"); printf("2. Generate All Subarrays (Iterative)\n"); printf("3. Generate All Subarrays (Recursive)\n"); printf("4. Analyze Subarrays\n"); printf("5. 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: { int size; if (readInteger("Enter array size (1-20): ", &size) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (size < 1 || size > 20) { printf("Size must be 1-20.\n"); break; } printf("Enter %d elements:\n", size); for (int i = 0; i < size; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); size = i; break; } } n = size; printf("Array: "); printArray(arr, n); break; } case 2: { if (n == 0) { printf("Please enter an array first.\n"); break; } int maxSubarrays = n * (n + 1) / 2 + 1; SubarrayCollection *collection = createCollection(maxSubarrays); if (collection == NULL) { fprintf(stderr, "Memory allocation failed.\n"); break; } generateIterative(arr, n, collection); printf("\n=== All Subarrays (Iterative) ===\n"); displaySubarrays(collection); freeCollection(collection); break; } case 3: { if (n == 0) { printf("Please enter an array first.\n"); break; } int maxSubarrays = n * (n + 1) / 2 + 1; SubarrayCollection *collection = createCollection(maxSubarrays); if (collection == NULL) { fprintf(stderr, "Memory allocation failed.\n"); break; } generateRecursive(arr, n, collection); printf("\n=== All Subarrays (Recursive) ===\n"); displaySubarrays(collection); freeCollection(collection); break; } case 4: { if (n == 0) { printf("Please enter an array first.\n"); break; } int maxSubarrays = n * (n + 1) / 2 + 1; SubarrayCollection *collection = createCollection(maxSubarrays); if (collection == NULL) { fprintf(stderr, "Memory allocation failed.\n"); break; } generateIterative(arr, n, collection); analyzeSubarrays(collection); freeCollection(collection); break; } case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Creates a collection with initial capacity */ SubarrayCollection *createCollection(int capacity) { SubarrayCollection *collection = malloc(sizeof(SubarrayCollection)); if (collection == NULL) return NULL; collection->items = malloc(capacity * sizeof(Subarray)); if (collection->items == NULL) { free(collection); return NULL; } collection->count = 0; collection->capacity = capacity; return collection; } /* Frees the collection */ void freeCollection(SubarrayCollection *collection) { if (collection == NULL) return; for (int i = 0; i < collection->count; i++) { free(collection->items[i].elements); } free(collection->items); free(collection); } /* Adds a subarray to the collection */ int addSubarray(SubarrayCollection *collection, const int arr[], int start, int end) { if (collection->count >= collection->capacity) { return -1; /* Collection full */ } int size = end - start + 1; Subarray *sub = &collection->items[collection->count]; sub->elements = malloc(size * sizeof(int)); if (sub->elements == NULL) { return -1; } sub->size = size; sub->startIndex = start; sub->endIndex = end; sub->sum = 0; for (int i = 0; i < size; i++) { sub->elements[i] = arr[start + i]; sub->sum += sub->elements[i]; } collection->count++; return 0; } /* Generates all subarrays iteratively */ void generateIterative(const int arr[], int n, SubarrayCollection *collection) { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { addSubarray(collection, arr, i, j); } } } /* Recursive helper to generate subarrays from a fixed start */ void generateRecursiveHelper(const int arr[], int n, int start, int end, SubarrayCollection *collection) { if (end >= n) return; addSubarray(collection, arr, start, end); generateRecursiveHelper(arr, n, start, end + 1, collection); } /* Generates all subarrays recursively */ void generateRecursive(const int arr[], int n, SubarrayCollection *collection) { if (n == 0) return; for (int start = 0; start < n; start++) { generateRecursiveHelper(arr, n, start, start, collection); } } /* Displays all subarrays */ void displaySubarrays(const SubarrayCollection *collection) { for (int i = 0; i < collection->count; i++) { displaySubarray(&collection->items[i]); if (i < collection->count - 1) printf(", "); } printf("\n\nTotal: %d subarrays\n", collection->count); } /* Displays a single subarray */ void displaySubarray(const Subarray *sub) { printf("["); for (int i = 0; i < sub->size; i++) { printf("%d", sub->elements[i]); if (i < sub->size - 1) printf(", "); } printf("]"); } /* Analyzes subarrays (min/max sum, etc.) */ void analyzeSubarrays(const SubarrayCollection *collection) { if (collection->count == 0) { printf("No subarrays to analyze.\n"); return; } int maxSum = collection->items[0].sum; int minSum = collection->items[0].sum; int maxSumIndex = 0; int minSumIndex = 0; for (int i = 1; i < collection->count; i++) { if (collection->items[i].sum > maxSum) { maxSum = collection->items[i].sum; maxSumIndex = i; } if (collection->items[i].sum < minSum) { minSum = collection->items[i].sum; minSumIndex = i; } } printf("\n=== Subarray Analysis ===\n"); printf("Total subarrays: %d\n", collection->count); printf("\nMaximum sum subarray: "); displaySubarray(&collection->items[maxSumIndex]); printf(" (sum = %d)\n", maxSum); printf("Minimum sum subarray: "); displaySubarray(&collection->items[minSumIndex]); printf(" (sum = %d)\n", minSum); } /* Prints an array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Reads an integer safely */ 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; }

Explanation of Subarray Generation

  1. Iterative: Triple nested loops (or two loops with incremental printing).
  2. Recursive: Recursion extends subarray from each start index.
  3. Storage: Subarray and SubarrayCollection structures store subarrays.
  4. Analysis: Finds max/min sum subarrays.
  5. Memory management: Frees all allocated memory.

Expected Output (sample run)

text

=== Subarray Generator and Analyzer === --- Menu --- 1. Enter Array 2. Generate All Subarrays (Iterative) 3. Generate All Subarrays (Recursive) 4. Analyze Subarrays 5. Exit Enter choice: 1 Enter array size (1-20): 3 Enter 3 elements: Element 0: 1 Element 1: 2 Element 2: 3 Array: [1, 2, 3] --- Menu --- ... Enter choice: 2 === All Subarrays (Iterative) === [1], [1, 2], [1, 2, 3], [2], [2, 3], [3] Total: 6 subarrays --- Menu --- ... Enter choice: 4 === Subarray Analysis === Total subarrays: 6 Maximum sum subarray: [1, 2, 3] (sum = 6) Minimum sum subarray: [1] (sum = 1)

Common Pitfalls, Edge Cases & Memory Considerations

1. Empty Array

An empty array has no subarrays.

c

int arr[] = {}; printAllSubarrays(arr, 0); // No output

Solution: Handle n == 0 separately.

2. Single Element

An array with one element has exactly one subarray.

c

int arr[] = {5}; // Subarrays: [5]

3. Duplicate Elements

Duplicate values produce distinct subarrays (by position).

c

int arr[] = {1, 1}; // Subarrays: [1], [1, 1], [1] (3 subarrays, all distinct by position)

4. Large Arrays

Number of subarrays grows as O(n²). For n = 1000, there are 500,500 subarrays.

c

int arr[1000]; /* 500,500 subarrays - may exhaust memory if stored */

Solution: Print subarrays incrementally instead of storing all.

5. Memory Leaks

Storing subarrays with malloc requires freeing each one.

c

for (int i = 0; i < count; i++) { free(collection->items[i].elements); } free(collection->items); free(collection);

Solution: Always free dynamically allocated memory.

6. Buffer Overflow

Using fixed-size buffers for subarrays may overflow for large arrays.

c

int current[100]; // BUG if n > 100

Solution: Allocate dynamically or use larger buffers.

7. Off-by-One Errors

Incorrect loop bounds produce missing or extra subarrays.

c

for (int j = i; j < n; j++) // Correct: j < n for (int j = i; j <= n; j++) // BUG: j <= n accesses out of bounds

Solution: Use j < n for inclusive ending index.

8. Integer Overflow in Sum

Summing large subarrays may overflow.

c

int sum = 0; for (int i = start; i <= end; i++) { sum += arr[i]; // May overflow for large values }

Solution: Use long long for sum calculations.

9. Recursion Depth

Recursive generation may cause stack overflow for large arrays.

Solution: Use iterative approach for large arrays.

10. Memory Considerations

  • Number of subarrays = n × (n + 1) / 2.
  • Each subarray of average length n/3 uses O(n) memory.
  • Total memory for storing all subarrays: O(n³).
  • For large n, print subarrays instead of storing.

Summary & Best Practices

Generating all subarrays is a fundamental operation with applications in algorithm design, data analysis, and interview preparation. Iterative approaches are simple; recursive approaches are elegant but less efficient.

Key Takeaways

  • Subarrays are contiguous portions of an array.
  • Number of subarrays = n × (n + 1) / 2.
  • Iterative approach: O(n³) or O(n²) time.
  • Recursive approach: O(n³) time, O(n) stack space.
  • Subarrays must be distinct by position, not value.
  • Store only when needed; print incrementally for large arrays.

Best Practices

  1. Use iterative approach for simplicity and efficiency.
  2. Use recursion only for educational purposes or specific requirements.
  3. Avoid storing all subarrays for large arrays (memory).
  4. Free dynamically allocated memory for subarrays.
  5. Handle empty arrays and single-element arrays.
  6. Use long long for sum calculations to prevent overflow.
  7. Use size_t for array sizes.
  8. Print incrementally for large arrays.
  9. Validate array size before generation.
  10. Test with edge cases: empty, single element, duplicates, negatives.

By mastering subarray generation, you’ll build a foundation for solving more complex array and range-based problems.

Learn array applications, advantages, and disadvantages. Master when to use arrays with practical C examples and best practices.
C Programming

Applications, Advantages and Disadvantages of Array

Applications, Advantages and Disadvantages of Array: A Comprehensive Tutorial

An array is a linear data structure that is a collection of data elements of the same type. Arrays are stored in contiguous memory locations and are static data structures with a fixed size. Understanding the applications, advantages, and disadvantages of arrays is essential for choosing the right data structure for specific problems.

This tutorial provides an in-depth exploration of arrays: their applications, advantages, disadvantages, practical implementations in C, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is an Array?

An array is a collection of elements of the same data type stored in contiguous memory locations. It provides:

  • Random access: O(1) time to access any element.
  • Cache friendliness: Locality of reference for faster processing.
  • Fixed size: Size determined at creation (static data structure).

Why Understanding Array Properties Matters

  • Algorithm selection: Choose arrays when random access is needed.
  • Performance optimization: Leverage cache efficiency.
  • Memory management: Understand fixed-size limitations.
  • Data structure design: Arrays as building blocks for other structures.

Applications of Arrays

1. Storing and Accessing Data

Arrays store elements in order with O(1) access.

c

#include <stdio.h> int main(void) { int scores[5] = {85, 92, 78, 95, 88}; /* O(1) random access */ printf("First score: %d\n", scores[0]); printf("Third score: %d\n", scores[2]); return 0; }

2. Searching (Sorted Arrays)

Binary search on sorted arrays: O(log n).

c

#include <stdio.h> int binarySearch(int arr[], int n, int target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } int main(void) { int arr[] = {1, 3, 5, 7, 9, 11, 13}; int n = sizeof(arr) / sizeof(arr[0]); int target = 7; int result = binarySearch(arr, n, target); printf("Found %d at index %d (O(log n))\n", target, result); return 0; }

3. Matrices

Two-dimensional arrays for matrices.

c

#include <stdio.h> #define ROWS 3 #define COLS 3 void multiplyMatrices(int a[][COLS], int b[][COLS], int result[][COLS]) { for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { result[i][j] = 0; for (int k = 0; k < COLS; k++) { result[i][j] += a[i][k] * b[k][j]; } } } } int main(void) { int a[ROWS][COLS] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; int b[ROWS][COLS] = {{9, 8, 7}, {6, 5, 4}, {3, 2, 1}}; int result[ROWS][COLS] = {{0}}; multiplyMatrices(a, b, result); printf("Matrix multiplication result:\n"); for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { printf("%d ", result[i][j]); } printf("\n"); } return 0; }

4. Implementing Other Data Structures

Arrays as underlying storage for stacks.

c

#include <stdio.h> #define MAX_STACK 100 typedef struct { int data[MAX_STACK]; int top; } Stack; void initStack(Stack *s) { s->top = -1; } int push(Stack *s, int value) { if (s->top >= MAX_STACK - 1) return -1; s->data[++s->top] = value; return 0; } int pop(Stack *s, int *value) { if (s->top < 0) return -1; *value = s->data[s->top--]; return 0; } int main(void) { Stack stack; initStack(&stack); push(&stack, 10); push(&stack, 20); push(&stack, 30); int value; while (pop(&stack, &value) == 0) { printf("%d ", value); } printf("\n"); return 0; }

5. Dynamic Programming

Arrays store intermediate results.

c

#include <stdio.h> /* Fibonacci using DP array: O(n) time, O(n) space */ int fibonacciDP(int n) { if (n <= 1) return n; int dp[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } int main(void) { int n = 10; printf("Fibonacci(%d) = %d\n", n, fibonacciDP(n)); return 0; }

Advantages of Arrays

1. Efficient and Fast Access

O(1) constant-time access to any element.

c

#include <stdio.h> #include <time.h> int main(void) { int arr[1000000] = {0}; clock_t start = clock(); /* O(1) access */ int value = arr[500000]; clock_t end = clock(); printf("Access time: %.6f seconds\n", ((double)(end - start)) / CLOCKS_PER_SEC); printf("O(1) constant time access\n"); return 0; }

2. Memory Efficiency

Contiguous memory allocation, no extra linking storage.

c

#include <stdio.h> int main(void) { int arr[10]; printf("Size of array: %zu bytes\n", sizeof(arr)); printf("Size of one element: %zu bytes\n", sizeof(arr[0])); printf("No extra memory for linking pointers.\n"); return 0; }

3. Versatility

Store various data types.

c

#include <stdio.h> int main(void) { int intArr[] = {1, 2, 3}; float floatArr[] = {1.5f, 2.5f, 3.5f}; char charArr[] = {'A', 'B', 'C'}; printf("Integer array: %d %d %d\n", intArr[0], intArr[1], intArr[2]); printf("Float array: %.1f %.1f %.1f\n", floatArr[0], floatArr[1], floatArr[2]); printf("Char array: %c %c %c\n", charArr[0], charArr[1], charArr[2]); return 0; }

4. Hardware Compatibility

Arrays work well with hardware architectures.

Disadvantages of Arrays

1. Fixed Size

Arrays have a fixed size at creation.

c

#include <stdio.h> #include <stdlib.h> int main(void) { int arr[5] = {1, 2, 3, 4, 5}; printf("Array has fixed size 5.\n"); printf("Cannot add a 6th element without creating new array.\n"); /* Would require copying to a larger array */ int newArr[6]; for (int i = 0; i < 5; i++) { newArr[i] = arr[i]; } newArr[5] = 6; printf("New array: "); for (int i = 0; i < 6; i++) printf("%d ", newArr[i]); printf("\n"); return 0; }

2. Memory Allocation Issues

Large arrays can exhaust memory.

c

#include <stdio.h> #include <stdlib.h> int main(void) { /* Attempting very large allocation */ size_t hugeSize = (size_t)-1; // Very large int *arr = malloc(hugeSize); if (arr == NULL) { printf("Memory allocation failed for huge array.\n"); } else { printf("Allocated successfully.\n"); free(arr); } return 0; }

3. Insertion and Deletion Challenges

Shifting elements is inefficient.

c

#include <stdio.h> void insertAtPosition(int arr[], int *n, int position, int value, int capacity) { if (*n >= capacity) { printf("Array full.\n"); return; } /* Shift elements right */ for (int i = *n; i > position; i--) { arr[i] = arr[i - 1]; } arr[position] = value; (*n)++; } int main(void) { int arr[10] = {1, 2, 3, 4, 5}; int n = 5; printf("Before insertion: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); insertAtPosition(arr, &n, 2, 99, 10); printf("After insertion at position 2: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); printf("Insertion required shifting elements: O(n)\n"); return 0; }

Full Practical Code Example with Explanation

This program demonstrates array applications, advantages, and disadvantages with a comprehensive example.

Program: Array Applications Analyzer

c

/** * array_applications.c * Demonstrates array applications, advantages, and disadvantages. * Includes random access, binary search, matrix operations, and more. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #include <errno.h> #define MAX_LINE_LEN 100 /* Function prototypes */ void demonstrateRandomAccess(void); void demonstrateBinarySearch(void); void demonstrateMatrixOperation(void); void demonstrateStackUsingArray(void); void demonstrateDynamicProgramming(void); void demonstrateAdvantages(void); void demonstrateDisadvantages(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Array Applications and Properties ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Random Access (O(1))\n"); printf("2. Binary Search on Sorted Array\n"); printf("3. Matrix Operation\n"); printf("4. Stack Implementation Using Array\n"); printf("5. Dynamic Programming (Fibonacci)\n"); printf("6. Advantages Demonstration\n"); printf("7. Disadvantages Demonstration\n"); printf("8. 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: demonstrateRandomAccess(); break; case 2: demonstrateBinarySearch(); break; case 3: demonstrateMatrixOperation(); break; case 4: demonstrateStackUsingArray(); break; case 5: demonstrateDynamicProgramming(); break; case 6: demonstrateAdvantages(); break; case 7: demonstrateDisadvantages(); break; case 8: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Demonstrates O(1) random access */ void demonstrateRandomAccess(void) { printf("\n=== Random Access O(1) ===\n"); int arr[1000000] = {0}; clock_t start = clock(); int value = arr[999999]; // O(1) clock_t end = clock(); printf("Access time: %.9f seconds\n", ((double)(end - start)) / CLOCKS_PER_SEC); printf("Random access: O(1) constant time.\n"); } /* Demonstrates binary search */ void demonstrateBinarySearch(void) { printf("\n=== Binary Search O(log n) ===\n"); int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; int n = sizeof(arr) / sizeof(arr[0]); int target = 13; int left = 0, right = n - 1; int found = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { found = mid; break; } if (arr[mid] < target) left = mid + 1; else right = mid - 1; } printf("Found %d at index %d\n", target, found); printf("Requires sorted array for O(log n) search.\n"); } /* Demonstrates matrix multiplication */ void demonstrateMatrixOperation(void) { printf("\n=== Matrix Operation ===\n"); int a[2][3] = {{1, 2, 3}, {4, 5, 6}}; int b[3][2] = {{7, 8}, {9, 10}, {11, 12}}; int result[2][2] = {{0}}; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 3; k++) { result[i][j] += a[i][k] * b[k][j]; } } } printf("Matrix multiplication result:\n"); for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { printf("%d ", result[i][j]); } printf("\n"); } } /* Demonstrates stack using array */ void demonstrateStackUsingArray(void) { printf("\n=== Stack Using Array ===\n"); int stack[10]; int top = -1; /* Push */ stack[++top] = 10; stack[++top] = 20; stack[++top] = 30; printf("Stack elements (LIFO): "); while (top >= 0) { printf("%d ", stack[top--]); } printf("\n"); } /* Demonstrates dynamic programming */ void demonstrateDynamicProgramming(void) { printf("\n=== Dynamic Programming ===\n"); int n = 15; int dp[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } printf("Fibonacci sequence up to %d:\n", n); for (int i = 0; i <= n; i++) { printf("%d ", dp[i]); } printf("\n"); printf("Uses array for intermediate results.\n"); } /* Demonstrates advantages */ void demonstrateAdvantages(void) { printf("\n=== Advantages ===\n"); int arr[10]; printf("1. Fast access: arr[i] is O(1)\n"); printf("2. Memory efficient: %zu bytes for 10 integers\n", sizeof(arr)); printf("3. Versatile: can store int, float, char, pointers\n"); printf("4. Hardware compatible\n"); /* Demonstrate contiguity */ printf("\nAddresses (contiguous memory):\n"); for (int i = 0; i < 5; i++) { printf("arr[%d]: %p\n", i, (void*)&arr[i]); } } /* Demonstrates disadvantages */ void demonstrateDisadvantages(void) { printf("\n=== Disadvantages ===\n"); int arr[5] = {1, 2, 3, 4, 5}; printf("1. Fixed size: cannot add 6th element without new array\n"); /* Insert at middle requires shifting */ printf("\n2. Insertion requires shifting (O(n)):\n"); printf(" Before: "); for (int i = 0; i < 5; i++) printf("%d ", arr[i]); printf("\n"); /* Simulate insertion at index 2 */ int newArr[6]; for (int i = 0; i < 2; i++) newArr[i] = arr[i]; newArr[2] = 99; for (int i = 2; i < 5; i++) newArr[i + 1] = arr[i]; printf(" After: "); for (int i = 0; i < 6; i++) printf("%d ", newArr[i]); printf("\n"); printf("\n3. Large arrays can exhaust memory\n"); }

Expected Output (partial)

text

=== Array Applications and Properties === --- Menu --- 1. Random Access (O(1)) 2. Binary Search on Sorted Array 3. Matrix Operation 4. Stack Implementation Using Array 5. Dynamic Programming (Fibonacci) 6. Advantages Demonstration 7. Disadvantages Demonstration 8. Exit Enter choice: 6 === Advantages === 1. Fast access: arr[i] is O(1) 2. Memory efficient: 40 bytes for 10 integers 3. Versatile: can store int, float, char, pointers 4. Hardware compatible Addresses (contiguous memory): arr[0]: 0x7ffc1234 arr[1]: 0x7ffc1238 arr[2]: 0x7ffc123c arr[3]: 0x7ffc1240 arr[4]: 0x7ffc1244

Common Pitfalls, Edge Cases & Memory Considerations

1. Array Index Out of Bounds

Accessing beyond array bounds.

Solution: Check index >= 0 && index < size.

2. Not Handling Fixed Size Limitation

Assuming arrays can grow dynamically.

Solution: Use malloc/realloc or linked lists for dynamic sizing.

3. Memory Leaks with Dynamic Arrays

Forgetting to free malloc‘d arrays.

Solution: Always free allocated memory.

4. Large Array on Stack

Stack overflow with huge automatic arrays.

Solution: Use static or malloc for large arrays.

5. Insertion/Deletion Inefficiency

Shifting elements is O(n).

Solution: Use linked lists for frequent insertions/deletions.

6. Not Validating Input

Invalid input causes crashes.

Solution: Validate user input.

7. Integer Overflow

Large sums or products overflow.

Solution: Use long long or size_t.

8. Empty Array Operations

Operations on empty arrays fail.

Solution: Check size before operations.

9. Not Considering Cache Performance

Access patterns affect cache efficiency.

Solution: Use row-major traversal for 2D arrays.

10. Memory Considerations

  • Size = n × sizeof(element).
  • Contiguous allocation.
  • No extra linking memory.
  • Stack arrays: automatic lifetime.
  • Heap arrays: manual lifetime.

Summary & Best Practices

Arrays are versatile data structures with O(1) random access and cache efficiency. They serve as building blocks for other structures but have fixed-size limitations.

Key Takeaways

  • Arrays: contiguous, same-type elements.
  • Applications: data storage, searching, matrices, stacks, DP.
  • Advantages: fast access, memory efficient, versatile.
  • Disadvantages: fixed size, insertion/deletion costly.
  • Use for random access and fixed collections.
  • Building block for other data structures.

Best Practices

  1. Use arrays for random access.
  2. Use dynamic allocation for variable sizes.
  3. Check bounds to prevent overflow.
  4. Use row-major traversal for cache efficiency.
  5. Free allocated memory.
  6. Handle edge cases.
  7. Document array assumptions.
  8. Choose appropriate data structure based on needs.
  9. Test with boundary values.
  10. Profile performance for large arrays.

By mastering arrays, you’ll choose the right data structure for each problem and write efficient, robust code.