Rust and Data Structures

Choosing Data Structures

Choosing the right data structure in Rust balances asymptotic time complexity ($O(1)$, $O(\log n)$, $O(n)$) against constant-factor hardware realities (contiguous cache lines vs pointer chasing, and allocation count).

Decision Tree for Standard Rust Collections:

  Need a sequence of items?
    |-- Only push/pop at back or index by `usize`?  ---> `Vec<T>` (Default for 90% of cases!)
    |-- Need O(1) push/pop at BOTH front and back?  ---> `VecDeque<T>`
    +-- Always extract the largest/smallest item?   ---> `BinaryHeap<T>`

  Need key-value lookup or uniqueness (`Set`)?
    |-- Point lookup (`get`, `insert`, `contains`)? ---> `HashMap<K, V>` / `HashSet<T>`
    +-- Sorted order or range queries (`a..=b`)?    ---> `BTreeMap<K, V>` / `BTreeSet<T>`

Asymptotic Complexity Matrix of Standard Library Collections

Collection Index [i] Search by Key/Value Insert Front Insert Back Insert Key Remove Mid Memory Overhead per Item
Vec<T> $O(1)$ $O(n)$ (or $O(\log n)$ if sorted) $O(n)$ $O(1)$ amortized — $O(n)$ (or $O(1)$ swap_remove) 0 bytes (beyond spare capacity)
VecDeque<T> $O(1)$ $O(n)$ $O(1)$ amortized $O(1)$ amortized — $O(n)$ 0 bytes (beyond spare capacity)
HashMap<K, V> — $O(1)$ expected — — $O(1)$ expected $O(1)$ expected ~1 control byte + load-factor slack
BTreeMap<K, V> — $O(\log n)$ — — $O(\log n)$ $O(\log n)$ Amortized across 6–11 keys per node
BinaryHeap<T> — $O(1)$ max (peek) — — $O(\log n)$ (push) $O(\log n)$ (pop) 0 bytes (backed by Vec<T>)
LinkedList<T> $O(n)$ $O(n)$ $O(1)$ $O(1)$ — $O(n)$ to reach 16 bytes (prev + next pointers) + allocator header per node!

Crossover Points: When Sorted Vec<(K, V)> Beats HashMap<K, V>

Asymptotic $O(1)$ vs $O(n)$ or $O(\log n)$ hides constant factors for small collections ($N \le 32$):

  • Computing a SipHash over a key and probing a HashMap takes ~15–25 ns.
  • Scanning a contiguous Vec<(K, V)> of 12 elements sitting inside two L1 cache lines takes under 5 ns—and requires less memory!
Collection Size $N$ Access Pattern Fastest Data Structure in Practice
$N \le 16$–$32$ Point lookup & iteration Linear scan on Vec<(K, V)> (or SmallVec<[(K, V); 8]>)
$N > 32$ (Write once, read many) Point lookup, range queries, & compact RAM Sorted Vec<(K, V)> + binary_search_by_key (Zero hash table slack!)
$N > 32$ (Dynamic inserts & lookups) Frequent insertions, deletions, & point lookups HashMap<K, V> (or BTreeMap<K, V> if sorted range queries are needed) 
/// A read-optimized immutable lookup table backed by a sorted `Box<[(K, V)]>`.
/// Uses 0 bytes of hash-table overhead and answers queries in O(log n) via binary search!
pub struct FrozenMap<K, V> {
    entries: Box<[(K, V)]>,
}

impl<K: Ord, V> FrozenMap<K, V> {
    pub fn from_vec(mut vec: Vec<(K, V)>) -> Self {
        vec.sort_unstable_by(|a, b| a.0.cmp(&b.0));
        vec.dedup_by(|a, b| a.0 == b.0);
        Self {
            entries: vec.into_boxed_slice(),
        }
    }

    pub fn get(&self, key: &K) -> Option<&V> {
        let idx = self.entries.binary_search_by(|(k, _)| k.cmp(key)).ok()?;
        Some(&self.entries[idx].1)
    }

    pub fn len(&self) -> usize {
        self.entries.len()
    }
}

fn main() {
    let table = FrozenMap::from_vec(vec![
        (404, "Not Found"),
        (200, "OK"),
        (500, "Internal Server Error"),
        (201, "Created"),
    ]);

    assert_eq!(table.get(&200), Some(&"OK"));
    assert_eq!(table.get(&404), Some(&"Not Found"));
    assert_eq!(table.get(&302), None);
    println!("FrozenMap ({} entries) lookup 200 -> {:?}", table.len(), table.get(&200));
}

FrozenMap (4 entries) lookup 200 -> Some("OK")