C Program To Implement Dictionary Using Hashing Algorithms May 2026

Once upon a time in the digital kingdom of , there was a chaotic library known as the Flat-File Archives

. Whenever the King (the CPU) wanted to know the meaning of a word, the Royal Librarian had to start at the very first shelf and read every single book until he found the right one. This was a "Linear Search," and it was painfully slow. One day, a clever architect named

proposed a revolutionary system. "Why search every shelf," he asked, "when the word itself can tell us exactly where it lives?" The Great Transformation Hash built a magical machine called the Hash Function

. Its job was simple: take any string of characters and turn it into a specific number—an The Formula: He decided on a method called Polynomial Rolling

. It took the ASCII value of each letter, multiplied it by a prime number, and added them up. The Constraints: Since the library only had 100 shelves (the Table Size ), he used the operator ( ) to make sure every number fit within the library's walls. The Conflict: The Collision

The system worked perfectly until two different words, "Apple" and "Sleep," both produced the same index: . This was the dreaded The architect had two choices: Open Addressing:

If Shelf 42 is full, go to 43, then 44, until you find a spot.

Hang a "Linked List" off Shelf 42. If multiple words land there, just line them up one after another. Hash chose

. It was cleaner and allowed the library to grow even if the shelves got crowded. The Blueprint (The Code)

To immortalize this system, the architect wrote it in the ancient language of TABLE_SIZE // The "Book" structure Node* next; }; // The Library (Hash Table) Node* hash_table[TABLE_SIZE]; // The Magic Machine (Hash Function) ; key[i] != ; i++) value = value * + key[i]; value % TABLE_SIZE; } // Adding a new word to the library * value) index = hash(key); Node* newNode = malloc(

Node)); strcpy(newNode->key, key); strcpy(newNode->value, value); // Chaining: Insert at the beginning of the list

newNode->next = hash_table[index]; hash_table[index] = newNode; printf( "Stored '%s' at Shelf %d\n" , key, index); // Finding a word index = hash(key); Node* temp = hash_table[index]; (strcmp(temp->key, key) == ) printf( "Found: %s -> %s\n" , key, temp->value); ; temp = temp->next; } printf( "Word not found.\n" // Initialize the library ; i < TABLE_SIZE; i++) hash_table[i] = NULL;

insert( "Algorithm" "A step-by-step procedure." );
insert( "A variable that stores a memory address." );
lookup( "Algorithm" Use code with caution. Copied to clipboard The Moral of the Story</p>

The library became the fastest in the land. Instead of searching thousands of books, the King could find any definition in "Constant Time," or

. The architect proved that with a little bit of math and a well-placed pointer, even the largest mountains of data could be tamed.

And so, the Kingdom of Memory flourished, forever organized by the power of the Hash. method like Linear Probing in more detail, or should we refine the hash function for better performance?

A dictionary entry needs a key, a value, and a pointer to the next entry in case of a hash collision. 

#include #include #include #define TABLE_SIZE 101 // A prime number is preferred for better distribution // The individual item in the dictionary typedef struct Entry char *key; char *value; struct Entry *next; Entry; // The Hash Table (Dictionary) typedef struct Entry *buckets[TABLE_SIZE]; Dictionary; Use code with caution. Copied to clipboard 2. The Hashing Algorithm 

The hash function converts a string key into an integer index. A common choice is the polynomial rolling hash (multiplier 31), which minimizes collisions for strings.  c program to implement dictionary using hashing algorithms

unsigned int hash(const char *key) unsigned int hash_value = 0; for (int i = 0; key[i] != '\0'; i++) hash_value = key[i] + (hash_value * 31); return hash_value % TABLE_SIZE; // Scale result to table size Use code with caution. Copied to clipboard 3. Essential Operations: Insert and Search 

These functions handle the logic of finding the right "bucket" and managing the linked list. 

// Insert a key-value pair void insert(Dictionary *dict, const char *key, const char *value) unsigned int index = hash(key); // Check if key already exists to update value Entry *current = dict->buckets[index]; while (current != NULL) if (strcmp(current->key, key) == 0) free(current->value); current->value = strdup(value); return; current = current->next; // Otherwise, add new entry at the head of the chain (O(1)) Entry *new_entry = malloc(sizeof(Entry)); new_entry->key = strdup(key); new_entry->value = strdup(value); new_entry->next = dict->buckets[index]; dict->buckets[index] = new_entry; // Search for a value by key char* search(Dictionary *dict, const char *key) unsigned int index = hash(key); Entry *current = dict->buckets[index]; while (current != NULL) if (strcmp(current->key, key) == 0) return current->value; current = current->next; return NULL; // Not found Use code with caution. Copied to clipboard 4. Implementation Analysis  Time Complexity: Average operations are

. If the hash function is poor and many keys collide in one bucket, it can degrade to (linked list traversal).

Memory Overhead: Each entry requires extra memory for a pointer to the next node.

Collision Handling: Using Separate Chaining allows the dictionary to store more elements than the table size, though performance drops as the "load factor" increases.  5. Practical Use Example 

int main() Dictionary myDict = 0; // Initialize buckets to NULL insert(&myDict, "Apple", "A sweet red fruit"); insert(&myDict, "C", "A powerful programming language"); char *result = search(&myDict, "Apple"); if (result) printf("Apple: %s\n", result); return 0; Use code with caution. Copied to clipboard Quick Way to Implement Dictionary in C - Stack Overflow

Abstract

A dictionary is a data structure that stores a collection of key-value pairs, where each key is unique and maps to a specific value. In this paper, we implement a dictionary using hashing algorithms in C programming language. We use a hash function to map keys to indices of a hash table, which stores the key-value pairs. The goal of this implementation is to provide efficient insertion, search, and deletion operations. We discuss the design and implementation of the dictionary using hashing algorithms and present the C code for the same.

Introduction

A dictionary, also known as a hash table or a map, is a fundamental data structure in computer science that stores a collection of key-value pairs. It allows for efficient retrieval of values by their associated keys. Hashing algorithms are widely used to implement dictionaries, as they provide fast lookup, insertion, and deletion operations.

Hashing Algorithms

Hashing algorithms are used to map keys to indices of a hash table. A hash function takes a key as input and generates a hash code, which is an integer that represents the index of the hash table where the corresponding value is stored. A good hash function should have the following properties:

1. Deterministic: Given a key, the hash function should always generate the same hash code.
2. Non-injective: Different keys should map to different hash codes.
3. Fixed output size: The hash function should generate a fixed-size hash code.

Design and Implementation

Our implementation of the dictionary using hashing algorithms consists of the following components:

1. Hash Table: A hash table is an array of structures, where each structure represents a key-value pair.
2. Hash Function: We use a simple hash function that calculates the hash code by taking the modulus of the key with the size of the hash table.
3. Insertion: When a new key-value pair is inserted, we calculate the hash code using the hash function and store the pair at the corresponding index of the hash table. If there is a collision (i.e., two keys map to the same index), we use chaining to store the colliding pairs.
4. Search: When searching for a value by its key, we calculate the hash code using the hash function and retrieve the value from the corresponding index of the hash table.
5. Deletion: When deleting a key-value pair, we calculate the hash code using the hash function and remove the pair from the corresponding index of the hash table.

C Code

Here is the C code for the dictionary implementation using hashing algorithms: Once upon a time in the digital kingdom

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_TABLE_SIZE 10
typedef struct Node 
    char* key;
    char* value;
    struct Node* next;
 Node;
typedef struct HashTable 
    Node** buckets;
    int size;
 HashTable;
// Hash function
int hash(char* key) 
    int hashCode = 0;
    for (int i = 0; i < strlen(key); i++) 
        hashCode += key[i];
return hashCode % HASH_TABLE_SIZE;
// Create a new node
Node* createNode(char* key, char* value) 
    Node* node = (Node*) malloc(sizeof(Node));
    node->key = (char*) malloc(strlen(key) + 1);
    strcpy(node->key, key);
    node->value = (char*) malloc(strlen(value) + 1);
    strcpy(node->value, value);
    node->next = NULL;
    return node;
// Create a new hash table
HashTable* createHashTable() 
    HashTable* hashTable = (HashTable*) malloc(sizeof(HashTable));
    hashTable->buckets = (Node**) malloc(sizeof(Node*) * HASH_TABLE_SIZE);
    hashTable->size = HASH_TABLE_SIZE;
    for (int i = 0; i < HASH_TABLE_SIZE; i++) 
        hashTable->buckets[i] = NULL;
return hashTable;
// Insert a key-value pair into the hash table
void insert(HashTable* hashTable, char* key, char* value) 
    int index = hash(key);
    Node* node = createNode(key, value);
    if (hashTable->buckets[index] == NULL) 
        hashTable->buckets[index] = node;
     else 
        Node* current = hashTable->buckets[index];
        while (current->next != NULL) 
            current = current->next;
current->next = node;
// Search for a value by its key
char* search(HashTable* hashTable, char* key) 
    int index = hash(key);
    Node* current = hashTable->buckets[index];
    while (current != NULL) 
        if (strcmp(current->key, key) == 0) 
            return current->value;
current = current->next;
return NULL;
// Delete a key-value pair from the hash table
void delete(HashTable* hashTable, char* key) 
    int index = hash(key);
    Node* current = hashTable->buckets[index];
    if (current == NULL) return;
    if (strcmp(current->key, key) == 0) 
        hashTable->buckets[index] = current->next;
        free(current->key);
        free(current->value);
        free(current);
     else 
        Node* previous = current;
        current = current->next;
        while (current != NULL) 
            if (strcmp(current->key, key) == 0) 
                previous->next = current->next;
                free(current->key);
                free(current->value);
                free(current);
                return;
previous = current;
            current = current->next;
// Print the hash table
void printHashTable(HashTable* hashTable) 
    for (int i = 0; i < HASH_TABLE_SIZE; i++) 
        Node* current = hashTable->buckets[i];
        printf("Bucket %d: ", i);
        while (current != NULL) 
            printf("%s -> %s, ", current->key, current->value);
            current = current->next;
printf("\n");
int main() 
    HashTable* hashTable = createHashTable();
    insert(hashTable, "apple", "fruit");
    insert(hashTable, "banana", "fruit");
    insert(hashTable, "carrot", "vegetable");
    printHashTable(hashTable);
    char* value = search(hashTable, "banana");
    printf("Value for key 'banana': %s\n", value);
    delete(hashTable, "apple");
    printHashTable(hashTable);
    return 0;

Conclusion

In this paper, we implemented a dictionary using hashing algorithms in C programming language. We discussed the design and implementation of the dictionary, including the hash function, insertion, search, and deletion operations. The C code provided demonstrates the implementation of the dictionary using hashing algorithms. This implementation provides efficient insertion, search, and deletion operations, making it suitable for a wide range of applications.

References

• Aho, A. V., & Ullman, J. D. (1983). Data Structures and Algorithms. Addison-Wesley.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
• Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.

In C, a dictionary is typically implemented using a hash table, which maps unique keys to specific values. Since C doesn't have a built-in dictionary type like Python or Java, you must build one using an array and a hashing function. 1. Define the Data Structures

The foundation of a dictionary consists of a structure for individual entries and the table itself. This example uses separate chaining with linked lists to handle collisions (when two keys hash to the same index).

#include #include #include #define TABLE_SIZE 101 // Structure for a single dictionary entry typedef struct Entry char *key; char *value; struct Entry *next; // Pointer to next entry in case of collision Entry; // The Hash Table (Dictionary) Entry *dictionary[TABLE_SIZE]; Use code with caution. Copied to clipboard 2. Implement the Hashing Algorithm

A good hash function should distribute keys evenly across the table to minimize collisions. The djb2 algorithm is a popular, efficient choice for string keys.

// djb2 hashing algorithm unsigned int hash(const char *str) unsigned long hash = 5381; int c; while ((c = *str++)) // hash * 33 + c hash = ((hash << 5) + hash) + c; return hash % TABLE_SIZE; Use code with caution. Copied to clipboard 3. Implement Core Operations

A dictionary requires three primary functions: insert, search, and delete. Insert (Put)

This function adds a new key-value pair or updates the value if the key already exists.

void insert(const char *key, const char *value) unsigned int index = hash(key); Entry *new_entry = dictionary[index]; // Check if key already exists to update it while (new_entry != NULL) if (strcmp(new_entry->key, key) == 0) free(new_entry->value); new_entry->value = strdup(value); return; new_entry = new_entry->next; // Create a new entry if not found new_entry = malloc(sizeof(Entry)); new_entry->key = strdup(key); new_entry->value = strdup(value); new_entry->next = dictionary[index]; // Insert at the head of the list dictionary[index] = new_entry; Use code with caution. Copied to clipboard Search (Get)

To properly review a C program implementing a dictionary via hashing, focus on the efficiency of the hash function robustness of collision resolution memory management 1. Hash Function Quality

A professional implementation must distribute keys uniformly across the table to avoid "clustering". www.andreinc.net Algorithm Choice

: Common practices include multiplying the hash value by a prime number (e.g., 31) at each step to spread the bits effectively. Modulo Operation : Ensure the final hash is taken modulo the table size ( ) to stay within array bounds. Data Types unsigned int

for hash values to prevent undefined behavior from integer overflow. 2. Collision Resolution Strategy

Since multiple keys can hash to the same index, a strategy is required to handle these conflicts. IIARD Journals

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;

3.3 Search Function

char* search(Dictionary *dict, const char *key) 
    unsigned long hash = dict->hash_func(key);
    unsigned long index = hash % dict->size;
Entry *curr = dict->buckets[index];
while (curr) 
    if (strcmp(curr->key, key) == 0) 
        return curr->value;
curr = curr->next;
return NULL; // Not found

Chapter 3: Designing the Dictionary Data Structures in C

We need three primary structures:

1. KeyValuePair: Represents a single entry.
2. HashTable: Contains an array of buckets, each being a linked list.
3. Dictionary API: Functions for insert, search, delete, and destroy.

Why Hashing for a Dictionary?

Hashing transforms a key (string, integer, etc.) into a fixed-size numerical index, allowing near-constant time O(1) average-case complexity for insertions, deletions, and lookups. Without hashing, these operations degrade to O(n) or O(log n).

2. Hash Functions

The hash function converts a string key into an index. A good hash function:

• Produces uniform distribution
• Is deterministic
• Is fast to compute

Simple polynomial rolling hash (djb2 variant):

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

Alternative: FNV-1a hash (better distribution):

unsigned long hash_fnv1a(const char *str, int table_size) 
    unsigned long hash = 2166136261UL;
    int c;
while ((c = *str++)) 
    hash ^= c;
    hash *= 16777619;
return hash % table_size;

The SDBM Algorithm

Excellent for low collision rates.

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;

3.4 Key-Value Types

Keys are null-terminated strings (char*). Values are integers (int) for demonstration; this can be made generic using void*.

Code Explanation

1. Data Structures:

   • DictionaryItem: A struct representing a node in a linked list. It holds the key, the value, and a pointer to the next item.
   • HashTable: A struct containing an array of pointers (buckets).

2. hashFunction:

   • Uses the modulo operator (%) to determine the index. key % SIZE ensures the index is always within the bounds of the array (0 to 9).

3. insert:

   • Calculates the index using the hash function.
   • If the bucket is empty, it places the new item there.
   • Collision Handling: If the bucket is not empty, it iterates through the linked list. If the key already exists, it updates the value. If not, it adds the new node to the beginning of the list.

4. search:

   • Calculates the index and traverses the specific linked list at that index to find the matching key.

5. deleteItem:

   • Finds the specific bucket and traverses the list. It handles edge cases (deleting the head node vs. a middle/end node) and frees memory.