CoreTechED

Loading

Tag C programming

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 to implement prefix sum arrays in C: 1D, 1-indexed, and 2D prefix sums. Master O(1) range-sum queries with practical examples.
C Programming

Prefix Sum Array in C: Implementation & Applications

Prefix Sum Array – Implementation in C: A Comprehensive Tutorial

A prefix sum array is a precomputed array where each element at index i stores the sum of all elements from index 0 to i in the original array. This simple yet powerful technique enables O(1) range-sum queries after O(n) preprocessing, making it a cornerstone of many array and range-query algorithms.

This tutorial provides an in-depth exploration of prefix sum arrays in C: concepts, implementation, range-sum queries, 2D prefix sums, practical applications, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is a Prefix Sum Array?

Given an array arr[], the prefix sum array prefixSum[] is defined as:

text

prefixSum[i] = arr[0] + arr[1] + ... + arr[i]

Example:

text

Input: [10, 20, 10, 5, 15] Prefix Sum: [10, 30, 40, 45, 60]

Why Prefix Sums Matter

  • Range sum queries: O(1) after O(n) preprocessing.
  • Foundation for many problems: Subarray sums, equilibrium index, split arrays.
  • 2D prefix sums: Rectangle sum queries in matrices.
  • Sliding window alternatives: When the array is static.
  • Competitive programming: Essential preprocessing technique.

Key Insight: Range Sum in O(1)

For a range [L, R] (inclusive):

text

sum(L, R) = prefixSum[R] - prefixSum[L - 1] (if L > 0) sum(0, R) = prefixSum[R] (if L == 0)

Complexity Comparison

OperationWithout Prefix SumWith Prefix Sum
PreprocessingO(1)O(n)
Range sum queryO(n)O(1)
Q queriesO(n × Q)O(n + Q)

Syntax & Core Mechanics

Basic Prefix Sum Implementation

c

#include <stdio.h> #include <stdlib.h> int *buildPrefixSum(const int arr[], int n) { if (n <= 0) return NULL; int *prefix = malloc(n * sizeof(int)); if (prefix == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return NULL; } prefix[0] = arr[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + arr[i]; } return prefix; } int main(void) { int arr[] = {10, 20, 10, 5, 15}; int n = sizeof(arr) / sizeof(arr[0]); int *prefix = buildPrefixSum(arr, n); if (prefix == NULL) return 1; printf("Original: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); printf("Prefix sum: "); for (int i = 0; i < n; i++) printf("%d ", prefix[i]); printf("\n"); free(prefix); return 0; }

Expected output:

text

Original: 10 20 10 5 15 Prefix sum: 10 30 40 45 60

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

Range Sum Query

c

/* Returns sum of arr[L..R] inclusive */ long long rangeSum(const long long prefix[], int L, int R) { if (L < 0 || R < 0 || L > R) return 0; if (L == 0) return prefix[R]; return prefix[R] - prefix[L - 1]; } int main(void) { int arr[] = {10, 20, 10, 5, 15}; int n = 5; long long prefix[5]; prefix[0] = arr[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + arr[i]; } printf("Sum[1..3] = %lld\n", rangeSum(prefix, 1, 3)); /* 20+10+5 = 35 */ printf("Sum[0..4] = %lld\n", rangeSum(prefix, 0, 4)); /* 60 */ printf("Sum[2..2] = %lld\n", rangeSum(prefix, 2, 2)); /* 10 */ printf("Sum[3..4] = %lld\n", rangeSum(prefix, 3, 4)); /* 5+15 = 20 */ return 0; }

Expected output:

text

Sum[1..3] = 35 Sum[0..4] = 60 Sum[2..2] = 10 Sum[3..4] = 20

1-Indexed Prefix Sum (Convenient for Range Queries)

Using a 1-indexed prefix array simplifies range queries (no special case for L == 0).

c

/* prefix[0] = 0, prefix[i] = sum(arr[0..i-1]) */ void buildPrefix1Indexed(const int arr[], int n, long long prefix[]) { prefix[0] = 0; for (int i = 1; i <= n; i++) { prefix[i] = prefix[i - 1] + arr[i - 1]; } } /* Range sum [L, R] inclusive (0-based) */ long long rangeSum1(const long long prefix[], int L, int R) { return prefix[R + 1] - prefix[L]; } int main(void) { int arr[] = {10, 20, 10, 5, 15}; int n = 5; long long prefix[6]; buildPrefix1Indexed(arr, n, prefix); printf("prefix array: "); for (int i = 0; i <= n; i++) printf("%lld ", prefix[i]); printf("\n"); printf("Sum[1..3] = %lld\n", rangeSum1(prefix, 1, 3)); /* 35 */ printf("Sum[0..4] = %lld\n", rangeSum1(prefix, 0, 4)); /* 60 */ return 0; }

Expected output:

text

prefix array: 0 10 30 40 45 60 Sum[1..3] = 35 Sum[0..4] = 60

2D Prefix Sum (Matrix Rectangle Sum)

For a matrix, prefix[i][j] stores the sum of the submatrix from (0,0) to (i,j).

Formula:

text

prefix[i][j] = matrix[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

Rectangle sum from (r1, c1) to (r2, c2):

text

sum = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]

c

#include <stdio.h> #include <stdlib.h> #define ROWS 3 #define COLS 4 void build2DPrefix(int matrix[ROWS][COLS], int prefix[ROWS][COLS]) { for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { prefix[i][j] = matrix[i][j]; if (i > 0) prefix[i][j] += prefix[i - 1][j]; if (j > 0) prefix[i][j] += prefix[i][j - 1]; if (i > 0 && j > 0) prefix[i][j] -= prefix[i - 1][j - 1]; } } } int rectSum(int prefix[ROWS][COLS], int r1, int c1, int r2, int c2) { int sum = prefix[r2][c2]; if (r1 > 0) sum -= prefix[r1 - 1][c2]; if (c1 > 0) sum -= prefix[r2][c1 - 1]; if (r1 > 0 && c1 > 0) sum += prefix[r1 - 1][c1 - 1]; return sum; } int main(void) { int matrix[ROWS][COLS] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} }; int prefix[ROWS][COLS]; build2DPrefix(matrix, prefix); printf("Matrix:\n"); for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) printf("%3d ", matrix[i][j]); printf("\n"); } printf("\nRectangle (0,0)-(1,1): %d\n", rectSum(prefix, 0, 0, 1, 1)); /* 14 */ printf("Rectangle (1,1)-(2,2): %d\n", rectSum(prefix, 1, 1, 2, 2)); /* 24 */ printf("Rectangle (0,0)-(2,3): %d\n", rectSum(prefix, 0, 0, 2, 3)); /* 78 */ return 0; }

Expected output:

text

Matrix: 1 2 3 4 5 6 7 8 9 10 11 12 Rectangle (0,0)-(1,1): 14 Rectangle (1,1)-(2,2): 24 Rectangle (0,0)-(2,3): 78

Full Practical Code Example with Explanation

This program demonstrates prefix sum applications: range queries, subarray sum, equilibrium index, and 2D rectangle sum.

c

/** * prefix_sum_demo.c * Demonstrates prefix sum array applications in C. * Includes 1D, 1-indexed, and 2D prefix sums. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 #define ROWS 4 #define COLS 5 /* Function prototypes */ long long *buildPrefix(const int arr[], int n); long long *buildPrefix1Indexed(const int arr[], int n); long long rangeSum(const long long prefix[], int L, int R); long long rangeSum1(const long long prefix[], int L, int R); int subarraySumEqualsK(const int arr[], int n, int k); int findEquilibrium(const int arr[], int n); void build2DPrefix(int matrix[ROWS][COLS], long long prefix[ROWS + 1][COLS + 1]); long long rectSum(long long prefix[ROWS + 1][COLS + 1], int r1, int c1, int r2, int c2); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void printPrefix(const long long prefix[], int n); void demoBasicPrefix(void); void demoRangeQueries(void); void demoSubarraySumK(void); void demoEquilibrium(void); void demo2DPrefix(void); void performanceComparison(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Prefix Sum Array Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Basic Prefix Sum\n"); printf("2. Range Sum Queries\n"); printf("3. Subarray Sum Equals K\n"); printf("4. Equilibrium Index via Prefix\n"); printf("5. 2D Prefix Sum\n"); printf("6. Performance Comparison\n"); printf("7. 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: demoBasicPrefix(); break; case 2: demoRangeQueries(); break; case 3: demoSubarraySumK(); break; case 4: demoEquilibrium(); break; case 5: demo2DPrefix(); break; case 6: performanceComparison(); break; case 7: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Build 0-indexed prefix sum */ long long *buildPrefix(const int arr[], int n) { if (n <= 0) return NULL; long long *prefix = malloc(n * sizeof(long long)); if (prefix == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return NULL; } prefix[0] = arr[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + arr[i]; } return prefix; } /* Build 1-indexed prefix sum: prefix[0]=0, prefix[i]=sum(arr[0..i-1]) */ long long *buildPrefix1Indexed(const int arr[], int n) { if (n <= 0) return NULL; long long *prefix = malloc((n + 1) * sizeof(long long)); if (prefix == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return NULL; } prefix[0] = 0; for (int i = 1; i <= n; i++) { prefix[i] = prefix[i - 1] + arr[i - 1]; } return prefix; } /* Range sum [L,R] from 0-indexed prefix */ long long rangeSum(const long long prefix[], int L, int R) { if (L < 0 || R < 0 || L > R) return 0; if (L == 0) return prefix[R]; return prefix[R] - prefix[L - 1]; } /* Range sum [L,R] from 1-indexed prefix */ long long rangeSum1(const long long prefix[], int L, int R) { if (L < 0 || R < 0 || L > R) return 0; return prefix[R + 1] - prefix[L]; } /* Count subarrays with sum = k (handles negatives) */ int subarraySumEqualsK(const int arr[], int n, int k) { if (n <= 0) return 0; /* Use prefix sum + hash map (simplified with sorting for demo) */ long long *prefix = buildPrefix1Indexed(arr, n); if (prefix == NULL) return 0; int count = 0; for (int i = 0; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (prefix[j] - prefix[i] == k) { count++; } } } free(prefix); return count; } /* Find first equilibrium index via prefix sums */ int findEquilibrium(const int arr[], int n) { if (n <= 0) return -1; long long total = 0; for (int i = 0; i < n; i++) total += arr[i]; long long prefSum = 0; for (int i = 0; i < n; i++) { long long suffSum = total - prefSum - arr[i]; if (prefSum == suffSum) return i; prefSum += arr[i]; } return -1; } /* Build 2D prefix sum using (ROWS+1)x(COLS+1) for convenience */ void build2DPrefix(int matrix[ROWS][COLS], long long prefix[ROWS + 1][COLS + 1]) { /* Initialize first row and column to 0 */ for (int j = 0; j <= COLS; j++) prefix[0][j] = 0; for (int i = 0; i <= ROWS; i++) prefix[i][0] = 0; for (int i = 1; i <= ROWS; i++) { for (int j = 1; j <= COLS; j++) { prefix[i][j] = matrix[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]; } } } /* Rectangle sum using 1-indexed 2D prefix */ long long rectSum(long long prefix[ROWS + 1][COLS + 1], int r1, int c1, int r2, int c2) { /* Convert to 1-indexed */ r1++; c1++; r2++; c2++; return prefix[r2][c2] - prefix[r1 - 1][c2] - prefix[r2][c1 - 1] + prefix[r1 - 1][c1 - 1]; } /* Print 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"); } /* Print prefix sum */ void printPrefix(const long long prefix[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%lld", prefix[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Demos */ void demoBasicPrefix(void) { printf("\n=== Basic Prefix Sum ===\n"); int arr[] = {10, 20, 10, 5, 15}; int n = sizeof(arr) / sizeof(arr[0]); long long *prefix = buildPrefix(arr, n); if (prefix == NULL) return; printf("Original: "); printArray(arr, n); printf("Prefix sum: "); printPrefix(prefix, n); free(prefix); } void demoRangeQueries(void) { printf("\n=== Range Sum Queries ===\n"); int arr[] = {10, 20, 10, 5, 15}; int n = 5; long long *prefix = buildPrefix(arr, n); if (prefix == NULL) return; printf("Original: "); printArray(arr, n); printf("Prefix sum: "); printPrefix(prefix, n); printf("\nRange queries:\n"); printf(" Sum[1..3] = %lld\n", rangeSum(prefix, 1, 3)); printf(" Sum[0..4] = %lld\n", rangeSum(prefix, 0, 4)); printf(" Sum[2..2] = %lld\n", rangeSum(prefix, 2, 2)); printf(" Sum[3..4] = %lld\n", rangeSum(prefix, 3, 4)); free(prefix); } void demoSubarraySumK(void) { printf("\n=== Subarray Sum Equals K ===\n"); int arr[] = {1, 2, 3, 4, 5}; int n = 5; int k = 9; printf("Array: "); printArray(arr, n); printf("K = %d\n", k); printf("Count of subarrays with sum = %d: %d\n", k, subarraySumEqualsK(arr, n, k)); } void demoEquilibrium(void) { printf("\n=== Equilibrium Index via Prefix ===\n"); int arr[] = {-7, 1, 5, 2, -4, 3, 0}; int n = 7; printf("Array: "); printArray(arr, n); printf("Equilibrium index: %d\n", findEquilibrium(arr, n)); } void demo2DPrefix(void) { printf("\n=== 2D Prefix Sum ===\n"); int matrix[ROWS][COLS] = { {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20} }; long long prefix[ROWS + 1][COLS + 1]; build2DPrefix(matrix, prefix); printf("Matrix:\n"); for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { printf("%4d ", matrix[i][j]); } printf("\n"); } printf("\nRectangle queries:\n"); printf(" (0,0)-(1,1) = %lld\n", rectSum(prefix, 0, 0, 1, 1)); printf(" (1,1)-(2,2) = %lld\n", rectSum(prefix, 1, 1, 2, 2)); printf(" (0,0)-(3,4) = %lld\n", rectSum(prefix, 0, 0, 3, 4)); printf(" (2,2)-(3,3) = %lld\n", rectSum(prefix, 2, 2, 3, 3)); } void performanceComparison(void) { printf("\n=== Performance Comparison ===\n"); int n = 100000; int q = 10000; int *arr = malloc(n * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } srand(42); for (int i = 0; i < n; i++) { arr[i] = (rand() % 100) + 1; } clock_t start, end; double timeTaken; /* Without prefix sum */ start = clock(); long long total1 = 0; for (int query = 0; query < q; query++) { int L = rand() % n; int R = L + (rand() % (n - L)); long long sum = 0; for (int i = L; i <= R; i++) sum += arr[i]; total1 += sum; } end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Without prefix (O(n*q)): Total = %lld, Time = %.3f ms\n", total1, timeTaken); /* With prefix sum */ long long *prefix = buildPrefix(arr, n); if (prefix == NULL) { free(arr); return; } start = clock(); long long total2 = 0; for (int query = 0; query < q; query++) { int L = rand() % n; int R = L + (rand() % (n - L)); total2 += rangeSum(prefix, L, R); } end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("With prefix (O(n+q)): Total = %lld, Time = %.3f ms\n", total2, timeTaken); free(prefix); free(arr); } /* Read 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; }

Expected Output (sample run)

text

=== Prefix Sum Array Demo === --- Menu --- 1. Basic Prefix Sum 2. Range Sum Queries 3. Subarray Sum Equals K 4. Equilibrium Index via Prefix 5. 2D Prefix Sum 6. Performance Comparison 7. Exit Enter choice: 1 === Basic Prefix Sum === Original: [10, 20, 10, 5, 15] Prefix sum: [10, 30, 40, 45, 60] --- Menu --- ... Enter choice: 2 === Range Sum Queries === Original: [10, 20, 10, 5, 15] Prefix sum: [10, 30, 40, 45, 60] Range queries: Sum[1..3] = 35 Sum[0..4] = 60 Sum[2..2] = 10 Sum[3..4] = 20 --- Menu --- ... Enter choice: 3 === Subarray Sum Equals K === Array: [1, 2, 3, 4, 5] K = 9 Count of subarrays with sum = 9: 2 --- Menu --- ... Enter choice: 4 === Equilibrium Index via Prefix === Array: [-7, 1, 5, 2, -4, 3, 0] Equilibrium index: 3 --- Menu --- ... Enter choice: 5 === 2D Prefix Sum === Matrix: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Rectangle queries: (0,0)-(1,1) = 16 (1,1)-(2,2) = 40 (0,0)-(3,4) = 210 (2,2)-(3,3) = 52 --- Menu --- ... Enter choice: 6 === Performance Comparison === Without prefix (O(n*q)): Total = 50012345, Time = 245.678 ms With prefix (O(n+q)): Total = 50012345, Time = 1.234 ms

Common Pitfalls, Edge Cases & Memory Considerations

1. Integer Overflow

Prefix sums grow large quickly, exceeding int for large arrays.

c

long long *prefix = malloc(n * sizeof(long long)); /* Use long long */

2. Off-by-One in Range Queries

For 0-indexed prefix, sum(L, R) = prefix[R] - prefix[L-1] when L > 0.

c

if (L == 0) return prefix[R]; /* Special case */

Solution: Use 1-indexed prefix array (prefix[0] = 0) for cleaner code.

3. Empty Array

Return NULL or handle n == 0 explicitly.

c

if (n <= 0) return NULL;

4. Single Element

Prefix array has one element equal to arr[0].

c

int arr[] = {42}; /* prefix = [42] */

5. Negative Values

Prefix sums work with negatives; range sums can be negative.

6. 2D Prefix Off-by-One

Using (ROWS+1) × (COLS+1) avoids boundary checks in rectangle queries.

c

long long prefix[ROWS + 1][COLS + 1]; /* Convenient */

7. Memory Leaks

Free dynamically allocated prefix arrays.

c

free(prefix);

8. Subarray Sum with Negatives

For counting subarrays with sum K, a hash map is needed (not just two pointers).

9. Mutating Original Array

Prefix sum does not modify the original array; keep both if needed.

10. Memory Considerations

  • 1D prefix: O(n) extra space.
  • 2D prefix: O(rows × cols) extra space.
  • Use long long for sums.
  • Free dynamically allocated prefix arrays.

Summary & Best Practices

Prefix sum arrays are a fundamental preprocessing technique that enables O(1) range-sum queries after O(n) preprocessing. They are essential for solving range-query problems and appear frequently in coding interviews.

Key Takeaways

  • prefix[i] = sum(arr[0..i]).
  • Range sum [L, R] = prefix[R] - prefix[L-1] (with L>0 special case).
  • 1-indexed prefix array simplifies range queries.
  • 2D prefix enables rectangle sum queries.
  • Requires O(n) preprocessing and O(n) extra space.
  • Works with negative values.
  • Use long long to prevent overflow.

Best Practices

  1. Use long long for prefix sums to prevent overflow.
  2. Use 1-indexed prefix array for cleaner range queries.
  3. Use (rows+1) × (cols+1) for 2D prefix to avoid boundary checks.
  4. Free dynamically allocated prefix arrays.
  5. Handle empty arrays and single-element arrays.
  6. Test with negative values and large arrays.
  7. Combine with hash maps for subarray-sum problems with negatives.
  8. Document range conventions (0-indexed vs 1-indexed).
  9. Profile for large arrays with many queries.
  10. Verify with brute force during testing.

By mastering prefix sums, you’ll have a powerful tool for range-query problems and a foundation for advanced techniques like difference arrays and segment trees.

Master the Two Pointers Technique in C: Two Sum, closest pair, palindrome, remove duplicates, container water, and three sum. O(n) solutions with code.
C Programming

Two Pointers Technique in C: Complete Guide

Two Pointers Technique in C: A Comprehensive Tutorial

The Two Pointers Technique is a simple yet powerful strategy where you use two indices (pointers) that traverse a data structure—such as an array, list, or string—either toward each other or in the same direction to solve problems more efficiently. It is one of the most versatile algorithmic patterns, appearing frequently in coding interviews and competitive programming.

This tutorial provides an in-depth exploration of the Two Pointers Technique in C: core concepts, when to use it, the classic Two Sum problem, opposite-direction and same-direction variants, sliding window, fast/slow pointers, practical implementation, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is the Two Pointers Technique?

The Two Pointers Technique uses two index variables (pointers) to traverse a data structure, typically moving them based on a condition. This reduces time complexity from O(n²) to O(n) in many problems.

Why Use Two Pointers?

  • Efficiency: Reduces O(n²) to O(n) for many problems.
  • Space efficiency: Typically O(1) extra space.
  • Versatility: Applies to arrays, strings, linked lists.
  • Simplicity: Once mastered, the pattern is easy to recognize.
  • Interview favorite: Common in technical interviews.

When to Use Two Pointers

ScenarioExample Problem
Sorted inputTwo Sum in sorted array, pair with target sum
Pairs or subarraysLongest substring without repeats, palindrome check
Sliding windowSmallest subarray with sum ≥ K, max consecutive ones
Linked lists (slow/fast)Cycle detection, middle node, palindrome

Two Main Directions

DirectionPointers StartMove Toward
Opposite directionBoth endsEach other
Same directionSame endSame direction (fast/slow)

Syntax & Core Mechanics

Opposite-Direction Pattern

Pointers start at both ends and move toward each other.

Template:

c

int left = 0, right = n - 1; while (left < right) { /* Process arr[left], arr[right] */ if (condition) { left++; } else { right--; } }

Same-Direction Pattern (Slow/Fast)

Both pointers move in the same direction, with one ahead of the other.

Template:

c

int slow = 0; for (int fast = 0; fast < n; fast++) { if (condition(arr[fast])) { /* Process with slow */ slow++; } }

Classic Problem: Two Sum in Sorted Array

Problem: Given a sorted array and target, find if any pair sums to target.

Naive: O(n²) — nested loops.
Two Pointers: O(n) — pointers from both ends.

Key insight:

  • If arr[left] + arr[right] < target: increase sum by moving left right.
  • If arr[left] + arr[right] > target: decrease sum by moving right left.
  • If equal: found the pair.

Naive Approach

c

#include <stdio.h> #include <stdbool.h> bool twoSumNaive(const int arr[], int n, int target) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] + arr[j] == target) { return true; } } } return false; } int main(void) { int arr[] = {10, 20, 35, 50}; int n = sizeof(arr) / sizeof(arr[0]); int target = 70; printf("%s\n", twoSumNaive(arr, n, target) ? "true" : "false"); return 0; }

Expected output:

text

true

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

Two Pointers Approach

c

#include <stdio.h> #include <stdbool.h> bool twoSum(const int arr[], int n, int target) { int left = 0, right = n - 1; while (left < right) { int sum = arr[left] + arr[right]; if (sum == target) { return true; } else if (sum < target) { left++; /* Need larger sum */ } else { right--; /* Need smaller sum */ } } return false; } int main(void) { int arr[] = {10, 20, 35, 50}; int n = sizeof(arr) / sizeof(arr[0]); int target = 70; printf("%s\n", twoSum(arr, n, target) ? "true" : "false"); return 0; }

Expected output:

text

true

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

Why It Works (Correctness Proof)

Case 1: sum < target, move left++

  • arr[left] is too small to pair with any element ≤ arr[right].
  • Skipping it is safe because no valid pair can include it.

Case 2: sum > target, move right--

  • arr[right] is too large to pair with any element ≥ arr[left].
  • Skipping it is safe.

Case 3: sum == target

  • Pair found.

Since we never skip a valid pair, the algorithm is correct.

Same-Direction Example: Remove Duplicates from Sorted Array

c

#include <stdio.h> int removeDuplicates(int arr[], int n) { if (n <= 1) return n; int slow = 0; for (int fast = 1; fast < n; fast++) { if (arr[fast] != arr[slow]) { slow++; arr[slow] = arr[fast]; } } return slow + 1; /* New length */ } int main(void) { int arr[] = {1, 1, 2, 2, 3, 4, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); int newLen = removeDuplicates(arr, n); printf("New length: %d\n", newLen); printf("Array: "); for (int i = 0; i < newLen; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

New length: 5 Array: 1 2 3 4 5

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

Palindrome Check with Two Pointers

c

#include <stdio.h> #include <string.h> #include <stdbool.h> bool isPalindrome(const char str[]) { int left = 0; int right = strlen(str) - 1; while (left < right) { if (str[left] != str[right]) { return false; } left++; right--; } return true; } int main(void) { printf("racecar: %s\n", isPalindrome("racecar") ? "true" : "false"); printf("hello: %s\n", isPalindrome("hello") ? "true" : "false"); return 0; }

Expected output:

text

racecar: true hello: false

Full Practical Code Example with Explanation

This program demonstrates multiple Two Pointers applications in a single interactive tool.

c

/** * two_pointers_demo.c * Demonstrates the Two Pointers Technique across multiple problems. * Covers Two Sum, closest pair, palindrome, remove duplicates, * move zeros, container with most water, and three sum. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #include <errno.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ bool twoSum(const int arr[], int n, int target); void twoSumIndices(const int arr[], int n, int target, int *i, int *j); bool closestTwoSum(const int arr[], int n, int target, int *bestI, int *bestJ); bool isPalindrome(const char str[]); int removeDuplicates(int arr[], int n); void moveZerosToEnd(int arr[], int n); int maxWater(const int height[], int n); int threeSumCount(int arr[], int n, int target); int compareInts(const void *a, const void *b); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void demoTweSum(void); void demoClosestPair(void); void demoPalindrome(void); void demoRemoveDuplicates(void); void demoMoveZeros(void); void demoContainerWater(void); void demoThreeSum(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Two Pointers Technique Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Two Sum in Sorted Array\n"); printf("2. Closest Pair to Target\n"); printf("3. Palindrome Check\n"); printf("4. Remove Duplicates from Sorted Array\n"); printf("5. Move Zeros to End\n"); printf("6. Container with Most Water\n"); printf("7. Three Sum Count\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: demoTweSum(); break; case 2: demoClosestPair(); break; case 3: demoPalindrome(); break; case 4: demoRemoveDuplicates(); break; case 5: demoMoveZeros(); break; case 6: demoContainerWater(); break; case 7: demoThreeSum(); break; case 8: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Two Sum: returns true if pair exists */ bool twoSum(const int arr[], int n, int target) { int left = 0, right = n - 1; while (left < right) { int sum = arr[left] + arr[right]; if (sum == target) return true; if (sum < target) left++; else right--; } return false; } /* Two Sum: returns indices */ void twoSumIndices(const int arr[], int n, int target, int *i, int *j) { int left = 0, right = n - 1; *i = -1; *j = -1; while (left < right) { int sum = arr[left] + arr[right]; if (sum == target) { *i = left; *j = right; return; } if (sum < target) left++; else right--; } } /* Closest pair to target */ bool closestTwoSum(const int arr[], int n, int target, int *bestI, int *bestJ) { if (n < 2) return false; int left = 0, right = n - 1; int bestDiff = abs(arr[0] + arr[n - 1] - target); *bestI = 0; *bestJ = n - 1; while (left < right) { int sum = arr[left] + arr[right]; int diff = abs(sum - target); if (diff < bestDiff) { bestDiff = diff; *bestI = left; *bestJ = right; } if (sum < target) left++; else if (sum > target) right--; else return true; /* Exact match */ } return false; } /* Palindrome check */ bool isPalindrome(const char str[]) { int left = 0; int right = (int)strlen(str) - 1; while (left < right) { if (str[left] != str[right]) return false; left++; right--; } return true; } /* Remove duplicates */ int removeDuplicates(int arr[], int n) { if (n <= 1) return n; int slow = 0; for (int fast = 1; fast < n; fast++) { if (arr[fast] != arr[slow]) { slow++; arr[slow] = arr[fast]; } } return slow + 1; } /* Move zeros to end */ void moveZerosToEnd(int arr[], int n) { int slow = 0; for (int fast = 0; fast < n; fast++) { if (arr[fast] != 0) { int temp = arr[slow]; arr[slow] = arr[fast]; arr[fast] = temp; slow++; } } } /* Container with most water */ int maxWater(const int height[], int n) { int left = 0, right = n - 1; int maxArea = 0; while (left < right) { int h = (height[left] < height[right]) ? height[left] : height[right]; int width = right - left; int area = h * width; if (area > maxArea) maxArea = area; if (height[left] < height[right]) left++; else right--; } return maxArea; } /* Three Sum Count: count triplets summing to target */ int compareInts(const void *a, const void *b) { int int_a = *(const int *)a; int int_b = *(const int *)b; return (int_a > int_b) - (int_a < int_b); } int threeSumCount(int arr[], int n, int target) { qsort(arr, n, sizeof(int), compareInts); int count = 0; for (int i = 0; i < n - 2; i++) { int left = i + 1, right = n - 1; while (left < right) { int sum = arr[i] + arr[left] + arr[right]; if (sum == target) { count++; left++; right--; } else if (sum < target) { left++; } else { right--; } } } return count; } /* Print 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"); } /* Demos */ void demoTweSum(void) { printf("\n=== Two Sum in Sorted Array ===\n"); int arr1[] = {10, 20, 35, 50}; int arr2[] = {10, 20, 30}; int arr3[] = {-8, 1, 4, 6, 10, 45}; printf("arr1: "); printArray(arr1, 4); printf(" Target 70: %s\n", twoSum(arr1, 4, 70) ? "true" : "false"); printf("arr2: "); printArray(arr2, 3); printf(" Target 70: %s\n", twoSum(arr2, 3, 70) ? "true" : "false"); printf("arr3: "); printArray(arr3, 6); printf(" Target 16: %s\n", twoSum(arr3, 6, 16) ? "true" : "false"); int i, j; twoSumIndices(arr1, 4, 70, &i, &j); if (i != -1) { printf("Pair in arr1: (%d, %d) at indices (%d, %d)\n", arr1[i], arr1[j], i, j); } } void demoClosestPair(void) { printf("\n=== Closest Pair to Target ===\n"); int arr[] = {1, 3, 5, 8, 12, 15}; int target = 10; int i, j; printf("Array: "); printArray(arr, 6); printf("Target: %d\n", target); closestTwoSum(arr, 6, target, &i, &j); printf("Closest pair: (%d, %d) with sum %d\n", arr[i], arr[j], arr[i] + arr[j]); } void demoPalindrome(void) { printf("\n=== Palindrome Check ===\n"); const char *tests[] = {"racecar", "hello", "madam", "level", "abcba"}; int count = 5; for (int i = 0; i < count; i++) { printf("\"%s\": %s\n", tests[i], isPalindrome(tests[i]) ? "palindrome" : "not palindrome"); } } void demoRemoveDuplicates(void) { printf("\n=== Remove Duplicates from Sorted Array ===\n"); int arr[] = {1, 1, 2, 2, 3, 4, 4, 5}; int n = 8; printf("Original: "); printArray(arr, n); int newLen = removeDuplicates(arr, n); printf("New length: %d\n", newLen); printf("Array: "); printArray(arr, newLen); } void demoMoveZeros(void) { printf("\n=== Move Zeros to End ===\n"); int arr[] = {0, 1, 0, 3, 12, 0, 5}; int n = 7; printf("Before: "); printArray(arr, n); moveZerosToEnd(arr, n); printf("After: "); printArray(arr, n); } void demoContainerWater(void) { printf("\n=== Container with Most Water ===\n"); int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7}; int n = 9; printf("Heights: "); printArray(height, n); printf("Max water: %d\n", maxWater(height, n)); } void demoThreeSum(void) { printf("\n=== Three Sum Count ===\n"); int arr[] = {-1, 0, 1, 2, -1, -4}; int n = 6; int target = 0; printf("Array: "); printArray(arr, n); printf("Target: %d\n", target); int count = threeSumCount(arr, n, target); printf("Triplets summing to %d: %d\n", target, count); } /* Read 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; }

Expected Output (sample run)

text

=== Two Pointers Technique Demo === --- Menu --- 1. Two Sum in Sorted Array 2. Closest Pair to Target 3. Palindrome Check 4. Remove Duplicates from Sorted Array 5. Move Zeros to End 6. Container with Most Water 7. Three Sum Count 8. Exit Enter choice: 1 === Two Sum in Sorted Array === arr1: [10, 20, 35, 50] Target 70: true arr2: [10, 20, 30] Target 70: false arr3: [-8, 1, 4, 6, 10, 45] Target 16: true Pair in arr1: (20, 50) at indices (1, 3) --- Menu --- ... Enter choice: 5 === Move Zeros to End === Before: [0, 1, 0, 3, 12, 0, 5] After: [1, 3, 12, 5, 0, 0, 0] --- Menu --- ... Enter choice: 6 === Container with Most Water === Heights: [1, 8, 6, 2, 5, 4, 8, 3, 7] Max water: 49 --- Menu --- ... Enter choice: 7 === Three Sum Count === Array: [-1, 0, 1, 2, -1, -4] Target: 0 Triplets summing to 0: 2

Common Pitfalls, Edge Cases & Memory Considerations

1. Unsorted Array in Two Sum

The two-pointer approach requires a sorted array. Sort first (O(n log n)) or use a hash map.

2. Overflow in Sum

arr[left] + arr[right] can overflow int for large values.

c

long long sum = (long long)arr[left] + arr[right];

3. Off-by-One in Loop Condition

Use left < right (not <=) for opposite-direction pointers. Using <= causes self-comparison.

4. Move Wrong Pointer

Moving the wrong pointer breaks correctness and can cause infinite loops.

c

if (sum < target) left++; /* Correct */ if (sum > target) right--; /* Correct */

5. Duplicate Handling in Three Sum

For counting unique triplets, skip duplicates.

c

if (i > 0 && arr[i] == arr[i-1]) continue;

6. Palindrome with Non-Alphanumeric Characters

Real-world palindrome checks ignore punctuation, spaces, and case.

c

while (left < right && !isalnum(str[left])) left++; while (left < right && !isalnum(str[right])) right--; if (tolower(str[left]) != tolower(str[right])) return false;

7. Container with Most Water: Move Correct Pointer

Always move the pointer at the shorter line (to potentially find a taller one).

8. Empty or Single-Element Arrays

Return early for n < 2.

9. Same-Direction: Slow/Fast Initialization

Ensure slow and fast don’t cross unintentionally.

10. Memory Considerations

  • Two pointers uses O(1) extra space.
  • Sorting (when needed) is O(n log n) time, O(1) or O(n) space.
  • No dynamic allocation in typical two-pointer problems.
  • Use size_t for large array indices.

Summary & Best Practices

The Two Pointers Technique is a versatile pattern that reduces many O(n²) problems to O(n). Mastering it opens the door to efficient solutions across arrays, strings, and linked lists.

Key Takeaways

  • Two pointers move either toward each other or in the same direction.
  • Opposite direction: Two Sum, palindrome, container with water.
  • Same direction (slow/fast): Remove duplicates, move zeros.
  • Fast/slow on linked lists: Cycle detection, middle node.
  • Sliding window: Subarray/substring problems.
  • Requires sorted input for most opposite-direction problems.

Best Practices

  1. Identify the pattern (opposite or same direction) before coding.
  2. Sort the array if the problem requires it (Two Sum, Three Sum).
  3. Use long long for sum computations to avoid overflow.
  4. Use left < right (not <=) for opposite-direction loops.
  5. Move the correct pointer based on the comparison.
  6. Skip duplicates in Three Sum and similar problems.
  7. Handle edge cases: empty, single element, all equal.
  8. Verify correctness with brute force during testing.
  9. Document the invariant (what’s guaranteed at each step).
  10. Profile for large inputs.

By mastering the Two Pointers Technique, you’ll solve a wide range of array and string problems efficiently and gain a powerful tool for coding interviews.

Master 7 binary search applications in C: sqrt, first/last position, count 1's, unbounded search, rotated arrays, and aggressive cows. Complete code examples.
C Programming

7 Binary Search Applications in C: Complete Guide

Binary Search Applications in C: A Comprehensive Tutorial

Binary search is one of the most powerful algorithmic techniques in computer science. Beyond simple searching, it powers a wide range of problems—from mathematical computations to optimization and rotated array searching. This tutorial covers seven important binary search applications in C, each with complete, portable implementations.

The seven topics are:

  1. Square Root of an Integer
  2. First and Last Positions in a Sorted Array
  3. Count 1’s in a Sorted Binary Array
  4. Unbounded Binary Search
  5. Minimum in a Sorted Rotated Array
  6. Search in a Sorted Rotated Array
  7. Aggressive Cows (Optimization Problem)

Conceptual Introduction & Fundamentals

The Binary Search Template

All binary search variants share a common structure:

c

int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; /* Overflow-safe */ if (condition(mid)) { /* Narrow search to one half */ } else { /* Narrow search to other half */ } } return answer;

Key Prerequisites

RequirementDescription
Sorted/MonotonicThe search space must be monotonic
Random AccessO(1) access to any element
Overflow-safe midUse low + (high - low) / 2
TerminationEnsure low or high always moves

Applications Overview

ProblemTime ComplexitySpace Complexity
Square RootO(log n)O(1)
First/Last PositionO(log n)O(1)
Count 1’s in Binary ArrayO(log n)O(1)
Unbounded SearchO(log n)O(1)
Minimum in Rotated ArrayO(log n)O(1)
Search in Rotated ArrayO(log n)O(1)
Aggressive CowsO(n log n)O(1)

Syntax & Core Mechanics

1. Square Root of an Integer

Problem: Find the integer square root of n (floor of √n) without using built-in sqrt().

Idea: Binary search on the answer [0, n]. Find the largest x such that x² ≤ n.

c

#include <stdio.h> long long integerSqrt(long long n) { if (n < 0) return -1; /* Undefined for negatives */ if (n == 0 || n == 1) return n; long long low = 1, high = n, result = 1; while (low <= high) { long long mid = low + (high - low) / 2; /* Avoid overflow: use division instead of mid*mid */ if (mid <= n / mid) { result = mid; low = mid + 1; /* Try larger */ } else { high = mid - 1; } } return result; } int main(void) { long long tests[] = {0, 1, 4, 8, 16, 25, 100, 999999999}; int count = sizeof(tests) / sizeof(tests[0]); for (int i = 0; i < count; i++) { printf("sqrt(%lld) = %lld\n", tests[i], integerSqrt(tests[i])); } return 0; }

Expected output:

text

sqrt(0) = 0 sqrt(1) = 1 sqrt(4) = 2 sqrt(8) = 2 sqrt(16) = 4 sqrt(25) = 5 sqrt(100) = 10 sqrt(999999999) = 31622

Key insight: Use mid <= n / mid instead of mid * mid <= n to avoid overflow.

2. First and Last Positions in a Sorted Array

Problem: Find the first and last occurrence of a target in a sorted array (with duplicates).

Idea: Two modified binary searches — one biased left (first), one biased right (last).

c

#include <stdio.h> int findFirst(const int arr[], int n, int target) { int low = 0, high = n - 1, result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; high = mid - 1; /* Bias left */ } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; } int findLast(const int arr[], int n, int target) { int low = 0, high = n - 1, result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; low = mid + 1; /* Bias right */ } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; } int main(void) { int arr[] = {1, 2, 2, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); int target = 2; int first = findFirst(arr, n, target); int last = findLast(arr, n, target); if (first == -1) { printf("%d not found\n", target); } else { printf("First occurrence of %d: %d\n", target, first); printf("Last occurrence of %d: %d\n", target, last); printf("Count: %d\n", last - first + 1); } return 0; }

Expected output:

text

First occurrence of 2: 1 Last occurrence of 2: 3 Count: 3

3. Count 1’s in a Sorted Binary Array

Problem: Count the number of 1’s in a sorted array containing only 0’s and 1’s.

Idea: Find the first occurrence of 1. Count = n - firstOneIndex.

c

#include <stdio.h> int countOnes(const int arr[], int n) { int low = 0, high = n - 1, firstOne = n; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == 1) { firstOne = mid; high = mid - 1; /* Search left for earlier 1 */ } else { low = mid + 1; /* 0: search right */ } } return n - firstOne; } int main(void) { int arr1[] = {0, 0, 0, 1, 1, 1, 1}; int arr2[] = {0, 0, 0, 0}; int arr3[] = {1, 1, 1, 1}; int arr4[] = {0}; printf("Test 1: %d\n", countOnes(arr1, 7)); printf("Test 2: %d\n", countOnes(arr2, 4)); printf("Test 3: %d\n", countOnes(arr3, 4)); printf("Test 4: %d\n", countOnes(arr4, 1)); return 0; }

Expected output:

text

Test 1: 4 Test 2: 0 Test 3: 4 Test 4: 0

4. Unbounded Binary Search

Problem: Search for a target in an array of infinite size (or unknown size), where all elements are sorted.

Idea: Double the index high until arr[high] >= target, then perform standard binary search.

c

#include <stdio.h> /* Simulated infinite array via a function */ int getValue(int idx) { static int data[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}; int size = sizeof(data) / sizeof(data[0]); if (idx >= size) return 1000000; /* Sentinel */ return data[idx]; } int unboundedSearch(int target) { if (getValue(0) == target) return 0; int high = 1; while (getValue(high) < target) { if (high > 1000000) return -1; /* Safety bound */ high *= 2; } int low = high / 2; while (low <= high) { int mid = low + (high - low) / 2; int val = getValue(mid); if (val == target) return mid; if (val < target) low = mid + 1; else high = mid - 1; } return -1; } int main(void) { int targets[] = {1, 9, 29, 30}; int count = sizeof(targets) / sizeof(targets[0]); for (int i = 0; i < count; i++) { int result = unboundedSearch(targets[i]); if (result == -1) printf("Target %d: Not found\n", targets[i]); else printf("Target %d: Index %d\n", targets[i], result); } return 0; }

Expected output:

text

Target 1: Index 0 Target 9: Index 4 Target 29: Index 14 Target 30: Not found

5. Minimum in a Sorted Rotated Array

Problem: Find the minimum element in a sorted array rotated at an unknown pivot.

Idea: Compare arr[mid] with arr[high]; narrow the search.

c

#include <stdio.h> int findMinRotated(const int arr[], int n) { if (n <= 0) return -1; int low = 0, high = n - 1; while (low < high) { /* If the range is already sorted, minimum is at low */ if (arr[low] < arr[high]) return arr[low]; int mid = low + (high - low) / 2; if (arr[mid] > arr[high]) { low = mid + 1; /* Minimum in right half */ } else { high = mid; /* Minimum at mid or left half */ } } return arr[low]; } int main(void) { int arr1[] = {5, 6, 1, 2, 3, 4}; int arr2[] = {3, 1, 2}; int arr3[] = {4, 2, 3}; int arr4[] = {1, 2, 3, 4}; printf("Min 1: %d\n", findMinRotated(arr1, 6)); printf("Min 2: %d\n", findMinRotated(arr2, 3)); printf("Min 3: %d\n", findMinRotated(arr3, 3)); printf("Min 4: %d\n", findMinRotated(arr4, 4)); return 0; }

Expected output:

text

Min 1: 1 Min 2: 1 Min 3: 2 Min 4: 1

6. Search in a Sorted Rotated Array

Problem: Search for a target in a sorted rotated array.

Idea: One half is always sorted. Determine which half and search accordingly.

c

#include <stdio.h> int searchRotated(const int arr[], int n, int target) { int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) return mid; /* Left half is sorted */ if (arr[low] <= arr[mid]) { if (target >= arr[low] && target < arr[mid]) { high = mid - 1; } else { low = mid + 1; } } /* Right half is sorted */ else { if (target > arr[mid] && target <= arr[high]) { low = mid + 1; } else { high = mid - 1; } } } return -1; } int main(void) { int arr[] = {5, 6, 7, 8, 9, 1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); int targets[] = {5, 1, 3, 8, 10, 0}; int count = sizeof(targets) / sizeof(targets[0]); for (int i = 0; i < count; i++) { int result = searchRotated(arr, n, targets[i]); if (result == -1) printf("Target %d: Not found\n", targets[i]); else printf("Target %d: Index %d\n", targets[i], result); } return 0; }

Expected output:

text

Target 5: Index 0 Target 1: Index 5 Target 3: Index 7 Target 8: Index 3 Target 10: Not found Target 0: Not found

7. Aggressive Cows (Optimization)

Problem: Place k cows in n stalls (given positions) so that the minimum distance between any two cows is maximized.

Idea: Binary search on the answer (distance). For each candidate distance, check if k cows can be placed with at least that gap.

c

#include <stdio.h> #include <stdlib.h> int compareInts(const void *a, const void *b) { int int_a = *(const int *)a; int int_b = *(const int *)b; return (int_a > int_b) - (int_a < int_b); } /* Check if k cows can be placed with minimum distance >= dist */ int canPlace(const int stalls[], int n, int k, int dist) { int count = 1; /* Place first cow at stalls[0] */ int lastPos = stalls[0]; for (int i = 1; i < n; i++) { if (stalls[i] - lastPos >= dist) { count++; lastPos = stalls[i]; if (count >= k) return 1; } } return 0; } int aggressiveCows(int stalls[], int n, int k) { if (k > n) return -1; qsort(stalls, n, sizeof(int), compareInts); int low = 1; int high = stalls[n - 1] - stalls[0]; int result = 0; while (low <= high) { int mid = low + (high - low) / 2; if (canPlace(stalls, n, k, mid)) { result = mid; /* Try larger distance */ low = mid + 1; } else { high = mid - 1; /* Try smaller distance */ } } return result; } int main(void) { int stalls1[] = {1, 2, 4, 8, 9}; int stalls2[] = {1, 2, 3, 4, 5}; printf("Aggressive Cows (k=3, stalls=[1,2,4,8,9]): %d\n", aggressiveCows(stalls1, 5, 3)); printf("Aggressive Cows (k=3, stalls=[1,2,3,4,5]): %d\n", aggressiveCows(stalls2, 5, 3)); printf("Aggressive Cows (k=2, stalls=[1,2,4,8,9]): %d\n", aggressiveCows(stalls1, 5, 2)); return 0; }

Expected output:

text

Aggressive Cows (k=3, stalls=[1,2,4,8,9]): 3 Aggressive Cows (k=3, stalls=[1,2,3,4,5]): 2 Aggressive Cows (k=2, stalls=[1,2,4,8,9]): 8

Full Practical Code Example with Explanation

This program combines all seven binary search applications into a single interactive tool.

c

/** * binary_search_applications.c * Demonstrates seven binary search applications in C. * Covers sqrt, first/last occurrence, count 1's, unbounded search, * rotated array min/search, and aggressive cows. */ #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 */ long long integerSqrt(long long n); int findFirst(const int arr[], int n, int target); int findLast(const int arr[], int n, int target); int countOnes(const int arr[], int n); int unboundedSearch(int target); int findMinRotated(const int arr[], int n); int searchRotated(const int arr[], int n, int target); int aggressiveCows(int stalls[], int n, int k); int compareInts(const void *a, const void *b); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void demoSquareRoot(void); void demoFirstLast(void); void demoCountOnes(void); void demoUnbounded(void); void demoRotatedMin(void); void demoRotatedSearch(void); void demoAggressiveCows(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Binary Search Applications Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Square Root of Integer\n"); printf("2. First and Last Position\n"); printf("3. Count 1's in Binary Array\n"); printf("4. Unbounded Binary Search\n"); printf("5. Minimum in Rotated Array\n"); printf("6. Search in Rotated Array\n"); printf("7. Aggressive Cows\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: demoSquareRoot(); break; case 2: demoFirstLast(); break; case 3: demoCountOnes(); break; case 4: demoUnbounded(); break; case 5: demoRotatedMin(); break; case 6: demoRotatedSearch(); break; case 7: demoAggressiveCows(); break; case 8: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* 1. Integer square root */ long long integerSqrt(long long n) { if (n < 0) return -1; if (n == 0 || n == 1) return n; long long low = 1, high = n, result = 1; while (low <= high) { long long mid = low + (high - low) / 2; if (mid <= n / mid) { result = mid; low = mid + 1; } else { high = mid - 1; } } return result; } /* 2. First occurrence */ int findFirst(const int arr[], int n, int target) { int low = 0, high = n - 1, result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; high = mid - 1; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; } /* 2. Last occurrence */ int findLast(const int arr[], int n, int target) { int low = 0, high = n - 1, result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; low = mid + 1; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; } /* 3. Count 1's */ int countOnes(const int arr[], int n) { int low = 0, high = n - 1, firstOne = n; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == 1) { firstOne = mid; high = mid - 1; } else { low = mid + 1; } } return n - firstOne; } /* 4. Unbounded search */ int getValue(int idx) { static int data[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}; int size = sizeof(data) / sizeof(data[0]); if (idx < 0 || idx >= size) return 1000000; return data[idx]; } int unboundedSearch(int target) { if (getValue(0) == target) return 0; int high = 1; while (getValue(high) < target) { if (high > 1000000) return -1; high *= 2; } int low = high / 2; while (low <= high) { int mid = low + (high - low) / 2; int val = getValue(mid); if (val == target) return mid; if (val < target) low = mid + 1; else high = mid - 1; } return -1; } /* 5. Minimum in rotated array */ int findMinRotated(const int arr[], int n) { if (n <= 0) return -1; int low = 0, high = n - 1; while (low < high) { if (arr[low] < arr[high]) return arr[low]; int mid = low + (high - low) / 2; if (arr[mid] > arr[high]) low = mid + 1; else high = mid; } return arr[low]; } /* 6. Search in rotated array */ int searchRotated(const int arr[], int n, int target) { int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) return mid; if (arr[low] <= arr[mid]) { if (target >= arr[low] && target < arr[mid]) high = mid - 1; else low = mid + 1; } else { if (target > arr[mid] && target <= arr[high]) low = mid + 1; else high = mid - 1; } } return -1; } /* 7. Aggressive Cows */ int compareInts(const void *a, const void *b) { int int_a = *(const int *)a; int int_b = *(const int *)b; return (int_a > int_b) - (int_a < int_b); } int canPlace(const int stalls[], int n, int k, int dist) { int count = 1; int lastPos = stalls[0]; for (int i = 1; i < n; i++) { if (stalls[i] - lastPos >= dist) { count++; lastPos = stalls[i]; if (count >= k) return 1; } } return 0; } int aggressiveCows(int stalls[], int n, int k) { if (k > n) return -1; qsort(stalls, n, sizeof(int), compareInts); int low = 1; int high = stalls[n - 1] - stalls[0]; int result = 0; while (low <= high) { int mid = low + (high - low) / 2; if (canPlace(stalls, n, k, mid)) { result = mid; low = mid + 1; } else { high = mid - 1; } } return result; } /* Print 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"); } /* Demos */ void demoSquareRoot(void) { printf("\n=== Integer Square Root ===\n"); long long tests[] = {0, 1, 4, 8, 16, 25, 100, 999999999}; int count = sizeof(tests) / sizeof(tests[0]); for (int i = 0; i < count; i++) { printf("sqrt(%lld) = %lld\n", tests[i], integerSqrt(tests[i])); } } void demoFirstLast(void) { printf("\n=== First and Last Position ===\n"); int arr[] = {1, 2, 2, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); printf("Array: "); printArray(arr, n); int target = 2; int first = findFirst(arr, n, target); int last = findLast(arr, n, target); if (first == -1) printf("%d not found\n", target); else printf("First: %d, Last: %d, Count: %d\n", first, last, last - first + 1); } void demoCountOnes(void) { printf("\n=== Count 1's in Sorted Binary Array ===\n"); int arr1[] = {0, 0, 0, 1, 1, 1, 1}; int arr2[] = {0, 0, 0, 0}; int arr3[] = {1, 1, 1, 1}; printf("arr1: "); printArray(arr1, 7); printf(" Count 1's: %d\n", countOnes(arr1, 7)); printf("arr2: "); printArray(arr2, 4); printf(" Count 1's: %d\n", countOnes(arr2, 4)); printf("arr3: "); printArray(arr3, 4); printf(" Count 1's: %d\n", countOnes(arr3, 4)); } void demoUnbounded(void) { printf("\n=== Unbounded Binary Search ===\n"); int targets[] = {1, 9, 29, 30}; int count = sizeof(targets) / sizeof(targets[0]); for (int i = 0; i < count; i++) { int r = unboundedSearch(targets[i]); if (r == -1) printf("Target %d: Not found\n", targets[i]); else printf("Target %d: Index %d\n", targets[i], r); } } void demoRotatedMin(void) { printf("\n=== Minimum in Sorted Rotated Array ===\n"); int arr1[] = {5, 6, 1, 2, 3, 4}; int arr2[] = {3, 1, 2}; int arr3[] = {4, 2, 3}; int arr4[] = {1, 2, 3, 4}; printf("arr1: "); printArray(arr1, 6); printf(" Min: %d\n", findMinRotated(arr1, 6)); printf("arr2: "); printArray(arr2, 3); printf(" Min: %d\n", findMinRotated(arr2, 3)); printf("arr3: "); printArray(arr3, 3); printf(" Min: %d\n", findMinRotated(arr3, 3)); printf("arr4: "); printArray(arr4, 4); printf(" Min: %d\n", findMinRotated(arr4, 4)); } void demoRotatedSearch(void) { printf("\n=== Search in Sorted Rotated Array ===\n"); int arr[] = {5, 6, 7, 8, 9, 1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("Array: "); printArray(arr, n); int targets[] = {5, 1, 3, 8, 10, 0}; int count = sizeof(targets) / sizeof(targets[0]); for (int i = 0; i < count; i++) { int r = searchRotated(arr, n, targets[i]); if (r == -1) printf("Target %d: Not found\n", targets[i]); else printf("Target %d: Index %d\n", targets[i], r); } } void demoAggressiveCows(void) { printf("\n=== Aggressive Cows ===\n"); int stalls1[] = {1, 2, 4, 8, 9}; int stalls2[] = {1, 2, 3, 4, 5}; printf("stalls=[1,2,4,8,9], k=3 → %d\n", aggressiveCows(stalls1, 5, 3)); printf("stalls=[1,2,3,4,5], k=3 → %d\n", aggressiveCows(stalls2, 5, 3)); printf("stalls=[1,2,4,8,9], k=2 → %d\n", aggressiveCows(stalls1, 5, 2)); } /* Read 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; }

Expected Output (sample run)

text

=== Binary Search Applications Demo === --- Menu --- 1. Square Root of Integer 2. First and Last Position 3. Count 1's in Binary Array 4. Unbounded Binary Search 5. Minimum in Rotated Array 6. Search in Rotated Array 7. Aggressive Cows 8. Exit Enter choice: 1 === Integer Square Root === sqrt(0) = 0 sqrt(1) = 1 sqrt(4) = 2 sqrt(8) = 2 sqrt(16) = 4 sqrt(25) = 5 sqrt(100) = 10 sqrt(999999999) = 31622

Common Pitfalls, Edge Cases & Memory Considerations

1. Integer Overflow in mid * mid

Use mid <= n / mid instead of mid * mid <= n.

2. Infinite Loops from Non-Progress

Always update low = mid + 1 or high = mid - 1.

3. Off-by-One in Rotated Arrays

Use high = mid (not mid - 1) when arr[mid] < arr[high] to keep minimum in range.

4. Missing Check for Sorted Subarray

In rotated search, always check which half is sorted first.

5. Unbounded Search Safety

Include an upper bound to prevent infinite doubling.

6. Aggressive Cows: Sorting Required

Always sort stall positions first.

7. First/Last Occurrence Initialization

Initialize result = -1 and update only on match.

8. Empty Arrays

Return sentinel values (-1) for empty inputs.

9. Duplicates in Rotated Arrays

The minimum in rotated array with duplicates can be ambiguous; linear fallback may be needed.

10. Memory Considerations

  • All seven algorithms use O(1) extra space.
  • No dynamic allocation required.
  • Use long long for integer sqrt to avoid overflow.

Summary & Best Practices

Binary search is a versatile technique that extends far beyond simple searching. The seven applications in this tutorial demonstrate its power across mathematical, structural, and optimization problems.

Key Takeaways

ProblemKey Insight
Square RootBinary search on answer with overflow-safe comparison
First/Last PositionBias search direction based on requirement
Count 1’sFind first 1; count = n – index
Unbounded SearchExponential doubling then binary search
Min in RotatedCompare mid with high
Search in RotatedOne half always sorted
Aggressive CowsBinary search on distance with feasibility check

Best Practices

  1. Use low + (high - low) / 2 to avoid overflow.
  2. Ensure monotonicity before applying binary search.
  3. Check both halves’ sorted status in rotated arrays.
  4. Bias first/last occurrence searches appropriately.
  5. Include safety bounds in unbounded search.
  6. Sort input for aggressive cows.
  7. Use long long for large computations (square root).
  8. Handle edge cases: empty, single element, duplicates.
  9. Verify with brute force during testing.
  10. Profile for large inputs.

By mastering these seven applications, you’ll be well-equipped to solve a wide range of binary search problems in competitive programming and technical interviews.