Table of Contents

Choosing a collection

Bodu.Collections ships more than a dozen collection types (with the thread-safe variants in Bodu.Collections.Concurrent). This page is the decision guide - it answers "which collection should I reach for?" without making the reader walk every namespace. For the full namespace map, start with the Bodu.Collections introduction; for vocabulary, read the Bodu.Collections concepts.

Quick decision tree

  1. Do you need a key-value store?
  2. Do you need a sequence (FIFO / LIFO / two-ended)?
  3. Do you need set semantics?
  4. Do you need string-keyed prefix lookups or multi-pattern text search?
  5. Do you need a priority queue with key-based updates? → IndexedPriorityQueue<TElement, TPriority>.
  6. Can the answer be approximate? When the exact structure no longer fits in memory and a quantified error is acceptable → the Bodu.Collections.Probabilistic sketches; see Approximate (probabilistic) collections below.

If none of the above fit, the BCL types (List<T>, Dictionary<TKey,TValue>, HashSet<T>, Queue<T>, Stack<T>) are the right choice. Bodu.Collections does not duplicate BCL primitives - every type below adds a contract the BCL does not provide.

The remainder of this page deepens that tree into per-axis tables, real-world scenarios, and a list of anti-patterns that come up most often when picking between similar types.

Decision tables

By access pattern

Requirement Reach for Notes
Single-ended FIFO ring CircularBuffer<T> AllowOverwrite toggles between sliding-window and bounded-throw modes.
Double-ended ring Deque<T> O(1) AddFirst / AddLast / RemoveFirst / RemoveLast.
Append-only stream of unknown length SegmentedBuffer<T> Grows by fixed-size chunks; avoids the array-doubling copy.
Min-heap priority queue with O(1) lookup-by-element IndexedPriorityQueue<TElement, TPriority> Required by Dijkstra, Prim, A* - the Update / EnqueueOrUpdate calls the BCL PriorityQueue<TElement,TPriority> cannot perform.
Range-keyed lookup (interval → value) RangeDictionary<TKey, TValue> O(log n) lookup; rejects overlapping inserts.
Range membership (in any interval?) RangeSet<T> Merges adjacent and overlapping intervals on insertion.
Overlap-storing interval index (stabbing / window queries) IntervalTree<T> / IntervalTree<TKey, TValue> The only range type that stores overlapping intervals - RangeDictionary rejects overlapping inserts, RangeSet merges them, and Bodu.Numerics' IntervalSet<T> normalizes to disjoint ranges. Closed [low, high] endpoints; O(log n + k) QueryPoint / QueryOverlaps, O(log n) Intersects.
Cache with policy-driven eviction EvictingDictionary<TKey, TValue> FIFO, LRU, LFU, MRU, Random, or Second-Chance.
Ordered key-value store with O(1) first/last access SequencedDictionary<TKey, TValue> Insertion order by default; opt into access order for LRU-style reordering. O(1) First / Last / TryRemoveFirst / TryRemoveLast.
One key → many values MultiValueDictionary<TKey, TValue> Indexer returns an empty live view, never null.
One-to-one map, O(1) lookup in both directions BiDictionary<TKey, TValue> Live Inverse view shares storage; duplicate-value conflicts follow the Throw / Replace policy.
Layered lookup with first-wins precedence LayeredDictionary<TKey, TValue> Python ChainMap semantics: a live view over ordered layers, writes to the first layer only; removing a shadowing entry unshadows the deeper value. Count/enumeration walk every layer.
Two-key map with row/column projections Table<TRow, TColumn, TValue> Guava Table shape: live Row / Column views over a row-major store. Column-axis operations are O(rows) - no second index. A plain Dictionary<(TRow, TColumn), TValue> covers lookup-only use.
Auto-materializing defaults on indexer read DefaultingDictionary<TKey, TValue> Python defaultdict semantics: only the indexer getter invokes the value factory and stores the result - TryGetValue/ContainsKey never materialize. The GetOrAdd extension stays the per-call-site option.
Dense integer membership as packed bits BitSet Java BitSet semantics. Prefer over the BCL BitArray, which is fixed-size, has no set-bit query surface (NextSetBit / NextClearBit / Cardinality), and enumerates boxed bool values instead of set-bit indices.
String-keyed prefix lookup (autocomplete, routing) Trie / Trie<TValue> Membership and prefix queries cost O(key length), independent of key count. Configurable IEqualityComparer<char>.
Prefix lookup over long, sparsely branching keys RadixTrie / RadixTrie<TValue> Same member-for-member surface as the tries over path-compressed string edges - node count tracks key count, not total key length.
Multi-pattern text search (all occurrences, one pass) AhoCorasickAutomaton / AhoCorasickAutomaton<TValue> Built once from the pattern set, immutable after. O(text + matches) regardless of pattern count; matches reported ascending by end index, then pattern length.

By capacity and lifecycle

Requirement Reach for Notes
Fixed capacity, never grows, reject on full CircularBuffer<T> with AllowOverwrite = false Or Deque<T> with AllowGrow = false for two-ended access.
Fixed capacity, overwrite on full CircularBuffer<T> with AllowOverwrite = true Sliding-window semantics - the default.
Fixed capacity, evict by policy on full EvictingDictionary<TKey, TValue> The only collection in the namespace that evicts a non-end element.
Growable with O(1) ends Deque<T> with AllowGrow = true Backing array doubles on overflow; capped at MaxLength.
Growable append-only without per-doubling copy SegmentedBuffer<T> New segments allocate without rehoming existing elements.
Runtime toggle between growable and fixed Deque<T> AllowGrow is a settable property; switching to false does not shrink the array.
Pre-grow before a known burst Deque<T>.EnsureCapacity Honoured even when AllowGrow = false.

By concurrency

Requirement Reach for Notes
Multi-threaded FIFO ring ConcurrentCircularBuffer<T> Implements IProducerConsumerCollection<T> over a Vyukov MPMC algorithm.
Multi-threaded unique set ConcurrentHashSet<T> Lock-free split-ordered hash set; every operation is CAS-based, so writers never block each other or readers.
Multi-threaded bounded cache (LRU / LFU / TTL) ConcurrentEvictingDictionary<TKey, TValue> Lock-striped segments over all six EvictingDictionaryPolicy values, optional TTL expiry, single-flight GetOrAdd, and a post-commit ItemEvicted event. Eviction order is exact per segment, approximate globally.
Multi-threaded read-heavy cache where approximate LRU is acceptable ConcurrentLruCache<TKey, TValue> Lock-free reads over a segmented pseudo-LRU (hot / warm / cold queues); maintenance is amortized onto writers. No TTL, no policy choice, and Count may transiently exceed Capacity. Prefer the evicting dictionary when you need exactness, TTL, or a stampede guard.
Single-threaded, every other scenario All non-concurrent types in Bodu.Collections.Generic Wrap with external synchronisation if shared across threads.

The non-concurrent types are not thread-safe even for concurrent reads - EvictingDictionary<TKey, TValue> mutates LRU and LFU metadata on read, and IndexedPriorityQueue<TElement, TPriority> mutates the element-to-slot map on every heap operation. Wrap with a lock or ReaderWriterLockSlim when sharing a single instance.

By ordering and uniqueness

Requirement Reach for Notes
Unique elements, no order HashSet<T> (BCL) Bodu does not duplicate this.
Unique elements, insertion-ordered, indexable IndexedSet<T> Implements IList<T> over an open-addressing hash table; O(1) Contains, IndexOf, indexed read.
Unique elements, insertion-ordered, set surface OrderedSet<T> Same engine as IndexedSet<T>; exposes indices only as a read-only view.
Unique elements, comparer-sorted, positional queries NavigableSet<T> Order-statistic sorted set: O(log n) TryGetFloor / TryGetCeiling / TryGetHigher / TryGetLower, rank/select (IndexOf / GetAt), and CountInRange. The BCL SortedSet<T> offers only GetViewBetween (no navigation or rank surface), and SortedList<TKey,TValue> pays O(n) per insert.
Duplicates retained with count Multiset<T> Count includes multiplicity; DistinctCount does not.
Sorted by priority, unique elements, mutable priorities IndexedPriorityQueue<TElement, TPriority> Enqueue of an existing element throws - use EnqueueOrUpdate.
Sorted by interval RangeSet<T> Half-open intervals over any IComparable<T>.
Key-value pairs, insertion- or access-ordered SequencedDictionary<TKey, TValue> Preserves a stable encounter order; access-order mode moves an entry to the tail on read. Unbounded - does not evict.
Key-value pairs, key-sorted, positional queries NavigableDictionary<TKey, TValue> Order-statistic sorted dictionary: O(log n) TryGetFloorEntry / TryGetCeilingEntry / TryGetHigherEntry / TryGetLowerEntry, rank/select (IndexOfKey / GetAt), and CountInRange. The BCL SortedDictionary<TKey,TValue> offers no navigation or rank surface, and SortedList<TKey,TValue> pays O(n) per insert.

By failure mode on overflow

Add when full does… Reach for
Throws InvalidOperationException. CircularBuffer<T> with AllowOverwrite = false; Deque<T> with AllowGrow = false.
Overwrites the oldest element. CircularBuffer<T> with AllowOverwrite = true.
Doubles the backing array. Deque<T> with AllowGrow = true.
Evicts a policy-selected entry. EvictingDictionary<TKey, TValue>.
Cannot happen (collection always grows). NavigableSet<T>, NavigableDictionary<TKey, TValue>, LayeredDictionary<TKey, TValue>, DefaultingDictionary<TKey, TValue>, Table<TRow, TColumn, TValue>, SegmentedBuffer<T>, IndexedSet<T>, OrderedSet<T>, SequencedDictionary<TKey, TValue>, MultiValueDictionary<TKey, TValue>, Multiset<T>, RangeDictionary<TKey, TValue>, RangeSet<T>, IntervalTree<T>, IntervalTree<TKey, TValue>, IndexedPriorityQueue<TElement, TPriority>, ConcurrentHashSet<T>.

The Try… overloads on the bounded ring-backed types substitute a false return for the throw, so callers can stay non-throwing without changing the toggle.

Approximate (probabilistic) collections

The Bodu.Collections.Probabilistic namespace trades exactness for a fixed memory footprint: each sketch is sized once at construction and answers queries over arbitrarily long streams in O(1) space, with an error bound you choose up front.

Warning

These types are approximate - do not use them for exact membership or exact counting. A Bloom filter can report a never-added element as present, a count-min estimate can exceed the true count, and a HyperLogLog cardinality is a statistical estimate. When the answer must be exact, stay with the exact types above.

Reach for When… Error contract
BloomFilter<T> You need "have I seen this?" over a stream too large for a HashSet<T>, and a definitive no plus a probabilistic yes is enough. No false negatives; false positives at the design rate p when filled to ExpectedItems (EstimatedFalsePositiveRate tracks the current fill).
CountMinSketch<T> You need per-element frequencies (heavy hitters, rate estimates) over high-cardinality streams where a counting dictionary would grow without bound. Never underestimates; overestimates by at most ε · TotalCount with probability at least 1 − δ.
HyperLogLog<T> You need a distinct-element count (unique visitors, distinct keys) in kilobytes rather than one entry per element. Relative standard error ≈ 1.04/√m for m = 2^precision one-byte registers (~0.81% at precision 14).

All three hash through the element's IEqualityComparer<T>, merge with parameter-compatible instances (UnionWith / MergeWith), and round-trip state through an opaque, version-checked export/import. None is thread-safe. See the Probabilistic collections guide for the full contracts, including the comparer-entropy and randomized-string-hash caveats.

Common scenarios

I want to… Reach for
Track the last N sensor readings, dropping the oldest. CircularBuffer<T> with AllowOverwrite = true.
Implement a rate limiter that rejects bursts. CircularBuffer<T> with AllowOverwrite = false.
Build a producer-consumer queue between threads. ConcurrentCircularBuffer<T>.
Build an undo / redo history with capped size. Deque<T> with AllowGrow = false.
Cache compiled artifacts by name with LRU eviction. EvictingDictionary<TKey, TValue> + EvictingDictionaryPolicy.LeastRecentlyUsed.
Track session liveness without reading the value. EvictingDictionary<TKey, TValue>.Touch.
Build a lookup from IP ranges to country codes. RangeDictionary<TKey, TValue>.
Maintain a set of free disk extents that merges on insert. RangeSet<T>.
Find every booking that clashes with a proposed meeting slot. IntervalTree<TKey, TValue> - overlaps are stored, QueryOverlaps lists the clashes.
Run Dijkstra's algorithm on a weighted graph. IndexedPriorityQueue<TElement, TPriority>.
Group log entries by correlation id. MultiValueDictionary<TKey, TValue>.
Keep a dictionary you can iterate in insertion order. SequencedDictionary<TKey, TValue>.
Layer request-scoped overrides over shared defaults. LayeredDictionary<TKey, TValue> - overrides first, defaults behind.
Pivot values by two keys and slice by either axis. Table<TRow, TColumn, TValue> - Row / Column live projections; keep the most-sliced axis on the row side.
Group items into lists without seeding empty lists. DefaultingDictionary<TKey, TValue> with _ => new List<T>(), or MultiValueDictionary<TKey, TValue> for a dedicated multi-map surface.
Build an unbounded LRU and evict the oldest yourself. SequencedDictionary<TKey, TValue> with accessOrder: true + TryRemoveFirst.
Find the nearest price at or below a limit, or the k-th smallest sample. NavigableSet<T> - TryGetFloor / GetAt in O(log n).
Look up the tax bracket, tier, or time-series entry in effect at a key. NavigableDictionary<TKey, TValue> - TryGetFloorEntry / Range in O(log n).
Count occurrences of tokens in a corpus. Multiset<T>.
Suggest completions for a typed prefix. Trie<TValue> - ItemsWithPrefix in O(prefix + matches).
Route requests by longest shared path segments. RadixTrie<TValue> - compressed edges keep URL/path tables compact.
Flag every banned keyword in a document in one pass. AhoCorasickAutomaton - EnumerateMatches reports all (overlapping) occurrences; HasMatch for a quick yes/no.
Maintain a list of items in entry order while ensuring uniqueness. IndexedSet<T>.
Track a thread-safe set of active correlation ids. ConcurrentHashSet<T>.
Stream-build a payload whose total length is unknown. SegmentedBuffer<T>, or PooledBufferBuilder<T> for an ArrayPool<T>-backed builder.
Skip re-crawling URLs already visited, tolerating rare false skips. BloomFilter<T> - approximate; never misses a visited URL.
Find the most frequent requests in a high-cardinality stream. CountMinSketch<T> - approximate; never undercounts.
Count unique visitors without storing every id. HyperLogLog<T> - approximate; ~1.04/√m standard error.

Anti-patterns

  • Do not use Deque<T> when you only need single-ended FIFO. A CircularBuffer<T> with AllowOverwrite = false expresses the constraint more clearly and is the same shape under the hood - both inherit from RingBackedCollection<T>.
  • Do not use EvictingDictionary<TKey, TValue> as a general dictionary. It evicts on overflow even when you would prefer growth - choose the BCL Dictionary<TKey,TValue> when the working set is unbounded, or SequencedDictionary<TKey, TValue> when you also need a stable iteration order.
  • Do not confuse SequencedDictionary<TKey, TValue> with the BCL OrderedDictionary<TKey,TValue> (.NET 9+). The BCL type is positional - index-addressable with Insert/RemoveAt. SequencedDictionary<TKey,TValue> has no positional surface; it gives O(1) ends and O(1) keyed removal instead, and adds an optional access-order (LRU) mode. (On net8.0 the BCL type is unavailable regardless.)
  • Do not assume the non-concurrent types are safe under concurrent reads. Reads on EvictingDictionary<TKey, TValue> mutate eviction metadata; reads on every collection rely on a structural-version counter that is not interlocked. Wrap with external synchronisation or pick the explicit concurrent variant.
  • Do not pair IndexedSet<T> with List<T> "to also enforce uniqueness". IndexedSet<T> already implements IList<T> with O(1) Contains and IndexOf - keeping two structures in sync introduces drift bugs.
  • Do not implement an LRU cache by hand around Dictionary<TKey, TValue> + Deque<T>. EvictingDictionary<TKey, TValue> already provides LRU, LFU, FIFO, MRU, Random, and Second-Chance through a single EvictingDictionaryPolicy selector.
  • Do not allocate a fresh PooledBufferBuilder<T> per call to "reuse the pool". The pool is global; the builder is the rental handle. For repeated rebuilds, call Reset to keep the current rented buffer.

See also