C Program To Implement Dictionary Using Hashing Algorithms

Essay: Implementing a Dictionary Using Hashing Algorithms in C

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.

The djb2 Algorithm (by Dan Bernstein)

Simple, fast, and provides good distribution. c program to implement dictionary using hashing algorithms

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

3. Dictionary Operations

Common Pitfalls

• Memory leaks - Always free keys and entries
• Modifying keys after insertion - Keys should be immutable
• Poor hash distribution - Test your hash function with expected data
• Ignoring load factor - Leads to degraded performance

Step 7: Advanced Optimizations

To take your dictionary to the next level, consider these improvements: Essay: Implementing a Dictionary Using Hashing Algorithms in

Get value by key

int get(Dictionary* dict, const char* key, int* found) 
    int index = hash(key, dict->size);
    Entry* curr = dict->buckets[index];
    while (curr != NULL) 
        if (strcmp(curr->key, key) == 0) 
            *found = 1;
            return curr->value;
curr = curr->next;
*found = 0;
    return -1;

3.4 Delete Function

Deletion requires careful pointer management. Memory leaks - Always free keys and entries

int delete_key(Dictionary *dict, const char *key) 
    unsigned long hash = dict->hash_func(key);
    unsigned long index = hash % dict->size;
Entry *curr = dict->buckets[index];
Entry *prev = NULL;
while (curr) 
    if (strcmp(curr->key, key) == 0) 
        if (prev) 
            prev->next = curr->next;
         else 
            dict->buckets[index] = curr->next;
free(curr->key);
        free(curr->value);
        free(curr);
        dict->count--;
        return 1; // Success
prev = curr;
    curr = curr->next;
return 0; // Key not found

3.2 Hash Function: Polynomial Rolling Hash

For string keys, we use a polynomial hash: [ \texthash = \sum_i=0^n-1 \textstr[i] \times p^i \mod M ] Where ( p ) is a prime (e.g., 31 or 131), and ( M ) is the table size (a prime number to distribute keys better).