Collection Performance Trade-Offs

Asymptotic Big-O notation hides constant factors—such as CPU cache locality, memory allocator pressure, hashing cost, and branch prediction—that often determine real-world collection performance on modern hardware.

1. Small $N$: Sorted or Linear Vec<(K, V)> vs. HashMap<K, V>

For small maps (typically $N \le 15\text{–}30$ entries with small keys like integers or short strings), a flat Vec<(K, V)> scanned linearly with .iter().find(...) or searched with .binary_search_by_key(...) often outperforms HashMap<K, V>:

• Scanning 16 contiguous (u32, u32) pairs reads just two 64-byte L1 cache lines with hardware prefetching and zero SipHash computation.
• A Vec<(K, V)> has zero control-byte or load-factor slack overhead.

struct SmallMap<K, V> {
    entries: Vec<(K, V)>,
}

impl<K: Eq, V> SmallMap<K, V> {
    fn new() -> Self {
        Self { entries: Vec::new() }
    }

    fn insert(&mut self, key: K, value: V) {
        if let Some((_, existing)) = self.entries.iter_mut().find(|(k, _)| *k == key) {
            *existing = value;
        } else {
            self.entries.push((key, value));
        }
    }

    fn get(&self, key: &K) -> Option<&V> {
        self.entries
            .iter()
            .find_map(|(k, v)| if k == key { Some(v) } else { None })
    }
}

fn main() {
    let mut headers = SmallMap::new();
    headers.insert("content-type", "application/json");
    headers.insert("accept", "*/*");

    println!("content-type: {:?}", headers.get(&"content-type"));
}

content-type: Some(&"application/json")

2. Memory Overhead per Element

3. Hashing Overhead vs. Comparison Overhead

When choosing between HashMap<K, V> and BTreeMap<K, V> for large $N$:

• Long string keys (String) with shared prefixes (such as URLs "https://example.com/api/v1/..."): BTreeMap must compare the shared prefix at every level of the tree ($O(\log n)$ comparisons), whereas HashMap hashes the string once and compares full keys only on the matching bucket.
• Small integer keys (u32, u64): Default SipHash-1-3 has a fixed initialization and finalization cost that can exceed simple integer comparisons. If keys are not attacker-controlled, using a fast non-cryptographic hasher (or BTreeMap if sorted order is useful) eliminates that hashing bottleneck.