Hashtable with open addressing

This library provides a simple hashtable written in C. The hashtable is stored as a single heap allocated array. This storage scheme is good for caching, since everything is densely packed and pointer chasing is avoided in contrast to hashtables which use linked lists. The array will grow automatically, when the filling reaches a certain threshold.

By using macros, the library is specialized for each entry type. For example it is possible to generate a hashset without overhead, by using entries consisting only of a key. Arbitrary key types are supported and various hash functions are provided in hashfn.h.

Configure the hash table

At first we create the hashtable functions and datastructure for the special entry type MyEntry. For optimal performance all hash functions are specialized for this entry type.

typedef struct {
    const char* k;
    int         v;
} MyEntry;

#define HASH        MyHash
#define ENTRY       MyEntry
#define PREFIX      myhash
#define KEY(e)      e->k
#define EXISTS(e)   e->k
#define KEYEQ(a, b) !strcmp(a, b)
#define HASHFN      hashString
#include "hashtable.h"

Usage

int main(void) {
    MyHash h = HASH_INIT;

    MyEntry* e;

    if (myhashCreate(&h, "a", &e)) {
        printf("ENTRY CREATED\n");
        e->k = "a";
        e->v = 1;
    }

    myhashCreate(&h, "b", &e);
    e->k = "b";
    e->v = 2;

    myhashCreate(&h, "c", &e);
    e->k = "c";
    e->v = 3;

    myhashCreate(&h, "c", &e);
    e->k = "c";
    e->v = 4;

    e = myhashFind(&h, "a");
    if (e)
        printf("FOUND a %d\n", e->v);
    else
        printf("NOT FOUND a\n");

    e = myhashFind(&h, "d");
    if (e)
        printf("FOUND d %d\n", e->v);
    else
        printf("NOT FOUND d\n");

    HASH_FOREACH(myhash, f, &h)
        printf("%s %d\n", f->k, f->v);
}

License

MIT (c) 2018 Daniel Mendler