A hash Table is a data structure that combine the random access ability of an array with the dynamism of a linked list. This post provides ready-to-go code snippets to implement one in your C script: a basic version and an improved one (with resizing).

A hash table combines:

  • A hash function, which returns an non-negative integer value called a hash code.
  • An array capable of storing data of the type we want

To prevent collisions, we use the Chaining method: each element of the array holds multiple pieces of data, using a linked-list. This way, we can now store an unlimited amount of data in our table.

Chaining using linked-lists inside each cell of the hash table

Basic script

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

#define TABLE_SIZE 3

typedef struct listNode
{
  int key;
  char *data;
  struct listNode *next;
}
ListNode;

typedef struct hashTableNode
{
  int bCount; // count of elements in a block or chain
  ListNode *next;
}
HashTableNode;

typedef struct hashTable
{
  int countOfElement; //count of elements in the hash table
  HashTableNode *table;
}
HashTable;

HashTable *h = NULL;

// Functions declaration
unsigned int hash(char *data);
bool insert(ListNode *newNode);
void create(int noOfEelement);
ListNode *createNode(char *data);
bool deleteNode(char *data, bool printResult);
bool searchNode(char *data, bool printResult);

void print_table(char *title);
void print_search(bool isFound);
void print_deleteNode(bool isDeleted);

// Run script
int main(void)
{
    create(10);
    insert(createNode("Harry"));
    insert(createNode("Hermione"));
    insert(createNode("Ron"));
    insert(createNode("Alex"));
    insert(createNode("Percy"));
    insert(createNode("Trevor"));

    // searching an element when it's not in the table
    searchNode("Voldemort", true);
    // search an element when it's in the table
    insert(createNode("Voldemort"));
    searchNode("Voldemort", true);
    // search an element when it's deleted from the table
    deleteNode("Voldemort", true);
    searchNode("Voldemort", true);

    // Insert more nodes
    insert(createNode("Drago"));
    insert(createNode("Dobbie"));
    insert(createNode("Hagrid"));
    insert(createNode("Sirius"));

    print_table("Hash Table");
    return 0;
}

// Functions

unsigned int hash(char *data)
{
	int sum = 0;
	for (int j = 0; data[j] != '\0'; j++)
	{
		sum += data[j];
	}
    int hash = sum % TABLE_SIZE;
    // printf("hash: %d\n", hash); // debug
	return hash;
}

void create(int noOfEelement)
{
    h = (HashTable*)malloc(sizeof(HashTable));
    h->countOfElement = 0;
    h->table = (HashTableNode *)malloc(TABLE_SIZE * sizeof(HashTableNode));

    for (int i = 0; i < TABLE_SIZE; i++)
    {
        h->table[i].next = NULL;
        h->table[i].bCount = 0;
    }
}

bool insert(ListNode *newNode)
{
    int index = newNode->key;
    char *data = newNode->data;

    // Check that the data does not exist already in the table
    if (searchNode(data, false))
    {
        return false;
    }

    newNode->next = h->table[index].next;
    h->table[index].next = newNode;
    h->table[index].bCount++;
    h->countOfElement++;

    return true;
}

ListNode *createNode(char *data)
{
  ListNode *temp;
  temp = (ListNode *)malloc(sizeof(ListNode));

  int index = hash(data);
  temp->key = index;
  temp->data = data;
  temp->next = NULL;

  return temp;
}

bool deleteNode(char *data, bool printResult)
{
    int index = hash(data);
    ListNode *temp = h->table[index].next, *prev = NULL;
    bool isDeleted = false;

    while (temp)
    {
        if (temp->data == data)
        {
            if (prev != NULL)
            {
                prev->next = temp->next;
            }
            else
            {
                h->table[index].next = temp->next;
            }

            free(temp);
            h->table[index].bCount--;
            h->countOfElement--;

            isDeleted = true;
            break;
        }
        prev = temp;
        temp = temp->next;
    }

    if (printResult)
    {
        print_deleteNode(isDeleted);
    }
    return isDeleted;
}

bool searchNode(char *data, bool printResult)
{
    int index = hash(data);
    ListNode *temp = h->table[index].next;
    bool isFound = false;

    while (temp)
    {
        if (temp->data == data)
        {
            isFound = true;
            break;
        }
        temp = temp->next;
    }

    if (printResult)
    {
        print_search(isFound);
    }
    return isFound;
}

// Utilities

void print_table(char *title)
{
    printf("%s:\n", title);
    printf("- Table Capacity = %d\n", TABLE_SIZE);
    printf("- Total elements = %d\n", h->countOfElement);
    printf("- Structure:\n");
    for (int i = 0; i < TABLE_SIZE; i++)
    {
        printf("  [%d] ", i);
        for (ListNode *temp = h->table[i].next; temp; temp = temp->next)
        {
            if (temp->next)
                printf("%s -> ", temp->data);
            else
            {
                printf("%s", temp->data);
            }
        }
        printf("\n");
    }
    printf("\n");
}

void print_search(bool isFound)
{
    printf("Processing function `searchNode`...\n");
    if (isFound)
    {
        printf("Result: found");
    }
    else
    {
        printf("Result: not found");
    }
    printf("\n\n");
}

void print_deleteNode(bool isDeleted)
{
    printf("Processing function `deleteNode`...\n");
    if (isDeleted)
    {
        printf("Result: deleted");
    }
    else
    {
        printf("Result: not deleted");
    }
    printf("\n\n");
}

Improved version (with resizing)

In this version, we defined a const LOAD_FACTOR that sets the maximum ratio of the number of nodes in the hash table over the number of cells of the hash table.

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

// The table will resize automatically if:
// (number of nodes) > (hashTable cells number) * LOAD_FACTOR
#define LOAD_FACTOR 5

typedef struct listNode
{
  int key;
  char *data;
  struct listNode *next;
}
ListNode;

typedef struct hashTableNode
{
  int bCount; // count of elements in a block or chain
  ListNode *next;
}
HashTableNode;

typedef struct hashTable
{
  int countOfElement; //count of elements in the hash table
  int tCapacity; // table capacity
  HashTableNode *table;
}
HashTable;

HashTable *h = NULL;

// Functions declaration
unsigned int hash(char *data, int tCapacity);
bool insert(ListNode *newNode);
void create(int noOfEelement);
ListNode *createNode(char *data);
bool deleteNode(char *data, bool printResult);
bool searchNode(char *data, bool printResult);
void reHash();

void print_table(char *title);
void print_search(bool isFound);
void print_deleteNode(bool isDeleted);

// Run script
int main(void)
{
    create(10);
    insert(createNode("Harry"));
    insert(createNode("Hermione"));
    insert(createNode("Ron"));
    insert(createNode("Alex"));
    insert(createNode("Percy"));
    insert(createNode("Trevor"));

    // searching an element when it's not in the table
    searchNode("Voldemort", true);
    // search an element when it's in the table
    insert(createNode("Voldemort"));
    searchNode("Voldemort", true);
    // search an element when it's deleted from the table
    deleteNode("Voldemort", true);
    searchNode("Voldemort", true);

    // Insert more nodes
    insert(createNode("Drago"));
    insert(createNode("Dobbie"));
    insert(createNode("Hagrid"));
    insert(createNode("Diego"));

    print_table("Hash Table (before capacity get doubled)");

    // After the execution of below line number of elements become 11:
    // LOAD_FACTOR = 11/TableCapacity = 11/5 = 5.2
    // 5.2 > actual LOAD_FACTOR decided. So, the capacity of the table has to be doubled
    insert(createNode("Sirius"));
    print_table("Hash Table (after capacity get doubled)");

    return 0;
}

// Functions

unsigned int hash(char *data, int tCapacity)
{
	int sum = 0;
	for (int j = 0; data[j] != '\0'; j++)
	{
		sum += data[j];
	}
    int hash = sum % tCapacity;
    // printf("hash: %d\n", hash); // debug
	return hash;
}

void create(int noOfEelement)
{
    h = (HashTable*)malloc(sizeof(HashTable));
    h->countOfElement = 0;
    h->tCapacity = noOfEelement/LOAD_FACTOR;
    h->table = (HashTableNode *)malloc(h->tCapacity * sizeof(HashTableNode));

    for (int i = 0; i<h->tCapacity; i++)
    {
        h->table[i].next = NULL;
        h->table[i].bCount = 0;
    }
}

bool insert(ListNode *newNode)
{
    int index = newNode->key;
    char *data = newNode->data;

    // Check that the data does not exist already in the table
    if (searchNode(data, false))
    {
        return false;
    }

    newNode->next = h->table[index].next;
    h->table[index].next = newNode;
    h->table[index].bCount++;
    h->countOfElement++;

    if (h->countOfElement > h->tCapacity * LOAD_FACTOR)
    {
        reHash();
    }

    return true;
}

ListNode *createNode(char *data)
{
  ListNode *temp;
  temp = (ListNode *)malloc(sizeof(ListNode));

  int index = hash(data, h->tCapacity);
  temp->key = index;
  temp->data = data;
  temp->next = NULL;

  return temp;
}

bool deleteNode(char *data, bool printResult)
{
    int index = hash(data, h->tCapacity);
    ListNode *temp = h->table[index].next, *prev = NULL;
    bool isDeleted = false;

    while (temp)
    {
        if (temp->data == data)
        {
            if (prev != NULL)
            {
                prev->next = temp->next;
            }
            else
            {
                h->table[index].next = temp->next;
            }

            free(temp);
            h->table[index].bCount--;
            h->countOfElement--;

            isDeleted = true;
            break;
        }
        prev = temp;
        temp = temp->next;
    }

    if (printResult)
    {
        print_deleteNode(isDeleted);
    }
    return isDeleted;
}

bool searchNode(char *data, bool printResult)
{
    int index = hash(data, h->tCapacity);
    ListNode *temp = h->table[index].next;
    bool isFound = false;

    while (temp)
    {
        if (temp->data == data)
        {
            isFound = true;
            break;
        }
        temp = temp->next;
    }

    if (printResult)
    {
        print_search(isFound);
    }
    return isFound;
}

void reHash()
{
    HashTableNode *oldTable;
    int oldCapacity = h->tCapacity;
    oldTable = h->table; h->tCapacity = h->tCapacity*2;

    h->table = (HashTableNode *)malloc(sizeof(HashTableNode) * h->tCapacity);
    if (!h->table)
    {
        printf("Allocation Failed");
        return;
    }
    for (int i = 0; i<h->tCapacity; i++){
        h->table[i].next = NULL;
        h->table[i].bCount = 0;
    }

    for (int i = 0; i<oldCapacity; i++){
        ListNode *temp = oldTable[i].next, *temp2;
        while (temp)
        {
            int index = hash(temp->data, h->tCapacity);
            temp2 = temp; temp = temp->next;

            if (h->table[index].bCount){
                temp2->next = h->table[index].next;
                h->table[index].next = temp2;
                h->table[index].bCount++;
            }
            else{
                h->table[index].next = temp2; temp2->next = NULL;
                h->table[index].bCount++;
            }
        }
    }
}

// Utilities

void print_table(char *title)
{
    printf("%s:\n", title);
    printf("- Table Capacity = %d\n", h->tCapacity);
    printf("- Total elements = %d\n", h->countOfElement);
    printf("- Structure:\n");
    for (int i = 0; i < h->tCapacity; i++)
    {
        printf("  [%d] ", i);
        for (ListNode *temp = h->table[i].next; temp; temp = temp->next)
        {
            if (temp->next)
                printf("%s -> ", temp->data);
            else
            {
                printf("%s", temp->data);
            }
        }
        printf("\n");
    }
    printf("\n");
}

void print_search(bool isFound)
{
    printf("Processing function `searchNode`...\n");
    if (isFound)
    {
        printf("Result: found");
    }
    else
    {
        printf("Result: not found");
    }
    printf("\n\n");
}

void print_deleteNode(bool isDeleted)
{
    printf("Processing function `deleteNode`...\n");
    if (isDeleted)
    {
        printf("Result: deleted");
    }
    else
    {
        printf("Result: not deleted");
    }
    printf("\n\n");
}
⇐ Basic CRUD App with Flask and...C: Linked List script ⇒
Posted by Edouard Proust
Image
Author of this website. I am passionate about programming and web design since the age of 12. After a stint in architecture and entrepreneurship, I came back to my original passion at 30 years old and became a self-taught web developer in less than 2 years.

Leave a Comment