He4: A fast fixed-memory hash table

I needed a fast, fixed-memory hash table in C, so I ended up writing one. The advantage is that the table does not automatically grow, keeps track of when items are found, and can be rehashed to a new table of exactly the same size. This allows for very predictable performance without ever running out of memory.

For instance, the following works nicely.

while (table->load() > 0.5) {
    table = he4_trim_and_rehash(table, table->capacity, table->max_touch / 2);

This creates and returns a new table with the same capacity as the old table, with the entries rehashed, and with all entries whose “touch index” is less than half the maximum index discarded and freed. The old table is also freed. In short, after this runs the table is at most half full and the least-recently-used items are the ones that have been discarded.

Find the code on Github if you are interested. Code is licensed under the BSD two-clause license.

Leave a Reply

Your email address will not be published. Required fields are marked *