C Program To Implement Dictionary Using Hashing Algorithms 〈HD 2024〉

The load factor (\alpha = \fracnm), where (n) is the number of stored elements and (m) is the table size. When (\alpha) exceeds a threshold (e.g., 0.75 for chaining, though chaining allows >1), performance degrades. To counter this, the table is resized (usually doubled) and all existing keys are rehashed into the new table. This operation is (O(n)) but occurs infrequently, amortizing to (O(1)) per insertion.

The load factor (α = count / size) affects performance. When α exceeds a threshold (typically 0.7–0.75), the dictionary should resize.

void resize(HashTable **dict, int new_size) 
    HashTable *old_dict = *dict;
    HashTable *new_dict = create_dict(new_size);
// Rehash all entries
for (int i = 0; i < old_dict->size; i++) 
    Entry *curr = old_dict->buckets[i];
    while (curr) 
        put(new_dict, curr->key, curr->value);
        curr = curr->next;
free_dict(old_dict);
*dict = new_dict;


// Call this after every insertion
void check_and_resize(HashTable **dict) 
float load = (float)(*dict)->count / (*dict)->size;
if (load > 0.75) 
resize(dict, (*dict)->size * 2);

A dictionary is an abstract data type that stores a collection of pairs (key, value). It supports three primary operations: c program to implement dictionary using hashing algorithms

The goal is to perform each of these operations in O(1) average time complexity.

A collision occurs when two different keys hash to the same table index. A robust dictionary implementation must handle collisions gracefully. Two primary strategies exist.

In the main function, notice the call to print_dictionary. Because we used Separate Chaining, you can visually see collisions. If "apple" and "banana" (hypothetically) hashed to the same index, the output would show:

Index [5]: (banana: 20) -> (apple: 15) -> NULL

This structure ensures that even if collisions occur, no data is lost, and performance degrades gracefully (linearly with chain length) rather than failing or requiring complex re-probing loops.

In computer science, a dictionary (also known as a map, associative array, or symbol table) is a data structure that stores key-value pairs. It provides efficient insertion, deletion, and lookup operations. When implementing a dictionary in C—a language without built-in associative arrays—hashing algorithms offer the most practical and performant solution. The load factor (\alpha = \fracnm), where (n)

This article walks through a complete implementation of a dictionary using separate chaining with a hash table, covering the core principles, collision resolution, memory management, and performance considerations.

The hash function is the heart of any hashing implementation. A good hash function for a dictionary should be:

For string keys (common in dictionaries), a popular choice is the DJB2 algorithm (designed by Daniel J. Bernstein), which is simple and yields good distribution:

unsigned long hash(char *str) 
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) 
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;

The index is then computed as hash(key) % table_size. Choosing a prime number for table_size further improves distribution.

Here is a working example that ties everything together: A dictionary is an abstract data type that

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// [Include all the functions defined above: hash_djb2, create_hash_table,
//  insert, search, delete_key, display, destroy_hash_table]
int main() 
// Create a dictionary with 10007 buckets
HashTable *dict = create_hash_table(TABLE_SIZE);
if (!dict) 
printf("Failed to create dictionary\n");
return 1;

printf("=== Dictionary Implementation using Hashing in C ===\n\n");
// Insert some key-value pairs
printf("Inserting entries...\n");
insert(dict, "apple", 10);
insert(dict, "banana", 20);
insert(dict, "orange", 30);
insert(dict, "grape", 40);
insert(dict, "apple", 99);  // Update existing key
display(dict);
// Search for keys
printf("\nSearching for keys:\n");
int found;
int value = search(dict, "banana", &found);
if (found) printf("banana -> %d\n", value);
else printf("banana not found\n");
value = search(dict, "kiwi", &found);
if (found) printf("kiwi -> %d\n", value);
else printf("kiwi not found\n");
// Delete a key
printf("\nDeleting 'orange'...\n");
if (delete_key(dict, "orange")) 
    printf("'orange' deleted successfully.\n");
 else 
    printf("'orange' not found.\n");
display(dict);
// Check dictionary size
printf("\nTotal number of key-value pairs: %d\n", dict->count);
// Cleanup
destroy_hash_table(dict);
return 0;

Expected Output:

=== Dictionary Implementation using Hashing in C ===
Inserting entries...