// Create new entry Entry *new_entry = (Entry*)malloc(sizeof(Entry)); new_entry->key = strdup(key); new_entry->value = strdup(value); new_entry->next = dict->buckets[index]; dict->buckets[index] = new_entry; dict->count++;
#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
Common probe methods:
Enter your choice: 4
Let’s go through the code section by section.
Below is a complete, compilable C program. It implements a Dictionary with String keys and Integer values.
First, define the linked list node for the chain: c program to implement dictionary using hashing algorithms
In C, a dictionary is typically implemented using a , which maps unique keys to specific values. Since C doesn't have a built-in dictionary type like Python or Java, you must build one using an array and a hashing function. 1. Define the Data Structures
Let n be the number of key‑value pairs stored, and m be the size of the hash table. The is α = n/m . Under the assumption of simple uniform hashing, the average length of each linked list is about α .
Search for a key and retrieve its value
Resizing involves creating a new larger bucket array, rehashing all entries, and freeing the old structure.
Next, define the hash table structure:
Using a hashing algorithm is the most efficient way to build a dictionary. It maps keys to specific indices in an array, offering average-case time complexities of for lookup, insertion, and deletion. 1. Core Concepts of Hashing rehashing all entries
A dictionary is a data structure that stores data in . While high-level languages like Python or Java have built-in dictionary classes, C requires manual implementation.
Is deterministic (always returns the same index for the same key). 3. Collision Resolution