Program To Implement Dictionary Using Hashing Algorithms [portable] | C

Report: Dictionary Implementation Using Hashing Algorithms in C

3.1 Data Structure: Separate Chaining

We use an array of linked lists (buckets). Each bucket contains all key-value pairs that hash to the same index. This method is simple, handles an arbitrary number of collisions gracefully, and does not require the table to be resized as aggressively as open addressing.

Why separate chaining over open addressing?

Easier to implement deletion.
Better for high load factors.
No clustering issues.

4.4 Complete Example with Main Function

int main() 
    Dictionary* dict = create_dict(TABLE_SIZE);
put(dict, "apple", 10);
put(dict, "banana", 20);
put(dict, "grape", 30);
put(dict, "apple", 99);  // update
int found;
int val = get(dict, "banana", &found);
if (found) printf("banana -> %d\n", val);
delete_key(dict, "grape");
printf("Dictionary contains %d entries.\n", dict->count);
free_dict(dict);
return 0;

Delete a key

int delete_key(Dictionary* dict, const char* key) 
    int index = hash(key, dict->size);
    Entry* curr = dict->buckets[index];
    Entry* prev = NULL;
while (curr != NULL) 
    if (strcmp(curr->key, key) == 0) 
        if (prev == NULL) 
            // deleting head of chain
            dict->buckets[index] = curr->next;
         else 
            prev->next = curr->next;
free(curr->key);
        free(curr);
        dict->count--;
        return 1; // success
prev = curr;
    curr = curr->next;
return 0; // key not found

Complete Example Program

int main() 
    // Create dictionary
    HashTable *dict = create_dict(TABLE_SIZE);
// Insert entries
put(dict, "apple", 10);
put(dict, "banana", 20);
put(dict, "cherry", 30);
// Lookup values
int found;
int val = get(dict, "banana", &found);
if (found) 
    printf("banana -> %d\n", val);
// Update existing key
put(dict, "apple", 99);
// Delete a key
delete_key(dict, "cherry");
// Display all entries
printf("\nDictionary contents:\n");
for (int i = 0; i < dict->size; i++) 
    Entry *curr = dict->buckets[i];
    if (curr) 
        printf("Bucket %d: ", i);
        while (curr) 
            printf("(%s:%d) ", curr->key, curr->value);
            curr = curr->next;
printf("\n");
// Cleanup
free_dict(dict);
return 0;

4.2 Hash Function

unsigned long hash(const char* key, int table_size) 
    unsigned long hash_value = 0;
    int prime = 31;
    while (*key) 
        hash_value = (hash_value * prime) + (*key);
        key++;
return hash_value % table_size;