#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_BUCKET_COUNT 16
/* Key-value entry mapping integer keys to string values */
typedef struct {
int key;
char* value;
} KeyValueEntry;
/* Container for returning collection of entries/keys/values */
typedef struct {
void* data;
int element_count;
} CollectionResult;
/* Simple hash table implementation backed by fixed-size array */
typedef struct {
KeyValueEntry* buckets[HASH_BUCKET_COUNT];
} SimpleArrayHashTable;
/* Hash function mapping integer keys to bucket indices */
static int hash_calculate(int key) {
return abs(key) % HASH_BUCKET_COUNT;
}
/* Initialize new empty array-backed hash table */
SimpleArrayHashTable* init_simple_hash_table() {
SimpleArrayHashTable* table = calloc(1, sizeof(SimpleArrayHashTable));
return table;
}
/* Free all memory associated with the hash table */
void destroy_simple_hash_table(SimpleArrayHashTable* table) {
for (int i = 0; i < HASH_BUCKET_COUNT; i++) {
if (table->buckets[i] != NULL) {
free(table->buckets[i]->value);
free(table->buckets[i]);
}
}
free(table);
}
/* Insert or update key-value pair in hash table */
void hash_table_put(SimpleArrayHashTable* table, const int key, const char* value) {
KeyValueEntry* entry = malloc(sizeof(KeyValueEntry));
entry->key = key;
entry->value = malloc(strlen(value) + 1);
strcpy(entry->value, value);
int bucket_idx = hash_calculate(key);
// Overwrite existing entry at this index (no collision handling)
if (table->buckets[bucket_idx] != NULL) {
free(table->buckets[bucket_idx]->value);
free(table->buckets[bucket_idx]);
}
table->buckets[bucket_idx] = entry;
}
/* Remove entry with specified key from hash table */
void hash_table_remove(SimpleArrayHashTable* table, const int key) {
int bucket_idx = hash_calculate(key);
if (table->buckets[bucket_idx] != NULL) {
free(table->buckets[bucket_idx]->value);
free(table->buckets[bucket_idx]);
table->buckets[bucket_idx] = NULL;
}
}
/* Retrieve all key-value pairs stored in the hash table */
void hash_table_get_all_entries(SimpleArrayHashTable* table, CollectionResult* result) {
int valid_entries = 0;
// First count non-null buckets
for (int i = 0; i < HASH_BUCKET_COUNT; i++) {
if (table->buckets[i] != NULL) valid_entries++;
}
KeyValueEntry* entries = malloc(sizeof(KeyValueEntry) * valid_entries);
int write_pos = 0;
for (int i = 0; i < HASH_BUCKET_COUNT; i++) {
if (table->buckets[i] != NULL) {
entries[write_pos].key = table->buckets[i]->key;
entries[write_pos].value = malloc(strlen(table->buckets[i]->value) + 1);
strcpy(entries[write_pos].value, table->buckets[i]->value);
write_pos++;
}
}
result->data = entries;
result->element_count = valid_entries;
}
/* Retrieve all keys stored in the hash table */
void hash_table_get_all_keys(SimpleArrayHashTable* table, CollectionResult* result) {
int valid_entries = 0;
for (int i = 0; i < HASH_BUCKET_COUNT; i++) {
if (table->buckets[i] != NULL) valid_entries++;
}
int* keys = malloc(sizeof(int) * valid_entries);
int write_pos = 0;
for (int i = 0; i < HASH_BUCKET_COUNT; i++) {
if (table->buckets[i] != NULL) {
keys[write_pos] = table->buckets[i]->key;
write_pos++;
}
}
result->data = keys;
result->element_count = valid_entries;
}
/* Retrieve all values stored in the hash table */
void hash_table_get_all_values(SimpleArrayHashTable* table, CollectionResult* result) {
int valid_entries = 0;
for (int i = 0; i < HASH_BUCKET_COUNT; i++) {
if (table->buckets[i] != NULL) valid_entries++;
}
char** values = malloc(sizeof(char*) * valid_entries);
int write_pos = 0;
for (int i = 0; i < HASH_BUCKET_COUNT; i++) {
if (table->buckets[i] != NULL) {
values[write_pos] = table->buckets[i]->value;
write_pos++;
}
}
result->data = values;
result->element_count = valid_entries;
}
/* Print all contents of the hash table to stdout */
void hash_table_print(SimpleArrayHashTable* table) {
CollectionResult res;
hash_table_get_all_entries(table, &res);
KeyValueEntry* entries = (KeyValueEntry*)res.data;
for (int i = 0; i < res.element_count; i++) {
printf("%d => %s\n", entries[i].key, entries[i].value);
free(entries[i].value);
}
free(res.data);
}
The above implementation uses a fixed-size array as buckets, with a hash function that maps integer keys directly to array indices. This naive implementation overwrites existing entries when two different keys map to the same index, a problem referred to as hash collision.
Since the input space for keys is almost always far larger than the number of available buckets, collisions are theoretically unavoidable. Increasing bucket count reduces collision probability but increases memory overhead, so rehashing (resizing the bucket array and reindexing all entries) is only triggered when necessary. The load factor, calculated as the number of stored entries divided by total bucket count, is the standard metric for triggering resizing operations. For example, Java's HashMap resizes to 2x its original capacity when the load factor exceeds 0.75.
Two primary approaches exist to handle collisions without immediate resizing: separate chaining and open addressing.
Separate Chaining
Separate chaining stores all entries that map to the same bucket in a linked list attached to that bucket. The implementation below uses linked lists, dynamic resizing, and load factor monitoring:
/* Linked list node for chained hash table entries */
typedef struct ListNode {
KeyValueEntry* entry;
struct ListNode* next;
} ListNode;
/* Hash table implementation with separate chaining collision handling */
typedef struct {
int entry_count;
int bucket_count;
double resize_threshold;
int resize_multiplier;
ListNode** buckets;
} ChainedHashTable;
/* Calculate bucket index for given key */
static int chained_hash_calculate(ChainedHashTable* table, int key) {
return abs(key) % table->bucket_count;
}
/* Compute current load factor of the hash table */
static double chained_load_factor(ChainedHashTable* table) {
return (double)table->entry_count / (double)table->bucket_count;
}
/* Initialize new chained hash table with default parameters */
ChainedHashTable* init_chained_hash_table() {
ChainedHashTable* table = malloc(sizeof(ChainedHashTable));
table->entry_count = 0;
table->bucket_count = 4;
table->resize_threshold = 0.75;
table->resize_multiplier = 2;
table->buckets = calloc(table->bucket_count, sizeof(ListNode*));
return table;
}
/* Free all memory used by the chained hash table */
void destroy_chained_hash_table(ChainedHashTable* table) {
for (int i = 0; i < table->bucket_count; i++) {
ListNode* current = table->buckets[i];
while (current != NULL) {
ListNode* temp = current;
current = current->next;
free(temp->entry->value);
free(temp->entry);
free(temp);
}
}
free(table->buckets);
free(table);
}
static void chained_hash_resize(ChainedHashTable* table);
/* Insert or update key-value pair in chained hash table */
void chained_hash_put(ChainedHashTable* table, int key, const char* value) {
// Resize if load factor exceeds threshold
if (chained_load_factor(table) > table->resize_threshold) {
chained_hash_resize(table);
}
int bucket_idx = chained_hash_calculate(table, key);
// Check if key already exists in the bucket's list
ListNode* current = table->buckets[bucket_idx];
while (current != NULL) {
if (current->entry->key == key) {
free(current->entry->value);
current->entry->value = malloc(strlen(value) + 1);
strcpy(current->entry->value, value);
return;
}
current = current->next;
}
// Key not found, add new entry to head of list
KeyValueEntry* new_entry = malloc(sizeof(KeyValueEntry));
new_entry->key = key;
new_entry->value = malloc(strlen(value) + 1);
strcpy(new_entry->value, value);
ListNode* new_node = malloc(sizeof(ListNode));
new_node->entry = new_entry;
new_node->next = table->buckets[bucket_idx];
table->buckets[bucket_idx] = new_node;
table->entry_count++;
}
/* Retrieve value for given key, returns empty string if key not found */
char* chained_hash_get(ChainedHashTable* table, int key) {
int bucket_idx = chained_hash_calculate(table, key);
ListNode* current = table->buckets[bucket_idx];
while (current != NULL) {
if (current->entry->key == key) {
return current->entry->value;
}
current = current->next;
}
return "";
}
/* Remove entry with given key from hash table */
void chained_hash_remove(ChainedHashTable* table, int key) {
int bucket_idx = chained_hash_calculate(table, key);
ListNode* current = table->buckets[bucket_idx];
ListNode* prev = NULL;
while (current != NULL) {
if (current->entry->key == key) {
if (prev == NULL) {
table->buckets[bucket_idx] = current->next;
} else {
prev->next = current->next;
}
free(current->entry->value);
free(current->entry);
free(current);
table->entry_count--;
return;
}
prev = current;
current = current->next;
}
}
/* Resize hash table to larger bucket count */
static void chained_hash_resize(ChainedHashTable* table) {
int old_bucket_count = table->bucket_count;
ListNode** old_buckets = table->buckets;
table->bucket_count *= table->resize_multiplier;
table->buckets = calloc(table->bucket_count, sizeof(ListNode*));
table->entry_count = 0;
// Rehash all entries from old buckets to new
for (int i = 0; i < old_bucket_count; i++) {
ListNode* current = old_buckets[i];
while (current != NULL) {
chained_hash_put(table, current->entry->key, current->entry->value);
ListNode* temp = current;
current = current->next;
free(temp->entry->value);
free(temp->entry);
free(temp);
}
}
free(old_buckets);
}
/* Print all buckets and their contents to stdout */
void chained_hash_print(ChainedHashTable* table) {
for (int i = 0; i < table->bucket_count; i++) {
printf("Bucket %d: [", i);
ListNode* current = table->buckets[i];
while (current != NULL) {
printf("%d=>%s", current->entry->key, current->entry->value);
if (current->next != NULL) printf(", ");
current = current->next;
}
printf("]\n");
}
}
Separate chaining offers simple implementation and no hard limit on load factor, though lookup performance degrades as list lengths increase. For high-load use cases, replacing linked lists with balanced search trees such as red-black trees reduces lookup time from O(k) to O(log k), where k is the length of the bucket's list. Drawbacks include extra memory overhead for list pointers and cache inefficiency from non-contiguous memory access.
Open Addressing
Open addressing resolves collisions by probing for empty buckets in the main array instead of using auxiliary data structures. Common probing strategies include linear probing, quadratic probing, and double hashing.
Linear Probing
Linear probing uses a fixed step size (typically 1) to search for empty buckets when a collision occurs. Key operations:
- Insert: If the target bucket is occupied, move forward step by step until an empty bucket is found.
- Lookup: Follow the same probe sequence as insertion until the key is found or an empty bucket is encountered.
- Delete: Direct deletion leaves a gap that breaks probe sequences, so lazy deletion with a tombstone marker is used to mark deleted entries without breaking traversal.
The implementation below includes lazy deletion, dynamic resizing, and tombstone repositioning to optimize lookup performance:
/* Open addressing hash table with linear probing */
typedef struct {
int entry_count;
int bucket_count;
double resize_threshold;
int resize_multiplier;
KeyValueEntry** buckets;
KeyValueEntry* TOMBSTONE;
} OpenAddrHashTable;
/* Calculate base bucket index for key */
static int open_addr_hash_calculate(OpenAddrHashTable* table, int key) {
return abs(key) % table->bucket_count;
}
/* Calculate current load factor */
static double open_addr_load_factor(OpenAddrHashTable* table) {
return (double)table->entry_count / (double)table->bucket_count;
}
/* Initialize new open addressing hash table */
OpenAddrHashTable* init_open_addr_hash_table() {
OpenAddrHashTable* table = malloc(sizeof(OpenAddrHashTable));
table->entry_count = 0;
table->bucket_count = 4;
table->resize_threshold = 0.7;
table->resize_multiplier = 2;
table->buckets = calloc(table->bucket_count, sizeof(KeyValueEntry*));
// Create singleton tombstone marker for deleted entries
table->TOMBSTONE = malloc(sizeof(KeyValueEntry));
table->TOMBSTONE->key = -1;
table->TOMBSTONE->value = "-1";
return table;
}
/* Free all memory used by open addressing hash table */
void destroy_open_addr_hash_table(OpenAddrHashTable* table) {
for (int i = 0; i < table->bucket_count; i++) {
KeyValueEntry* entry = table->buckets[i];
if (entry != NULL && entry != table->TOMBSTONE) {
free(entry->value);
free(entry);
}
}
free(table->TOMBSTONE);
free(table->buckets);
free(table);
}
static void open_addr_hash_resize(OpenAddrHashTable* table);
/* Internal function to find bucket index for target key, handles probing and tombstone repositioning */
static int find_bucket_index(OpenAddrHashTable* table, int key) {
int base_idx = open_addr_hash_calculate(table, key);
int first_tombstone_idx = -1;
int current_idx = base_idx;
while (table->buckets[current_idx] != NULL) {
if (table->buckets[current_idx]->key == key) {
// Move entry to earlier tombstone position if found to optimize future lookups
if (first_tombstone_idx != -1) {
table->buckets[first_tombstone_idx] = table->buckets[current_idx];
table->buckets[current_idx] = table->TOMBSTONE;
return first_tombstone_idx;
}
return current_idx;
}
// Record first encountered tombstone
if (first_tombstone_idx == -1 && table->buckets[current_idx] == table->TOMBSTONE) {
first_tombstone_idx = current_idx;
}
current_idx = (current_idx + 1) % table->bucket_count;
}
// Return first tombstone if found, else empty bucket index
return first_tombstone_idx == -1 ? current_idx : first_tombstone_idx;
}
/* Retrieve value for given key, returns empty string if not found */
char* open_addr_hash_get(OpenAddrHashTable* table, int key) {
int idx = find_bucket_index(table, key);
if (table->buckets[idx] != NULL && table->buckets[idx] != table->TOMBSTONE) {
return table->buckets[idx]->value;
}
return "";
}
/* Insert or update key-value pair */
void open_addr_hash_put(OpenAddrHashTable* table, int key, const char* value) {
if (open_addr_load_factor(table) > table->resize_threshold) {
open_addr_hash_resize(table);
}
int idx = find_bucket_index(table, key);
// Update existing entry
if (table->buckets[idx] != NULL && table->buckets[idx] != table->TOMBSTONE) {
free(table->buckets[idx]->value);
table->buckets[idx]->value = malloc(strlen(value) + 1);
strcpy(table->buckets[idx]->value, value);
return;
}
// Insert new entry
KeyValueEntry* new_entry = malloc(sizeof(KeyValueEntry));
new_entry->key = key;
new_entry->value = malloc(strlen(value) + 1);
strcpy(new_entry->value, value);
table->buckets[idx] = new_entry;
table->entry_count++;
}
/* Remove entry with given key */
void open_addr_hash_remove(OpenAddrHashTable* table, int key) {
int idx = find_bucket_index(table, key);
if (table->buckets[idx] != NULL && table->buckets[idx] != table->TOMBSTONE) {
free(table->buckets[idx]->value);
free(table->buckets[idx]);
table->buckets[idx] = table->TOMBSTONE;
table->entry_count--;
}
}
/* Resize hash table to larger capacity */
static void open_addr_hash_resize(OpenAddrHashTable* table) {
int old_bucket_count = table->bucket_count;
KeyValueEntry** old_buckets = table->buckets;
table->bucket_count *= table->resize_multiplier;
table->buckets = calloc(table->bucket_count, sizeof(KeyValueEntry*));
table->entry_count = 0;
// Rehash all valid entries to new bucket array
for (int i = 0; i < old_bucket_count; i++) {
KeyValueEntry* entry = old_buckets[i];
if (entry != NULL && entry != table->TOMBSTONE) {
open_addr_hash_put(table, entry->key, entry->value);
free(entry->value);
free(entry);
}
}
free(old_buckets);
}
/* Print all bucket contents to stdout */
void open_addr_hash_print(OpenAddrHashTable* table) {
for (int i = 0; i < table->bucket_count; i++) {
if (table->buckets[i] == NULL) {
printf("Bucket %d: EMPTY\n", i);
} else if (table->buckets[i] == table->TOMBSTONE) {
printf("Bucket %d: DELETED\n", i);
} else {
printf("Bucket %d: %d=>%s\n", i, table->buckets[i]->key, table->buckets[i]->value);
}
}
}
Linear probing suffers from primary clustering, where long runs of occupied buckets form and increase collision probability over time.
Quadratic Probing
Quadratic probing replaces the fixed step size with steps equal to the square of the probe number (1, 4, 9, 16, ...) to reduce primary clustering effects. While it mitigates linear clustering, it still suffers from secondary clustering, and may fail to find empty buckets evenif they exist if the probe sequence does not cover the entire array.
Double Hashing
Double hashing uses multiple independent hash functions to generate probe sequences. If the first hash function returns a conflicting index, subsequent hash functions are used to calculate step sizes until an empty bucket is found. This approach minimizes clustering but adds overhead from calculating multiple hash values.
Hash Algorithm Design
The performance of a hash table depends heavily on the quality of its underlying hash function. A well-designed hash function minimizes collision probability and ensures even distribution of entries across buckets. The standard hash calculation pipeline is:
bucket_index = hash(key) % bucket_count
Required Properties of Hash Functions
For general hash table use cases:
- Determinism: The same input must always produce the same hash output.
- Efficiency: Hash calculation must be fast to avoid adding overhead to hash table operations.
- Uniform Distribution: Output values must be evenly spread across the entire possible range to minimize collisions.
For cryptographic use cases (e.g., password storage, data integrity checks), additional properties are required:
- One-Way Function: It must be computationally infeasible to derive the original input from its hash value.
- Collision Resistance: It must be extremely difficult to find two different inputs that produce the same hash value.
- Avalanche Effect: Small changes to the input must produce large, unpredictable changes to the output hash.
Common Simple Hash Functions
The following examples implement basic hash functions for string inputs, all using a large prime modulus (10^9+7) to ensure even distribution:
#define HASH_MOD 1000000007
/* Additive hash: sum of ASCII values of all characters */
int additive_hash(const char* key) {
long long hash = 0;
int len = strlen(key);
for (int i = 0; i < len; i++) {
hash = (hash + (unsigned char)key[i]) % HASH_MOD;
}
return (int)hash;
}
/* Multiplicative hash: rolling hash with prime multiplier */
int multiplicative_hash(const char* key) {
long long hash = 0;
int len = strlen(key);
for (int i = 0; i < len; i++) {
hash = (37 * hash + (unsigned char)key[i]) % HASH_MOD;
}
return (int)hash;
}
/* XOR hash: cumulative XOR of all character values */
int xor_hash(const char* key) {
int hash = 0;
int len = strlen(key);
for (int i = 0; i < len; i++) {
hash ^= (unsigned char)key[i];
}
return hash & HASH_MOD;
}
/* Rotating hash: combine bit rotation and XOR for better distribution */
int rotating_hash(const char* key) {
long long hash = 0;
int len = strlen(key);
for (int i = 0; i < len; i++) {
hash = ((hash << 5) ^ (hash >> 27) ^ (unsigned char)key[i]) % HASH_MOD;
}
return (int)hash;
}
Large prime moduli are preferred for hash calculations because they reduce the risk of periodic clustering when input keys follow a predictable pattern. Composite moduli can cause hash values to cluster if the input key sequence shares a common divisor with the modulus.
Production-Grade Hash Algorithms
For real-world applications, standardized hash algorithms are used:
- MD5: Produces 128-bit hashes, widely used for file integrity checks, though no longer considered cryptographically secure.
- SHA-1: Produces 160-bit hashes, deprecated for cryptographic use due to collision vulnerabilities.
- SHA-2: Family of algorithms (SHA-256, SHA-512) that produce 256/512-bit hashes, currently the standard for secure applications.
- SHA-3: The latest secure hash standard, designed to resist attacks that affect older SHA variants.