How to Implement Hash Table in C: Simple Guide with Example

To implement a hash table in C, create an array of linked lists (buckets) and use a hash function to map keys to bucket indices. Insert, search, and delete elements by hashing the key and traversing the linked list at that index.

Syntax

A hash table in C typically uses an array of pointers to linked list nodes. Each node stores a key-value pair. The hash function converts a key into an index for the array. Basic operations include insert, search, and delete.

• struct Node: stores key, value, and pointer to next node.
• hash_function(key): returns an index for the key.
• insert(key, value): adds a new node to the correct bucket.
• search(key): finds a node by key.
• delete(key): removes a node by key.

c

typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

#define TABLE_SIZE 10

Node* hash_table[TABLE_SIZE];

unsigned int hash_function(int key) {
    return key % TABLE_SIZE;
}

void insert(int key, int value);
int search(int key);
void delete(int key);

Example

This example shows a simple hash table with insert, search, and delete functions using chaining to handle collisions.

c

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

typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

#define TABLE_SIZE 10

Node* hash_table[TABLE_SIZE] = {NULL};

unsigned int hash_function(int key) {
    return key % TABLE_SIZE;
}

void insert(int key, int value) {
    unsigned int index = hash_function(key);
    Node* new_node = malloc(sizeof(Node));
    if (new_node == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return;
    }
    new_node->key = key;
    new_node->value = value;
    new_node->next = hash_table[index];
    hash_table[index] = new_node;
}

int search(int key) {
    unsigned int index = hash_function(key);
    Node* current = hash_table[index];
    while (current) {
        if (current->key == key) {
            return current->value;
        }
        current = current->next;
    }
    return -1; // Not found
}

void delete(int key) {
    unsigned int index = hash_function(key);
    Node* current = hash_table[index];
    Node* prev = NULL;
    while (current) {
        if (current->key == key) {
            if (prev) {
                prev->next = current->next;
            } else {
                hash_table[index] = current->next;
            }
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

int main() {
    insert(1, 10);
    insert(11, 20); // Collision with key 1
    insert(21, 30); // Collision with key 1 and 11

    printf("Value for key 1: %d\n", search(1));
    printf("Value for key 11: %d\n", search(11));
    printf("Value for key 21: %d\n", search(21));

    delete(11);
    printf("After deleting key 11, search returns: %d\n", search(11));

    return 0;
}

Output

Value for key 1: 10
Value for key 11: 20
Value for key 21: 30
After deleting key 11, search returns: -1

Common Pitfalls

• Not handling collisions: Without chaining or open addressing, keys that hash to the same index overwrite each other.
• Memory leaks: Forgetting to free nodes when deleting causes leaks.
• Incorrect hash function: A poor hash function causes many collisions and slows down operations.
• Not initializing the table: The array must be initialized to NULL pointers.

c

/* Wrong: Overwriting without chaining */
void insert_wrong(int key, int value) {
    unsigned int index = hash_function(key);
    Node* new_node = malloc(sizeof(Node));
    if (new_node == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return;
    }
    new_node->key = key;
    new_node->value = value;
    new_node->next = NULL;
    hash_table[index] = new_node; // Overwrites existing node
}

/* Right: Insert at head of linked list */
void insert_right(int key, int value) {
    unsigned int index = hash_function(key);
    Node* new_node = malloc(sizeof(Node));
    if (new_node == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return;
    }
    new_node->key = key;
    new_node->value = value;
    new_node->next = hash_table[index];
    hash_table[index] = new_node;
}

Quick Reference

• Hash function: Maps keys to array indices, e.g., key % TABLE_SIZE.
• Collision handling: Use chaining (linked lists) or open addressing.
• Insert: Add new node at bucket head.
• Search: Traverse linked list at bucket to find key.
• Delete: Remove node from linked list and free memory.

Key Takeaways

Use a hash function to convert keys into array indices for fast access.

Handle collisions by chaining with linked lists to store multiple items per bucket.

Always initialize your hash table array to NULL pointers before use.

Free memory properly when deleting nodes to avoid memory leaks.

Test your hash function to minimize collisions and improve performance.