C Program To Implement Dictionary Using Hashing Algorithms -

Use void* and store type information:

typedef struct 
    void *key;
    void *value;
    enum  INT, STRING, FLOAT  key_type;
 GenericEntry;

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.

To make the dictionary work with any data type, replace int value with void *value and store the size or use a union.

// Free all memory used by the hash table
void destroy_hash_table(HashTable *table) 
    if (!table) return;
for (int i = 0; i < table->size; i++) 
    KeyValuePair *current = table->buckets[i];
    while (current) 
        KeyValuePair *temp = current;
        current = current->next;
        free(temp->key);
        free(temp);
free(table->buckets);
free(table);

---

For strings, one of the most effective and simple algorithms is the DJB2 hash function, created by Daniel J. Bernstein. It provides excellent distribution and is easy to compute.

// DJB2 hash function for strings
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;

We'll also implement the SDBM hash as an alternative for comparison.

// SDBM hash function
unsigned long hash_sdbm(const char *str) 
    unsigned long hash = 0;
    int c;
while ((c = *str++)) 
    hash = c + (hash << 6) + (hash << 16) - hash;
return hash;

Index calculation: int index = hash_function(key) % table->size;

---

Let's analyze the time complexities:

| Operation | Average Case | Worst Case (All Collisions) | |-----------|-------------|-------------------------------| | Insert | O(1) | O(n) | | Search | O(1) | O(n) | | Delete | O(1) | O(n) | | Resize | O(n) amortized | O(n) |

The worst case occurs when all keys hash to the same bucket.