Celerity

Celerity is a .NET library of specialized, high-performance collections — drop-in alternatives to the BCL that trade flexibility for speed or memory on specific workloads. Hashers are structs supplied as generic constraints (so the JIT inlines them), load factors are configurable, and you can plug in your own hash functions.

dotnet add package Celerity.Collections

New here? Jump to Choosing a collection — the table maps your workload to the right type in one line.

Packages

Celerity's core ships as layered NuGet packages. Celerity.Collections pulls in the hashing and primitives packages transitively, so a single dotnet add package Celerity.Collections still gives you everything on that line — add the lower packages directly only if you want the hashers or primitives without the collections. Celerity.Sorting is a sibling rather than a dependency of the collections: add it when you want the sorts.

Package	What it adds	Depends on
Celerity.Collections	dictionaries, sets, frozen/perfect-hash collections, streaming sketches	Celerity.Hashing, Celerity.Primitives
Celerity.Hashing	IHashProvider<T> / IHashProvider64<T>, the struct hashers, HashQualityEvaluator	Celerity.Primitives
Celerity.Primitives	FastUtils, struct PRNGs, VarInt, FastGuid, SortedSpan	—
Celerity.Sorting	RadixSort, CountingSort, PartialSort — non-comparison sorts and selection over primitive keys	Celerity.Primitives

Upgrading from 1.x? Namespaces are unchanged except FastUtils, which moved from Celerity to Celerity.Primitives. See the migration guide.

All four packages multi-target net8.0, net9.0, and net10.0, so NuGet hands your project the assembly built against its own runtime. net8.0 (LTS) is the floor — Celerity runs anywhere from .NET 8 upward.

Built with Celerity

Standalone libraries built on top of Celerity — each solves a real problem in a domain where a pure-managed .NET implementation is the right call (chatty per-element work over managed keys, fixed-memory streaming over unbounded input, or hashing that must be identical across runtimes) and dropping to a native C/C++ library would be a net loss. They ship as separate NuGet packages that depend on Celerity.Collections — add only the one you need.

Package	What it gives you
Celerity.Ring	Consistent-hash & rendezvous (HRW) rings for sharding and request routing, generic over your key type and hasher — with byte-identical node assignment across OS / architecture / runtime (x64, arm64, Blazor WASM), so every node in a cluster agrees on the mapping. Fills a gap the BCL has no type for. README
Celerity.Sentinel	Streaming abuse / heavy-hitter detection — surfaces the top offenders, per-key rate, and fan-out cardinality of a request stream in a fixed footprint regardless of key cardinality, so it survives the attacker key-rotation that drives a Dictionary<,> counter to OOM. Includes a striped tracker for concurrent hot paths. README
Celerity.Cardinality	Mergeable approximate COUNT(DISTINCT) and windowed dedup over unbounded managed streams — exact for small inputs, promoting to a fixed ~16 KB estimator past a threshold, with deterministic cross-shard merge identical on every runtime. README

These are a separate tier from the core Celerity.Collections family above: they depend on it, but you don't get them by installing it — reach for one only when its problem is yours. (The NuGet badges populate on first publish.)

Collections

Dictionaries

• CelerityDictionary<TKey, TValue, THasher> — the generic baseline: open-addressed dictionary with a struct hasher constraint.
• RobinHoodDictionary<TKey, TValue, THasher> — Robin Hood probing bounds probe-length variance, keeping worst-case lookups close to average on clustered / adversarial keys (cost: a per-slot probe-distance int).
• SwissDictionary<TKey, TValue, THasher> — Swiss-table SIMD group probing: one Vector128 compare tests 16 slots per lookup, filtered by a 7-bit hash tag (cost: one control byte per slot). For lookup-heavy tables.
• HashCachingDictionary<TKey, TValue, THasher> — struct-of-arrays layout: a dense side array of 32-bit hash fingerprints lets probes scan metadata only and skip expensive key equality on a single integer compare (cost: four bytes per slot). For costly-equality keys.
• PooledCelerityDictionary<TKey, TValue, THasher> — backing arrays rented from ArrayPool<T>.Shared and returned on Dispose, cutting GC pressure for short-lived, frequently-rebuilt dictionaries. Same API plus IDisposable.
• FrozenCelerityDictionary<TValue> / <TValue, THasher> — build-once, read-many string-keyed dictionary that searches for a perfect (collision-free) hash so lookups are single-probe.
• CelerityMultiMap<TKey, TValue, THasher> — one-to-many map: Add appends instead of overwriting. Implements ILookup<TKey, TValue?>.
• CelerityMultiSet<T, THasher> — counting multiset (bag): each element maps to its multiplicity. Single-probe Add-increment for frequency counting, vs the two-probe Dictionary<T,int> idiom. Count (distinct) / TotalCount (occurrences).
• SmallDictionary<TKey, TValue> — flat-array, linear-scan dictionary for the very-small (n <= ~16) case. No hasher; the default key is stored inline.
• EnumMap<TEnum, TValue> — dense array-backed dictionary for enum keys (the .NET EnumMap): a lookup is a direct array index — no hashing, no probing, no collisions. Enumerates in ascending underlying-value order. The dictionary counterpart of EnumSet.
• IntDictionary<TValue> / LongDictionary<TValue> — int / long-keyed specializations (default to Int32WangNaiveHasher / Int64WangNaiveHasher).

Sets

• CeleritySet<T, THasher> — generic set counterpart to CelerityDictionary.
• SwissSet<T, THasher> — Swiss-table SIMD group probing for sets: one Vector128 compare tests 16 slots per membership check, filtered by a 7-bit hash tag (cost: one control byte per slot). For membership-heavy sets with many negative lookups. The set counterpart of SwissDictionary.
• RobinHoodSet<T, THasher> — Robin Hood probing for sets: bounds probe-length variance and lets negative Contains lookups exit early on clustered / adversarial elements (cost: a per-slot probe-distance int). The set counterpart of RobinHoodDictionary.
• HashCachingSet<T, THasher> — struct-of-arrays layout for sets: a dense side array of 32-bit hash fingerprints lets probes scan metadata only and short-circuit expensive element equality on a single integer compare (cost: four bytes per slot). For lookup-heavy sets and costly-equality elements. The set counterpart of HashCachingDictionary.
• PooledCeleritySet<T, THasher> — backing array rented from ArrayPool<T>.Shared and returned on Dispose, cutting GC pressure for short-lived, frequently-rebuilt sets. Same API plus IDisposable. The set counterpart of PooledCelerityDictionary.
• FrozenCeleritySet / <THasher> — build-once, read-many string set with single-probe membership. Implements IReadOnlySet<string>.
• IntSet / LongSet — int / long-keyed set specializations.
• SmallSet<T> — flat-array, linear-scan set for the very-small (n <= ~16) case. No hasher; the default element is stored inline. The set counterpart of SmallDictionary.
• EnumSet<TEnum> — bit-vector set for enum keys (the .NET EnumSet): membership is a single bit test and set algebra is word-wise bitwise ops, with no hashing or boxing. Enumerates in ascending underlying-value order.
• SparseSet — bounded-universe integer set (Briggs–Torczon sparse set): O(1) Clear that leaves the backing arrays untouched, plus dense, cache-friendly iteration — for clear-and-rebuild "visited" sets over ids in [0, N) (graph traversal, ECS, sweep-line). Costs O(Universe) memory.
• CompressedIntSet — exact, compressed set of 32-bit integers: each 65,536-value chunk is stored as a sorted array or a bitmap by density, with an opt-in run-length form for clustered data that Optimize() and AddRange produce. Set algebra runs word-parallel inside a chunk and skips a whole chunk with one comparison, memory is ~10x below HashSet<int> (far more when dense or clustered), and enumeration is in ascending order. For huge-and-sparse integer sets — posting lists, row-id sets, cohort intersection. No portable Roaring format: this is an in-process structure, not an interop codec.

The mutable sets (CeleritySet, SwissSet, RobinHoodSet, HashCachingSet, IntSet, LongSet, SmallSet, EnumSet, SparseSet, CompressedIntSet) all implement ISet<T> — the full HashSet<T> set-algebra surface (UnionWith / IntersectWith / ExceptWith / SymmetricExceptWith and the IsSubsetOf / IsSupersetOf / Overlaps / SetEquals query family, plus CopyTo) with BCL semantics — so they drop in wherever a HashSet<T> is used. (The bounded-domain sets, EnumSet and SparseSet, are the exception to "drop in anywhere": they store only values in their fixed domain, so a mutating op that must add an out-of-domain value throws.)

Caches

• LruCache<TKey, TValue, THasher> — fixed-capacity least-recently-used cache with O(1) get/put and automatic eviction of the least-recently-used entry. Recency runs through an intrusive doubly-linked list over fixed-size arrays, so the hot get/put/evict path allocates nothing — unlike the idiomatic Dictionary + LinkedList LRU that heap-allocates a node per insert. Reads count as uses (a hit promotes the entry to most-recently-used); TryPeek / ContainsKey inspect without disturbing recency.

Sequences

• Deque<T> — growable double-ended queue backed by a circular buffer: O(1) amortized push / pop / peek at both ends, plus O(1) random access by index. The array-backed deque the BCL lacks (Queue<T> is FIFO-only, Stack<T> LIFO-only, and LinkedList<T> allocates a node per element) — a bounded FIFO / sliding-window churn reuses the buffer with wrap-around and allocates nothing, and enumeration walks contiguous memory. Implements IReadOnlyList<T>.

Union-find

• DisjointSet<T> — union-find over arbitrary elements: partitions them into disjoint sets with near-O(1) amortized Union / Find / Connected via union by size + path halving. The union-find the BCL lacks — incremental connectivity, connected components, Kruskal MST, and undirected cycle detection in near-linear total time, where the Dictionary + HashSet set-merge substitute is quadratic. GetComponents() materializes the current partition.

Priority queue

• IndexedPriorityQueue<TElement, TPriority, THasher> — addressable binary min-heap: unlike the BCL PriorityQueue<,> it can change a queued element's priority (Update / decrease-key) and remove an arbitrary element in O(log n), and answer Contains / TryGetPriority in O(1). The heap the priority-relaxation loop of Dijkstra / Prim / A* needs — no lazy-deletion heap growth. Each element is a key (appears once); pass a custom IComparer<TPriority> for a max-heap.

Prefix trees

• Trie<TValue> — ordered prefix tree mapping string keys to values. GetByPrefix lists every entry whose key starts with a prefix in O(prefix + matches), and TryGetLongestPrefix finds the longest stored key that is a prefix of a query in O(query). The trie the BCL lacks — autocomplete, longest-prefix routing, and ordered (ascending-ordinal) iteration, where a Dictionary<string, TValue> has no prefix index and must scan every key and run StartsWith. Exact Add / TryGetValue favour a Dictionary (one hash vs a character walk); the trie earns its place on the prefix operations. Implements IReadOnlyDictionary<string, TValue?>.

Span-keyed string lookups

• StringInternTable / StringInternTable<THasher> — a canonicalizing token table probed with a ReadOnlySpan<char>: GetOrAdd returns the one shared string for those characters and allocates only on a miss. A 10M-cell parse over 100 distinct tokens creates 100 strings instead of 10,000,000. The collection you cannot build on the pre-.NET-9 BCL — HashSet<string>.TryGetValue makes you allocate the string before you can discover you already had it, and string.Intern is process-wide, never collected, and still needs a string. Implements IReadOnlyCollection<string>.
• The same span-keyed probes ship on FrozenCelerityDictionary, FrozenCeleritySet, CelerityDictionary<string, …>, CeleritySet<string, …>, and Trie<TValue> — so a tokenizer, CSV/log reader, or route dispatcher holding a slice of its input buffer never has to call new string(span) per lookup. Works on all three target frameworks, including the net8.0 floor where the BCL has no equivalent (.NET 9 added Dictionary<string,V>.GetAlternateLookup). See span-keyed lookups.

Sorted (ordered) collections

• BTreeDictionary<TKey, TValue, TComparer> / BTreeDictionary<TKey, TValue> — a sorted map backed by a B-tree: up to 31 keys per node in flat arrays, so a lookup visits log₃₂(n) nodes instead of chasing log₂(n) pointers — roughly 4 cache misses instead of ~20 at n = 1M. Adds the ordered surface a hash table cannot answer: Min, Max, TryGetLowerBound / TryGetUpperBound, EnumerateRange in O(log n + k), and in-order enumeration. The B-tree the BCL lacks — SortedDictionary<,> is a red-black tree with one heap object per entry, and SortedList<,> memmoves the tail on every insert. Implements IDictionary<TKey, TValue?> and IReadOnlyDictionary<TKey, TValue?>.
• BTreeSet<T, TComparer> / BTreeSet<T> — the set counterpart, with the same ordered surface and no values to store, so the memory saving over SortedSet<T> is larger still. Implements ISet<T> and IReadOnlySet<T>.

Both take their ordering as a struct IComparer<T> type parameter (DefaultComparer<T> by default), exactly as the hashers are struct type parameters, so the comparison inlines instead of costing a virtual call per key inspected inside a node.

Range aggregates

• FenwickTree<T> — a Binary Indexed Tree over a fixed-length numeric sequence (where T : struct, INumber<T>): point update and prefix / range sum both in O(log n), in one flat array with no per-node overhead. The prefix-sum structure the BCL lacks — running aggregates, rank / order-statistics counters, cumulative-frequency tables — where a plain array is O(n) per query (recompute the slice) or O(n) per update (fix the suffix). Wins precisely when updates and partial-sum queries interleave.
• SegmentTree<T, TMonoid> — range aggregates over an arbitrary associative fold: point update and range query both in O(log n), in one flat array of 2n cells. The half of the range-query space a Fenwick tree cannot reach — its query is the difference of two prefix folds, so it needs an inverse, while a segment tree stores each node's fold outright. That puts range min, max, gcd, bitwise and/or and any monoid you write in reach. The BCL has no range-aggregate structure at all, so the baseline is a plain array scanned per query. SumMonoid / MinMonoid / MaxMonoid / BitwiseAndMonoid / BitwiseOrMonoid ship built in, as struct type parameters so the fold inlines; non-commutative folds are safe, since the query preserves index order.

Probabilistic & bit-level

• BloomFilter<T, THasher> — probabilistic membership: bit-array storage, no false negatives, tunable false-positive rate, a fraction of a HashSet<T>'s memory. Add-and-test only.
• CuckooFilter<T, THasher> — probabilistic membership that supports deletion: fingerprint buckets, no false negatives, tunable false-positive rate, ≤2 cache lines per lookup. The Bloom filter you can Remove from.
• XorFilter<T, THasher> — probabilistic membership that is build-once & immutable: ~9.84 bits/element (smaller than a Bloom filter at the same rate), three probes + two XORs per lookup (branch-free). The smallest, fastest-to-query filter for a fixed element set.
• BitSet — dense, exact bit vector in 64-bit words: O(n/64) hardware popcount (Count) and SIMD bulk And/Or/Xor/Not. A faster, count-aware BitArray.
• RankSelectBitVector — immutable succinct index over a dense bit vector: Rank(i) (set bits below i) in O(1) and Select(k) (position of the k-th set bit) in O(log n), for 25% space over the bits. The BCL has no rank or select anywhere, so the baseline is a hand-rolled O(i/64) popcount loop. Build-once — any mutation means rebuilding the index, so keep mutating vectors in BitSet and snapshot once they settle.
• HyperLogLog<T, THasher> — probabilistic cardinality estimator: counts distinct elements from a fixed ~16 KB of registers (~0.8% error), never growing with the data. Mergeable.
• CountMinSketch<T, THasher> — probabilistic frequency estimator: estimates per-element counts from a fixed grid, never underestimating (overestimate bounded by epsilon · TotalCount). Mergeable.
• TopKSketch<T, THasher> — probabilistic top-k / heavy-hitters sketch (Space-Saving): reports a stream's most frequent elements from a fixed k monitors in O(k) memory, never underestimating and never missing a hitter above TotalCount / k.

The mutable dictionaries implement both IDictionary<TKey, TValue?> and IReadOnlyDictionary<TKey, TValue?>, so they drop into an existing API taking either BCL interface; the immutable FrozenCelerityDictionary and the prefix-tree Trie<TValue> implement the read-only one only. All of them ship allocation-free struct enumerators, Keys / Values views, and an IEnumerable<KeyValuePair<TKey, TValue>> constructor. The hash-table collections store default(TKey) (zero / null) out-of-band so it never collides with the empty-slot sentinel; SmallDictionary stores it inline.

Quick start

Two examples cover the common surface; every other type has a runnable example in the API reference and in the collapsible sections below.

IntDictionary<TValue> defaults to Int32WangNaiveHasher, so most callers don't pick a hasher:

using Celerity.Collections;

var counts = new IntDictionary<int>();
counts[42] = 1;
counts[42]++;            // indexer get/set
counts.TryAdd(7, 100);   // false if present, no overwrite
counts.Add(8, 200);      // throws if present

if (counts.TryGetValue(42, out var hits))
    Console.WriteLine(hits); // 2

counts.Remove(7);
foreach (var kvp in counts) // allocation-free struct enumerator
    Console.WriteLine($"{kvp.Key} -> {kvp.Value}");

The zero key is a legitimate value, not the sentinel — counts[0] = 99 round-trips. LongDictionary<TValue> is the same surface for long keys.

For non-int/long keys, pick a hasher from Celerity.Hashing (or supply your own); DefaultHasher<T> falls back to EqualityComparer<T>.Default:

using Celerity.Collections;
using Celerity.Hashing;

var byId = new CelerityDictionary<Guid, string, GuidHasher>();
byId[Guid.NewGuid()] = "alice";

var byName = new CelerityDictionary<string, int, StringFnV1AHasher>();
byName["bob"] = 1;

The hasher is a struct generic constraint, so the JIT devirtualizes and inlines Hash() on the probe path.

Specialized dictionaries — RobinHood, Swiss, HashCaching, Pooled, Frozen, MultiMap, MultiSet, Small, EnumMap

All four CelerityDictionary peers below are drop-in (same API, same hashers) and differ only in collision strategy / storage:

// RobinHood — bounds probe variance for clustered / adversarial keys (also ends
// negative lookups early). Cost: a per-slot probe-distance int.
var rh = new RobinHoodDictionary<int, string, Int32WangNaiveHasher>();
rh[42] = "hello";

// Swiss — SIMD group probing for lookup-heavy tables (large tables, many negative
// lookups). One Vector128 compare tests 16 slots, filtered by a 7-bit tag.
var swiss = new SwissDictionary<int, string, Int32WangNaiveHasher>();
swiss[42] = "hello";

// HashCaching — a 32-bit fingerprint side array skips costly key equality on a
// single int compare. For long-string / large value-type keys, cache-cold tables.
var hc = new HashCachingDictionary<string, int, StringFnV1AHasher>();
hc["hello"] = 42;

// Pooled — backing arrays rented from ArrayPool<T>.Shared. Dispose returns them;
// forgetting is not a leak, just no pooling benefit. After Dispose, members throw.
using var pooled = new PooledCelerityDictionary<int, string, Int32WangNaiveHasher>();
pooled[42] = "hello";

FrozenCelerityDictionary<TValue> is build-once, read-many and searches for a perfect (collision-free) hash at construction, so each lookup is single-probe. Immutable; implements IReadOnlyDictionary<string, TValue?>. Use the <TValue, THasher> overload (e.g. StringFnV1AFullHasher for non-ASCII keys) for the single-probe fast path on keys the default would collide — lookups stay correct regardless.

var routes = new FrozenCelerityDictionary<int>(new[]
{
    new KeyValuePair<string, int>("/",        0),
    new KeyValuePair<string, int>("/health",  1),
    new KeyValuePair<string, int>("/metrics", 2),
});
Console.WriteLine(routes.IsPerfectlyHashed); // True
Console.WriteLine(routes["/health"]);        // 1

CelerityMultiMap<TKey, TValue, THasher> groups many values per key (Add appends), hands back an allocation-free ValueGroup on lookup, returns an empty group for absent keys, and implements ILookup<TKey, TValue?> (so it flows through LINQ):

var subs = new CelerityMultiMap<string, string, StringFnV1AHasher>();
subs.Add("orders", "billing");
subs.Add("orders", "fulfilment");
Console.WriteLine(subs["orders"].Count);  // 2
subs.Remove("orders", "billing");         // drop one value
subs.RemoveAll("orders");                 // drop a whole key

CelerityMultiSet<T, THasher> is the counting sibling — each element maps to its multiplicity. It's the type to reach for when building a frequency histogram: Add is a single probe-and-increment, where the idiomatic Dictionary<T,int> counting pattern (d[x] = d.GetValueOrDefault(x) + 1) costs two probes per item. Count is the distinct-element count; TotalCount is the sum of all occurrences:

var freq = new CelerityMultiSet<string, StringFnV1AHasher>();
foreach (string w in "the cat sat on the mat the".Split(' '))
    freq.Add(w);
Console.WriteLine(freq["the"]);       // 3
Console.WriteLine(freq.Count);        // 5 distinct words
Console.WriteLine(freq.TotalCount);   // 7 occurrences
freq.SetCount("cat", 0);              // remove an element entirely

SmallDictionary<TKey, TValue> skips hashing and linear-scans a flat array — at n <= ~16 that beats a hash table (no hash, no probe chain, great cache locality). No hasher to pick; a 0 / null / default key is stored inline. Lookups are O(n), so move to IntDictionary / CelerityDictionary once instances grow.

var scope = new SmallDictionary<string, int>();
scope["x"] = 1;
scope.TryAdd("x", 99);          // false — already present
Console.WriteLine(scope["x"]);  // 1

EnumMap<TEnum, TValue> is the dense array-backed dictionary for enum keys — the .NET analogue of Java's EnumMap and the dictionary counterpart of EnumSet. It maps the enum's underlying value straight to an array slot, so this[key] / TryGetValue / ContainsKey / Add / Remove are a shift-mask-and-index — no hashing, no probing, no collisions — and a full sweep is a linear array walk. A parallel occupancy bit vector means a key mapped to default(TValue) is a genuine entry, distinct from an absent one. It supports enums whose members are small non-negative integers (the default declaration); negative or sparse [Flags] enums throw NotSupportedException (use CelerityDictionary there). Enumeration is deterministic — ascending by underlying value.

enum Priority { Low, Normal, High, Critical }

var queued = new EnumMap<Priority, int> { [Priority.Low] = 3, [Priority.High] = 7 };
queued[Priority.High]++;                             // direct array index, no hashing
Console.WriteLine(queued.ContainsKey(Priority.Normal)); // False — a single bit test

Sets — IntSet, CeleritySet, SwissSet, RobinHoodSet, HashCachingSet, FrozenCeleritySet, SmallSet, EnumSet, SparseSet, CompressedIntSet

var seen = new IntSet();
seen.Add(1);
Console.WriteLine(seen.Contains(1)); // true

var visited = new CeleritySet<Guid, GuidHasher>();
visited.TryAdd(Guid.NewGuid()); // true on first add, false on duplicate

The mutable sets implement ISet<T>, so the full HashSet<T> set algebra works (with matching semantics):

var a = new IntSet(new[] { 1, 2, 3, 4 });
a.IntersectWith(new[] { 2, 4, 6 });        // a -> { 2, 4 }
a.UnionWith(new[] { 4, 5 });               // a -> { 2, 4, 5 }
Console.WriteLine(a.IsSubsetOf(new[] { 2, 4, 5, 9 })); // true

ISet<int> asSet = a;                        // usable anywhere ISet<int>/ICollection<int> is expected
Console.WriteLine(asSet.Add(7));            // true — ISet<T>.Add is the non-throwing add

SwissSet<T, THasher> is the SIMD-probed set — the set counterpart of SwissDictionary. One Vector128 compare tests a whole 16-slot group per membership check and filters candidates by a 7-bit hash tag before any element comparison, so negative Contains lookups (the common case for a set) stay cheap. Same API as CeleritySet, at the cost of one control byte per slot.

var swissSeen = new SwissSet<int, Int32WangNaiveHasher>();
swissSeen.Add(42);
Console.WriteLine(swissSeen.Contains(999)); // false — negative lookup short-circuits on the group scan

RobinHoodSet<T, THasher> is the Robin Hood-probed set — the set counterpart of RobinHoodDictionary. It stores each element's probe-sequence length (distance from its ideal slot) so inserts displace richer residents ("rob from the rich"), bounding probe-length variance; a negative Contains exits as soon as the probe distance exceeds a resident's stored distance. Same API as CeleritySet, at the cost of a per-slot probe-distance int — reach for it on clustered / adversarial elements.

var rhSeen = new RobinHoodSet<int, Int32WangNaiveHasher>();
rhSeen.Add(42);
Console.WriteLine(rhSeen.Contains(999)); // false — the PSL invariant stops the probe early

HashCachingSet<T, THasher> is the struct-of-arrays set — the set counterpart of HashCachingDictionary. It keeps a dense side array of 32-bit hash fingerprints alongside the elements, so a probe scans only that compact metadata and dereferences an element (running the full equality check) only on a fingerprint match. Same API as CeleritySet, at the cost of four bytes of metadata per slot — reach for it on lookup-heavy sets and elements with expensive equality (long strings, large structs).

var hcSeen = new HashCachingSet<string, StringFnV1AHasher>();
hcSeen.Add("alpha");
Console.WriteLine(hcSeen.Contains("omega")); // false — rejected on the fingerprint compare

FrozenCeleritySet is the build-once, read-many string set counterpart of FrozenCelerityDictionary — single-probe Contains, immutable, implements IReadOnlySet<string> (so SetEquals, IsSubsetOf, Overlaps, … are available), and silently dedupes. Use FrozenCeleritySet<THasher> (e.g. StringFnV1AFullHasher) for non-ASCII elements.

var reserved = new FrozenCeleritySet(new[] { "select", "from", "where", "join" });
Console.WriteLine(reserved.IsPerfectlyHashed); // True
Console.WriteLine(reserved.Contains("join"));  // True

SmallSet<T> is the flat-array set — the set counterpart of SmallDictionary. It skips hashing and linear-scans a flat array, which at n <= ~16 beats a hash table (no hash, no probe chain, great cache locality). No hasher to pick; a 0 / null / default element is stored inline. Lookups are O(n), so move to IntSet / CeleritySet once instances grow. Implements ISet<T>, so the full set algebra works.

var seenScope = new SmallSet<string>();
seenScope.Add("x");
Console.WriteLine(seenScope.TryAdd("x")); // False — already present, unchanged

EnumSet<TEnum> is the bit-vector set for enum keys — the .NET analogue of Java's EnumSet. It stores one bit per possible element, so Add / Contains / Remove are a single shift-mask-and-bit-op (no hashing, no boxing) and set algebra between two EnumSets is a word-wise bitwise OR / AND / XOR over a handful of ulongs. It supports enums whose members are small non-negative integers (the default declaration); negative or sparse [Flags] enums throw NotSupportedException (use CeleritySet there). Enumeration is deterministic — ascending by underlying value. EnumSet<TEnum>.All() builds the full universe of declared constants.

var granted = new EnumSet<Permission> { Permission.Read, Permission.Write };
var required = new EnumSet<Permission> { Permission.Read, Permission.Execute };
Console.WriteLine(granted.IsSupersetOf(required)); // False — word-wise subset test
granted.UnionWith(required);                        // one bitwise OR

SparseSet is the bounded-universe integer set — the classic Briggs–Torczon sparse set (a dense value array + a sparse index array). Over a fixed universe [0, Universe) chosen at construction, Add / Contains / Remove are O(1) with no hashing, but the point of the type is what HashSet<int> can't match: Clear() is O(1) (it resets the count without scanning or clearing the backing arrays, versus zeroing the whole table) and iteration is a dense, contiguous scan over exactly the present elements. That is the winning shape for clear-and-rebuild "visited" sets — graph BFS/DFS, ECS entity membership, sweep-line — where the set is emptied every iteration. The cost is O(Universe) memory and non-negative-values-only: a value outside [0, Universe) throws on Add and reads as absent on Contains / Remove. It is an opt-in specialized type, not a HashSet<int> replacement — for an unbounded or huge-and-sparse key space, reach for IntSet.

var visited = new SparseSet(nodeCount);   // universe = ids in [0, nodeCount)
visited.Add(start);
Console.WriteLine(visited.TryAdd(start)); // False — already seen, unchanged
visited.Clear();                          // O(1) — ready for the next traversal

CompressedIntSet is the exact, compressed integer set — the huge-and-sparse shape none of the above serves. It splits the 32-bit value space into 65,536-value chunks and stores each chunk as a sorted ushort[] or a 1024-word bitmap by density, with a third run-length form for clustered data that Optimize() and AddRange produce. Set algebra then works inside a chunk (a sorted merge, or one ANDed word per 64 values) instead of one hash probe per element, and a chunk neither side populates is skipped with a single comparison — so intersecting two posting lists costs the number of populated chunks, not the number of elements. Memory lands ~10x below HashSet<int> for sparse data and far lower for dense or clustered data, and enumeration is in ascending signed order, which HashSet<int> does not offer. Two honest caveats: point lookups are still faster in a hash table, and there is no portable Roaring format — Celerity ships no serializers, so this is an in-process structure, not Lucene / Druid / Spark interop. Compression is explicit: Optimize() is what produces the run form, after the data has settled.

var termA = new CompressedIntSet(PostingsFor("celerity"));      // ~1M ids over ~100M docs
var termB = new CompressedIntSet(PostingsFor("collections"));
termA.Optimize();                                                // re-encode; run form appears here

long both = termA.IntersectCount(termB);                         // size of the overlap, nothing materialized
termA.IntersectWith(termB);                                      // chunk-wise; skips unshared chunks
foreach (int id in termA) Render(id);                            // ascending, allocation-free

var recent = new CompressedIntSet();
recent.AddRange(90_000_000, 99_999_999);                         // 10M ids as one run pair per chunk

Probabilistic & bit-level — BloomFilter, CuckooFilter, XorFilter, HyperLogLog, CountMinSketch, TopKSketch

BloomFilter is a membership gate that stores nothing but a bit array: no false negatives (a false is always correct), with a tunable false-positive rate. Add-and-test only (no Remove, no enumeration); merge equally-sized filters with UnionWith.

var seen = new BloomFilter<string, StringMurmur3Hasher>(1_000_000, 0.001); // n, fp-rate
seen.Add("https://example.com/a");
Console.WriteLine(seen.Contains("https://example.com/a")); // True (definitely added)
Console.WriteLine(seen.Contains("https://example.com/z")); // False (no false negatives)

CuckooFilter is the membership filter you can delete from — the same no-false-negatives contract and tunable false-positive rate as BloomFilter, but backed by fingerprint buckets so it supports Remove, with lookups touching at most two cache lines. Use it for a shrinking set (sliding windows, cache-admission, expiring keys); BloomFilter is simpler when the set only grows.

var recent = new CuckooFilter<long, Int64WangHasher>(100_000, 0.001); // n, fp-rate
recent.Add(42);
Console.WriteLine(recent.Contains(42)); // True (definitely added)
recent.Remove(42);                      // Bloom cannot do this
Console.WriteLine(recent.Contains(42)); // False

XorFilter is the build-once, immutable membership filter — the smallest and fastest to query. You hand the whole element set to the constructor (there is no Add/Remove); in return it packs to ~9.84 bits/element (smaller than a Bloom filter at the same ~0.4% rate) and every Contains is exactly three probes and two XORs, with no probe loop or data-dependent branch. Use it for a fixed set — static allow/deny lists, a precomputed membership gate in front of an expensive exact lookup.

var known = new XorFilter<string, StringXxHash3Hasher>(issuedApiKeys); // built once, then read-only
Console.WriteLine(known.Contains("key-abc")); // True if issued (or a ~0.4% false positive)
Console.WriteLine(known.Contains("key-zzz")); // False (no false negatives)

HyperLogLog estimates the distinct count of a stream from a fixed ~16 KB of registers that never grow with the data (~0.8% error). Add-and-estimate only; Precision sets the accuracy trade-off (StandardError ≈ 1.04/√m); merge equal-precision estimators with UnionWith.

var unique = new HyperLogLog<long, Int64Murmur3Hasher>();
for (long id = 0; id < 10_000_000; id++)
    unique.Add(id % 1_000_000);
Console.WriteLine(unique.EstimateCardinality()); // ≈ 1,000,000 (±~0.8%), from 16 KB

CountMinSketch estimates per-element frequencies from a fixed grid of counters that never grows with the distinct-key count, and never underestimates (overestimate bounded by epsilon · TotalCount). Add-and-estimate only; epsilon / delta set the trade-off; merge equally-sized sketches with UnionWith.

var hits = new CountMinSketch<string, StringMurmur3Hasher>(epsilon: 0.001, delta: 0.001);
foreach (string url in requestStream)
    hits.Add(url);
Console.WriteLine(hits.EstimateCount("/api/login")); // >= true count, over by <= 0.1% of total

TopKSketch reports a high-cardinality stream's most frequent elements from a fixed k monitors (the Space-Saving algorithm), so its memory is O(k) instead of one entry per distinct key. It never underestimates a monitored count and never misses an element whose true frequency exceeds TotalCount / k. Add-and-query only (no Remove, and no UnionWith — bounded top-k summaries have no exact merge).

var hot = new TopKSketch<string, StringMurmur3Hasher>(capacity: 100); // track the top ~100
foreach (string url in requestStream)
    hot.Add(url);
foreach (TopKEntry<string> e in hot.GetTopK(10))
    Console.WriteLine($"{e.Element}: ~{e.Count} (±{e.Error})"); // heaviest first, bounded error

BitSet is a dense, exact bit vector — see the API reference for popcount, the SIMD bulk operators, and the set-bit enumerator.

RankSelectBitVector is the build-once succinct index over such a vector — see the API reference for the full surface. Rank(i) returns how many bits are set below i in O(1), and Select(k) returns the position of the k-th set bit in O(log n). Nothing in .NET offers either, so the alternative is the O(i/64) popcount loop a caller writes by hand — at the midpoint of a 100-million-bit vector, ~780,000 iterations replaced by two index loads and one masked popcount. The index costs 25% over the bits and is invalidated by any mutation, so mutate a BitSet and snapshot it once the bits have settled.

var present = new BitSet(rowCount);
foreach (int row in nonNullRows) present[row] = true;

var index = new RankSelectBitVector(present);   // freeze, then query
int denseSlot = index.Rank(row);                // logical row -> dense slot, O(1)
int logicalRow = index.Select(denseSlot);       // and back, O(log n)

Caches — LruCache

LruCache is a fixed-capacity least-recently-used cache: O(1) get/put, and once at capacity every insert evicts the least-recently-used entry. Its recency order runs through an intrusive doubly-linked list threaded over fixed-size arrays, so after construction the hot path allocates nothing — where the idiomatic Dictionary + LinkedList LRU heap-allocates a node per insert. A read is a use: a hit (indexer get or TryGet) promotes the entry to most-recently-used; TryPeek / ContainsKey inspect without touching recency.

var cache = new LruCache<long, string, Int64WangHasher>(capacity: 3);
cache[1] = "one";
cache[2] = "two";
cache[3] = "three";       // full: MRU..LRU = 3, 2, 1
_ = cache[1];             // a hit promotes 1 -> MRU..LRU = 1, 3, 2
cache[4] = "four";        // evicts the least-recently-used (2), not 1
Console.WriteLine(cache.ContainsKey(2)); // False (evicted)
Console.WriteLine(cache.ContainsKey(1)); // True  (spared by the read)

Sequences — Deque

Deque<T> is a growable double-ended queue backed by a circular buffer: O(1) amortized push / pop / peek at both ends, plus O(1) random access by index. The BCL has no deque — Queue<T> is FIFO-only, Stack<T> LIFO-only, and only LinkedList<T> supports both ends, at the cost of a heap-allocated node per element. A bounded FIFO or sliding-window churn reuses the buffer with wrap-around, so after warm-up it allocates nothing, and enumeration walks contiguous memory. See the API reference.

var work = new Deque<int>(new[] { 1, 2, 3 }); // front-to-back: 1, 2, 3
work.PushFront(0);                            // [0, 1, 2, 3]
work.PushBack(4);                             // [0, 1, 2, 3, 4]
int hi = work.PopFront();                     // 0 — take from the front
int lo = work.PopBack();                      // 4 — take from the back
int mid = work[1];                            // 2 — O(1) random access, front-relative

Union-find — DisjointSet

DisjointSet<T> is the union-find the BCL lacks: it partitions arbitrary elements into disjoint sets and answers Union / Find / Connected in near-O(1) amortized time via union by size + path halving. Union auto-adds missing elements, so it doubles as the edge-insertion primitive; Connected is a pure query that never mutates. Ideal for incremental connectivity, connected components, Kruskal's MST, and undirected cycle detection — a whole stream of merges runs in near-linear time, where a Dictionary + HashSet set-merge is quadratic.

var uf = new DisjointSet<string>();
foreach (var (u, v) in new[] { ("a", "b"), ("b", "c"), ("d", "e") })
    uf.Union(u, v);

Console.WriteLine(uf.Connected("a", "c")); // True  (a-b-c chain)
Console.WriteLine(uf.Connected("a", "e")); // False (separate component)
Console.WriteLine(uf.SetCount);            // 2: {a,b,c} and {d,e}
Console.WriteLine(uf.ComponentSize("a"));  // 3

foreach (var component in uf.GetComponents())
    Console.WriteLine(string.Join(", ", component));

Addressable priority queue — IndexedPriorityQueue

IndexedPriorityQueue<TElement, TPriority, THasher> is an addressable binary min-heap: unlike the BCL PriorityQueue<,> it keeps an element→heap-slot index (a dogfooded CelerityDictionary) so it can change a queued element's priority and remove an arbitrary element in O(log n), and look one up in O(1). That is exactly what the priority-relaxation loop of Dijkstra / Prim / A* needs — the BCL heap forces lazy deletion (re-enqueue + skip stale entries), which grows the heap by one entry per update. Each element is a key (it appears once); pass a custom IComparer<TPriority> for a max-heap.

var pq = new IndexedPriorityQueue<string, int, DefaultHasher<string>>();
pq.Enqueue("a", 10);
pq.Enqueue("b", 30);
pq.Enqueue("c", 20);

pq.Update("b", 5);              // decrease-key: 'b' jumps to the front
Console.WriteLine(pq.Peek());  // b

Console.WriteLine(pq.Dequeue()); // b (priority 5)
Console.WriteLine(pq.Dequeue()); // a (priority 10)
Console.WriteLine(pq.Remove("c", out int p)); // True; p == 20

Prefix trees — Trie

Trie<TValue> is the ordered prefix tree the BCL lacks: it maps string keys to values and answers the prefix queries a Dictionary<string, TValue> can't do without an O(n) scan. GetByPrefix lists every entry under a prefix in O(prefix + matches) and in ascending key order; TryGetLongestPrefix finds the most specific stored key that prefixes a query. Reach for it for autocomplete, longest-prefix routing, or ordered iteration — not for pure exact-key lookups, where a Dictionary (one hash vs a character walk) wins. See the API reference.

var routes = new Trie<string>();
routes["/"] = "home";
routes["/api"] = "api-root";
routes["/api/v1/users"] = "users-v1";
routes["/api/v1/orders"] = "orders-v1";

// Autocomplete: every entry under a prefix, already sorted.
foreach (var (path, handler) in routes.GetByPrefix("/api/v1/"))
    Console.WriteLine($"{path} -> {handler}"); // /api/v1/orders, then /api/v1/users

// Longest-prefix routing: the most specific stored route that prefixes the request.
if (routes.TryGetLongestPrefix("/api/v1/users/42", out string? route, out string? handler))
    Console.WriteLine($"{route} -> {handler}"); // /api/v1/users -> users-v1

Sorted maps and sets with range scans — BTreeDictionary / BTreeSet

BTreeDictionary<TKey, TValue> and BTreeSet<T> keep their keys in order across nodes of up to 31 keys held in flat arrays, so a lookup visits log₃₂(n) nodes rather than chasing log₂(n) pointers the way SortedDictionary<,> / SortedSet<> (red-black trees, one heap object per entry) must. They add the ordered surface a hash table has no answer for — bounds and O(log n + k) range scans.

var series = new BTreeDictionary<long, double>();
series[1_000] = 1.5;
series[1_010] = 2.5;
series[1_020] = 3.5;

Console.WriteLine(series.Min.Key);   // 1000
Console.WriteLine(series.Max.Key);   // 1020

// First key at or after 1005, and the first strictly after it.
series.TryGetLowerBound(1_005, out var atOrAfter);   // 1010
series.TryGetUpperBound(1_010, out var strictlyAfter); // 1020

// Seek in O(log n), then walk contiguous node arrays — no full scan, no allocation.
foreach (var sample in series.EnumerateRange(1_000, 1_020))
    Console.WriteLine(sample.Key); // 1000, 1010

Prefix sums with live updates — FenwickTree

FenwickTree<T> (where T : struct, INumber<T>) is a Binary Indexed Tree: a fixed-length numeric sequence that answers prefix / range sums and applies point updates both in O(log n), in one array with no per-node overhead. The BCL ships nothing for the interleaved update + prefix-sum-query workload — a plain array is O(n) per query or O(n) per update. It wins precisely when both interleave (running aggregates, rank counters, cumulative-frequency tables).

var tree = new FenwickTree<long>(new long[] { 3, 1, 4, 1, 5, 9 });

Console.WriteLine(tree.PrefixSum(3));   // 8  (3 + 1 + 4)
Console.WriteLine(tree.RangeSum(2, 5)); // 10 (4 + 1 + 5)

tree.Add(0, 10);                        // point update, O(log n)
Console.WriteLine(tree[0]);             // 13
Console.WriteLine(tree.Total);          // 33

Range min / max / any associative fold with live updates — SegmentTree

SegmentTree<T, TMonoid> answers the aggregate of any half-open range under an arbitrary associative fold, with point updates and range queries both in O(log n). It is the half of the range-query space FenwickTree<T> cannot reach: a Fenwick range query is the difference of two prefix sums, so the operation must have an inverse — minimum has none. The fold arrives as a struct type parameter, exactly like the hashers, so Combine inlines instead of costing a virtual call per level.

// A live order book: the cheapest ask in any price band, while prices keep moving.
var book = new SegmentTree<long, MinMonoid<long>>(new long[] { 105, 102, 108, 101, 110, 103 });

Console.WriteLine(book.Query(0, 4));   // 101 — cheapest in the first band
Console.WriteLine(book.Aggregate);     // 101 — cheapest overall

book[3] = 999;                         // that order was filled, O(log n)
Console.WriteLine(book.Query(0, 4));   // 102 — refolded

// Any monoid works. Write a struct with an Identity and an associative Combine:
public readonly struct GcdMonoid : IMonoid<uint>
{
    public uint Identity => 0;                  // gcd(0, a) == a
    public uint Combine(uint left, uint right)
    {
        while (right != 0) (left, right) = (right, left % right);
        return left;
    }
}

Construct from an existing collection

The dictionaries accept any IEnumerable<KeyValuePair<TKey, TValue>>; an ICollection<T> source is used to pre-size the backing storage so the bulk fill avoids resizes. Duplicate keys (including duplicate default(TKey)) throw ArgumentException, matching BCL Dictionary<,>.

var bcl = new Dictionary<int, string> { [1] = "a", [2] = "b", [3] = "c" };
var fast = new IntDictionary<string>(bcl);

var fromKvps = new CelerityDictionary<string, int, StringFnV1AHasher>(new[]
{
    new KeyValuePair<string, int>("alice", 1),
    new KeyValuePair<string, int>("bob",   2),
});

Choosing a collection

Each type buys a different tradeoff. Find your workload below; if it isn't here, the BCL collection is usually the right starting point.

Your workload	Use	Why
Dictionary keyed by int	IntDictionary<TValue>	Avoids generic boxing / EqualityComparer<int> dispatch; defaults to Int32WangNaiveHasher.
Dictionary keyed by long	LongDictionary<TValue>	64-bit equivalent of IntDictionary; defaults to Int64WangNaiveHasher.
Dictionary keyed by Guid, string, or any other type	CelerityDictionary<TKey, TValue, THasher>	Pick a struct hasher from Celerity.Hashing (e.g. GuidHasher, StringFnV1AHasher) so the JIT can inline Hash() on the probe path. For string keys, try HashCachingDictionary (next rows but one) first: the BCL Dictionary stores a hash code per entry, and matching that is what closes the gap on reference-type keys — see the performance guide.
Dictionary with clustered / adversarial keys where worst-case lookup latency matters	RobinHoodDictionary<TKey, TValue, THasher>	Same API as CelerityDictionary, but Robin Hood probing bounds probe-length variance so tail-latency lookups don't degrade on bunched keys. Costs a per-slot probe-distance int; for uniform keys with a good hasher, prefer CelerityDictionary.
Lookup-heavy dictionary (large tables, many negative lookups) where SIMD pays off	SwissDictionary<TKey, TValue, THasher>	Same API as CelerityDictionary, but Swiss-table group probing tests 16 slots per Vector128 compare and filters candidates by a 7-bit hash tag before any key comparison. Costs a one-byte control tag per slot; for small or write-dominated tables, CelerityDictionary is competitive.
Lookup-heavy dictionary with costly key equality (long strings, large value-type keys) or large cache-cold tables	HashCachingDictionary<TKey, TValue, THasher>	Same API as CelerityDictionary, but a dense side array of 32-bit hash fingerprints lets probes scan metadata only and short-circuit the key comparison on a single integer compare. Costs four bytes of metadata per slot; complementary to SwissDictionary (scalar wide fingerprint vs SIMD one-byte tags). For small tables of cheap keys, CelerityDictionary is roughly a wash. On 100k string keys it is the difference between losing to the BCL Dictionary and beating it on the negative-lookup path — see the performance guide.
Short-lived dictionary rebuilt frequently on a hot path where GC pressure matters	PooledCelerityDictionary<TKey, TValue, THasher>	Same API as CelerityDictionary plus IDisposable; rents its backing arrays from ArrayPool<T>.Shared and returns them on Dispose, so build/use/dispose cycles recycle buffers instead of allocating. Dispose it (a using scope); for long-lived dictionaries the pooling buys nothing, so prefer CelerityDictionary.
Build-once, read-many lookup table keyed by string	FrozenCelerityDictionary<TValue>	Immutable; searches for a perfect (collision-free) hash at build time so lookups are single-probe. Tune the hasher via the <TValue, THasher> overload.
One key maps to many values (one-to-many)	CelerityMultiMap<TKey, TValue, THasher>	Add appends to a per-key value group instead of overwriting; implements ILookup<,>. Pick the struct hasher for your key type, as with CelerityDictionary.
Counting occurrences / frequency histogram (element → count)	CelerityMultiSet<T, THasher>	Add is a single probe-and-increment vs the two-probe Dictionary<T,int> counting idiom; SetCount / Remove / RemoveAll manage multiplicities, Count is distinct elements and TotalCount the sum. Pick the struct hasher for your element type.
Tiny dictionary (n <= ~16) that stays small	SmallDictionary<TKey, TValue>	Flat-array linear scan beats hashing at small n — no hash to compute, great cache locality, no hasher to pick. Degrades to O(n) for large key sets, so only when instances stay small.
Dictionary keyed by a small enum — config-by-enum, per-state data, enum→handler tables	EnumMap<TEnum, TValue>	Dense array indexed on the enum's underlying value (the .NET EnumMap): this[key] / TryGetValue / Add / Remove are a single direct array index — no hashing, no probing, no collisions — and a full sweep is a linear array walk. The dictionary counterpart of EnumSet; enumerates ascending by value. For enums whose members are small non-negative integers (the default); negative or sparse [Flags] enums are unsupported — use CelerityDictionary<TEnum, TValue, THasher> there.
Tiny set (n <= ~16) that stays small — per-scope "seen" sets, small membership guards, deduping a handful of items	SmallSet<T>	The set counterpart of SmallDictionary: flat-array linear scan beats hashing at small n, no hasher to pick, the default element is stored inline. Implements ISet<T>. Degrades to O(n) for large sets, so only when instances stay small.
Set of enum values — flag sets, permission sets, state sets over a small enum	EnumSet<TEnum>	Bit-vector set indexed on the enum's underlying value (the .NET EnumSet): Add / Contains / Remove are a single bit op — no hashing, no boxing — and set algebra between two EnumSets is a word-wise bitwise OR / AND / XOR. Enumerates ascending by value; All() builds the full universe. For enums whose members are small non-negative integers (the default); negative or sparse [Flags] enums are unsupported — use CeleritySet<TEnum, THasher> there.
Set of small non-negative ints over a bounded range that is cleared & rebuilt often — "visited" sets in graph BFS/DFS, ECS entity membership, sweep-line	SparseSet	Briggs–Torczon sparse set (dense value array + sparse index array): O(1) Clear that leaves the backing arrays untouched (vs HashSet<int> zeroing its table) and dense, cache-friendly iteration over just the present elements. Add / Contains / Remove are O(1), no hashing. Costs O(Universe) memory and stores only values in [0, Universe); for an unbounded or huge-and-sparse key space use IntSet / HashSet<int>.
Huge, sparse set of 32-bit ints where the work is set algebra, not point lookups — inverted-index posting lists, column-store row-id sets, bitmap analytics, cohort intersection; also any int set where memory is the constraint	CompressedIntSet	Exact, compressed: the value space is split into 65,536-value chunks and each chunk is stored as a sorted ushort[], a 1024-word bitmap, or run-length pairs — whichever is smallest. UnionWith / IntersectWith / ExceptWith work inside a chunk (a sorted merge, or one ANDed word per 64 values) and skip a chunk neither side populates with a single comparison, so cost tracks populated chunks rather than elements. Memory is ~10x below HashSet<int> when sparse and far lower when dense or clustered; enumeration is in ascending order. Point Contains is still faster in a hash table — use IntSet / HashSet<int> if lookups are the whole workload. BitSet beats it when the universe is small and dense, SparseSet when it is small and cleared every iteration. No portable Roaring format (Celerity ships no serializers), so it is not a Lucene / Druid / Spark interop path.
Sorting many primitive keys — ids, join keys, timestamps — at a thousand elements and up	RadixSort (package Celerity.Sorting)	Four or eight branch-free counting passes instead of introsort's O(n log n) mispredicting comparisons, in keys-only, key+payload, and argsort forms. Stable. Needs O(n) scratch, which is why Array.Sort cannot do this at all. Below a few hundred elements Array.Sort wins — the crossover is measured on the dashboard.
Sorting values drawn from few distinct keys — enum ordinals, bucket ids, quantized scores	CountingSort (package Celerity.Sorting)	One histogram pass and one run-fill, O(n + range); the keys-only forms never move an element twice and allocate nothing for byte keys. Loses once range approaches n — use RadixSort there.
Only the top / bottom k of a large span is wanted	PartialSort (package Celerity.Sorting)	O(n) introselect for the k smallest in place, or an O(n log k) bounded heap into a destination when the source must not be reordered. Against LINQ the win is allocation and boxing, not asymptotics — OrderBy().Take(k) already partial-sorts.
Set of int values	IntSet	Same fast path as IntDictionary, membership only.
Set of long values	LongSet	64-bit equivalent of IntSet; defaults to Int64WangNaiveHasher.
Set of any other type	CeleritySet<T, THasher>	Same hasher choice as CelerityDictionary.
Membership-heavy set (large sets, many negative Contains lookups, clustered elements) where SIMD pays off	SwissSet<T, THasher>	Same API as CeleritySet, but Swiss-table group probing tests 16 slots per Vector128 compare and filters candidates by a 7-bit hash tag before any element comparison. The set counterpart of SwissDictionary. Costs a one-byte control tag per slot; for small or write-dominated sets, CeleritySet is competitive.
Set with clustered / adversarial elements where worst-case Contains latency matters	RobinHoodSet<T, THasher>	Same API as CeleritySet, but Robin Hood probing bounds probe-length variance and lets negative lookups exit early via the probe-distance invariant so tail-latency lookups don't degrade on bunched elements. The set counterpart of RobinHoodDictionary. Costs a per-slot probe-distance int; for uniform elements with a good hasher, prefer CeleritySet.
Lookup-heavy set with costly element equality (long strings, large structs) or cache-cold Contains	HashCachingSet<T, THasher>	Same API as CeleritySet, but a dense side array of 32-bit hash fingerprints lets a probe scan metadata only and run the full equality check on a candidate element solely when its fingerprint matches — so negative lookups reject on a single integer compare. The set counterpart of HashCachingDictionary; complementary to the SIMD-probed SwissSet. Costs four bytes of metadata per slot; for small tables of cheap elements, CeleritySet is a wash.
Short-lived set rebuilt frequently on a hot path where GC pressure matters	PooledCeleritySet<T, THasher>	Same API as CeleritySet plus IDisposable; rents its backing array from ArrayPool<T>.Shared and returns it on Dispose, so build/use/dispose cycles recycle buffers instead of allocating. The set counterpart of PooledCelerityDictionary. Dispose it (a using scope); for long-lived sets the pooling buys nothing, so prefer CeleritySet.
Build-once, read-many membership set keyed by string	FrozenCeleritySet	Immutable; searches for a perfect (collision-free) hash at build time so Contains is single-probe. The set counterpart of FrozenCelerityDictionary; implements IReadOnlySet<string>. Tune the hasher via the <THasher> overload.
Membership gate where a small, bounded false-positive rate is acceptable in exchange for a large memory saving (dedup pre-filters, "have I seen this before?" guards in front of an expensive exact lookup)	BloomFilter<T, THasher>	Probabilistic: bit-array storage with no false negatives and a tunable false-positive rate, using a fraction of a HashSet<T>'s memory and never growing with element size. Add-and-test only — no Remove, no enumeration, no retrieval. If you need exact membership or to get the elements back, use CeleritySet / FrozenCeleritySet; if you need to delete from the filter, use CuckooFilter.
Deletable membership gate — the same approximate-membership trade-off as BloomFilter but for a set that shrinks as well as grows (sliding windows of recent keys, cache-admission filters, expiring-entry sets)	CuckooFilter<T, THasher>	Probabilistic: fingerprint-bucket storage with no false negatives, a tunable false-positive rate, and Remove. Lookups touch at most two buckets (≈ two cache lines). Only remove elements you actually added. Insertion can fail at very high load (reports full). If your set only grows or you reset it wholesale, BloomFilter is simpler and can be more compact at high target false-positive rates.
Static membership gate over a fixed element set known up front (precomputed allow/deny lists, a read-only "have I seen this?" gate in front of an expensive exact lookup) where the smallest, fastest filter matters	XorFilter<T, THasher>	Probabilistic, build-once & immutable: the whole set goes to the constructor (no Add/Remove). Packs to ~9.84 bits/element (smaller than a Bloom filter at the same ~0.4% rate) and every Contains is three probes + two XORs, branch-free — the fastest, most compact filter. If the set changes over the filter's lifetime, use BloomFilter (grows) or CuckooFilter (grows and shrinks) instead; the false-positive rate is fixed at ~0.4% (8-bit fingerprint), so use BloomFilter when you need a tunable rate.
Dense set of small integer indices (or a fixed universe of flags) where you count set bits or combine whole vectors — bitmaps, visited/presence masks, sieves	BitSet	Exact dense bit vector packed into 64-bit words: O(n/64) population count (Count) via hardware popcount and SIMD bulk And/Or/Xor/Not. A faster, count-aware System.Collections.BitArray. For sparse indices over a huge/unbounded domain, IntSet / LongSet is more memory-efficient — and CompressedIntSet more so again when the work is set algebra rather than point lookups; for approximate membership over arbitrary elements, use BloomFilter. To ask positional questions of a settled bit vector — "how many set bits below here", "where is the k-th one" — index it with RankSelectBitVector.
Positional queries over a bit vector that has stopped changing — dense↔sparse index remapping in a column store, succinct / compressed tries, wavelet trees	RankSelectBitVector	Immutable succinct index over the bits of a BitSet (or packed ulong[]): Rank(i) — set bits below i — in O(1) from a two-level popcount index, and Select(k) — position of the k-th set bit — in O(log n). The BCL has no rank or select at all, so the baseline is a hand-rolled O(i/64) popcount loop; the index replaces ~780,000 iterations with two loads and one masked popcount at the midpoint of a 100M-bit vector. Costs 25% space over the bits, and is build-once: any mutation requires an O(n/64) rebuild, so a vector that keeps changing should stay a plain BitSet (or SparseSet) and be snapshotted only once it settles.
Distinct count over a large or unbounded stream (unique visitors / events, distinct-value cardinality, deduplicated counts across shards) where a small relative error is acceptable	HyperLogLog<T, THasher>	Probabilistic: estimates the distinct count from a fixed array of registers (16 KB at the default precision) with a ~0.8% relative standard error, never growing with the cardinality — unlike a HashSet<T> that stores every distinct value. Add-and-estimate only; merge shard estimators with UnionWith. If you need an exact count or to test a specific element, use HashSet<T> / CeleritySet; for approximate membership rather than counting, use BloomFilter.
Per-element frequency of a specific element over a large or unbounded stream (approximate per-key counts, rate limiting, deduplicated frequency counts across shards) where a small one-sided overestimate is acceptable	CountMinSketch<T, THasher>	Probabilistic: estimates each element's frequency from a fixed grid of counters (sized from epsilon / delta) that never grows with the distinct-key count — unlike a Dictionary<TKey, int> frequency table. Never underestimates; overestimates bounded by epsilon · TotalCount with confidence 1 − delta. Add-and-estimate only; merge shard sketches with UnionWith. If you need exact counts or to enumerate keys, use a Dictionary<TKey, int>; if you want the set of heaviest elements rather than a specific one's count, use TopKSketch; for the distinct count use HyperLogLog, for approximate membership use BloomFilter.
Top-k / heavy hitters — the most frequent elements of a large or unbounded, high-cardinality stream (top URLs / IPs, trending items, network flow monitoring, hot keys) where only the heaviest matter	TopKSketch<T, THasher>	Probabilistic (Space-Saving): keeps a fixed k monitors, so memory is O(k) regardless of the distinct-key count — unlike a Dictionary<TKey, int> that must materialize every distinct key just to rank the top few. Never underestimates a monitored count and never misses an element above TotalCount / k; each result carries a bounded Error. Add-and-query only (no Remove, no UnionWith). If you need the exact fully-ranked counts, use a dictionary frequency table; for a specific element's frequency use CountMinSketch.
Bounded cache with automatic eviction — memoize the last N results, an admission cache in front of an expensive lookup, any hot key→value store that must not grow without bound	LruCache<TKey, TValue, THasher>	Fixed-capacity least-recently-used cache: O(1) get/put, and once at capacity every insert evicts the least-recently-used entry. Its recency list is threaded through fixed-size arrays, so after construction the hot get/put/evict path allocates nothing — where the idiomatic Dictionary + LinkedList LRU allocates a LinkedListNode per insert. Reads are uses (they promote to most-recently-used); use TryPeek / ContainsKey to inspect without touching recency. Single-threaded — because reads mutate recency, even a read-mostly concurrent workload needs a write lock.
Double-ended queue — add/remove at both ends (bounded FIFO queue, sliding window, work-stealing / undo buffer) or a queue needing random access by position	Deque<T>	Growable double-ended queue backed by a circular buffer: O(1) amortized PushFront / PushBack / PopFront / PopBack / peek and O(1) random access by index. The BCL has no deque — Queue<T> is FIFO-only, Stack<T> LIFO-only, and LinkedList<T> (the only O(1)-both-ends type) allocates a node per element. A warm bounded churn reuses the buffer with wrap-around so it allocates nothing, and enumeration walks contiguous memory. For a strict FIFO queue that never pushes front / pops back, BCL Queue<T> is already a circular buffer and is simpler.
Incremental connectivity / connected components — union equivalence classes and ask whether two elements are in the same group (Kruskal MST, clustering, image segmentation, undirected cycle detection, "are these accounts linked?")	DisjointSet<T>	Union-find with union by size + path halving: near-O(1) amortized Union / Find / Connected, O(α(n)) ≤ 4. Runs a stream of merges + connectivity queries in near-linear total time, where the BCL substitutes are super-linear — a Dictionary<T, HashSet<T>> set-merge is O(n²) to coalesce n singletons, and a per-query BFS/DFS is O(V+E) every query. Grows only by merging (no un-union); it is not an ISet<T> — for element membership with add/remove/set-algebra use CeleritySet or HashSet<T>.
Priority queue whose priorities change — a best-so-far frontier you relax (Dijkstra / Prim / A*), or an event scheduler that reschedules / cancels pending items	IndexedPriorityQueue<TElement, TPriority, THasher>	Addressable binary min-heap with an element→slot index: Update (decrease-/increase-key) and Remove an arbitrary element in O(log n), Contains / TryGetPriority in O(1). The BCL PriorityQueue<,> can do none of these — its only substitute is lazy deletion, which grows the heap by one entry per update. Each element is a key (appears once); custom IComparer<TPriority> for a max-heap. For plain enqueue/dequeue with duplicate elements, the BCL PriorityQueue<,> is simpler.
Prefix / autocomplete / longest-prefix over string keys — list everything under a prefix, find the most specific stored key that prefixes a query, or iterate keys in order (typeahead, route/dispatch tables, tokenizer / dictionary matching, namespace listing)	Trie<TValue>	Ordered prefix tree: GetByPrefix yields every entry under a prefix in O(prefix + matches) and in ascending key order, TryGetLongestPrefix finds the longest stored prefix of a query in O(query), and enumeration is sorted for free — none of which a Dictionary<string, TValue> can do without an O(n) scan + StartsWith. For pure exact-key Add / TryGetValue / Remove a Dictionary (one hash vs a per-character walk) is faster; the trie earns its place only when you use the prefix operations. Implements IReadOnlyDictionary<string, TValue?>; not thread-safe.
Many occurrences of few distinct strings, produced as slices of a buffer you already hold — CSV / log / JSON parsing, tokenizers, column stores, header dispatch: you want one canonical string per distinct token, not one per occurrence	StringInternTable	Probed with a ReadOnlySpan<char>: GetOrAdd returns the shared instance and allocates only on a miss, so a 10M-cell parse over 100 distinct tokens creates 100 strings, not 10,000,000. HashSet<string> cannot express this before .NET 9 — its TryGetValue takes a string, so you must allocate the string before you can discover you already had it. string.Intern is process-wide, never collected, and still needs a string; this table's lifetime is yours and Clear releases it. On .NET 9+ Dictionary<string,V>.GetAlternateLookup is comparable; this works on net8.0 too. Not thread-safe.
Look a string key up from a ReadOnlySpan<char> you already hold (route dispatch, header lookup, parse-then-map) without allocating a string per probe	span overloads on FrozenCelerityDictionary / FrozenCeleritySet / CelerityDictionary<string, …> / CeleritySet<string, …> / Trie<TValue>	TryGetValue(ReadOnlySpan<char>, …) / ContainsKey / Contains probe the table directly, deleting the new string(span) allocation and copy per lookup. Available whenever the hasher implements ISpanHashProvider — every built-in String*Hasher does. Same results as the string overloads (ordinal comparison); an empty span means "", never the null key. See span-keyed lookups.
Sorted keys — you need the entries in comparer order, or the ordered questions a hash table cannot answer: smallest / largest key, "first key at or after x", "every key in [a, b)" (time-series by timestamp, order books, LSM-style memtables, sweep-line events, interval endpoints)	BTreeDictionary<TKey, TValue> / BTreeSet<T>	B-tree with up to 31 keys per node in flat arrays: a lookup visits log₃₂(n) nodes instead of chasing log₂(n) pointers (~4 cache misses instead of ~20 at n = 1M), an in-order walk streams contiguous arrays rather than successor pointers, and allocation is one node per 31 entries instead of one object per entry. The BCL has no B-tree: SortedDictionary<,> / SortedSet<> are red-black trees, SortedList<,> is O(n) per middle insert, and OrderedDictionary<,> (.NET 9) is insertion-ordered, not sorted. Wins on the interleaved insert + lookup + range-scan load; for a few dozen entries a SortedList<,> is hard to beat, and if you never need order a hash table answers in O(1).
Prefix / range sums over a sequence you keep mutating — running aggregates, rank / order-statistics counters (inversions, "how many ≤ x seen"), cumulative-frequency tables	FenwickTree<T>	Binary Indexed Tree (T : INumber<T>): point update and prefix / range sum both O(log n), in one array with no per-node overhead. The BCL has no prefix-sum structure; a plain array forces O(n) per query (recompute the slice) or O(n) per update (fix the suffix). Wins precisely when updates and partial-sum queries interleave. If the data is immutable after build, a one-shot precomputed prefix-sum array answers in O(1) with less code; if you only update and never query a partial sum, a raw array is simpler.
Range min / max / gcd / bit-mask over a sequence you keep mutating — sliding-window extrema over a live history, "cheapest offer in this price band" over an order book, per-window capability masks, or any other associative fold with no inverse	SegmentTree<T, TMonoid>	Point update and range query both O(log n), in one flat array of 2n cells. FenwickTree<T> cannot answer these at all: it computes a range as the difference of two prefix folds, so the operation must be invertible. Five folds ship (Sum / Min / Max / BitwiseAnd / BitwiseOr) and any associative one you write is a field-free struct; non-commutative folds are safe. The BCL has no range-aggregate structure, so the alternative is an O(n) scan per query — 14.8× faster on interleaved update + range-min at 100k, 81× on a query batch, but only 1.4× at 1k, where scanning a contiguous array is cache-friendly. If the fold is addition use FenwickTree<T> (half the memory); if the sequence never changes after build, a sparse table or a prefix array answers in O(1). Range updates are not supported — that needs lazy propagation, a different contract.
Set algebra over two lists you already hold in sorted order — intersect / union / diff sorted ID, row-id or posting lists, or just ask how many values they share (inverted indexes, cohort intersection, join-key pre-filters)	SortedSpan.Intersect / Union / Except / IntersectCount / Overlaps (in Celerity.Primitives)	Not a collection — static set algebra over spans. A two-cursor merge exploits the ordering the data already has, so it touches each element once and writes into caller-owned memory: 4.2× faster than HashSet<int> at 1M × 1M and 0 bytes allocated against 17.9 MB, and 257× faster on the asymmetric 1k × 10M shape where it gallops. IntersectCount / Overlaps need no buffer at all. ⚠️ Both spans must be sorted ascending — unsorted input silently returns a wrong answer. If your data is not already sorted, sorting it first to use this is usually a loss; reach for a set instead. See sorted-span set algebra.
Need a stable iteration order or multi-threaded access	BTreeDictionary<,> / BTreeSet<> for sorted order, Trie<TValue> for ordered string keys; BCL ConcurrentDictionary<,> for concurrency	Celerity is single-threaded, and the hash-based collections leave iteration order unspecified. The ordered collections do promise order by contract: the B-trees iterate in comparer order, Trie<TValue> in ascending ordinal key order.

Celerity is not the right answer when you need concurrent access (use ConcurrentDictionary<,> or your own lock — Celerity is single-threaded), or a guaranteed iteration order from the hash-based collections (they implement IDictionary<,> / IReadOnlyDictionary<,> and ISet<>, but none promises an order across versions). When you do need ordered iteration, reach for the ordered collections instead: BTreeDictionary<,> / BTreeSet<> iterate in comparer order and support bounds and range scans, and Trie<TValue> gives ascending ordinal order over string keys. Interface support is no longer a reason to choose one over another — every mutable dictionary implements IDictionary<,> and every mutable set implements ISet<>.

Choosing a hasher

Once the collection is settled, pick a hasher for your key shape. Defaults are good; escalate only with evidence (clustering, adversarial input). The full hasher matrix documents every option and its tradeoff.

Key type	Default	When to escalate
int / long	Int32WangNaiveHasher / Int64WangNaiveHasher (built into IntDictionary / LongDictionary)	Uniform / trusted keys (dense sequential IDs) → drop to Int32IdentityHasher / Int64IdentityHasher (the zero-work floor — no mixing, nothing beats it on speed). Clustered keys → Int32WangHasher → Int32Murmur3Hasher (the Wang full finalizer is a cheaper middle tier than Murmur3).
uint / ulong	UInt32Hasher (cheap XOR-fold) / UInt64Hasher (fmix64)	uint: → UInt32WangHasher → UInt32Murmur3Hasher. ulong: drop to UInt64WangHasher / UInt64WangNaiveHasher when the fmix64 multiplies cost more than they buy on uniform keys.
string (ASCII)	StringFnV1AHasher (folds the low byte per char)	Non-ASCII or long keys → StringFnV1AFullHasher / StringFnV1A64Hasher. Clustered keys → strong-avalanche StringMurmur3Hasher, StringXxHash3Hasher, etc.
string (untrusted input)	DefaultHasher<string> (BCL Marvin32, per-process-randomized)	A keyed PRF — StringSipHash13Hasher (Rust's default), StringSipHash24Hasher, StringHalfSipHash24Hasher, or StringHighwayHash64Hasher — but only resists hash-flooding if seeded with a secret, per-process-random key; with a fixed seed it is deterministic, not DoS-resistant (see caveat below).
Guid	GuidHasher	—
Any other type	DefaultHasher<T> (delegates to EqualityComparer<T>.Default)	Replace with a hand-written struct hasher if profiling shows Hash on the hot path.

Counting past ~10^8 distinct elements? Pick a 64-bit hasher. The probabilistic sketches (HyperLogLog, BloomFilter, CuckooFilter, XorFilter, CountMinSketch) never store the element, so two elements that hash alike are indistinguishable forever — and a 32-bit hash reaches only 2^32 ≈ 4.3 billion values, no matter how it is widened. Hashers that carry genuine 64-bit entropy implement IHashProvider64<T> and the sketches route through it automatically: Int64WangHasher / Int64Murmur3Hasher (long), UInt64WangHasher / UInt64Hasher (ulong), GuidHasher (Guid), and the nine 64-bit string hashers (StringXxHash64Hasher, StringXxHash3Hasher, StringCityHash64Hasher, StringMetroHash64Hasher, StringHighwayHash64Hasher, StringSipHash13Hasher, StringSipHash24Hasher, StringFnV1A64Hasher, StringFnV164Hasher). They already computed 64 bits internally and folded them away, so Hash64 costs nothing extra. With a 32-bit-only hasher the sketches still work — HyperLogLog applies the classical large-range correction so its estimate stays honest — but the entropy floor is real. See IHashProvider64<T>.

The value of a struct hasher is distribution quality (avalanche), determinism, and the zero-cost devirtualized generic — not raw hashing speed. For int keys especially, GetHashCode() is already the identity (zero work), so no mixing hasher beats it on speed; Int32IdentityHasher / Int64IdentityHasher expose that zero-work floor explicitly so you can skip mixing when keys are already uniform, and you escalate to a mixer only when distribution (not speed) demands it.

Fixed-seed hashers are not a HashDoS defence. string.GetHashCode() is already a purpose-built Marvin32 with per-process random seeding; a hardcoded-seed Murmur3 / FNV / xxHash is not more flood-resistant — usually less, because an attacker who knows the fixed algorithm and seed can precompute colliding keys offline. What stops hash-flooding is a keyed PRF with a secret, per-process-random key, not merely picking a "stronger" fixed hash. For untrusted string keys, the BCL string.GetHashCode() (DefaultHasher<string>) is the safe default; reach for the keyed SipHash / HighwayHash hashers only when you also supply a secret seed. The fixed-seed hashers' real strength is reproducibility (same code across processes and runtimes), which GetHashCode() deliberately does not give you.

Probing from a ReadOnlySpan<char>? Any String*Hasher will do. All 23 implement ISpanHashProvider — a Hash(ReadOnlySpan<char>) overload that returns exactly what Hash(string) returns for the same characters — which is what unlocks the span-keyed lookups and StringInternTable. The two overloads share one body, so they cannot drift; a custom string hasher only needs to implement the interface to work the same way. See ISpanHashProvider.

The hashing library also ships classic / compatibility hashes (djb2, sdbm, ELF/PJW, CRC-32, Adler-32, FNV-1, MurmurHash2, CityHash, MetroHash, xxHash32/64) for matching an external system's key distribution — see docs/api/hashing.md for the complete list, costs, and avalanche notes, and use HashQualityEvaluator (below) to compare candidates on your own keys.

Benchmarks

Up to 2.4× faster than Dictionary<int, int> on lookups, with zero allocations — this is a collection-layout win (open addressing with direct == key comparison and no per-call EqualityComparer<T> dispatch), independent of the hasher. It does not mean the hashers beat GetHashCode() on speed (they don't, and for int cannot — see Choosing a hasher). The live dashboard tracks every shipped collection against its BCL counterpart on every main push, with historical trends and per-PR regression comparisons. For high-precision local numbers, run dotnet run -c Release in src/Celerity.Benchmarks — hosted CI runners are noisier than your laptop.

The suite also includes StringHasherBenchmark and IntegerHasherBenchmark (every built-in hasher bracketed by two baselines — the direct GetHashCode() and EqualityComparer<T>.Default.GetHashCode(), the per-probe call a BCL Dictionary<,> actually makes; rendered under Hash function throughput on the dashboard; run locally with --filter "*HasherBenchmark*"). Treat these as a raw-mixing-cost diagnostic only and read them alongside the distribution metrics from HashQualityEvaluator — a fast hasher that clusters is not a win. The isolated Hash() number alone is misleading (for int, GetHashCode() is identity — zero work — so no mixer can beat it), so the extended suite adds HasherEndToEndBenchmark, which times each hasher through the dictionary across all four key shapes, and a deterministic probe-length report (dotnet run -c Release -- --probe-analysis) — the cases where a strong hasher "loses" the microbench but wins end-to-end. See measuring probe length.

An extended local suite answers the harder questions a single random-key benchmark can't: multiple key distributions (uniform / sequential / clustered / adversarial), million-item scale, allocation profiling, concurrent read scaling, cache locality, mixed read-heavy workloads, and a FrozenDictionary<,> comparison. These run on demand — e.g. dotnet run -c Release -- --filter "*Distribution*". See the extended benchmark suite.

Custom hashing

Implement IHashProvider<T> as a struct (required by where THasher : struct, IHashProvider<T>) so the JIT can devirtualize and inline Hash():

public interface IHashProvider<T>
{
    int Hash(T key);
}

For the probabilistic sketches there is a 64-bit sibling. Implement it alongside when your hasher genuinely carries 64 bits of entropy — see IHashProvider64<T> for the contract and why widening a 32-bit code does not qualify:

public interface IHashProvider64<T>
{
    ulong Hash64(T key);
}

The package ships built-in hashers for int, long, uint, ulong, Guid, and string, plus a DefaultHasher<T> fallback. Not sure which fits your key shape? HashQualityEvaluator.Evaluate<T, THasher>(keys) runs a key sample through a hasher and returns a HashQualityReport (collision count, bucket occupancy, max bucket load, chi-squared, and a normalized distribution score where 1.0 = ideal uniform) — a diagnostic to compare candidates offline before committing. For the metric a lookup actually pays, ProbeStatisticsEvaluator.Evaluate<T, THasher>(keys) replays the real open-addressed linear-probing placement and returns a ProbeStatistics (average / worst-case probe length and the open-addressing collision rate). See docs/api/hashing.md.

Primitives

The Celerity.Primitives package exposes low-level helpers that fill genuine BCL gaps. FastUtils.FastMod / FastDiv are Lemire's reciprocal modulo and division: when a divisor is fixed at run time and reused across a hot loop (hash buckets, ring buffers, sharding, rate limiting), precompute a reciprocal once and each value % divisor / value / divisor becomes a multiply-and-shift — 2–4× faster than the long-latency hardware DIV (the same trick the BCL uses internally but keeps private). 32- and 64-bit overloads; both reproduce the built-in operators bit-for-bit.

using Celerity.Primitives;

ulong multiplier = FastUtils.GetFastModMultiplier(shardCount);   // once
uint shard = FastUtils.FastMod(key, shardCount, multiplier);     // == key % shardCount, per item

The Celerity.Primitives namespace also ships a curated suite of struct PRNGs — Xoshiro256StarStar (general-purpose default), Xoroshiro128Plus (fast doubles), WyRand (raw throughput), SplitMix64 (seed expander), and Pcg32 (statistical reputation + independent streams). System.Random is a heap class behind virtual dispatch whose seeded path falls back to the legacy Knuth algorithm; these are value types with no allocation and no virtual dispatch, and the shared NextDouble / NextSingle / bounded-and-unbiased NextInt / NextBytes surface inlines through a where TRng : struct, IRandomSource constraint, so they work generically (a zero-cost shuffle) and reproducibly from an explicit seed.

using Celerity.Primitives;

var rng = new Xoshiro256StarStar(seed: 12345);   // deterministic
double unit = rng.NextDouble();                  // [0, 1)
int dieRoll = rng.NextInt(1, 7);                 // [1, 7), unbiased (Lemire)

Celerity.Primitives also ships VarInt, a span-based variable-length integer codec: LEB128 for uint / ulong and zig-zag + LEB128 for int / long, encoding straight over a caller-owned Span<byte> with no stream and no allocation. The BCL exposes 7-bit-encoded integers only on BinaryWriter / BinaryReader (stream-bound and allocating); VarInt is the no-alloc span path custom wire codecs and serializers actually want. Every TryWrite / TryRead is bounds-safe (returns false on a short or truncated buffer, never throws).

Span<byte> buffer = stackalloc byte[VarInt.MaxVarIntLength64];
VarInt.TryWriteVarInt(buffer, 300u, out int n);              // n == 2
VarInt.TryReadVarInt(buffer, out uint value, out int read);  // value == 300

FastUtils also exposes CountDigits — the base-10 digit count of an integer, for sizing a buffer before TryFormat, aligning fixed-width numeric columns, or pre-measuring log / CSV / JSON output. The BCL's fast LZCNT-based counter is internal, and the only public base-10 log is the floating-point Math.Log10, which is slower and mis-rounds at exact powers of ten. CountDigits is exact and branch-lean (the 32-bit path is a single Log2/LZCNT plus a table lookup); the companion integer Log10 is CountDigits - 1. 32- and 64-bit unsigned overloads, plus signed overloads that count the magnitude (sign excluded, MinValue handled without overflow).

int width = FastUtils.CountDigits(1234u);   // 4
Span<char> buf = stackalloc char[width];
(1234u).TryFormat(buf, out _);

Finally, FastGuid generates GUIDs from a struct PRNG instead of the OS cryptographic RNG: a non-cryptographic version 4 (random) and an RFC 9562 version 7 (Unix-millisecond time-ordered). The version 7 layout is big-endian, so — unlike .NET 9's Guid.CreateVersion7, whose mixed-endian storage scrambles the sort order — the canonical string sorts in creation order, keeping database indexes compact; GuidV7Generator<TRng> adds a monotonic counter so a same-millisecond burst is still strictly increasing. Both run several times faster than RNG-backed Guid.NewGuid(). Not for unguessable IDs (security tokens etc.) — use Guid.NewGuid() there.

var rng = new Xoshiro256StarStar(seed: 12345);
Guid traceId = FastGuid.CreateVersion4(ref rng);                                  // fast random id
Guid dbKey   = FastGuid.CreateVersion7(ref rng, DateTimeOffset.UtcNow.ToUnixTimeMilliseconds()); // sortable

FastUtils also exposes alignment helpers — AlignUp / AlignDown / IsAligned for int / long sizes and pointer-sized nuint addresses — that round to a power-of-two boundary (the internal BCL Align trick, exposed): sub-allocating from a buffer, padding a stride to a SIMD width, or finding the start of the cache line a pointer sits in.

int padded     = FastUtils.AlignUp(length, 16);       // round a byte count up to 16
nuint lineStart = FastUtils.AlignDown(address, 64);   // start of the containing cache line

And SpanBits is the non-owning counterpart to BitSet: bit Get / Set / Clear / Flip, hardware-POPCNT PopCount, and a TZCNT NextSetBit scan over a caller-owned Span<ulong> — a stackalloc buffer, a slice, or a pooled array — with no heap object. (System.Collections.BitArray is a heap class with no span access, no popcount, and no scan.) Use BitSet when you want an owning bit vector; use SpanBits when you already manage the storage.

Span<ulong> bits = stackalloc ulong[SpanBits.WordCount(200)];   // 200-bit scratch bitmap, no allocation
SpanBits.Set(bits, 5);
for (int i = SpanBits.NextSetBit(bits, 0); i >= 0; i = SpanBits.NextSetBit(bits, i + 1)) { /* ... */ }

The BitWriter / BitReader ref-struct cursors are the sequential, sub-byte counterpart: they pack and unpack arbitrary-width bit fields (a 3-bit flag group, a 12-bit sample, a 20-bit offset) end-to-end over a caller-owned Span<byte>, LSB-first, with no stream and no allocation — so a record of odd-width fields occupies exactly ceil(total_bits / 8) bytes. Where VarInt is byte-granular and SpanBits is random-access, these append and consume whole multi-bit fields at a moving cursor. The BCL has no equivalent (System.Collections.BitArray sets one bit at a time and can't append a multi-bit field). Every TryWrite / TryRead is bounds-safe (returns false and leaves the cursor unchanged rather than writing a partial field), and only the low bitCount bits of a value are stored, so an out-of-range value never corrupts a following field.

Span<byte> buffer = stackalloc byte[BitWriter.ByteCount(3 + 12 + 20)]; // 5 bytes
var writer = new BitWriter(buffer);
writer.TryWriteBits(5, 3); writer.TryWriteBits(3000, 12); writer.TryWriteBits(0xABCDE, 20);

var reader = new BitReader(buffer);
reader.TryReadBits(3, out ulong flags);   // 5
reader.TryReadBits(12, out ulong sample); // 3000

Then, SimdReductions ships the two span reductions that System.Numerics.Tensors.TensorPrimitives (which you should use for plain Sum / Min / Max) doesn't cover: a fused single-pass MinMax that computes both extrema in one pass instead of the two passes TensorPrimitives.Min + TensorPrimitives.Max cost (~1.8× faster on large, out-of-cache int arrays — a memory-bandwidth win; a wash for small in-cache spans), and an overflow-checked CheckedSum that widens int lanes to long so the SIMD accumulation can't overflow and throws OverflowException rather than wrapping like TensorPrimitives.Sum (~4.6× faster than the only safe alternative, a scalar checked loop).

var (lo, hi) = SimdReductions.MinMax(samples);    // both extrema, one pass
int total    = SimdReductions.CheckedSum(samples); // throws on overflow instead of wrapping

Finally, Branchless is a guaranteed branch-free conditional select. The JIT already emits cmov for Math.Min / Max / Abs / Clamp, but it does not reliably if-convert a general data-dependent condition ? a : b — in a loop over an unpredictable bool it emits a real branch, and the misprediction penalty dominates. Branchless.Select picks a value with pure mask arithmetic (whenFalse ^ ((whenTrue ^ whenFalse) & mask)), so there is no jump to mispredict: the #198 spike measured a per-element blend over a 1,000,000-element array with a 50/50 unpredictable condition at ~6× faster than the branchy ternary. Scalar overloads cover int / long / uint / ulong / float / double (floats bit-exact, signed zero and NaN preserved); bulk span overloads blend two arrays branch-free (and auto-vectorise). Reach for it only when the condition is genuinely unpredictable — a well-predicted branch is already free.

int clamped = Branchless.Select(value > limit, limit, value); // no branch to mispredict
Branchless.Select(mask, a, b, destination);                   // destination[i] = mask[i] ? a[i] : b[i]

And SortedSpan is set algebra over spans that are already sorted ascending — Intersect / Union / Except straight into a caller-owned Span<T>, plus IntersectCount and Overlaps that need no buffer and allocate nothing at all. The BCL has none of this: MemoryExtensions has no set operation and TensorPrimitives none either, so the alternatives are HashSet<T>.IntersectWith (allocate a table, then hash and probe every element) or LINQ Intersect — neither exploits sortedness. A two-cursor merge touches each element once instead: intersecting two 1M-element sorted int arrays runs at 6.1 ms vs 25.7 ms for HashSet<int> (4.2×, and 5.7× vs LINQ) while allocating 0 bytes against 17.9 MB. When one side is ≥32× the other it gallops (exponential search), which is where the win gets large: 1k against 10M takes 0.37 ms vs 94.3 ms — 257×. ⚠️ Sorted by construction, or this is worthless: unsorted input silently returns a wrong answer (Debug builds assert; Release deliberately does not check).

Span<int> buffer = stackalloc int[Math.Min(a.Length, b.Length)];
int n = SortedSpan.Intersect(a, b, buffer);   // a, b sorted ascending; result in buffer[..n]
bool any = SortedSpan.Overlaps(a, b);         // allocation-free, early-exit

See docs/api/utilities.md for the full surface and the generator-selection table.

Sorting

The Celerity.Sorting package fills the one gap the BCL structurally cannot close. Array.Sort and MemoryExtensions.Sort<T> route through a scalar comparison introsort for primitive keys on every current runtime — there is no radix, counting, or selection path anywhere in the BCL — and Array.Sort is contractually in-place, while a radix sort needs O(n) scratch. Trading that in-place guarantee for a scratch buffer is exactly the flexibility-for-speed deal Celerity exists to make.

dotnet add package Celerity.Sorting

Type	What it gives you
RadixSort	LSD radix over uint / int / ulong / long / float / double: four (32-bit) or eight (64-bit) counting passes with purely sequential reads and no comparisons and no data-dependent branches, where introsort's every partition step is a branch the predictor cannot learn on random data. Keys alone, keys with a parallel payload, or ArgSort — the index permutation that ranks without moving a wide payload (the BCL has no argsort). Stable, unlike Array.Sort(keys, items).
CountingSort	Bounded key ranges — byte, ushort, or int over a declared [min, max]: one histogram pass and one run-fill, O(n + range), for the shape that enum ordinals, bucket ids and quantized scores take. The keys-only forms never move an element twice and allocate nothing at all for byte keys. Stable with a payload.
PartialSort	Selection instead of sorting: Select / Sort are an O(n) in-place introselect for the k smallest, TopK an O(n log k) bounded heap over a span it never writes to. A three-way partition keeps duplicate-heavy input linear; a depth budget bounds the adversarial case.

RadixSort and CountingSort each pair their entry points with a SortWithScratch twin that allocates nothing, so a hot loop supplies its buffers once instead of renting per call. PartialSort needs no scratch and allocates nothing in any form:

using Celerity.Sorting;

int[] ids = LoadIds();
RadixSort.Sort(ids.AsSpan());                       // rents its scratch

int[] scratch = new int[ids.Length];                // ...or supply it once
foreach (var batch in batches)
{
    batch.CopyTo(ids);
    RadixSort.SortWithScratch(ids.AsSpan(), scratch.AsSpan());
}

int[] worst = new int[10];                          // top 10 of a million,
PartialSort.TopK<int>(latencies, worst);            // without reordering the source

Where it does not win, stated plainly. RadixSort loses below a few hundred elements — the histogram's fixed cost dominates, so use Array.Sort for small spans; the benchmark dashboard sweeps from 100 to 1,000,000 elements precisely so the crossover is a measured number rather than a guess. CountingSort loses once range approaches n. And PartialSort is not asymptotically better than LINQ: OrderBy().Take(k) has applied its own partial-sort optimization since .NET 6, so the win there is allocation and boxing, not complexity. One more thing to know before sorting reals: RadixSort orders NaN by sign bit and -0.0 before +0.0, where Array.Sort moves all NaNs to the front and calls the zeros equal. Full details in the sorting API reference.

Native AOT & trimming

Celerity is Native AOT and trimming compatible — no reflection, runtime code generation, or dynamic type loading. Every collection is a generic over a struct hasher, and the only BCL primitives on the hot paths (MemoryMarshal, Unsafe, EqualityComparer<T>.Default) are AOT-safe. The assembly is marked <IsAotCompatible>true</IsAotCompatible>, so a PublishAot app gets no trim or AOT warnings. Compatibility is enforced on every build (the trim/AOT analyzers run during compilation) and CI publishes a Native AOT smoke-test binary exercising every collection and hasher. See docs/aot.md.

API at a glance

The dictionaries mirror the parts of Dictionary<TKey, TValue> most callers reach for: indexer get/set, ContainsKey, TryGetValue, Add, TryAdd, Remove (both overloads), Clear, EnsureCapacity / TrimExcess, Count, Keys, Values, GetEnumerator(). The string-keyed types additionally take a ReadOnlySpan<char> on TryGetValue / ContainsKey / Contains, so a caller holding a slice of a buffer never allocates a string to probe. They implement IDictionary<TKey, TValue?> and IReadOnlyDictionary<TKey, TValue?> — the Keys / Values views widen to read-only ICollection<T>s through the mutable interface, whose mutators throw NotSupportedException exactly as Dictionary<,>.KeyCollection does — and accept an IEnumerable<KeyValuePair<TKey, TValue>> at construction. The sets expose Add, TryAdd, Contains, Remove, Clear, EnsureCapacity / TrimExcess, Count, and a struct enumerator. EnsureCapacity(n) pre-grows the table once for a known-size bulk insert (no incremental rehashes); TrimExcess() rehashes back down to fit Count. The zero / default(TKey) key (or element) is stored out-of-band so it never collides with the empty-slot sentinel.

Full constructors, signatures, exceptions, and per-type examples: API reference.

Project docs

• docs/ — documentation index & API reference.
• Sorting API · Performance tuning · Migration guide · Troubleshooting · FAQ · Testing & coverage.
• ROADMAP.md · CHANGELOG.md · CONTRIBUTING.md · GitHub Issues.