Data structures & hashing

Open-addressing hash table that filters 8-16 slots at once with 1-byte hash tags and SIMD, giving fast lookups at 87.5 % load.

Linear probing where an inserting key evicts any resident closer to its home slot, keeping probe lengths short and uniform at 90 % load.

Every key lives in one of two candidate buckets, so lookups read at most two cache lines; inserts evict residents to their alternate bucket.

Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.

Byte-wise radix tree whose nodes resize between 4, 16, 48 and 256 children; ordered, space-efficient, and close to hash-table speed in memory.

Sorted linked list with random express lanes; O(log n) search, simple inserts, and easy lock-free or single-writer concurrent reads.

Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.

Index of ranges that answers "which intervals overlap this point or range?" in O(log n + k); static sorted-array form is the compact, cache-friendly choice.

Bit array answering "definitely not present" or "probably present" in about 10 bits per key for 1 % false positives; inserts are cheap, deletes impossible.

Static membership filter where 3 slots xor to the key's fingerprint; 1.23× the space minimum and 3 memory reads per query.

Counts distinct elements in kilobytes with about 1 % error by tracking the longest run of leading zero bits in hashed values per bucket.

d rows of w counters estimate any item's frequency in a stream, overestimating by at most ε·N with probability 1-δ, in fixed tiny memory.

Bounded wait-free queue for exactly one producer and one consumer thread, built from an array and two indices with acquire/release ordering.

A hash function mapping n fixed keys to 0..n-1 without collisions, in 1.5-4 bits per key; the keys themselves are not stored.

Bitvector plus small count tables: ones before position i and position of the k-th one in O(1); Elias-Fano builds compressed sorted lists on it.