11. Collections: Vec, HashMap, and friends

11.1 Vec growth and capacity

fn main() {
    let mut v: Vec<u32> = Vec::with_capacity(4); // one allocation up front, like make([]T, 0, n)
    for i in 0..10 {
        v.push(i);
        print!("{}/{} ", v.len(), v.capacity()); // capacity at least doubles when it runs out
    }
    println!();
    v.retain(|&x| x % 2 == 0);    // filter in place
    v.dedup();                    // remove consecutive duplicates
    v.truncate(3);
    v.shrink_to_fit();            // give memory back
    println!("{v:?} cap={}", v.capacity());
    let drained: Vec<u32> = v.drain(..1).collect();
    println!("{drained:?} {v:?}");
}

11.2 HashMap and the entry API

use std::collections::HashMap;

fn main() {
    let log = "GET /a\nGET /b\nPOST /a\nGET /a";
    let mut hits: HashMap<&str, u32> = HashMap::new();
    for line in log.lines() {
        let path = line.split_whitespace().nth(1).unwrap_or("?");
        *hits.entry(path).or_insert(0) += 1; // ONE hash lookup, no double borrow
    }
    let mut sorted: Vec<_> = hits.iter().collect();
    sorted.sort_by(|a, b| b.1.cmp(a.1).then(a.0.cmp(b.0)));
    println!("{sorted:?}"); // [("/a", 3), ("/b", 1)]

    if let Some(n) = hits.get_mut("/b") { *n += 10; }
    println!("{:?} {:?}", hits.get("/b"), hits.get("/zzz"));
}

The entry API exists because of borrowing. The obvious version, "if !map.contains_key(k) { map.insert(k, 0) } then get_mut", does two lookups. Versions that hold a reference from the first lookup while inserting do not compile. entry() does one lookup and returns a handle to the slot.

Security note: HashMap uses SipHash-1-3 with a random key per process by default. That makes it resistant to hash-flooding DoS, where an attacker sends many keys that collide. Go's maps are also randomly seeded. C hash tables like the C guide's djb2 table are not. For trusted keys in hot code, a faster hasher (ahash, FxHash) can be several times quicker. Never use those for keys an attacker controls.