C Program To Implement Dictionary Using Hashing Algorithms [ 2024-2026 ]

Use void* and store type information:

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

In the realm of computer science, a dictionary (also known as a map, symbol table, or associative array) is one of the most fundamental and versatile data structures. It allows you to store key-value pairs and retrieve values in near-constant time, regardless of the size of the data. While languages like Python, Java, and C++ have built-in dictionary implementations (e.g., dict, HashMap, std::unordered_map), the C programming language does not provide a standard one. This forces C developers to implement their own dictionary from scratch.

The most efficient way to implement a dictionary in C is by using hashing algorithms. This article provides an exhaustive guide to building a robust dictionary using hashing, covering everything from the theory of hash functions to collision resolution strategies, complete with a fully functional C implementation.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 101
// A key-value pair node
typedef struct Entry 
char* key;
int value;
struct Entry* next;
 Entry; c program to implement dictionary using hashing algorithms
// Dictionary structure
typedef struct 
Entry** buckets;
int size;      // number of buckets (table size)
int count;     // number of key-value pairs stored
 Dictionary;

A dictionary is a data structure that stores data in key-value pairs. While high-level languages like Python or Java have built-in dictionary classes, C requires manual implementation.

To achieve average-case constant time complexity $O(1)$ for insertion, deletion, and lookup, we utilize Hashing. Use void* and store type information: typedef struct

The hash function is the heart of any hashing implementation. A good hash function for a dictionary should be:

For string keys (common in dictionaries), a popular choice is the DJB2 algorithm (designed by Daniel J. Bernstein), which is simple and yields good distribution:

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

The index is then computed as hash(key) % table_size. Choosing a prime number for table_size further improves distribution.

Let's build the dictionary step by step. hashFunction :