29 specialized .NET data structures with documented Big-O bounds, multi-targeted for net8.0 and netstandard2.1.
29 .NET data structures the BCL doesn't ship: spatial indexes, observable collections, bounded-memory probabilistic estimators, temporal queries, and keyed collections that maintain access order. All public types document Big-O time and space complexity per operation. Multi-targets net8.0 and netstandard2.1; symbol packages and SourceLink ship with every release.
dotnet add package OmniCollectionsThe umbrella package pulls in all 8 sub-packages. For trimmed deployments, install only the per-namespace packages you need: OmniCollections.Linear, OmniCollections.Spatial, OmniCollections.Hybrid, OmniCollections.Probabilistic, OmniCollections.Grid, OmniCollections.Reactive, OmniCollections.Temporal, OmniCollections.Core.
v3.0 cuts three Hybrid types whose value props didn't justify their existence after the v2.x curation pass. If you used any of them, here's the drop-in replacement:
| Removed | Replace with |
|---|---|
PredictiveDictionary<K,V> |
Dictionary<K,V> + your own n-gram predictor (the v2.x type was 259 LOC of pattern bookkeeping over a plain dict, with no automatic prefetch — the predictor logic is small enough to inline where you need it) |
QueueDictionary<K,V> |
Queue<KeyValuePair<K,V>> + Dictionary<K,V> kept in sync (≈30 lines of wrapper) |
DequeDictionary<K,V> |
LinkedList<KeyValuePair<K,V>> + Dictionary<K, LinkedListNode<KeyValuePair<K,V>>> kept in sync (≈30 lines of wrapper — the dictionary maps to list nodes so removal stays O(1)) |
If you need the v2.x source as a starting point, it's in the git history (git log --all -- src/Omni.Collections.Hybrid/PredictiveDictionary src/Omni.Collections.Hybrid/QueueDictionary src/Omni.Collections.Hybrid/DequeDictionary.cs).
No other public-API changes between v2.1.x and v3.0.0.
Organized by namespace. Click each category to expand.
BoundedList, PooledList, PooledStack, PooledQueue, MinHeap, MaxHeap (6 types)
List<T>-shaped collection with a hard upper-bound capacity set at construction. Throws on overflow (or call TryAdd).
| Operation | Time | Space |
|---|---|---|
Add |
O(1) | O(1) |
TryAdd |
O(1) | O(1) |
Insert(i, item) |
O(N) | O(1) |
Remove(item) |
O(N) | O(1) |
RemoveAt(i) |
O(N − i) | O(1) |
RemoveLast |
O(1) | O(1) |
this[i] |
O(1) | — |
Contains |
O(N) | O(1) |
Clear |
O(N) | — |
| Storage | — | O(capacity), fixed at construction |
var list = new BoundedList<Sample>(capacity: 1024);
list.Add(sample); // throws if full
if (!list.TryAdd(other)) { /* full */ }Use when capacity is known up-front and you want zero resize overhead — real-time loops, fixed-size buffers, GC-conscious paths.
Don't use when capacity is unpredictable; pay the resize cost with List<T> and skip the throw.
List<T>-shaped collection whose backing array is rented from ArrayPool<T> and returned on Dispose.
| Operation | Time | Space |
|---|---|---|
Add |
O(1) amortized | O(1) |
AddRange(span) |
O(n) | O(1) |
Insert(i, item) / RemoveAt(i) |
O(N − i) | O(1) |
RemoveLast |
O(1) | O(1) |
this[i] / AsSpan |
O(1) | — |
IndexOf / Contains |
O(N) | O(1) |
| Storage | — | O(capacity), buffer rented from ArrayPool<T> |
using var list = PooledList<Item>.CreateWithArrayPool(initialCapacity: 1000);
list.Add(item);
ReadOnlySpan<Item> view = list.AsSpan();Use when you create and drop many short-lived lists per second — buffer rental amortizes allocation across instances. Don't use when the list is long-lived; the pool rental adds overhead without payoff.
LIFO stack whose backing array is rented from ArrayPool<T>. Adds Span<T> batch push/pop on top of the standard Stack<T> shape.
| Operation | Time | Space |
|---|---|---|
Push |
O(1) amortized | O(1) |
Pop |
O(1) | O(1) |
Peek |
O(1) | — |
PushSpan(span) |
O(n) | O(1) |
PopSpan(count) |
O(n) — allocates a fresh T[count] per call |
O(n) heap |
| Storage | — | O(capacity), buffer rented from ArrayPool<T> |
using var stack = PooledStack<Item>.CreateWithArrayPool(initialCapacity: 1000);
stack.Push(item);
ReadOnlySpan<Item> popped = stack.PopSpan(8);The pooled buffer backs the stack itself; PopSpan returns a fresh T[] (no caller cleanup) rather than a slice of the pool.
Use when you create and drop many short-lived stacks, or want span-based batch push/pop the BCL Stack<T> doesn't expose.
Don't use when the stack is long-lived and you don't use the span APIs — Stack<T> is simpler.
FIFO queue whose backing array is rented from ArrayPool<T>. Adds Span<T> batch enqueue/dequeue on top of the standard Queue<T> shape.
| Operation | Time | Space |
|---|---|---|
Enqueue |
O(1) amortized | O(1) |
Dequeue |
O(1) | O(1) |
Peek |
O(1) | — |
EnqueueSpan(span) |
O(n) | O(1) |
DequeueSpan(count) |
O(n) — allocates a fresh T[count] per call |
O(n) heap |
| Storage | — | O(capacity), buffer rented from ArrayPool<T> |
using var queue = PooledQueue<Order>.CreateWithArrayPool(capacity: 10_000);
queue.Enqueue(order);
ReadOnlySpan<Order> burst = queue.DequeueSpan(8);The pooled buffer backs the queue itself; DequeueSpan returns a fresh T[] (no caller cleanup) rather than a slice of the pool.
Use when queue instances churn (per-request, per-frame) and you want buffer reuse across them, or you need span-batch enqueue/dequeue.
Don't use when a single long-lived queue suffices — Queue<T> is simpler and at parity for that case.
Binary min-heap over T : IComparable<T>. Smallest element always at the root. Optional ArrayPool<T> rental.
| Operation | Time | Space |
|---|---|---|
Insert |
O(log N)* — amortized; O(N) on resize | O(1) |
ExtractMin |
O(log N) | O(1) |
PeekMin |
O(1) | — |
InsertRange |
O(n log N)* | O(1) |
BuildHeap(array) |
O(N) (Floyd build) | O(1) |
| Storage | — | O(N), grows on Insert via doubling |
using var heap = MinHeap<Task>.CreateWithArrayPool(initialCapacity: 1000);
heap.Insert(task);
var urgent = heap.ExtractMin();Use when Insert volume dominates Extract, you need linear-time bulk-build via BuildHeap, or you want pooled backing memory.
Don't use when you only need rare priority extraction over a stable set — the BCL PriorityQueue<,> is fine.
Binary max-heap over T : IComparable<T>. Largest element always at the root. Optional ArrayPool<T> rental.
| Operation | Time | Space |
|---|---|---|
Insert |
O(log N)* — amortized; O(N) on resize | O(1) |
ExtractMax |
O(log N) | O(1) |
PeekMax |
O(1) | — |
InsertRange |
O(n log N)* | O(1) |
BuildHeap(array) |
O(N) (Floyd build) | O(1) |
| Storage | — | O(N), grows on Insert via doubling |
using var heap = MaxHeap<int>.CreateWithArrayPool(initialCapacity: 1000);
heap.Insert(score);
var top = heap.ExtractMax();Use when you need top-K / largest-first ordering — PriorityQueue<,> requires inverted comparers for max-heap semantics.
Don't use when you only ever peek; sort once and index from the end of the array.
QuadTree, OctTree, KdTree, SpatialHashGrid, TemporalSpatialHashGrid, BloomRTreeDictionary (6 types)
2D point-keyed tree that subdivides space into four quadrants per node. Returns items intersecting an axis-aligned query rectangle.
Below N=5000 (the internal _spatialThreshold default), QuadTree<T> stores items in a flat linear list. The complexities below describe spatial mode (N≥5000); below threshold, Insert is O(1) amortized, Remove / Query / FindNearest are O(N), and the one-time mode switch is O(N).
| Operation | Time (spatial mode, N≥5000) | Space |
|---|---|---|
Insert(point, item) |
O(log N) avg, O(N) worst (degenerate / colocated) | O(1) |
Remove(point, item) |
O(log N) avg | O(1) |
Query(rect) |
O(log N + k), k = result size | O(k) |
FindNearest(point) |
O(log N) avg | O(1) |
| Storage | — | O(N) |
var tree = new QuadTree<GameObject>(new Rectangle(0, 0, 1024, 1024));
tree.Insert(new Point(x, y), gameObject);
List<GameObject> visible = tree.Query(cameraBounds);Use when you have many 2D points and the dominant query is "what's inside this rectangle?" — collision broad phase, viewport culling, GIS overlays. Don't use when points move every frame; rebuild cost outweighs query savings unless you batch-rebuild.
3D analog of QuadTree — subdivides space into eight octants per node. Supports sphere, AABB, and frustum queries.
| Operation | Time | Space |
|---|---|---|
Insert(item) |
O(log N) avg, O(N) worst | O(1) |
FindInSphere(center, radius) |
O(log N + k) | O(k) |
FindInBounds(aabb) |
O(log N + k) | O(k) |
FindInFrustum(planes) |
O(log N + k) | O(k) |
FindNearest(point) |
O(log N) avg | O(1) |
Clear |
O(1) (orphans the tree; GC reclaims) | — |
| Storage | — | O(N) |
var tree = OctTree<Entity>.Create3D(e => e.X, e => e.Y, e => e.Z, minSize: 1.0f);
tree.Insert(entity);
List<Entity> visible = tree.FindInFrustum(camera.Frustum);Use when you query a 3D point set by sphere / AABB / view frustum — 3D culling, range pickup, proximity AI.
Don't use when all points lie roughly in a 2D plane; QuadTree halves the bookkeeping per node.
K-dimensional tree for nearest-neighbor and range queries on multi-dimensional points.
| Operation | Time | Space |
|---|---|---|
Insert |
O(log N) avg amortized; periodic O(N log N) rebuild every 64 inserts past N=1000 when height exceeds 2·log₂(N)+2 | O(1) |
FindNearest |
O(log N) avg | O(1) |
FindNearestK(k) |
O((log N + k) log k) avg | O(k) |
FindNearestK(k) (List<T> overload) |
same — additionally allocates BoundedPriorityQueue + List<T> per call (use the PooledList<T> overload for alloc-free queries) |
O(k) heap |
RangeQuery |
O(N^(1−1/d) + k) where k = result size | O(k) |
InsertRange(M items) |
O(M log N) for small batches; O((N+M) log(N+M)) avg when batch ≥ N/2 (rebuild path via Quickselect partition) | O(M) |
Clear |
O(1) (orphans the tree; GC reclaims) | — |
var tree = KdTree<DataPoint>.Create3D(p => p.X, p => p.Y, p => p.Z);
tree.Insert(point);
var nearest = tree.FindNearest(query);Use when the point set is read-mostly: build once, query many times. Don't use when points churn faster than you query — incremental inserts skew the tree, eventually forcing a rebalance pass.
Uniform-cell hash grid keyed by 2D coordinates. Each cell holds a list of items currently inside it.
Below N=5000 (the internal _spatialThreshold default), SpatialHashGrid<T> stores items in a flat linear list and every read scans the list — Remove / GetObjectsAt / GetObjectsInRadius / GetObjectsInRectangle are O(N), and GetPotentialCollisions is O(N²). The complexities below describe spatial mode (N≥5000); the one-time mode switch is O(N).
| Operation | Time (spatial mode, N≥5000) | Space |
|---|---|---|
Insert(x, y, item) |
O(1) avg | O(1) |
Remove(x, y, item) (point-inserted entry) |
O(1) avg | O(1) |
Remove(x, y, item) (InsertBounds-inserted entry) |
O(C·M), C = cells spanned, M = entries per cell | O(1) |
GetObjectsAt(x, y) |
O(c), c = items in that cell | O(c) |
GetObjectsInRadius(x, y, r) |
O((r/cellSize)² · c) | O(k) |
GetObjectsInRectangle(...) |
O((w·h/cellSize²) · c) | O(k) |
GetPotentialCollisions() |
O(Σ c_i²) where c_i = items per cell; ≈ O(N) for uniform distribution, worse for clustered | O(pairs) |
GetStatistics() |
O(C log C) — sorts cell counts | O(C) |
Clear |
O(occupied cells) | — |
| Storage | — | O(N + occupied cells) |
var grid = new SpatialHashGrid<Entity>(cellSize: 64.0f);
grid.Insert(x, y, entity);
foreach (var e in grid.GetObjectsInRadius(px, py, 100f)) { /* ... */ }Use when point density is roughly uniform across the world (bullets, particles, units on an even map) and the query radius is on the order of a few cells.
Don't use when density is wildly skewed (most items in 1% of the world) — a single cell becomes the bottleneck. A QuadTree handles that better.
SpatialHashGrid<T> plus a time-stamped snapshot ring. Lets you query the grid as it existed at a prior time, replay an object's trajectory, or extrapolate from velocity.
| Operation | Time | Space |
|---|---|---|
UpdateObject / RemoveObject |
O(1) avg amortized; periodic O(N) when snapshotInterval elapses (snapshot pass copies all current objects) |
O(1) |
GetObjectsInRadius (live) |
O((r/cellSize)² · c) | O(k) |
GetObjectsInRadiusAtTime(when) |
O(log snapshots) + O((r/cellSize)² · c) | O(k) |
GetObjectTrajectory(obj, lookBack) |
O(s log s), s = matching snapshots in window | O(s) |
GetObjectsAlongPath(...) |
O(path length / cellSize · c) | O(k) |
| Storage | — | O(N + retained snapshots × snapshot size) |
var grid = new TemporalSpatialHashGrid<Mob>(
cellSize: 32f, snapshotInterval: TimeSpan.FromSeconds(1),
historyRetention: TimeSpan.FromMinutes(10));
grid.UpdateObject(mob, x, y, vx, vy);
var past = grid.GetObjectsInRadiusAtTime(x, y, 50f, DateTime.UtcNow.AddMinutes(-1));Use when you need spatial queries that look back in time (replay debugging, lag compensation, post-hoc audit).
Don't use when you only ever query "now" — the snapshot ring is dead weight; use SpatialHashGrid<T>.
Keyed dictionary whose values also live in an R-tree indexed by per-entry bounding rectangles. A bloom filter pre-screens key lookups against the negative path.
| Operation | Time | Space |
|---|---|---|
Add(key, value, bounds) |
O(log N) avg (R-tree insert) | O(1) |
this[key] (get) |
O(1) avg | — |
TryGetValue(key) |
O(1) avg | O(1) |
Remove(key) |
O(log N) avg | O(1) |
FindIntersecting(bounds) |
O(log N + k) | O(k) |
FindContained(bounds) |
O(log N + k) | O(k) |
FindAtPoint(x, y) |
O(log N + k) | O(k) |
Clear |
O(N) | — |
| Storage | — | O(N) for dict + R-tree + bloom bits |
var dict = new BloomRTreeDictionary<string, Building>(
expectedCapacity: 10_000, falsePositiveRate: 0.01);
dict.Add("b1", building, new BoundingRectangle(x0, y0, x1, y1));
var hits = dict.FindIntersecting(searchBounds);Use when the same data needs both dict[key] access and "what's intersecting this region?" queries.
Don't use when you only need one of the two access patterns — pay only for what you use with a plain Dictionary or a standalone R-tree.
BoundedDictionary, LinkedDictionary, CounterDictionary, GraphDictionary, LinkedMultiMap, ConcurrentLinkedDictionary (6 types)
Fixed-capacity dictionary backed by a ring buffer. When full, the next Add evicts the oldest insert (FIFO order, not access order).
| Operation | Time | Space |
|---|---|---|
Add / this[key] = |
O(1) avg, O(N) worst (collision) | O(1) |
TryGetValue |
O(1) avg — does not touch eviction order | O(1) |
ContainsKey |
O(1) avg | O(1) |
Remove |
O(1) avg | O(1) |
GetOldest / GetNewest |
O(1) avg | — |
Clear |
O(capacity) | — |
| Storage | — | O(capacity), fixed at construction |
var cache = new BoundedDictionary<string, Data>(capacity: 1000);
cache["k"] = data; // evicts oldest insert when full
var oldest = cache.GetOldest();Use when you want a bounded cache and eviction by insert age is correct (rolling event log, recent-N buffer).
Don't use when you want LRU semantics — reuse should reset the eviction clock; use LinkedDictionary instead.
Dictionary<K,V> that maintains an access-order linked list. Reads move the entry to the front; the back is the eviction candidate when used as a fixed-capacity LRU cache.
| Operation | Time | Space |
|---|---|---|
AddOrUpdate |
O(1) avg, O(N) worst (collision) | O(1) |
TryGetValue |
O(1) avg — mutates LRU order | O(1) |
ContainsKey |
O(1) avg — does not touch LRU order | O(1) |
this[key] (get) |
O(1) avg — mutates LRU order | — |
Remove |
O(1) avg | O(1) |
Clear |
O(N) | — |
| Storage | — | O(N), one entry + two list pointers per key |
var lru = new LinkedDictionary<string, byte[]>(capacity: 1000, CapacityMode.Fixed);
lru.AddOrUpdate("k", payload);
if (lru.TryGetValue("k", out var v)) { /* "k" is now most-recently-used */ }Use when you want a single-threaded LRU cache without the MemoryCache weight class.
Don't use when iteration must not perturb recency — ContainsKey is the side-effect-free probe; TryGetValue and the indexer both touch order.
Dictionary that tracks per-key access frequency in a frequency-bucket linked list. Supports "top-K most frequent" and "least frequent" in time linear in K, not N.
| Operation | Time | Space |
|---|---|---|
AddOrUpdate |
O(1) avg | O(1) |
TryGetValue |
O(1) avg — mutates frequency count | O(1) |
TryPeek |
O(1) avg — does not touch counts | O(1) |
IncrementCount(key) |
O(1) avg | O(1) |
GetMostFrequent(k) |
O(k) | O(k) |
GetLeastFrequent(k) |
O(k) | O(k) |
RemoveLeastFrequent |
O(1) | O(1) |
Remove(key) |
O(1) avg | O(1) |
Clear |
O(N) | — |
| Storage | — | O(N + distinct frequency values) |
var counter = new CounterDictionary<string, Product>();
counter.AddOrUpdate("p1", product);
counter.IncrementCount("p1");
foreach (var kv in counter.GetMostFrequent(10)) { /* hot keys */ }Use when you need LFU eviction or "top-K most accessed" without sorting all keys.
Don't use when you only need raw counts — a Dictionary<TKey, int> is half the size and faster per-op.
Vertex-keyed dictionary plus weighted directed edges. BFS shortest-path, distance-bounded reachability, and Tarjan SCC built on top.
| Operation | Time | Space |
|---|---|---|
Add(key, value) / TryGetValue |
O(1) avg | O(1) |
Remove(key) |
O(deg(key)) | O(1) |
AddEdge / RemoveEdge / HasEdge |
O(1) avg | O(1) |
GetNeighbors(key) |
O(deg(key)) | O(deg) |
Keys / Values |
O(N) — materializes a snapshot copy under read lock | O(N) |
FindShortestPath (weighted; reads EdgeInfo.Weight) |
O((V+E) log V) — Dijkstra with sorted-set priority queue | O(V) |
FindShortestUnweighted (unweighted; ignores edge weights) |
O(V + E) — BFS, returns the path with the fewest hops | O(V) |
FindNodesWithinDistance |
O((V+E) log V) — bounded Dijkstra | O(V) |
FindStronglyConnectedComponents |
O(V + E) | O(V) |
GetClusteringCoefficient(key) |
O(deg(key)²) | O(1) |
| Storage | — | O(V + E) |
var g = new GraphDictionary<string, User>();
g.Add("alice", aliceUser);
g.AddEdge("alice", "bob", weight: 1.0);
var path = g.FindShortestPath("alice", "carol");Use when vertex values, topology, and graph algorithms need to live in one structure (social graphs, dependency DAGs, route maps).
Don't use when you have only edges, no per-vertex values; use a plain adjacency Dictionary<TKey, List<TKey>>.
Dictionary where each key maps to an ordered list of values. Append per key is O(1); insertion order within a key is preserved.
| Operation | Time | Space |
|---|---|---|
Add(key, value) |
O(1) avg | O(1) |
this[key] (get) |
O(1) — returns a NodeValueView aliasing the per-key value list; mutates LRU order |
O(1) |
TryGetValues(key) |
O(1) — same view shape; mutates LRU order | O(1) |
NodeValueView.Count |
O(1) | — |
NodeValueView enumeration |
O(values for this key) | O(1) |
NodeValueView[i] (indexer) |
O(i) — per-key value list is singly linked; prefer foreach for sequential reads |
O(1) |
RemoveKey(key) |
O(1) avg — unlinks KeyNode; values reclaimed by GC | O(1) |
Remove(key, value) |
O(values for that key) | O(1) |
ContainsKey |
O(1) avg | O(1) |
Contains(key, value) |
O(values for that key) | O(1) |
GetValueCount(key) |
O(1) | — |
Clear |
O(buckets) — zeroes bucket array; values reclaimed by GC | — |
| Storage | — | O(keys + total values) |
The returned NodeValueView aliases the live multimap state — mutations after the view is obtained invalidate it. Call the standard LINQ ToArray() for a snapshot copy.
var mm = new LinkedMultiMap<string, Tag>();
mm.Add("photo1", tag1);
mm.Add("photo1", tag2);
var tags = mm["photo1"]; // O(1), live view
foreach (var tag in tags) { … } // O(values)Use when one key naturally maps to many values and per-key insertion order matters (tag bags, event streams partitioned by topic). Don't use when values per key are unbounded and you query "give me the i-th value" — the per-key list is singly linked, so positional access is O(i).
Thread-safe LinkedDictionary variant. Per-bucket fine-grained locks for writes; reads acquire the bucket lock briefly to update the access timestamp used for eviction ordering.
| Operation | Time | Space |
|---|---|---|
AddOrUpdate |
O(1) avg — acquires per-bucket monitor; on existing-key update also acquires the per-instance LRU writer lock | O(1) |
TryGetValue |
O(1) avg — mutates per-node access timestamp under the per-bucket monitor | O(1) |
ContainsKey |
O(1) avg — mutates per-node access timestamp under the per-bucket monitor | O(1) |
TryRemove |
O(1) avg | O(1) |
this[key] (get) |
O(1) avg — mutates per-node access timestamp under the per-bucket monitor | — |
Clear |
O(buckets) under per-bucket locks; nodes reclaimed by GC | — |
| Storage | — | O(N) + one lock per bucket |
Enumeration takes a one-time O(N) snapshot of the LRU chain under the read lock, then releases the lock before yielding — concurrent writers are not blocked during iteration. Mutations after the snapshot is taken are not reflected.
var cache = new ConcurrentLinkedDictionary<string, byte[]>(
capacity: 10_000, CapacityMode.Fixed);
cache.AddOrUpdate("k", payload);
if (cache.TryGetValue("k", out var v)) { /* concurrent-safe */ }Use when multiple threads share an LRU cache and you don't want one global lock around it.
Don't use when you only have one writer thread — LinkedDictionary skips the lock cost.
BloomFilter, CountMinSketch, HyperLogLog, Digest, DigestStreamingAnalytics (5 types)
Space-efficient set membership test with a tuneable false-positive rate and zero false negatives.
| Operation | Time | Space |
|---|---|---|
Add |
O(h), h = hash-function count | O(1) |
Contains |
O(h) | O(1) |
AddRange(span) |
O(n·h) | O(1) |
Clear |
O(m), m = bit-array size | — |
| Storage | — | O(m) bits, m = ⌈−N·ln(p) / (ln 2)²⌉ |
Where N is expectedItems and p is the configured false-positive rate. Memory does not grow with items inserted — undersized filters degrade FPR, they do not allocate.
var filter = new BloomFilter<string>(expectedItems: 1_000_000, falsePositiveRate: 0.01);
filter.Add("token");
if (filter.Contains("other")) { /* probably yes; verify against source if it matters */ }Use when the set is large enough that a HashSet<T> is too expensive to hold in RAM, and false positives are acceptable.
Don't use when the set fits in HashSet<T> comfortably — HashSet.Contains is faster per op and false-positive-free.
Frequency sketch with bounded over-estimation. Width and depth set the error envelope: estimated count is between true count and true count + ε·N with probability 1 − δ.
| Operation | Time | Space |
|---|---|---|
Add(item) / Add(item, count) |
O(d), d = depth | O(1) |
EstimateCount(item) |
O(d) | O(1) |
EstimateFrequency(item) |
O(d) | O(1) |
IsHeavyHitter(item, threshold) |
O(d) | O(1) |
Merge(other) |
O(width · depth) | O(1) |
Scale(factor) |
O(width · depth) | — |
Clear |
O(width · depth) | — |
| Storage | — | O(roundUpToPowerOf2(width) · depth) uint cells — actual width is up to 2× the constructor arg |
var sketch = new CountMinSketch<string>(width: 1024, depth: 4);
sketch.Add("event");
uint approx = sketch.EstimateCount("event");
sketch.Merge(otherShard);Use when unique-key cardinality is huge and approximate counts (with one-sided over-estimate error) are acceptable — telemetry, top-K heavy hitters, log analysis. Mergeable across shards.
Don't use when exact counts matter; a Dictionary<T, int> is exact and simpler when it fits in RAM.
Cardinality estimator. Estimates distinct-element count with bounded relative error using ~2^bucketBits bytes of storage regardless of N.
| Operation | Time | Space |
|---|---|---|
Add(item) |
O(1) | O(1) |
AddRange(span) |
O(n) | O(1) |
EstimateCardinality() |
O(m) on first call after change, O(1) cached | O(1) |
Merge(other) |
O(m) | O(1) |
EstimateUnion(other) / EstimateIntersection(other) |
O(m) | O(1) |
Clear |
O(m) | — |
| Storage | — | O(m) bytes, m = 2^bucketBits |
Standard error is ~1.04 / √m.
var hll = new HyperLogLog<string>(bucketBits: 14);
hll.Add("user-id-42");
long unique = hll.EstimateCardinality();
hll.Merge(otherShard);Use when you need distinct-count over an unbounded stream and approximate is fine — unique-visitor count, distinct-IP, distinct-URL.
Don't use when you need exact cardinality — HashSet<T>.Count is exact when memory permits.
Streaming approximate quantile sketch. Compresses observations into a bounded set of weighted centroids; quantile error is small near tails (P99, P999) and slightly larger near the median.
| Operation | Time | Space |
|---|---|---|
Add(value) / Add(value, weight) |
O(log c), c = centroid count — skip-list descent locates insert position and updates cumulative-weight prefix sums per level | O(1) avg per node |
Quantile(q) / Percentile(p) |
O(log c) — top-down skip-list descent advancing while cumulative width < target | O(1) |
Cdf(x) |
O(log c) | O(1) |
Merge(other) |
O(c₁ + c₂) — linear two-pointer merge of both digests' in-order centroid sequences, then bulk-rebuild | O(c₁ + c₂) intermediate |
Compress |
O(c) — level-0 walk + single-pass bulk-rebuild (no per-centroid descent) | — |
Clone |
O(c) | O(c) |
Clear |
O(c) | — |
| Storage | — | O(compression), typically c ≤ ~compression centroids; per-node overhead ~96 bytes (forward + width arrays at expected ~2 levels avg) |
var d = new Digest(compression: 100.0);
d.Add(latencyMs);
double p99 = d.Quantile(0.99);
d.Merge(otherShard);Use when you need running percentiles over an unbounded stream in bounded memory — SLA monitoring, latency dashboards, distributed shards merged at query time. Don't use when the dataset is small enough to sort in memory; sort + index is exact and simpler.
Digest over a sliding time window. Old observations expire when their window passes; quantile queries operate on the live window only.
| Operation | Time | Space |
|---|---|---|
Add(item, ts?) |
O(log c) per call (inherits Digest); periodic O(buffer) on cleanup boundary when cleanupInterval elapses |
O(1) |
AddRange(items) |
O(n · log c) | O(1) |
GetPercentile(p) |
O(log c) | O(1) |
GetPercentiles([...]) |
O(p · log c) | O(p) |
GetAnalytics() |
O(log c) (six fixed-percentile descents) | O(1) |
Merge(other) |
O(c₁ + c₂) | O(c₁ + c₂) intermediate |
Clear |
O(c) | — |
| Storage | — | O(compression) for the digest + bounded recent-value buffer |
var stream = new DigestStreamingAnalytics<Sample>(
windowSize: TimeSpan.FromMinutes(5),
valueExtractor: s => s.Milliseconds);
stream.Add(sample);
double p99 = stream.GetPercentile(99.0);Use when you want "P99 over the last 5 minutes" rather than lifetime — SLO dashboards, alert thresholds, anomaly detection.
Don't use when you want lifetime quantiles — Digest is leaner without the windowing machinery.
BitGrid2D, LayeredGrid2D, HexGrid2D (3 types)
Boolean 2D grid backed by a bit-packed ulong array — one bit per cell. Bulk set operations (And, Or, Xor, area fill) operate on whole 64-bit words.
| Operation | Time | Space |
|---|---|---|
this[x, y] (get/set) |
O(1) | O(1) |
Toggle(x, y) |
O(1) | O(1) |
FillArea(x, y, w, h, value) |
O(w · h / 64) | — |
SetAll(value) |
O(W·H / 64) | — |
And / Or / Xor (other) |
O(W·H / 64) | — |
CountSetBits |
O(W·H / 64) | O(1) |
CopyRowTo(y, span) |
O(W) | O(1) |
EnumerateSetBits |
O(set bits + W·H / 64) | O(1) |
| Storage | — | ⌈W · H / 8⌉ bytes |
using var fog = new BitGrid2D(width: 1024, height: 1024);
fog[x, y] = true;
fog.Or(otherMask);Use when the grid is large and Boolean — fog-of-war, collision masks, cellular automata, bitmap font glyphs.
Don't use when values are non-Boolean; use LayeredGrid2D<T> or a flat T[].
2D grid with N parallel layers stored as a single contiguous T[]. Per-layer fill, copy, and span access. Indexer with two coordinates targets layer 0; the three-coordinate indexer takes a layer.
| Operation | Time | Space |
|---|---|---|
this[x, y] (layer 0) |
O(1) | — |
this[layer, x, y] |
O(1) | — |
FillArea(x, y, w, h, value) (layer 0) |
O(w · h) | — |
FillLayerArea(layer, x, y, w, h, v) |
O(w · h) | — |
FillLayer(layer, value) |
O(W · H) | — |
ClearLayer(layer) |
O(W · H) | — |
CopyLayer(src, dst) |
O(W · H) | — |
GetRowSpan(y) (layer 0) |
O(1) | — |
GetLayerRowSpan(layer, y) |
O(1) | — |
| Storage | — | O(W · H · layerCount), one contiguous buffer |
using var map = new LayeredGrid2D<int>(width: 256, height: 256, layerCount: 3);
map[layer: 0, x: 5, y: 7] = terrainId;
map.FillLayer(layer: 1, value: 0);Use when several aligned 2D grids share a coordinate system (terrain + decoration + collision; foreground/background tiles) and you want them in one allocation. Don't use when layers have different sizes or coordinate systems — they don't share the contiguous buffer.
Sparse hexagonal grid keyed by axial HexCoord(q, r). Supports neighbor lookup (six directions), distance, ring traversal, line interpolation, and A* pathfinding via a caller-supplied movement-cost function.
| Operation | Time | Space |
|---|---|---|
this[coord] (get/set) / Set / Contains / Remove |
O(1) avg | — |
GetNeighbors(coord) |
O(6) | O(6) |
GetWithinDistance(center, d) |
O(d²) | O(d²) |
GetRing(center, d) / GetLine(start, end) |
O(d) / O(distance) | O(d) / O(distance) |
FindPath(start, goal, isBlocked, getCost?) |
O((V + E) log V) A* | O(V) |
GetReachable(start, movementPoints, isBlocked, getCost?) |
O((V + E) log V) bounded by movementPoints |
O(V) |
| Storage | — | O(N) cells |
var hex = new HexGrid2D<Tile>();
hex[new HexCoord(q: 0, r: 0)] = startTile;
foreach (var c in hex.GetNeighbors(new HexCoord(0, 0))) { /* six neighbors */ }
var path = hex.FindPath(start, goal,
isBlocked: c => !hex.Contains(c),
getCost: c => hex[c].MoveCost);Use when the gameplay grid is hexagonal — strategy games, board games, hex-based simulation. Axial coordinate math is built in. Don't use when the grid is rectangular; the hex coordinate transforms are dead weight.
ObservableList, ObservableHashSet (2 types)
List<T> plus INotifyCollectionChanged and INotifyPropertyChanged. Side-channel events (ItemAdded, ItemInserted, ItemRemovedAt, ItemReplaced, ListCleared) fire alongside the standard events. Re-entrant mutations from inside event handlers are blocked.
| Operation | Time | Space |
|---|---|---|
Add |
O(1) amortized + O(s) notify | O(1) |
AddRange |
O(n) + one batched notify | O(1) |
Insert(i, item) / RemoveAt(i) |
O(N − i) + O(s) | O(1) |
Remove(item) |
O(N) + O(s) | O(1) |
RemoveAll(predicate) / Clear / BatchUpdate |
O(N) + one Reset notify |
— |
this[i] (get / set) |
O(1) (set: + O(s)) | — |
| Storage | — | O(N) |
var list = new ObservableList<Item>();
list.CollectionChanged += (s, e) => RefreshUi(e);
list.Add(item); // single Add notification
list.BatchUpdate(l => { l.Add(a); l.Add(b); }); // single Reset notificationUse when a UI framework (WPF / Avalonia / MAUI) binds to the collection and you want batch mutations without per-item notification storms. Don't use when there are no subscribers — the bookkeeping has no payoff.
HashSet<T> plus INotifyCollectionChanged and INotifyPropertyChanged. Set algebra (UnionWith, IntersectWith, ExceptWith, SymmetricExceptWith) batches notifications.
| Operation | Time | Space |
|---|---|---|
Add(item) / Remove(item) |
O(1) avg + O(s) notify | O(1) |
AddRange / RemoveWhere |
O(n) + one batched notify | O(1) |
Contains(item) |
O(1) avg | — |
UnionWith |
O(other.Count) + one notify | O(1) |
IntersectWith / ExceptWith |
O(N + other.Count) + one notify | O(1) |
SymmetricExceptWith(other) |
O(N + other.Count) + one notify — allocates one HashSet snapshot of size N | O(N) heap |
Clear |
O(N) + one Reset |
— |
| Storage | — | O(N) |
var achievements = new ObservableHashSet<string>();
achievements.CollectionChanged += (s, e) => Persist(e);
achievements.Add("first-blood");Use when a UI or persistence layer needs to observe set membership changes without losing set algebra (UnionWith etc.).
Don't use when there are no subscribers — HashSet<T> is leaner.
TimelineArray (1 type)
Fixed-capacity ring buffer of (timestamp, T) pairs. Records are written at "now" or at an explicit timestamp; queries find the snapshot at a target time via binary search over the live window.
| Operation | Time | Space |
|---|---|---|
Record(snapshot) / Record(snapshot, ts) |
O(1) | O(1) |
GetAtTime(ts) / RewindTo / JumpForward / JumpBackward |
O(log N) | O(1) |
Replay(start, end) |
O(log N + k) | O(1) streaming |
ReplayAtFps(startTime, fps = 60) |
O(log N + frames) — yields (T, long) from startTime to EndTime |
O(1) streaming |
GetTimeWindow(start, duration) |
O(log N + k) | O(1) streaming |
| Storage | — | O(capacity), buffer optionally rented from ArrayPool<T> |
using var timeline = TimelineArray<GameState>.CreateWithArrayPool(capacity: 1800);
timeline.Record(state);
GameState? past = timeline.GetAtTime(targetTimestamp);
foreach (var (snapshot, ts) in timeline.ReplayAtFps(startTime, fps: 30)) { /* ... */ }Use when you record per-frame or per-tick state and need to query "what did it look like at time T" — replay buffers, lag compensation, deterministic rollback netcode. Don't use when you only care about the latest value; a single field beats a ring buffer.
Summary across all 32 types. Symbols used in this table:
N— items currently in the collectioni— index passed to a positional operationk— result-set size (number of items returned by a query)h— hash-function count (BloomFilter only — disambiguated fromkto avoid the collision)m— bit-array size (BloomFilter) or HLL register count, depending on the rowc— Digest centroid count, or SpatialHashGrid cell count, depending on the rowC— occupied cell count (SpatialHashGrid)d— sketch depth (CountMinSketch)deg— vertex degree (GraphDictionary)r— query radius (Spatial)s— subscriber count onINotifyCollectionChanged(Reactive)V,E— graph vertex / edge count (GraphDictionary)W,H— grid width / height in cells (Grid)*— amortized (typical for resize-on-grow containers)
| Type | Add / Insert | Lookup / Query | Remove | Iterate | Space |
|---|---|---|---|---|---|
| Linear | |||||
BoundedList<T> |
O(1) | O(1) index, O(N) Contains | O(N − i) | O(N) | O(capacity) |
PooledList<T> |
O(1)* | O(1) index, O(N) Contains | O(N − i) | O(N) | O(capacity) |
PooledStack<T> |
O(1)* Push | O(1) Peek | O(1) Pop | O(N) | O(capacity) |
PooledQueue<T> |
O(1)* Enqueue | O(1) Peek | O(1) Dequeue | O(N) | O(capacity) |
MinHeap<T> |
O(log N)* Insert | O(1) PeekMin | O(log N) ExtractMin | O(N) | O(N) |
MaxHeap<T> |
O(log N)* Insert | O(1) PeekMax | O(log N) ExtractMax | O(N) | O(N) |
| Spatial | |||||
QuadTree<T> |
O(log N) avg | O(log N + k) Query | O(log N) avg | O(N) | O(N) |
OctTree<T> |
O(log N) avg | O(log N + k) Sphere/AABB/Frustum | — | O(N) | O(N) |
KdTree<T> |
O(log N) avg* | O(log N) Nearest, O(N^(1−1/d) + k) Range | — | O(N) | O(N) |
SpatialHashGrid<T> |
O(1) avg | O((r/cell)² · c) Radius (spatial mode) | O(1) avg | O(N) | O(N + cells) |
TemporalSpatialHashGrid<T> |
O(1) avg* | O((r/cell)² · c) live, + O(log snapshots) at past time | O(1) avg | O(N) | O(N + snapshots) |
BloomRTreeDictionary<TKey,TValue> |
O(log N) avg | O(1) by key, O(log N + k) by region | O(log N) avg | O(N) | O(N) |
| Hybrid | |||||
BoundedDictionary<TKey,TValue> |
O(1) avg | O(1) avg | O(1) avg | O(N) | O(capacity) |
LinkedDictionary<TKey,TValue> |
O(1) avg | O(1) avg (mutates LRU on TryGetValue / get) |
O(1) avg | O(N) | O(N) |
CounterDictionary<TKey,TValue> |
O(1) avg | O(1) avg (count++ on TryGetValue) |
O(1) avg | O(N) | O(N + freq buckets) |
GraphDictionary<TKey,TValue> |
O(1) avg vertex / edge | O((V+E) log V) ShortestPath (Dijkstra), O(V+E) ShortestUnweighted (BFS) / SCC | O(deg) vertex, O(1) avg edge | O(V+E) | O(V + E) |
LinkedMultiMap<TKey,TValue> |
O(1) avg | O(1) view (mutates LRU); enumeration O(values), indexer O(i) | O(1) avg key, O(values) per pair | O(keys + values) | O(keys + values) |
ConcurrentLinkedDictionary<TKey,TValue> |
O(1) avg | O(1) avg (mutates access timestamp) | O(1) avg | O(N) | O(N + 1 lock per bucket) |
| Probabilistic | |||||
BloomFilter<T> |
O(h) | O(h) Contains (one-sided FP) | — | — | O(m) bits |
CountMinSketch<T> |
O(d) | O(d) Estimate | — | — | O(width · depth) |
HyperLogLog<T> |
O(1) | O(m) first call, O(1) cached | — | — | O(m) bytes |
Digest |
O(log c) Add | O(log c) Quantile / Cdf | — | — | O(compression) |
DigestStreamingAnalytics<T> |
O(log c) Add | O(log c) Percentile | — | — | O(compression + window buffer) |
| Grid | |||||
BitGrid2D |
O(1) set | O(1) get | — | O(W·H) | ⌈W·H / 8⌉ bytes |
LayeredGrid2D<T> |
O(1) set | O(1) get | — | O(W·H·layers) | O(W·H·layers) |
HexGrid2D<T> |
O(1) avg set | O(1) avg get; O((V+E) log V) FindPath | O(1) avg | O(N) | O(N) |
| Reactive | |||||
ObservableList<T> |
O(1)* + O(s) | O(1) index, O(N) Contains | O(N − i) + O(s) | O(N) | O(N) |
ObservableHashSet<T> |
O(1) avg + O(s) | O(1) avg | O(1) avg + O(s) | O(N) | O(N) |
| Temporal | |||||
TimelineArray<T> |
O(1) Record | O(log N) GetAtTime | — | O(log N + k) Replay | O(capacity) |
Benchmarks are hardware-dependent. Reproduce on your machine with .\bench.ps1 --rigorous --filter '*<TypeName>Benchmarks*'. Methodology and profile definitions at docs/benchmarks.md.
Libraries multi-target net8.0;netstandard2.1. Tests cover net8.0 and net6.0. Public surface is baselined with Microsoft.CodeAnalysis.PublicApiAnalyzers — patch releases will not break consumers without an explicit major-version bump. SourceLink and .snupkg symbol packages ship with every release.
MIT. Free for any use — personal, commercial, fork, modify, redistribute — provided the copyright notice and license text remain in derivative works.
Issues and pull requests welcome — file against dev/omni-collections-v2. Performance-affecting PRs need before/after numbers from bench.ps1 --standard (or --rigorous for headline claims).