---
title: Collection Types
url: https://doc.liz6.com/en/rust/10-standard-library-depth/02-collection-types
locale: en
area: rust
tags:
- rust
- standard-library-depth
date: 2026-06-30
modified: 2026-07-16
description: 'Vec is a contiguous array on the heap (O(1) random access, amortized O(1) tail insertion), HashMap uses SwissTable (cache-friendly open addressing), BTreeMap is sorted by key (Vec’s cache locality vs BTreeMap’s ordered traversal—you can’t have both). VecDeque is a ring buffer with O(1) insertion at both ends. Selection depends on access patterns: sequential traversal with Vec, key lookup with HashMap, range queries with BTreeMap.'
---

# Collection Types

> Vec is a contiguous array on the heap (O(1) random access, amortized O(1) tail insertion), HashMap uses SwissTable (cache-friendly open addressing), BTreeMap is sorted by key (Vec’s cache locality vs BTreeMap’s ordered traversal—you can’t have both). VecDeque is a ring buffer with O(1) insertion at both ends. Selection depends on access patterns: sequential traversal with Vec, key lookup with HashMap, range queries with BTreeMap.

## Vec<T>: Dynamic Array

```rust
let mut v = Vec::with_capacity(100);  // Pre-allocate — avoids realloc on push
v.push(42);
```

Internally (24 bytes on the stack for 64-bit): `[ptr: 8B | len: 8B | cap: 8B]`, where `ptr` points to a `[T; cap]` array on the heap.

Growth strategy: When `len == cap`, the new capacity becomes `max(old × 2, len + 1)`. This is the classic strategy for amortized O(1) pushes. Note: `realloc` may copy data to a new address—any references to elements in the old Vec become dangling after reallocation. This is why the borrow checker prohibits pushing while holding a reference to an element.

## HashMap: Default SipHash, Optional FxHash

```rust
use std::collections::HashMap;
let mut map = HashMap::new();
map.insert("key", 42);
```

The standard library’s `HashMap` uses **SipHash 1-3** by default. Why not a faster hash? SipHash is designed to be resistant to HashDoS attacks—where an attacker constructs many keys that produce the same hash, causing HashMap lookups to degrade to O(n) and amplifying CPU resource consumption. SipHash uses a random key (generated at each process startup), so attackers cannot predict hash results.

Trade-off: SipHash is 10-30% slower than FxHash. If your input is controlled (keys are not exposed externally), you can use `rustc_hash::FxHashMap` (the hash table used by rustc itself)—it is a fast hash based on integer arithmetic, but it is not resistant to HashDoS.

## BTreeMap: Ordered Collection

B-tree structure: keys are stored in sorted order, with each node containing B keys. Lookup/insertion is O(log N). Advantages over HashMap:
- **Range scan**: `map.range("a".."z")` is O(log N + K), which HashMap cannot do (unordered)
- **Predictable performance**: No worst-case O(N) degradation (HashMap may degrade during collisions)
- **Memory locality**: B-tree nodes are contiguous (cache-friendly)

Use cases: Ordered traversal and key-range queries.

## VecDeque: Optimized for Double-Ended Operations

Internally uses a ring buffer—both `push_front` and `push_back` are O(1) amortized. Suitable for FIFO queues and double-ended queues. Difference from `Vec`: `Vec::remove(0)` is O(n) (requires memmove for all elements), whereas `VecDeque::pop_front` is O(1) (only moves the ring buffer pointers).

## Selection Guide

| Requirement | Recommendation |
|------|------|
| Sequential storage + random access | Vec |
| FIFO | VecDeque |
| Double-ended queue | VecDeque |
| Key-value, unordered | HashMap (default) / FxHashMap (high performance) |
| Key-value, ordered, range scan | BTreeMap |
| Small collections (< 20 items) without heap | smallvec / tinyvec |
| Fixed size, known at compile time | `[T; N]` |

## References

- **Rust Book**: Chapter 8
- **hashbrown**: Rust HashMap implementation (now part of std)
- **smallvec**: docs.rs/smallvec

*Keywords: Vec, HashMap, BTreeMap, VecDeque, SipHash, FxHash, ring buffer, reallocation*