A simple hash table in C

This page summarizes the projects mentioned and recommended in the original post on news.ycombinator.com

Our great sponsors
  • Onboard AI - Learn any GitHub repo in 59 seconds
  • InfluxDB - Collect and Analyze Billions of Data Points in Real Time
  • SaaSHub - Software Alternatives and Reviews
  • QEMU

    Official QEMU mirror. Please see https://www.qemu.org/contribute/ for how to submit changes to QEMU. Pull Requests are ignored. Please only use release tarballs from the QEMU website.

    I've had lately a look at QEMUs internals and saw their thread safe implementation of a hash table, capable of concurrent reads: qht [0].

    If the author sees this, you might want to take a look at it.

    [0] https://github.com/qemu/qemu/blob/master/util/qht.c

  • smol_world

    Compact garbage-collected heap and JSON-like object model

    Thank you for this article.

    I have been working on trying to design a contiguous hash table data structure that has these two mutual requirements:

    a) allows deep clones (due to contiguous memory copyable with memcpy)

    b) supports arbitrarily nestable hashmaps

    The closest library I know about is smolworld ( https://github.com/snej/smol_world ) but I don't know how easy it can be cloned.

    These requirements rules out multiple mallocs: I do one single malloc and expect that to be enough for the entire hashmap.

    I'm not sure if these constraints might also force a fixed number of buckets and a fixed capacity.

    The clonable property requires interior mutability be limited, because if you memcpy pointers they would cause structure sharing, that I'm trying to avoid, hence a deep clone.

    Rationale: these are the use cases I have for such a data structure. The first is cheap copy on write. I also have a left-right concurrency hashmap, but I feel the properties of this data structure are even better. The first is a sharding in multithreading design: do a cheap memcpy for each thread and shard the processing and merge at the end, without any synchronization cost while the threads are working. I know that deep cloning is slow in Java if you do it with loops rather than memcpy. Another use case is efficient serialization.

  • Onboard AI

    Learn any GitHub repo in 59 seconds. Onboard AI learns any GitHub repo in minutes and lets you chat with it to locate functionality, understand different parts, and generate new code. Use it for free at www.getonboard.dev.

  • Klib

    A standalone and lightweight C library

  • sc

    Common libraries and data structures for C.

  • uthash

    C macros for hash tables and more

  • ctl

    My variant of the C Template Library (by rurban)

    search for htable or hashtable in thousands of open source projects. only a minority has worse hashtables than this one (clisp, perl5 e.g.).

    For better ones I would point to my linked list implementation: https://github.com/rurban/ctl/blob/master/ctl/unordered_set.... (because it has various security policies, nobody else has)

  • swiss-table

    C adaptation of the swiss table (flat hash map) presented at CppCon by Google (https://www.youtube.com/watch?v=ncHmEUmJZf4).

  • InfluxDB

    Collect and Analyze Billions of Data Points in Real Time. Manage all types of time series data in a single, purpose-built database. Run at any scale in any environment in the cloud, on-premises, or at the edge.

NOTE: The number of mentions on this list indicates mentions on common posts plus user suggested alternatives. Hence, a higher number means a more popular project.

Suggest a related project

Related posts