Are there any maintained hash table implementations in C that are designed for embedded systems?

Question

Situation: I have a set of key-value pairs of (uint32_t, uint8_t[12]). My current approach to retrieving the uint8_t[12] values is to parse a CSV file that contains the mappings, and fill a buffer if it's found. Ideally, I'd like to retain the ability to reload the hash table from the CSV, but for now I just need something fast and memory efficient.

Constraints: 64kiB of 16-bitRAM, 10MHz CPU, storage for at least 1600 key-value pairs (about 27kB by my calculations).

Solutions I have considered:

• GHashTable: Seems like it may have too many features. glib is a large library

• khash: Unmaintained, macro heavy and so difficult to debug/modify

• uthash: Seems decent, relatively recent release (July 2016), but also macro heavy. Any thoughts?

Answer 1

Update: now as a proper Github repository: https://github.com/vi/macro_robinhood_hash

---

Here is my Robin Hood open addressing hash table in C implemented entirely in macros: https://gist.github.com/vi/42c4d7bc854653a17e9085c8831c6dcd

It is fixed size and memory-allocation-free and you can choose your own storage scheme. You give it primitives: setting/geting/clearing key/value for a cell, swapping cells and it gives you hash map operations.

Example:

#include <assert.h>
#include "robinhoodhash.h"

struct entry {
    int key;
    char value;
};

struct entry hshtable [100];

#define qqq_setvalue(index, key_, val_) \
        hshtable[index].key=key_; hshtable[index].value=val_;
#define qqq_setnil(index)   \
        hshtable[index].key=-1; hshtable[index].value=0;
#define qqq_swap(index1, index2) \
        struct entry tmp = hshtable[index1]; \
        hshtable[index1] = hshtable[index2]; \
        hshtable[index2] = tmp;

#define qqq_nilvalue        0
#define qqq_getvalue(index) hshtable[index].value
#define qqq_getkey(index)   hshtable[index].key
#define qqq_keysequal(key1,key2) key1 == key2
#define qqq_isnil(index)    hshtable[index].key == -1
#define qqq_n_elem          100
#define qqq_getbucket(key)  key%99 + 1
#define qqq_overflow        {}
#define qqq_removefailed(key)  {}

int main() {
    ROBINHOOD_HASH_CLEAR(qqq);

    char value = '_';

    ROBINHOOD_HASH_GET(qqq, 4433, value);
    assert(value == 0);

    ROBINHOOD_HASH_SET(qqq, 4433, 'A');
    ROBINHOOD_HASH_SET(qqq, 123,  'B');

    ROBINHOOD_HASH_GET(qqq, 4433, value);
    assert(value == 'A');
    ROBINHOOD_HASH_GET(qqq, 123, value);
    assert(value == 'B');

    ROBINHOOD_HASH_DEL(qqq, 4433);

    ROBINHOOD_HASH_GET(qqq, 4433, value);
    assert(value == 0);
    ROBINHOOD_HASH_GET(qqq, 123, value);
    assert(value == 'B');
    return 0;
}

Answer 2

khash

It is a header only hash table implemented with macros, memory efficient and fast. It holds up well even compared to modern c++ hash tables.

khash uses double hashing as a probing strategy. I found out about it when trying to develop a c++ hash table to improve memory efficiency and in my tests it is only slightly slower than the best c++ hash tables there are.

khash is part of klib, a collection of c data structures and algorithms, mostly in their own respective headers, very modular, efficient and useful altogether.

With 1600 key-value pairs you might get away with a sorted list however, even easier, maybe fast enough.