Hash tables are among the most fundamental and useful data structures in computer science. They provide O(1) average-case time complexity for insertions, deletions, and lookups, making them invaluable for everything from caching to symbol tables. This guide walks you through building a simple yet functional hash table in C from the ground up.

What is a Hash Table?

A hash table is a data structure that maps keys to values using a hash function. The hash function computes an index into an array of buckets, where the key-value pair is stored.

Key: "apple" → Hash Function → Index: 3 → [Bucket 3] → Value: "red" Key: "banana" → Hash Function → Index: 7 → [Bucket 7] → Value: "yellow"

Core Components

Hash Function: Converts a key into an array index
Array (Buckets): Stores the key-value pairs
Collision Resolution: Handles when two keys hash to the same index

Simple Hash Table Structure

Let's start with the basic structure for a hash table using separate chaining (linked lists) for collision resolution.

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> // Node structure for linked list (separate chaining) typedef struct HashNode { char *key; int value; struct HashNode *next; } HashNode; // Hash table structure typedef struct { HashNode **buckets; // Array of pointers to linked lists int size; // Number of buckets int count; // Number of key-value pairs } HashTable;

Hash Function

A good hash function distributes keys uniformly across the array. Here's a simple but effective string hash function (djb2 by Dan Bernstein):

// djb2 hash function - simple and effective unsigned long hash(const char *str, int table_size) { unsigned long hash = 5381; int c; while ((c = *str++)) { hash = ((hash << 5) + hash) + c; // hash * 33 + c } return hash % table_size; }

Creating and Destroying Hash Table

// Create a new hash table HashTable* ht_create(int size) { HashTable *table = (HashTable*)malloc(sizeof(HashTable)); if (table == NULL) { fprintf(stderr, "Memory allocation failed\n"); return NULL; } table->size = size; table->count = 0; // Allocate array of bucket pointers table->buckets = (HashNode**)calloc(size, sizeof(HashNode*)); if (table->buckets == NULL) { free(table); fprintf(stderr, "Memory allocation failed\n"); return NULL; } return table; } // Create a new node HashNode* create_node(const char *key, int value) { HashNode *node = (HashNode*)malloc(sizeof(HashNode)); if (node == NULL) return NULL; node->key = (char*)malloc(strlen(key) + 1); if (node->key == NULL) { free(node); return NULL; } strcpy(node->key, key); node->value = value; node->next = NULL; return node; } // Free a node void free_node(HashNode *node) { if (node) { free(node->key); free(node); } } // Destroy hash table void ht_destroy(HashTable *table) { if (table == NULL) return; // Free all nodes in all buckets for (int i = 0; i < table->size; i++) { HashNode *current = table->buckets[i]; while (current != NULL) { HashNode *temp = current; current = current->next; free_node(temp); } } free(table->buckets); free(table); }

Insert Operation

// Insert a key-value pair bool ht_insert(HashTable *table, const char *key, int value) { if (table == NULL || key == NULL) return false; // Compute hash index int index = hash(key, table->size); // Check if key already exists HashNode *current = table->buckets[index]; while (current != NULL) { if (strcmp(current->key, key) == 0) { // Key exists - update value current->value = value; return true; } current = current->next; } // Key doesn't exist - create new node HashNode *new_node = create_node(key, value); if (new_node == NULL) return false; // Insert at beginning of linked list new_node->next = table->buckets[index]; table->buckets[index] = new_node; table->count++; return true; }

Search Operation

// Search for a key, return value if found int ht_search(HashTable *table, const char *key, bool *found) { if (table == NULL || key == NULL) { *found = false; return 0; } int index = hash(key, table->size); HashNode *current = table->buckets[index]; while (current != NULL) { if (strcmp(current->key, key) == 0) { *found = true; return current->value; } current = current->next; } *found = false; return 0; } // Simplified version that returns pointer to value int* ht_get(HashTable *table, const char *key) { if (table == NULL || key == NULL) return NULL; int index = hash(key, table->size); HashNode *current = table->buckets[index]; while (current != NULL) { if (strcmp(current->key, key) == 0) { return &current->value; } current = current->next; } return NULL; }

Delete Operation

// Delete a key-value pair bool ht_delete(HashTable *table, const char *key) { if (table == NULL || key == NULL) return false; int index = hash(key, table->size); HashNode *current = table->buckets[index]; HashNode *prev = NULL; while (current != NULL) { if (strcmp(current->key, key) == 0) { // Found the node to delete if (prev == NULL) { // Node is at the head of the list table->buckets[index] = current->next; } else { prev->next = current->next; } free_node(current); table->count--; return true; } prev = current; current = current->next; } return false; // Key not found }

Utility Functions

// Get the number of key-value pairs int ht_size(HashTable *table) { return table ? table->count : 0; } // Check if the hash table is empty bool ht_is_empty(HashTable *table) { return table ? table->count == 0 : true; } // Clear all entries (remove all key-value pairs) void ht_clear(HashTable *table) { if (table == NULL) return; for (int i = 0; i < table->size; i++) { HashNode *current = table->buckets[i]; while (current != NULL) { HashNode *temp = current; current = current->next; free_node(temp); } table->buckets[i] = NULL; } table->count = 0; } // Check if a key exists bool ht_contains(HashTable *table, const char *key) { if (table == NULL || key == NULL) return false; int index = hash(key, table->size); HashNode *current = table->buckets[index]; while (current != NULL) { if (strcmp(current->key, key) == 0) { return true; } current = current->next; } return false; }

Iteration

// Simple iterator structure typedef struct { HashTable *table; int bucket_index; HashNode *current_node; } HashIterator; // Create an iterator HashIterator* ht_iterator_create(HashTable *table) { HashIterator *iter = (HashIterator*)malloc(sizeof(HashIterator)); if (iter == NULL) return NULL; iter->table = table; iter->bucket_index = -1; iter->current_node = NULL; return iter; } // Get next key-value pair bool ht_iterator_next(HashIterator *iter, char **key, int *value) { if (iter == NULL || iter->table == NULL) return false; // Move to next non-empty bucket if (iter->current_node != NULL) { iter->current_node = iter->current_node->next; } while (iter->current_node == NULL) { iter->bucket_index++; if (iter->bucket_index >= iter->table->size) { return false; // No more entries } iter->current_node = iter->table->buckets[iter->bucket_index]; } *key = iter->current_node->key; *value = iter->current_node->value; return true; } // Destroy iterator void ht_iterator_destroy(HashIterator *iter) { free(iter); }

Display and Statistics

// Print all key-value pairs void ht_print(HashTable *table) { if (table == NULL) { printf("Hash table is NULL\n"); return; } printf("Hash Table (size=%d, count=%d):\n", table->size, table->count); for (int i = 0; i < table->size; i++) { if (table->buckets[i] != NULL) { printf(" Bucket %d: ", i); HashNode *current = table->buckets[i]; while (current != NULL) { printf("(%s: %d) ", current->key, current->value); current = current->next; } printf("\n"); } } } // Print hash table statistics void ht_print_stats(HashTable *table) { if (table == NULL) return; printf("\n=== Hash Table Statistics ===\n"); printf("Table size: %d\n", table->size); printf("Number of entries: %d\n", table->count); printf("Load factor: %.2f\n", (float)table->count / table->size); int max_chain = 0; int empty_buckets = 0; int total_chain_length = 0; for (int i = 0; i < table->size; i++) { int chain_length = 0; HashNode *current = table->buckets[i]; while (current != NULL) { chain_length++; current = current->next; } if (chain_length == 0) { empty_buckets++; } if (chain_length > max_chain) { max_chain = chain_length; } total_chain_length += chain_length; } printf("Empty buckets: %d (%.2f%%)\n", empty_buckets, (float)empty_buckets / table->size * 100); printf("Max chain length: %d\n", max_chain); printf("Average chain length: %.2f\n", (float)total_chain_length / table->size); }

Complete Example Program

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> // Include all the function definitions above int main() { printf("=== Simple Hash Table Demo ===\n\n"); // Create a hash table with 10 buckets HashTable *table = ht_create(10); // Insert some values printf("1. Inserting values:\n"); ht_insert(table, "apple", 10); ht_insert(table, "banana", 20); ht_insert(table, "orange", 30); ht_insert(table, "grape", 40); ht_insert(table, "watermelon", 50); ht_insert(table, "mango", 60); printf(" Inserted 6 items\n"); ht_print_stats(table); // Display all entries printf("\n2. Displaying all entries:\n"); ht_print(table); // Search for values printf("\n3. Searching:\n"); const char *keys[] = {"apple", "banana", "grape", "kiwi"}; for (int i = 0; i < 4; i++) { int *value = ht_get(table, keys[i]); if (value != NULL) { printf(" %s -> %d\n", keys[i], *value); } else { printf(" %s -> not found\n", keys[i]); } } // Update a value printf("\n4. Updating value:\n"); printf(" Before: apple -> %d\n", *ht_get(table, "apple")); ht_insert(table, "apple", 100); printf(" After: apple -> %d\n", *ht_get(table, "apple")); // Delete a value printf("\n5. Deleting:\n"); printf(" Deleting 'banana': %s\n", ht_delete(table, "banana") ? "success" : "failed"); printf(" Deleting 'kiwi': %s\n", ht_delete(table, "kiwi") ? "success" : "failed"); ht_print_stats(table); // Iterate through all entries printf("\n6. Iterating through entries:\n"); HashIterator *iter = ht_iterator_create(table); char *key; int value; while (ht_iterator_next(iter, &key, &value)) { printf(" %s: %d\n", key, value); } ht_iterator_destroy(iter); // Check if key exists printf("\n7. Contains checks:\n"); printf(" Contains 'apple': %s\n", ht_contains(table, "apple") ? "yes" : "no"); printf(" Contains 'banana': %s\n", ht_contains(table, "banana") ? "yes" : "no"); // Clear the table printf("\n8. Clearing table:\n"); ht_clear(table); printf(" Size after clear: %d\n", ht_size(table)); printf(" Is empty: %s\n", ht_is_empty(table) ? "yes" : "no"); // Clean up ht_destroy(table); printf("\n=== Demo Complete ===\n"); return 0; }

Collision Resolution: Open Addressing (Alternative)

For completeness, here's a simple open addressing implementation:

// Open addressing hash table typedef struct { char **keys; int *values; int *occupied; // 1 if occupied, 0 if empty int size; int count; } OpenHashTable; OpenHashTable* oht_create(int size) { OpenHashTable *table = (OpenHashTable*)malloc(sizeof(OpenHashTable)); table->keys = (char**)calloc(size, sizeof(char*)); table->values = (int*)calloc(size, sizeof(int)); table->occupied = (int*)calloc(size, sizeof(int)); table->size = size; table->count = 0; return table; } // Linear probing insertion bool oht_insert(OpenHashTable *table, const char *key, int value) { if (table->count >= table->size) return false; int index = hash(key, table->size); int original_index = index; // Linear probing while (table->occupied[index]) { if (table->keys[index] && strcmp(table->keys[index], key) == 0) { // Update existing key table->values[index] = value; return true; } index = (index + 1) % table->size; if (index == original_index) return false; // Table is full } // Insert new key table->keys[index] = (char*)malloc(strlen(key) + 1); strcpy(table->keys[index], key); table->values[index] = value; table->occupied[index] = 1; table->count++; return true; } // Linear probing search int* oht_get(OpenHashTable *table, const char *key) { int index = hash(key, table->size); int original_index = index; while (table->occupied[index]) { if (table->keys[index] && strcmp(table->keys[index], key) == 0) { return &table->values[index]; } index = (index + 1) % table->size; if (index == original_index) break; } return NULL; }

Performance Testing

#include <time.h> void performance_test() { const int NUM_OPERATIONS = 50000; const int TABLE_SIZE = 10000; HashTable *table = ht_create(TABLE_SIZE); // Test insertion clock_t start = clock(); for (int i = 0; i < NUM_OPERATIONS; i++) { char key[32]; sprintf(key, "key_%d", i); ht_insert(table, key, i); } clock_t end = clock(); double insert_time = (double)(end - start) / CLOCKS_PER_SEC; // Test lookup start = clock(); for (int i = 0; i < NUM_OPERATIONS; i++) { char key[32]; sprintf(key, "key_%d", i); ht_get(table, key); } end = clock(); double lookup_time = (double)(end - start) / CLOCKS_PER_SEC; printf("\n=== Performance Results ===\n"); printf("Insert %d items: %.3f seconds\n", NUM_OPERATIONS, insert_time); printf("Lookup %d items: %.3f seconds\n", NUM_OPERATIONS, lookup_time); printf("Load factor: %.2f\n", (float)NUM_OPERATIONS / TABLE_SIZE); ht_destroy(table); }

Best Practices

Choose a good hash function: Distribute keys uniformly across buckets
Pick appropriate table size: Prime numbers often work well
Monitor load factor: Consider resizing when load factor > 0.75
Handle collisions properly: Separate chaining is simpler, open addressing more memory-efficient
Free memory correctly: Always free keys and nodes
Check for NULL pointers: Always validate input
Use consistent key comparisons: For strings, use strcmp()

Common Pitfalls

// DON'T: Forgetting to check for NULL ht_insert(table, NULL, 10); // Will crash // DO: Check input bool ht_insert(HashTable *table, const char *key, int value) { if (table == NULL || key == NULL) return false; // ... } // DON'T: Using a poor hash function unsigned long bad_hash(const char *str) { return strlen(str) % size; // Very poor distribution } // DON'T: Not handling collisions // Always implement collision resolution // DON'T: Memory leak // Always free allocated memory

Conclusion

This simple hash table implementation provides a solid foundation for understanding how hash tables work. The key concepts covered include:

Hash functions: Converting keys to array indices
Collision resolution: Handling multiple keys that hash to the same bucket
Basic operations: Insert, search, delete
Memory management: Proper allocation and deallocation
Iteration: Traversing all key-value pairs

While this implementation is simple, it's functional and can be extended with features like dynamic resizing, generic values, or different collision resolution strategies. Understanding these fundamentals will help you build more sophisticated hash tables for your C projects.

Complete C Programming Guide + Compilers Collection

1. C srand() Function – Understanding Seed Initialization

https://macronepal.com/understanding-the-c-srand-function
Explains how srand() initializes the pseudo-random number generator in C by setting a seed value. Using the same seed produces the same sequence, while time(NULL) gives different results each run.

2. C rand() Function Mechanics and Limitations

https://macronepal.com/c-rand-function-mechanics-and-limitations
Explains how rand() generates pseudo-random numbers between 0 and RAND_MAX, its deterministic nature, and limitations for security use cases.

3. C log() Function

https://macronepal.com/c-log-function-2
Covers natural logarithm calculation using <math.h> and its applications.

4. Mastering Date and Time in C

https://macronepal.com/mastering-date-and-time-in-c
Explains <time.h> functions like time(), clock(), difftime(), and struct tm.

5. Mastering time_t Type in C

https://macronepal.com/mastering-the-c-time_t-type-for-time-management
Explains time representation as seconds since Unix epoch and conversion functions.

6. C exp() Function

https://macronepal.com/c-exp-function-mechanics-and-implementation
Explains exponential function exp(x) and its scientific applications.

7. C log() Function (Alternate Guide)

https://macronepal.com/c-log-function
Comparison of log() and log10() with usage examples.

8. C log10() Function

https://macronepal.com/mastering-the-log10-function-in-c
Explains base-10 logarithm for engineering and scientific applications.

9. C tan() Function

https://macronepal.com/understanding-the-c-tan-function
Explains tangent function and radian-based calculations.

10. Random Numbers in C (Secure vs Predictable)

https://macronepal.com/mastering-c-random-numbers-for-secure-and-predictable-applications
Explains difference between rand() and secure randomness methods.

11. Free Online C Compiler

https://macronepal.com/free-online-c-code-compiler-2
Browser-based compiler for testing C programs instantly.

C Functions, Arguments, Parameters & Flow

Mastering Functions in C – Complete Guide

https://macronepal.com/c/mastering-functions-in-c-a-complete-guide/
Covers function structure, modular programming, and real-world usage.

Function Arguments in C

https://macronepal.com/c-function-arguments/
Explains how arguments are passed and used in function calls.

Function Parameters in C

https://macronepal.com/c-function-parameters/
Explains defining inputs for functions and matching them with arguments.

Function Declarations in C

https://macronepal.com/c-function-declarations-syntax-rules-and-best-practices/
Covers prototypes, syntax rules, and best practices.

Function Calls in C

https://macronepal.com/understanding-function-calls-in-c-syntax-mechanics-and-best-practices/
Explains execution flow and parameter handling during function calls.

Void Functions in C

https://macronepal.com/understanding-void-functions-in-c-syntax-patterns-and-best-practices/
Explains functions that do not return values.

Return Values in C

https://macronepal.com/c-return-values-mechanics-types-and-best-practices/
Explains different return types and how functions return results.

Pass-by-Value in C

https://macronepal.com/aws/understanding-pass-by-value-in-c-mechanics-implications-and-best-practices/
Explains how copies of variables are passed into functions.

Pass-by-Reference in C

https://macronepal.com/c/understanding-pass-by-reference-in-c-pointers-semantics-and-safe-practices/
Explains using pointers to modify original variables.

C strstr() Function

https://macronepal.com/aws/c-strstr-function/
Explains substring search inside strings in C.

C Preprocessor & Macros

C Structures, Memory, Scope & Linkage

C Scope, Storage Classes & Typedef

Extra Articles

https://macronepal.com/13757-2/
https://macronepal.com/13748-2/
https://macronepal.com/13747-2/
https://macronepal.com/13746-2/
https://macronepal.com/13745-2/
https://macronepal.com/13708-2/
https://macronepal.com/13707-2/
https://macronepal.com/13702-2/

Online Compilers