4
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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;
}
\$\endgroup\$
2
  • \$\begingroup\$ Your suggestion for struct hashtable_t works for OP's code where the hash table is never resized, but if you want to dynamically size the number of buckets, you do need the indirection. \$\endgroup\$ – G. Sliepen Dec 16 '20 at 22:46
  • \$\begingroup\$ @G.Sliepen Agree. If you need to resize buckets then a separate bucket list may be useful. But I think that is a more advanced feature. \$\endgroup\$ – Martin York Dec 16 '20 at 23:11
3
\$\begingroup\$

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.

\$\endgroup\$
2
+25
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ Thanks for your review, definitly helpful. I am also really curious if the add and get code can be more concise/cleaner. Do you have any suggestions for that as well? As for the memory leak issue - good catch. What is the best way to implement the free logic here? Should I make a check if malloc1 == 0 and malloc2 < 0 then free - or what would be the cleanest approach here. I also just realized that valgrind also reports a memory leak in the ht_add function. I have to look into that. \$\endgroup\$ – 766F6964 Dec 15 '20 at 21:58
  • \$\begingroup\$ The suffix _t is reserved by POSIX. Even C reserves some names ending with _t, see this question. \$\endgroup\$ – G. Sliepen Dec 15 '20 at 22:48
  • 1
    \$\begingroup\$ @G.Sliepen Sure; but that's a problem with the original question, not something I've introduced in my answer. Feel free to address it in an answer of your own. \$\endgroup\$ – Reinderien Dec 15 '20 at 23:01
  • 2
    \$\begingroup\$ It's not well-advised to set a struct tag the same as its typedef. Every C project I have been on sets them to the same value. They are in different namespaces so they will never clash. \$\endgroup\$ – Martin York Dec 16 '20 at 22:30
  • \$\begingroup\$ @MartinYork Distinguish between "can" and "should". It's a stretch to say "every C project names tags and typedefs the same way", and counterexamples abound - see for instance most of win32. \$\endgroup\$ – Reinderien Dec 16 '20 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.