This article briefly introduces how to create a hash table using uthash, as well as perform operations such as adding, deleting, looking up an item, printing the table, and clearing the table.

C language provides only basic data types, arrays, and pointers, as well as memory allocation functions. This means that programmers need to manually create complex data structures. While some data structures (e.g., binary trees, linked lists) can be implemented relatively easily, creating hash tables can be quite challenging.

Recently I'm working on Leetcode problems, and some of them require the use of hash tables (such as problems 1, 30, 49). In this article, I demonstrated how to implement a hash table from scratch with C. It works well, but writing a new hash table for each specific task wastes a lot of time.

Fortunately, uthash, a set of C macros developed by troydhanson, makes it much more convenient to build custom hash tables in C.

How to start

Download the uthash library to the project directory.

In the C source file, include the uthash.h header file using the following directive:

#include "uthash.h"

String Int HashTable

This hash table has key as string and value as integer. It is very useful in LeetCode problem 30. The structure of the hash table is as follows.

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

typedef struct {
    char *key;
    int value;
    UT_hash_handle hh;
} StrIntHash;

Here are some operations I wrote for this hash table. Since these functions have simple logic and their purposes can be easily understood according to the code and function names, they will not be described in detail here.

void addItem(StrIntHash **hash_table, const char *key, int value) {
    StrIntHash *item = (StrIntHash *) malloc(sizeof(StrIntHash));
    item->key = strdup(key);
    item->value = value;
    HASH_ADD_STR(*hash_table, key, item);
}

void deleteItem(StrIntHash **hash_table, const char *key) {
    StrIntHash *item;
    HASH_FIND_STR(*hash_table, key, item);
    if(item) {
        free(item->key);
        HASH_DEL(*hash_table, item);
        free(item);
    }
    else {
        printf("%s is not found!\n", key);
    }
}

StrIntHash *findItem(StrIntHash **hash_table, const char *key) {
    StrIntHash *item;
    HASH_FIND_STR(*hash_table, key, item);
    return item;
}

void printTable(StrIntHash **hash_table) {
    StrIntHash *current_item, *tmp;
    HASH_ITER(hh, *hash_table, current_item, tmp) {
        printf("key: %s, value: %d\n", current_item->key, current_item->value);
    }
}

void clearTable(StrIntHash **hash_table) {
    StrIntHash *current_item, *tmp;
    HASH_ITER(hh, *hash_table, current_item, tmp) {
        free(current_item->key);
        HASH_DEL(*hash_table, current_item);
        free(current_item);
    }
}

These functions can be utilized as follows.

int main() {
    StrIntHash *hash_table = NULL, *found_item;

    /* add items */
    addItem(&hash_table, "A", 1);
    addItem(&hash_table, "B", 3);
    addItem(&hash_table, "C", 5);
    
    /* print table */
    printTable(&hash_table);
    printf("----------------\n");

    /* find an item */
    found_item = findItem(&hash_table, "B");
    if(found_item) {
        printf("Found key: %s, value: %d\n", found_item->key, found_item->value);
    }
    else {
        printf("Not found\n");
    }
    printf("----------------\n");

    /* delete an item */
    deleteItem(&hash_table, "D");

    /* clear the table to free the memory */
    clearTable(&hash_table);

    return 0;
}

The running result is shown below. All allocated memory was freed.

Int Int HashTable

Here is the code when both key and value are int, which can be used in LeetCode problem 1.

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

typedef struct {
    int key;
    int value;
    UT_hash_handle hh;
} IntIntHash;

void addItem(IntIntHash **hash_table, int key, int value) {
    IntIntHash *item = (IntIntHash *)malloc(sizeof(IntIntHash));
    item->key = key;
    item->value = value;
    HASH_ADD_INT(*hash_table, key, item);
}

IntIntHash *findItem(IntIntHash **hash_table, int key) {
    IntIntHash *item;
    HASH_FIND_INT(*hash_table, &key, item);
    return item;
}

void deleteItem(IntIntHash **hash_table, IntIntHash *item) {
    if(item) {
        HASH_DEL(*hash_table, item);
        free(item);
    }
}

void clearTable(IntIntHash **hash_table) {
    IntIntHash *current_item, *tmp;
    HASH_ITER(hh, *hash_table, current_item, tmp) {
        HASH_DEL(*hash_table, current_item);
        free(current_item);
    }
}

int main(int argc, char **argv) {
    int nums[] = {2, 7, 11, 15};
    IntIntHash *hash_table = NULL;

    /* add items */ 
    for(int i = 0; i < sizeof(nums) / sizeof(int); ++i) {
        addItem(&hash_table, nums[i], i);
    }

    /* find an item */
    IntIntHash *item = findItem(&hash_table, 7);
    if(item) {
        printf("Found key: %d, value: %d\n", item->key, item->value);
    }
    else {
        printf("Not found\n");
    }

    /* delete an item */
    deleteItem(&hash_table, item);

    /* clear the table to free the memory */
    clearTable(&hash_table);
    
    return 0;
}

Running result:

These two examples demonstrated above show that a new hash table with different key or value can be implemented with only minor code modification.

For more uthash operations, see uthash's User Guide.