Generic implementation of a hashtable with double-linked list

Question

I implemented a hashtable that handles collisions by chaining entries using a double linked list. The idea is that it can store/lookup any kind of generic data structure, while maintaining an API that is convenient to use.

For now the implementation only supports adding, obtaining and removing entries, - resizing of the table is planned in the future.

Can I make my implementation more performant and readable, so that I can easiely reuse it in future projects? I feel like the ht_add and ht_delete functions especially have room for improvement. Looking forward for any feedback.

hashtable.h

#ifndef HASHTABLE_H
#define HASHTABLE_H

typedef struct entry_t
{
    unsigned int key;
    void* value;
    struct entry_t* next;
    struct entry_t* prev;
} entry_t;

typedef struct hashtable_t
{
    unsigned int buckets_count;
    struct entry_t **buckets;
} hashtable_t;

// ToDo: Add resizing functionality

unsigned int compute_hash(struct hashtable_t *ht, unsigned int key);
hashtable_t *ht_new(unsigned int size);
int ht_add(struct hashtable_t* ht, unsigned int key, void* value);
entry_t* ht_get(struct hashtable_t* ht, unsigned int key);
void ht_print(struct hashtable_t* ht);
void ht_delete(struct hashtable_t* ht, unsigned int key);
void ht_free(struct hashtable_t* ht);

#endif

hashtable.c

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

// Sources used as reference/learning material:
// http://pokristensson.com/code/strmap/strmap.c
// https://github.com/Encrylize/hashmap/blob/master/hashmap.c
// https://github.com/goldsborough/hashtable/blob/master/hashtable.c

hashtable_t *ht_new(unsigned int bucket_count)
{
    struct hashtable_t *ht;

    ht = malloc(sizeof(struct hashtable_t));
    if (ht == NULL)
        return NULL;

    ht->buckets = malloc(sizeof(entry_t) * bucket_count);
    if (ht->buckets == NULL)
        return NULL;

    ht->buckets_count = bucket_count;

    return ht;
}

void ht_delete(struct hashtable_t *ht, unsigned int key)
{
    unsigned int index = compute_hash(ht, key);
    entry_t *e_curr = ht_get(ht, key);

    /* Chain has no entries */
    if (e_curr == NULL)
        return;

    entry_t *e_prev = e_curr->prev;
    entry_t *e_next = e_curr->next;

    /* Entry is first element in the chain */
    if(e_prev == NULL)
    {
        if(e_next != NULL)
        {
            e_next->prev = NULL;
        }

        ht->buckets[index] = e_next;
        free(e_curr);
    }
    /* Entry is not the first element in the chain */
    else
    {
        while(e_curr->key != key)
        {
            e_curr = e_next;
            e_prev = e_curr;
        }

        e_prev->next = e_next;

        if(e_next != NULL)
            e_next->prev = e_prev;

        free(e_curr);
    }
}

int ht_add(struct hashtable_t *ht, unsigned int key, void* value)
{
    unsigned int index = compute_hash(ht, key);

    struct entry_t *new_entry = malloc(sizeof(struct entry_t));
    if (new_entry == NULL)
        return -1;

    if (ht->buckets[index] != NULL)
    {
        /* Go to the end of the linked list and append new entry */
        entry_t *current_entry = ht->buckets[index];
        while (current_entry->next != NULL)
        {
            current_entry = current_entry->next;
        }

        new_entry->key = key;
        new_entry->value = value;
        new_entry->next = NULL;
        new_entry->prev = current_entry;
        current_entry->next = new_entry;

    } else
    {
        new_entry->key = key;
        new_entry->value = value;
        new_entry->next = NULL;
        new_entry->prev = NULL;

        ht->buckets[index] = new_entry;
    }
    return 0;
}

// Taken from https://burtleburtle.net/bob/hash/integer.html
// Should give a fairly decent distribution of entries
unsigned int compute_hash(struct hashtable_t *ht, unsigned int key)
{
    key = (key ^ 61) ^ (key >> 16);
    key = key + (key << 3);
    key = key ^ (key >> 4);
    key = key * 0x27d4eb2d;
    key = key ^ (key >> 15);
    return key % ht->buckets_count;
}

void ht_print(struct hashtable_t *ht)
{
    for (int i = 0; i < ht->buckets_count; ++i)
    {
        struct entry_t *e_curr = ht->buckets[i];

        printf("[%d]", i);
        do
        {
            if (e_curr == NULL)
            {
                printf(" NULL\n");
                break;
            }
            printf(" %d <->", e_curr->key);

            if (e_curr->next == NULL)
            {
                printf(" NULL\n");
                break;
            }
            e_curr = e_curr->next;
        } while (1);
    }
}

entry_t *ht_get(struct hashtable_t *ht, unsigned int key)
{
    unsigned int index = compute_hash(ht, key);

    entry_t *e_curr = ht->buckets[index];

    while (e_curr->key != key)
    {
        e_curr = e_curr->next;

        /* Specified key does not exist in ht */
        if (e_curr == NULL)
            return NULL;
    }

    return e_curr;
}

void ht_free(struct hashtable_t *ht)
{
    free(ht->buckets);
    free(ht);
}

main.c

#include <stdio.h>
#include "hashtable.h"

int main()
{
    hashtable_t *ht = ht_new(5);

    printf("ADDING ELEMENTS ...\n");

    ht_add(ht, 10, 1);
    ht_add(ht, 20, 2);
    ht_add(ht, 30, 3);
    ht_add(ht, 40, 4);
    ht_add(ht, 50, 5);
    ht_add(ht, 60, 6);
    ht_add(ht, 70, 7);
    ht_add(ht, 80, 8);
    ht_add(ht, 90, 9);
    ht_add(ht, 100, 10);
    ht_print(ht);

    printf("DELETING ELEMENTS ...\n");

    ht_delete(ht, 80);
    ht_delete(ht, 70);
    ht_delete(ht, 50);
    ht_print(ht);

    ht_free(ht);
    return 0;
}

Answer 1

Design:

The frist thing I see is that the hashtable is in two parts. You don't need to do this. Make it a single object and remove a whole bunch of edge cases you need to test.

typedef struct hashtable_t
{
    unsigned int buckets_count;
    struct entry_t **buckets;     // A pointer to another block.
                                  // This block needs to be seprately
                                  // allocated and maintained.
} hashtable_t;

Rather do this:

typedef struct hashtable_t
{
    unsigned int buckets_count;
    entry_t      buckets[0];     // This is a fake array object.
                                 // You just allocate enough space for
                                 // the buckets you want and they
                                 // be correctly aligned in the same
                                 // object.
} hashtable_t;


hashtable_t&  table  = (hashtable_t*)malloc(sizeof(hashtable_t) + sizeof(entry_t) * buckets_count);

---

Hash tables are hard to get correct and sizing the number of buckets is important if you want to avoid clashes. So *Normally you want a bucket count that is a prime number. You can not expect the user of your hash table to know this some asking them for a bucket count is a bad idea. I would change the interface so that your code simply uses a prime number of buckets (if you want to be expandable then allow them to input some value that gets converted to nearest prime or select from a know good set of primes that you support).

---

Your design allows for multiple entries in the table to have the same key. You could argue this is a design decision I suppose. But usually you would expect keys to be unique and subsequent writes with the same key to over-right existing values.

If you deliberately want to support multiple items with the same key then you really need to explain this in the documentation up front to make sure the user is clear on the concept.

Code Review

I would note that POSIX reserves all identifers that end in _t.

typedef struct hashtable_t
{} hashtable_t;

---

    ht = malloc(sizeof(struct hashtable_t));
    if (ht == NULL)
        return NULL;

    ht->buckets = malloc(sizeof(entry_t) * bucket_count);
    if (ht->buckets == NULL)
        // If you return here.
        // You have leaked the initial allocation.
        // you need to add free(ht) first
        // don't forget the braces.
        return NULL;

---

Why not put the ht_free() next?

void ht_free(struct hashtable_t *ht)
{
    free(ht->buckets);
    free(ht);
}

Would have nice to have the allocation/deallocation close to each other.

---

This is a bad choice.

        /* Go to the end of the linked list and append new entry */
        entry_t *current_entry = ht->buckets[index];
        while (current_entry->next != NULL)
        {
            current_entry = current_entry->next;
        }

Put new clashes at the front of the list. It is more likely that new values will be used sooner than old values. So a value that has recently been put in the table will likely be used again and thus putting it at the front of the list will decrease accesses time.

---

Useless code that is never executed.

    /* Entry is not the first element in the chain */
    else
    {
        // This is never true.
        // You just searched for the item with ht_get() which either
        // returns the first item that matches key or null.
        while(e_curr->key != key)
        {
            // This loop will never be entered.
            e_curr = e_next;
            e_prev = e_curr;
        }

---

We could simplify the print a lot:

void ht_print(struct hashtable_t *ht)
{
    for (int i = 0; i < ht->buckets_count; ++i)
    {
        printf("[%d] ", i);
        struct entry_t *e_curr = ht->buckets[i];

        for (;e_curr != NULL; e_curr = e_curr->next)
        {
            printf("%d <=>", e_curr->key);
        }
        printf(" NULL\n");
    }
}

---

I would simplify the loop here:

entry_t *ht_get(struct hashtable_t *ht, unsigned int key)
{
    unsigned int index   = compute_hash(ht, key);
    entry_t      *e_curr = ht->buckets[index];

    for (;e_curr != NULL; e_curr = e_curr->next) {
        if (e_curr->key == key) {
            return e_curr;
        }
    }

    return NULL;
}

Answer 2

Some people might say that you should split these into more functions. Things that can easily be extracted into functions are those code-blocks for when you're dealing with just the one element or multiple elements in a bucket. E.g. in ht_delete(), you might say something like:

if (e_prev->prev == NULL) {
    ht__delete_head_element(e_curr, index);
} else {
    ht__delete_tail_element(e_curr, index);
}

I also noticed that if ht_new() fails on the second malloc(), the result of the first malloc() leaks.

Answer 3

Documentation

If you want this to be generically usable as a library, consider adding documentation comments to hashtable.h. In particular, details about who's responsible for freeing the value pointer on ht_free - this library or the caller (it seems like the latter) - are very important. You can follow something like Doxygen format or a basic /**/ comment.

Constant references

ht_get should use a const struct hashtable_t *ht.

Tags vs. typedef

It's not well-advised to set a struct tag the same as its typedef. Also, you're failing to use the typedef name and rewriting struct on every reference to hashtable_t. Instead consider something like

typedef struct hashtable_tag
{
    // ...
} hashtable_t;


void ht_free(hashtable_t* ht);

Memory leak

What if

ht = malloc(sizeof(struct hashtable_t));

succeeds, but

ht->buckets = malloc(sizeof(entry_t) * bucket_count);

fails? You will have leaked the memory for ht. You should have a corresponding free for it before the return NULL.

Explicit sizes

It seems like you assume key to be 32 bits here:

unsigned int compute_hash(struct hashtable_t *ht, unsigned int key)
{
    key = key * 0x27d4eb2d;

This is not a safe assumption to make. Consider uint32_t instead.