0

C Program To Implement Dictionary Using Hashing Algorithms Better ✔

The Hash Function: Converts a string (the key) into an integer index. A common choice is the djb2 algorithm because it distributes strings evenly across the table.

The Hash Table: An array of structs, where each struct holds the word (key) and its definition (value).

Collision Handling: Since different words can hash to the same index, we use Linear Probing—if a slot is taken, the program simply looks at the next available slot (index + 1). The Implementation

#include #include #include #define SIZE 20 struct DataItem char key[50]; char value[100]; ; struct DataItem* hashArray[SIZE]; // Simple hash function (Sum of ASCII values % SIZE) int hashCode(char* key) int hash = 0; for(int i = 0; key[i] != '\0'; i++) hash += key[i]; return hash % SIZE; // Insert a word and definition void insert(char* key, char* value) struct DataItem* item = (struct DataItem*) malloc(sizeof(struct DataItem)); strcpy(item->key, key); strcpy(item->value, value); int hashIndex = hashCode(key); // Linear Probing: find next empty slot while(hashArray[hashIndex] != NULL) hashIndex = (hashIndex + 1) % SIZE; hashArray[hashIndex] = item; // Search for a definition char* search(char* key) int hashIndex = hashCode(key); while(hashArray[hashIndex] != NULL) if(strcmp(hashArray[hashIndex]->key, key) == 0) return hashArray[hashIndex]->value; hashIndex = (hashIndex + 1) % SIZE; return "Not Found"; int main() insert("Algorithm", "A step-by-step procedure for calculations."); insert("Pointer", "A variable that stores a memory address."); insert("Boolean", "A data type with two possible values: true or false."); printf("Search 'Pointer': %s\n", search("Pointer")); printf("Search 'C-Language': %s\n", search("C-Language")); return 0; Use code with caution. Copied to clipboard Why this works Speed: In a perfect scenario, finding a word is

, meaning it takes the same amount of time regardless of how many words are in the dictionary. c program to implement dictionary using hashing algorithms

Memory: By using a fixed SIZE, we manage memory predictably, though in a real-world app, you would implement Dynamic Resizing to expand the table as it fills up.

1. Data Structures

We need two primary structures:

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

#define TABLE_SIZE 10007  // Prime number for better distribution


// Dictionary entry (key-value pair)
typedef struct Entry 
char *key;
int value;
struct Entry *next;
 Entry; The Hash Function: Converts a string (the key)


// Hash table structure
typedef struct 
Entry **buckets;  // Array of linked list heads
int size;         // Number of buckets
int count;        // Number of stored key-value pairs
 HashTable;

1.1 What is a Dictionary?

A dictionary is an abstract data type that stores a collection of pairs (key, value). It supports three primary operations:

The goal is to perform each of these operations in O(1) average time complexity. Node : Represents a single key-value pair (linked

Data Structures

First, define the linked list node for the chain:

typedef struct Entry 
    char *key;
    char *value;
    struct Entry *next;
 Entry;

Next, define the hash table structure:

typedef struct Dictionary 
    Entry **buckets;    // Array of pointers to linked lists
    unsigned long size; // Current number of buckets
    unsigned long count; // Number of key-value pairs stored
    unsigned long (*hash_func)(const char *); // Function pointer for hash algorithm
 Dictionary;

Step 2: Collision Resolution – Separate Chaining

Collisions are inevitable. The two main strategies are:

We will implement separate chaining because it handles high load factors gracefully and is simpler to manage in C.

Initialization

HashTable* create_dict(int size) 
    HashTable *dict = (HashTable*)malloc(sizeof(HashTable));
    if (!dict) return NULL;

dict->size = size;
dict->count = 0;
dict->buckets = (Entry**)calloc(size, sizeof(Entry*));
if (!dict->buckets) 
    free(dict);
    return NULL;
return dict;