Collections Chosen by Access Pattern

A collection is an algorithmic decision disguised as a type. Choosing one because it is familiar can make retrieval nondeterministic, queues quadratic, deduplication unreliable, or timeline queries needlessly expensive.

Choose from required operations, ordering guarantees, memory limits, and adversarial behavior.

Learning objectives

After this chapter, you will be able to:

• derive a collection choice from lookup, insertion, ordering, and traversal requirements;
• distinguish sequence order, key order, insertion order, priority order, and no promised order;
• use Vec, VecDeque, HashMap, BTreeMap, HashSet, and BinaryHeap appropriately;
• design multi-index state without leaving partial updates after an error;
• make deterministic output explicit for traces, evals, and tests;
• enforce collection cardinality and element-size limits;
• investigate queue and map performance failures;
• run an evidence index with ID, time, queue, and dedup access paths; and
• explain when a database or external index should replace an in-memory collection.

Dependencies and downstream use

This chapter depends on owned values, references, enums, and typed errors. Iterators are used lightly; the next chapter explains fallible iterator pipelines in depth.

Collections appear throughout the system:

run state
├── HashMap<ArtifactId, Artifact>     exact identity lookup
├── BTreeMap<Timestamp, Vec<EventId>> time-range traversal
├── VecDeque<JobId>                   bounded FIFO work
├── HashSet<ContentHash>              exact deduplication
└── BinaryHeap<ScoredCandidate>       best candidate first

One entity may need several indexes. The hard part then becomes keeping them consistent.

Start with required operations

Write the operations before selecting a type:

Requirement	Likely collection
dense ordered elements, index access, append	Vec<T>
FIFO push-back/pop-front	VecDeque<T>
exact key lookup	HashMap<K, V>
sorted keys and range queries	BTreeMap<K, V>
exact membership/deduplication	HashSet<T>
sorted unique values	BTreeSet<T>
repeatedly remove highest-priority item	BinaryHeap<T>
tiny fixed-size set	array or small Vec<T> may be simplest

These are defaults, not proofs. Measure realistic distributions and include memory, not only operation count.

Vec<T>: the default dense sequence

Vec<T> stores elements contiguously. It is strong for:

• appending;
• indexed and sequential access;
• cache-friendly scans;
• sorting;
• conversion to slices;
• ownership transfer across stages.

let mut violations = Vec::new();
violations.push(Violation::missing("$.summary"));
violations.sort_by(|left, right| left.path.cmp(&right.path));

Removing from the front shifts all remaining elements and is linear. A repeated vec.remove(0) queue can become quadratic.

Preallocate with Vec::with_capacity only when a trustworthy bound is known. Never allocate a client-declared count without applying a server limit; malicious or corrupt lengths can exhaust memory.

Stable order is a product property

A vector preserves sequence order. But what created that sequence?

• filesystem traversal may differ by platform;
• parallel tasks may complete in different order;
• hash-map iteration is unspecified;
• provider results may be unstable.

Sort by a documented total key before serializing traces or eval results. “It happened to be stable in one test” is not a guarantee.

VecDeque<T>: a real double-ended queue

VecDeque supports efficient operations at both ends:

let mut pending = std::collections::VecDeque::new();
pending.push_back(job);
let next = pending.pop_front();

It uses a ring buffer and may be physically split into two slices. Algorithms requiring one contiguous buffer can call make_contiguous, which may move elements.

An in-memory queue is not durable. Process loss drops it. It also needs an explicit capacity:

if pending.len() == max_pending {
    return Err(QueueError::Full);
}

Later production chapters use bounded channels for async backpressure and database leases for restart-safe jobs.

HashMap<K, V>: exact lookup without order

A hash map provides expected constant-time lookup under normal hashing behavior:

let mut by_id = HashMap::new();
by_id.insert(run.id.clone(), run);
let run = by_id.get(&requested_id);

Requirements:

• keys need Eq and Hash;
• mutating a key so its equality/hash changes while stored is a logic error;
• iteration order is not a stable serialization or evaluation order;
• one insert may replace an existing value unless you use entry or check first.

Use the entry API when lookup and mutation are one operation:

let count = counts.entry(model_id).or_insert(0);
*count += 1;

For untrusted keys, use the standard map’s default randomized hasher unless a reviewed alternative has the needed collision resistance. A faster deterministic hasher can expose denial-of-service risk when attackers control keys.

BTreeMap<K, V>: sorted keys and range queries

A B-tree keeps keys ordered:

let events = timeline.range(window_start..=window_end);

This is ideal for:

• timelines;
• ordered pagination;
• prefix/range traversal;
• deterministic key iteration;
• nearest-bound searches.

Lookup is logarithmic rather than expected constant time. For small collections, representation and cache behavior can outweigh asymptotic theory. Benchmark the actual workload.

Timestamp keys may collide. BTreeMap<u64, Event> silently supports only one event per millisecond if ordinary insert replaces the previous value. Use:

• BTreeMap<Timestamp, Vec<EventId>>;
• a composite (Timestamp, Sequence) key;
• or a unique event ID plus a separate time index.

The companion uses a vector per timestamp.

Sets encode membership

HashSet<T> and BTreeSet<T> say values are unique and membership matters. That is clearer than a map to bool.

if !seen_hashes.insert(content_hash) {
    return Err(IngestError::DuplicateContent);
}

Exact hash deduplication is not semantic deduplication. Two differently encoded images can depict the same scene; two normalized texts can derive from distinct legal evidence. Name the equivalence relation and preserve provenance.

Approximate structures such as Bloom filters trade false positives for memory. They require an explicit acceptable-error policy and usually must not be the sole basis for discarding evidence.

BinaryHeap<T>: priority, not full sorting

A binary heap efficiently exposes the greatest item according to Ord:

let mut candidates = BinaryHeap::new();
candidates.push(ScoredCandidate::new(score, id));
let best = candidates.pop();

Rust’s BinaryHeap is a max-heap. Use std::cmp::Reverse for minimum-first ordering.

Do not implement Ord over raw floating-point scores casually: f32 and f64 contain NaN and do not implement total Ord. Use a validated non-NaN/finite score newtype or an explicit total-order policy. Define tie-breaking by stable candidate ID so eval output is reproducible.

A heap does not keep all elements globally sorted. Repeated pops produce priority order; iterating the heap does not.

Multiple indexes and atomicity

The companion EvidenceIndex stores:

• HashMap<EvidenceId, Evidence> for identity;
• BTreeMap<u64, Vec<EvidenceId>> for time ranges;
• VecDeque<EvidenceId> for pending work;
• HashSet<String> for exact content deduplication.

The primary entity is owned once by by_id; secondary structures store cloned small IDs. This avoids duplicating the full evidence text.

Insertion order matters:

if self.by_id.contains_key(&evidence.id) {
    return Err(IndexError::DuplicateId(evidence.id.0));
}
if !self.seen_content.insert(evidence.text.clone()) {
    return Err(IndexError::DuplicateContent);
}
// update remaining indexes only after all fallible checks

This version has one subtle limitation: inserting content into seen_content happens before the remaining in-memory inserts, which are treated as infallible apart from process-level allocation failure. As validation becomes more complex, prepare a validated mutation first, then commit all indexes in one method.

Across a database, queue, and object store, one in-memory critical section is insufficient. Later chapters use transactions, outbox records, idempotency keys, and reconciliation.

Borrowing from collections

Collection access often returns references:

fn get(&self, id: &EvidenceId) -> Option<&Evidence> {
    self.by_id.get(id)
}

The returned evidence cannot outlive the map borrow. Mutating the map while retaining that reference is restricted because insertion may reallocate and invalidate internal addresses.

Sometimes a method needs mutable access to two fields. Struct fields can often be borrowed separately, but holding a reference returned from one field while mutating the same collection is not allowed. Extract owned IDs, narrow scopes, or split responsibilities instead of cloning whole entities reflexively.

Determinism for traces and evals

Any collection that reaches an external artifact needs a canonical order:

• sort violations by (path, code, message);
• sort cases by stable case ID;
• order timeline items by timestamp and sequence;
• order map keys before hashing or serializing if the format does not canonicalize them;
• define tie-breakers for equal model scores.

Determinism improves diffs and replay. It does not imply model inference is deterministic; it removes avoidable noise in the deterministic shell.

Serde JSON maps may use a map representation whose insertion/serialization behavior differs by configuration. Do not rely on incidental library internals for a cryptographic digest. Define and test canonicalization.

Bounds are part of every collection API

Unbounded collections are delayed outages. State limits for:

• number of pending jobs;
• evidence items per run;
• bytes per item and in total;
• violations per output;
• candidates per retrieval stage;
• timeline events per window;
• cache entries and retention time.

The safe sequence is usually:

1. validate one item size;
2. check collection cardinality/total budget;
3. reserve or insert;
4. record the accepted cost;
5. release or evict deterministically.

HashMap::with_capacity(client_count) before bounding client_count is a memory-exhaustion bug.

Runnable companion implementation

Run:

cd rust/rust-ai-engineering
cargo run -q -p mosaic-domain --example collections
cargo test --workspace --examples

Expected output:

first pending: deploy; incident-window items: 2

The code is crates/mosaic-domain/examples/collections.rs. It inserts three incident facts, dequeues in FIFO order, and performs an inclusive time-range query. Its test verifies duplicate content is rejected without partially updating the ID map, timeline, or queue.

Study the clones: only IDs and the deduplication string are cloned; full Evidence values are owned once. A production index should deduplicate by a validated content hash instead of retaining a second full text string in seen_content.

Failure investigation: eval reports reorder on every run

Symptom: JSON reports contain the same cases but produce noisy diffs and different artifact hashes.

Likely cause: report serialization iterates a HashMap.

Investigation:

1. reproduce with identical inputs and build identity;
2. compare semantic values after parsing;
3. locate unordered collection iteration;
4. identify the required canonical key and tie-breaker;
5. sort into a vector or use an ordered map at the artifact boundary;
6. add a test running construction in different insertion orders.

Fix: keep a hash map for internal lookup if appropriate, then materialize and sort the report. Do not switch every map globally to a B-tree without measuring the access path.

Failure investigation: worker throughput degrades quadratically

Symptom: enqueue is fast, but draining a large in-memory queue becomes progressively slower.

Likely cause: repeated Vec::remove(0) shifts every remaining element.

Fix: use VecDeque::pop_front, a bounded async channel, or a durable queue depending on required lifetime. Add a capacity and overload policy; changing the container alone does not prevent memory growth.

Common failure modes

One collection serving every access path

Repeatedly scanning a vector for ID lookup is simple but may dominate at scale. Add an index only after stating consistency and memory costs.

Depending on hash iteration order

Sort external artifacts explicitly.

Silent map replacement

insert returns the old value. Check it, use entry, or reject duplicate IDs before mutation.

Floating-point heap ordering

Validate finite scores and define a total order with stable ties.

Unbounded “temporary” vectors

Retrieval candidates, violations, and trace events need hard caps even if they usually stay small.

In-memory state presented as durable

A VecDeque disappears on restart. Choose a database-backed lease queue when completion must survive process loss.

Security and performance implications

Security:

• bound attacker-controlled key/value counts before allocation;
• retain randomized hashing for untrusted keys unless an alternative is reviewed;
• validate duplicate semantics before discarding evidence;
• avoid leaking secrets through debug output of whole collections;
• canonicalize signed/hashed artifacts with an explicit specification.

Performance:

• consider element size and cache locality, not only Big-O;
• reserve capacity after validation when a trustworthy estimate exists;
• store entities once and small IDs in secondary indexes;
• avoid cloning full strings for set membership—prefer validated hashes or interned IDs when appropriate;
• measure range-query distribution, load factor, queue depth, and eviction churn.

If the working set exceeds process memory, if multiple replicas need consistency, or if queries need durability, use a database/search/vector index. An in-memory collection is not a miniature database with free correctness.

Exercises

Recall

1. Why is a vector poor for repeated pop-front?
2. What ordering does HashMap promise?
3. When does BTreeMap provide a direct capability a hash map does not?
4. What does iterating a BinaryHeap guarantee?

Implementation

1. Replace content strings in seen_content with a ContentHash newtype.
2. Add a maximum pending-item capacity and prove rejection leaves all indexes unchanged.
3. Add removal that cleans every secondary index.
4. Define a composite (timestamp, sequence) timeline key.
5. Add a priority queue of investigation candidates with finite scores and stable ID tie-breakers.

Design

Select collections for:

• model adapters by model ID;
• last 100 trace events;
• retry jobs ordered by due time;
• unique capability grants;
• top 20 retrieval candidates;
• artifact lookup by hash;
• event scan between two timestamps.

State operation complexity, ordering guarantees, memory bound, and durability requirements.

Failure lab

Write regression tests for:

1. duplicate IDs;
2. two events at the same timestamp;
3. queue capacity exhaustion;
4. equal candidate scores;
5. different insertion orders producing identical serialized reports;
6. removal halfway through a multi-index mutation.

Solution guidance

For capacity, validate before mutating any collection. Prefer a dedicated Capacity newtype that cannot be zero if zero has no useful meaning.

Removal needs enough metadata to find the timeline bucket and dedup key. Remove the primary entity only after gathering those values. Delete empty timeline buckets. Test a missing ID as a distinct result, not silent success unless idempotent removal is the contract.

For candidate ordering, wrap a finite score and implement Ord consistently with Eq. Include the stable ID in comparisons so equal scores are deterministic.

For canonical reports, convert map entries to a vector and sort by case ID before serialization. Test exact bytes if the artifact hash depends on them.

Check your understanding

• Why might Vec<T> beat a map for a tiny collection?
• Can HashSet prove two images are semantically duplicates?
• What happens when a map insert uses an existing key?
• Why does a timeline often need more than timestamp -> event?
• When should secondary indexes store IDs rather than whole entities?
• Why is a bounded VecDeque still not a durable job queue?
• What makes a report order reproducible?

Completion checklist

• I list required operations before choosing a collection.
• I define every externally visible ordering and tie-breaker.
• I bound cardinality and item size before reserving memory.
• I avoid linear pop-front on vectors.
• I keep multi-index mutations consistent under every ordinary error.
• I distinguish exact, semantic, and approximate deduplication.
• I know when the state must move to a durable service.
• I ran the collection example and its partial-update test.

Authoritative references

• The Rust Programming Language: Storing Lists of Values with Vectors
• The Rust Programming Language: Storing Keys with Hash Maps
• std::collections
• std::collections::VecDeque
• std::collections::HashMap
• std::collections::BTreeMap
• std::collections::BinaryHeap