Quick Implementation of Dictionary Data Structure in C

Fundamental Concepts of Dictionary Data Structure

A dictionary, also known as a map or associative array, is a fundamental data structure that stores data in key-value pairs, enabling efficient insertion, lookup, and deletion operations. While the C standard library doesn't provide a built-in dictionary implementation, we can leverage C's core features to create this essential data structure.

Hash Table-Based Dictionary Implementation

Hash tables represent one of the most efficient methods for implementing dictionaries. They utilize hash functions to map keys to specific array positions, facilitating rapid data access. Below is a complete hash table dictionary implementation:

struct nlist {
    struct nlist *next;
    char *name;
    char *defn;
};

#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE];

unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

struct nlist *lookup(char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np;
    return NULL;
}

struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL) {
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = strdup(name)) == NULL)
            return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else {
        free((void *) np->defn);
    }
    if ((np->defn = strdup(defn)) == NULL)
        return NULL;
    return np;
}

char *strdup(char *s)
{
    char *p;
    p = (char *) malloc(strlen(s)+1);
    if (p != NULL)
        strcpy(p, s);
    return p;
}

Hash Function Design Principles

The hash function serves as the core component of hash table implementation, responsible for transforming keys of arbitrary length into fixed-range array indices. The example implementation employs a classic multiplicative and additive combination:

hashval = *s + 31 * hashval;

This design effectively distributes string hash values, minimizing collision occurrences. The choice of 31 as the multiplier is strategic, as it's a prime number that helps reduce hash collisions.

Collision Resolution Mechanism

Hash collisions occur when different keys produce identical hash values. The example implementation utilizes chaining to handle collisions:

np->next = hashtab[hashval];
hashtab[hashval] = np;

This approach stores elements with identical hash values in linked lists. While worst-case lookup time may reach O(n), this method typically performs well in practical applications.

Array-Based Simple Implementation

For small-scale applications or educational purposes, a straightforward array-based implementation can be used:

#define MAX_SIZE 100
int size = 0;
char keys[MAX_SIZE][100];
int values[MAX_SIZE];

int getIndex(char key[])
{
    for (int i = 0; i < size; i++) {
        if (strcmp(keys[i], key) == 0) {
            return i;
        }
    }
    return -1;
}

void insert(char key[], int value)
{
    int index = getIndex(key);
    if (index == -1) {
        strcpy(keys[size], key);
        values[size] = value;
        size++;
    } else {
        values[index] = value;
    }
}

int get(char key[])
{
    int index = getIndex(key);
    if (index == -1) {
        return -1;
    } else {
        return values[index];
    }
}

Comparative Analysis of Both Implementations

The hash table implementation offers superior average-case time complexity, with O(1) average time for insertion and lookup operations, though it requires handling hash collisions and dynamic memory allocation. The array-based implementation, while simple and intuitive, suffers from performance degradation with larger datasets, exhibiting O(n) time complexity for lookup operations.

Memory Management and Error Handling

Memory management constitutes a critical consideration in hash table implementation. The example code employs the strdup function to duplicate strings, ensuring each key-value pair occupies independent memory space. Additionally, the code validates malloc return values to prevent program crashes due to memory allocation failures.

Performance Optimization Recommendations

To enhance hash table performance, consider these optimization strategies: adjust HASHSIZE to reduce collision probability; employ more sophisticated hash functions for improved distribution uniformity; and consider rehashing or alternative collision resolution methods when linked lists become excessively long.

Practical Application Scenarios

Dictionary data structures find extensive applications in C programming, including configuration file parsing, symbol table management, and cache implementation. Selecting the appropriate implementation approach requires careful consideration of specific performance requirements, data scale, and maintenance costs.