hashset.h File Reference

High-performance hash set implementation in C. More...

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

Include dependency graph for hashset.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Detailed Description

High-performance hash set implementation in C.

Why this implementation is fast?

Flat open-addressed hash table with keys stored inline.

• Zero extra heap allocations per element.
• Linear probing with Robin Hood displacement to minimise variance.
• Metadata byte per slot (EMPTY / DELETED / hash-fingerprint) enables cache-friendly SIMD-style batch scans even in plain C.
• Backward-shift deletion: no tombstone accumulation.
• One contiguous allocation for the whole table.

Trade-offs

• Keys are copied inline; key_size must be fixed.
• Table must be reallocated when load exceeds 75 %.
• Iteration order is insertion-independent.

Definition in file hashset.h.