Quick Way to Implement Dictionary in C

Learn quick way to implement dictionary in c with practical examples, diagrams, and best practices. Covers c, data-structures, dictionary development techniques with visual explanations.
Tags:
Categories:

Implementing a Dictionary (Hash Map) in C: A Quick Guide

Hero image for Quick Way to Implement Dictionary in C

Learn how to quickly implement a basic dictionary or hash map data structure in C using a simple array of linked lists for collision resolution.

Dictionaries, also known as hash maps or associative arrays, are fundamental data structures that store key-value pairs. They allow for efficient retrieval of values based on their associated keys. While C doesn't have a built-in dictionary type like many higher-level languages, you can implement one using basic C constructs. This article will guide you through creating a simple, yet effective, dictionary using an array of linked lists to handle hash collisions.

Understanding the Core Concept: Hashing and Collision Resolution

At the heart of a dictionary is a hash function. This function takes a key as input and returns an integer index, which ideally points to the location where the corresponding value is stored. However, different keys can sometimes produce the same hash index – this is known as a hash collision. To handle collisions, we typically use techniques like separate chaining or open addressing.

For this quick implementation, we'll use separate chaining, where each index in our hash table (an array) points to a linked list. If a collision occurs, the new key-value pair is simply added to the linked list at that index. When retrieving a value, we hash the key, go to the corresponding linked list, and traverse it to find the matching key.

flowchart TD
    A[Key Input] --> B{Hash Function}
    B --> C[Hash Index]
    C --> D[Hash Table Array]
    D --"Index points to"--> E[Linked List Head]
    E --> F[Node 1 (Key-Value Pair)]
    F --> G[Node 2 (Key-Value Pair)]
    G --> H[...]
    H --> I[Node N (Key-Value Pair)]
    I --"If key matches"--> J[Return Value]
    I --"If key not found"--> K[Key Not Found]

Flowchart illustrating the hash map lookup process with separate chaining.

Defining the Data Structures

We need two primary structures: one for the individual key-value pairs (nodes in our linked lists) and another for the hash table itself, which will be an array of pointers to these linked lists.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 100 // A simple, fixed size for our hash table

// Structure for a key-value pair node in the linked list
typedef struct Entry {
    char* key;
    char* value;
    struct Entry* next;
} Entry;

// Structure for the hash table itself
typedef struct Dictionary {
    Entry* table[TABLE_SIZE];
} Dictionary;

Basic data structures for the dictionary and its entries.

Implementing Essential Dictionary Functions

To make our dictionary functional, we'll need a hash function, and functions to initialize, insert, and retrieve elements. We'll also add a function to free the allocated memory.

// Simple hash function (djb2 algorithm)
unsigned long hash(const char* str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash % TABLE_SIZE;
}

// Initialize the dictionary
void initDictionary(Dictionary* dict) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        dict->table[i] = NULL;
    }
}

// Insert a key-value pair into the dictionary
void insert(Dictionary* dict, const char* key, const char* value) {
    unsigned long index = hash(key);

    // Create a new entry
    Entry* newEntry = (Entry*)malloc(sizeof(Entry));
    if (newEntry == NULL) {
        perror("Failed to allocate memory for new entry");
        exit(EXIT_FAILURE);
    }
    newEntry->key = strdup(key);
    newEntry->value = strdup(value);
    newEntry->next = NULL;

    // Handle memory allocation failures for strdup
    if (newEntry->key == NULL || newEntry->value == NULL) {
        perror("Failed to allocate memory for key/value string");
        free(newEntry->key); // Free if one succeeded
        free(newEntry->value); // Free if one succeeded
        free(newEntry); // Free the entry itself
        exit(EXIT_FAILURE);
    }

    // Check for existing key and update value
    Entry* current = dict->table[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            free(current->value); // Free old value
            current->value = strdup(value); // Update with new value
            if (current->value == NULL) {
                perror("Failed to allocate memory for updated value");
                exit(EXIT_FAILURE);
            }
            free(newEntry->key);
            free(newEntry->value);
            free(newEntry);
            return;
        }
        current = current->next;
    }

    // Add new entry to the beginning of the linked list
    newEntry->next = dict->table[index];
    dict->table[index] = newEntry;
}

// Retrieve a value by key
char* get(Dictionary* dict, const char* key) {
    unsigned long index = hash(key);
    Entry* current = dict->table[index];

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }
    return NULL; // Key not found
}

// Free all allocated memory for the dictionary
void freeDictionary(Dictionary* dict) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Entry* current = dict->table[i];
        while (current != NULL) {
            Entry* temp = current;
            current = current->next;
            free(temp->key);
            free(temp->value);
            free(temp);
        }
        dict->table[i] = NULL;
    }
}

Core functions for hashing, initialization, insertion, retrieval, and memory management.

Putting It All Together: Example Usage

Here's how you can use the dictionary implementation in a main function to store and retrieve some data.

int main() {
    Dictionary myDict;
    initDictionary(&myDict);

    // Insert some key-value pairs
    insert(&myDict, "name", "Alice");
    insert(&myDict, "age", "30");
    insert(&myDict, "city", "New York");
    insert(&myDict, "occupation", "Engineer");

    // Test retrieval
    printf("Name: %s\n", get(&myDict, "name")); // Expected: Alice
    printf("Age: %s\n", get(&myDict, "age"));   // Expected: 30
    printf("City: %s\n", get(&myDict, "city")); // Expected: New York
    printf("Country: %s\n", get(&myDict, "country") ? get(&myDict, "country") : "Not Found"); // Expected: Not Found

    // Update a value
    insert(&myDict, "age", "31");
    printf("Updated Age: %s\n", get(&myDict, "age")); // Expected: 31

    // Free allocated memory
    freeDictionary(&myDict);

    return 0;
}

Example of using the implemented dictionary.