C Program To Implement Dictionary Using Hashing Algorithms 〈No Survey〉

Building a High-Performance Dictionary in C: A Complete Guide to Hashing Algorithms

Why Separate Chaining?

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.

Chapter 5: Complete Example Program

Here is a working example that ties everything together:

#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...


Why Hashing for a Dictionary?


Before writing code, we must understand why hashing is the preferred method for dictionary implementation.


A dictionary needs three core operations: c program to implement dictionary using hashing algorithms


    

  1. Insert(key, value) – Store a pair.
    2. 

  2. Search(key) – Retrieve the value for a given key.
    3. 

  3. Delete(key) – Remove a key-value pair.
    4. 



If you use an array (sorted), search is O(log n) with binary search, but insert/delete are O(n). If you use a linked list, search is O(n). Hashing transforms this by using a hash function to convert the key into an integer index, allowing direct access to an array slot. In an ideal scenario, all operations are O(1).




The Hash Function


We need a deterministic function that converts a string into an integer. A popular choice is the djb2 algorithm (by Daniel J. Bernstein), which uses bit shifting to generate a well-distributed hash.


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;





Insert (or update) a key-value pair


void put(Dictionary* dict, const char* key, int value) 
    int index = hash(key, dict->size);
    Entry* curr = dict->buckets[index];

// Check if key already exists
while (curr != NULL) 
    if (strcmp(curr->key, key) == 0) 
        curr->value = value;  // update
        return;
curr = curr->next;
// Insert new node at head of chain
Entry* new_entry = (Entry*)malloc(sizeof(Entry));
new_entry->key = strdup(key);
new_entry->value = value;
new_entry->next = dict->buckets[index];
dict->buckets[index] = new_entry;
dict->count++;







Step 4: Alternative Implementation – Open Addressing (Linear Probing)


While separate chaining is robust, open addressing saves memory by storing entries directly in the array. Here’s a simplified version using linear probing. Building a High-Performance Dictionary in C: A Complete


typedef struct 
    char *key;
    char *value;
    int is_occupied; // Tombstone support for deletions
 HashEntry;

typedef struct 
HashEntry *entries;
unsigned long size;
unsigned long count;
 ProbeDict;


unsigned long find_slot(ProbeDict *dict, const char *key) 
unsigned long hash = hash_djb2(key);
unsigned long index = hash % dict->size;
unsigned long original = index;


while (dict->entries[index].is_occupied) 
    if (dict->entries[index].key && strcmp(dict->entries[index].key, key) == 0) 
        return index; // Found
index = (index + 1) % dict->size;
    if (index == original) break; // Full table
return index; // Empty slot or tombstone







Pros of probing: Better cache locality.

Cons: Clustering issues, more complex deletions (require tombstones). This structure ensures that even if collisions occur,




3. Dictionary Operations


1. Abstract


This report presents the design and implementation of a dictionary data structure in the C programming language using hashing techniques. A dictionary, also known as a symbol table or associative array, stores key-value pairs and supports efficient insertion, search, and deletion operations. Hashing provides average-case O(1) time complexity for these operations. This implementation uses separate chaining to handle collisions and a simple polynomial rolling hash function for strings.