C Program To Implement Dictionary Using Hashing Algorithms

, meaning it takes the same amount of time regardless of how many words are in the dictionary.

Real-world examples include symbol tables in compilers, database indexes, caches, and configuration stores.

gcc -o hash_dict hash_dict.c -Wall ./hash_dict

Simple "sum of ASCII" functions lead to many collisions. Algorithms like djb2 or MurmurHash are much better for real-world data. c program to implement dictionary using hashing algorithms

// The hash table – an array of pointers to Entry typedef struct Dictionary Entry **buckets; int size; // number of buckets (table_size) int count; // number of stored entries Dictionary;

Provide a function to iterate over all key‑value pairs without exposing the internal linked lists. This would require a “cursor” that walks through the slots and lists.

A good hash function for a string (or integer) key should: , meaning it takes the same amount of

/*============================================================== * DICTIONARY USING HASHING WITH SEPARATE CHAINING * ------------------------------------------------------------ * Implements a dictionary (key-value store) where keys are * strings and values are integers. Collisions are resolved * using separate chaining with singly linked lists. *==============================================================*/

#include #include #include #define TABLE_SIZE 20 // Node representing a key-value pair in separate chaining typedef struct Node char* key; char* value; struct Node* next; Node; // Dictionary wrapper containing the bucket array typedef struct Dictionary Node* buckets[TABLE_SIZE]; Dictionary; // 1. The DJB2 Hashing Algorithm unsigned long hash_function(const char* str) unsigned long hash = 5381; int c; while ((c = *str++)) hash = ((hash << 5) + hash) + c; // hash * 33 + c return hash % TABLE_SIZE; // Helper function to create a new key-value node Node* create_node(const char* key, const char* value) Node* new_node = (Node*)malloc(sizeof(Node)); if (!new_node) printf("Memory allocation failed!\n"); exit(1); new_node->key = strdup(key); // Allocate memory and copy string new_node->value = strdup(value); // Allocate memory and copy string new_node->next = NULL; return new_node; // 2. Initialize Dictionary Dictionary* create_dictionary() Dictionary* dict = (Dictionary*)malloc(sizeof(Dictionary)); if (!dict) printf("Memory allocation failed!\n"); exit(1); for (int i = 0; i < TABLE_SIZE; i++) dict->buckets[i] = NULL; return dict; // 3. Insert or Update Key-Value Pairs void insert(Dictionary* dict, const char* key, const char* value) unsigned long index = hash_function(key); Node* head = dict->buckets[index]; Node* temp = head; // Check if the key already exists; if so, update its value while (temp != NULL) if (strcmp(temp->key, key) == 0) free(temp->value); temp->value = strdup(value); return; temp = temp->next; // Key does not exist; insert a new node at the beginning of the chain Node* new_node = create_node(key, value); new_node->next = dict->buckets[index]; dict->buckets[index] = new_node; // 4. Lookup / Search for a Key const char* search(Dictionary* dict, const char* key) unsigned long index = hash_function(key); Node* temp = dict->buckets[index]; while (temp != NULL) if (strcmp(temp->key, key) == 0) return temp->value; // Key found temp = temp->next; return NULL; // Key not found // 5. Delete a Key-Value Pair int delete_key(Dictionary* dict, const char* key) unsigned long index = hash_function(key); Node* temp = dict->buckets[index]; Node* prev = NULL; while (temp != NULL) if (strcmp(temp->key, key) == 0) if (prev == NULL) // Node to delete is the head of the chain dict->buckets[index] = temp->next; else // Node to delete is in the middle or end prev->next = temp->next; free(temp->key); free(temp->value); free(temp); return 1; // Deletion successful prev = temp; temp = temp->next; return 0; // Key not found // 6. Print the Entire Dictionary (For Debugging) void display_dictionary(Dictionary* dict) printf("\n--- Dictionary State ---\n"); for (int i = 0; i < TABLE_SIZE; i++) printf("Bucket [%d]: ", i); Node* temp = dict->buckets[i]; while (temp != NULL) printf("[%s -> %s] -> ", temp->key, temp->value); temp = temp->next; printf("NULL\n"); printf("------------------------\n"); // 7. Free Allocated Memory void free_dictionary(Dictionary* dict) for (int i = 0; i < TABLE_SIZE; i++) Node* temp = dict->buckets[i]; while (temp != NULL) Node* delete_target = temp; temp = temp->next; free(delete_target->key); free(delete_target->value); free(delete_target); free(dict); // Main Driver Function int main() Dictionary* my_dict = create_dictionary(); // Inserting Data insert(my_dict, "apple", "A sweet red or green fruit."); insert(my_dict, "compiler", "A program that translates source code to machine code."); insert(my_dict, "hashing", "A process of mapping data to fixed-size values."); insert(my_dict, "c_language", "A procedural, low-level programming language."); // Testing update capability insert(my_dict, "apple", "An awesome crunchy fruit."); display_dictionary(my_dict); // Searching Data const char* query = "compiler"; const char* result = search(my_dict, query); if (result) printf("\nSearch Found! '%s': %s\n", query, result); else printf("\nSearch Failed! '%s' not found.\n", query); // Deleting Data printf("\nDeleting key 'hashing'...\n"); if (delete_key(my_dict, "hashing")) printf("Successfully deleted.\n"); else printf("Key not found.\n"); display_dictionary(my_dict); // Cleanup memory free_dictionary(my_dict); return 0; Use code with caution. Detailed Code Breakdown The DJB2 Hash Algorithm

However, collisions occur when two different keys hash to the same index. A robust must handle collisions gracefully. Algorithms like djb2 or MurmurHash are much better

If you want to optimize or expand this hash table, I can help you with that. Tell me if you would like to see implemented, or if you prefer to see this re-written using linear probing instead. Share public link

The algorithm jumps straight to the index via the hash value and loops through the short linked list linearly using strcmp . Memory Cleanups

Before diving into the complete program, let us break down the architectural structs required for separate chaining. Data Structure Definitions

Enter your choice: 3 Enter key to delete: banana Deleted key 'banana'