A simple hash table in C

• QEMU

  190 9,277 10.0 C

  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

  3 80 1.5 C++

  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.

• InfluxDB

  www.influxdata.com sponsored

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• Klib

  23 4,021 4.3 C

  A standalone and lightweight C library

• sc

  17 2,165 6.3 C

  Common libraries and data structures for C.

• uthash

  4 3,931 2.3 C

  C macros for hash tables and more

• ctl

  22 162 5.9 C

  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

  2 11 0.0 C

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

• WorkOS

  workos.com sponsored

  The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  

Suggest a related project