Collections

In one sentence

The standard collections map almost one to one to Java’s (Vec is ArrayList, HashMap is HashMap, BTreeMap is TreeMap), but they own their elements, and lookups return Option instead of null.

The Java you know

Java 8 added computeIfAbsent and merge to update a map with one call. Rust has the same idea, the entry API:

Java

static Map<String, List<Long>> ordersByCustomer(List<Map.Entry<String, Long>> orders) {
    Map<String, List<Long>> map = new HashMap<>();
    for (var order : orders) {
        map.computeIfAbsent(order.getKey(), k -> new ArrayList<>()).add(order.getValue());
    }
    return map;
}

static Map<String, Integer> countItems(List<String> items) {
    Map<String, Integer> counts = new HashMap<>();
    for (var item : items) {
        counts.merge(item, 1, Integer::sum);
    }
    return counts;
}

Rust

pub fn orders_by_customer(orders: &[(&str, u64)]) -> HashMap<String, Vec<u64>> {
    let mut map: HashMap<String, Vec<u64>> = HashMap::new();
    for &(customer, id) in orders {
        map.entry(customer.to_string()) // one lookup
            .or_default() // insert an empty `Vec` if the key is new
            .push(id); // then change the value in place
    }
    map
}

pub fn count_items(items: &[&str]) -> HashMap<String, u32> {
    let mut counts = HashMap::new();
    for item in items {
        *counts.entry((*item).to_string()).or_insert(0) += 1;
    }
    counts
}

The Rust you will see

Rust	Java	Note
Vec<T>	ArrayList<T>	growable, on the heap
[T; N]	T[] with a fixed length	the length is part of the type
&[T]	(none)	a slice: a borrowed view of part of a Vec or an array
HashMap<K, V>	HashMap<K, V>	no defined order
BTreeMap<K, V>	TreeMap<K, V>	sorted by key
HashSet<T>, BTreeSet<T>	HashSet<T>, TreeSet<T>
VecDeque<T>	ArrayDeque<T>	a queue with both ends
String	StringBuilder (and String)	see Strings

The collections own their elements. A Vec<Order> holds the orders, not references to them. When the Vec is dropped, the orders are dropped. To share elements, use references (Vec<&Order>) or Rc/Arc (see Smart pointers).

pub fn sequences() -> (usize, u64, usize) {
    let mut prices: Vec<u64> = Vec::new(); // growable, on the heap: `ArrayList<Long>`
    prices.push(1_999);
    prices.extend([500, 250]);

    let weekdays: [&str; 5] = ["Mon", "Tue", "Wed", "Thu", "Fri"]; // fixed size, known at compile time

    let first_two: &[u64] = &prices[..2]; // a slice: a view into part of the `Vec`
    let total: u64 = first_two.iter().sum();

    (prices.len(), total, weekdays.len())
}

A function that only reads a sequence takes a slice &[T], not &Vec<T>. A slice accepts a Vec, an array, and a part of either. See S06: &String, &Vec<T>, &Box<T> parameters.

How to read it

Index or get

v[i] panics if i is out of range, like an ArrayIndexOutOfBoundsException that nobody catches. v.get(i) returns Option<&T>:

pub fn price_at(prices: &[u64], index: usize) -> Option<u64> {
    prices.get(index).copied() // `None` if `index` is out of range
}

pub fn price_at_or_panic(prices: &[u64], index: usize) -> u64 {
    prices[index] // panics if `index` is out of range
}

The same holds for maps: map["key"] panics if the key is missing, and map.get("key") returns an Option. In review, an index into data that comes from outside the program (a request, a file, a user) needs a check or a get. See S24: Indexing (v[i], s[a..b]) on untrusted input.

Maps

pub fn stock_report(items: &[(&str, u32)]) -> (Option<u32>, Vec<String>) {
    let by_name: HashMap<&str, u32> = items.iter().copied().collect();
    let apples = by_name.get("apple").copied(); // `Option<u32>`, never `null`

    let sorted: BTreeMap<&str, u32> = items.iter().copied().collect(); // sorted by key
    let lines = sorted
        .iter()
        .map(|(name, n)| format!("{name}: {n}"))
        .collect();

    (apples, lines)
}

• collect() builds a map from an iterator of (key, value) pairs.
• get returns Option<&V>. .copied() turns Option<&u32> into Option<u32>.
• BTreeMap iterates in key order. HashMap iterates in an order that can change from one run to the next: Rust randomizes the hash seed to protect against attacks that use hash collisions.

The entry API

map.entry(key) looks up the key once, and returns a handle to the slot, whether it is empty or not. Then:

pub fn orders_by_customer(orders: &[(&str, u64)]) -> HashMap<String, Vec<u64>> {
    let mut map: HashMap<String, Vec<u64>> = HashMap::new();
    for &(customer, id) in orders {
        map.entry(customer.to_string()) // one lookup
            .or_default() // insert an empty `Vec` if the key is new
            .push(id); // then change the value in place
    }
    map
}

pub fn count_items(items: &[&str]) -> HashMap<String, u32> {
    let mut counts = HashMap::new();
    for item in items {
        *counts.entry((*item).to_string()).or_insert(0) += 1;
    }
    counts
}

1. Line 4: entry takes the key by value. Here it is an owned String, because the map stores it.
2. Line 5: or_default() inserts Vec::new() (the Default value) if the key is missing, and returns &mut Vec<u64> either way. Like computeIfAbsent(k, k -> new ArrayList<>()).
3. Line 6: The &mut lets the code change the value in the map directly.
4. Line 14: or_insert(0) returns &mut u32. The * dereferences it, so += 1 changes the count in the map. This line is merge(item, 1, Integer::sum).

Other forms you will see: or_insert_with(|| ...) (compute the default only when needed), and_modify(|v| ...) (change an existing value), and match map.entry(k) { Entry::Occupied(..) => .., Entry::Vacant(..) => .. } for full control.

Sets and queues

pub fn unique_and_queue(tags: &[&str]) -> (usize, Option<String>) {
    let unique: HashSet<&str> = tags.iter().copied().collect();

    let mut queue: VecDeque<String> = VecDeque::new(); // `ArrayDeque`
    queue.push_back("first".to_string());
    queue.push_back("second".to_string());
    queue.push_front("urgent".to_string());

    (unique.len(), queue.pop_front())
}

HashSet::insert returns true if the value was new. That makes “keep the first of each” a one-line filter: .filter(|x| seen.insert(x.clone())).

Java habit

There is no Collections.unmodifiableList in Rust. A collection is read-only when the code has a & reference to it, and changeable when it has &mut or owns it. The compiler checks it. See Borrowing.

What good looks like

• Vec by default. Most code needs nothing else.
• Slices in parameters: &[T] to read, &mut [T] to change elements, &mut Vec<T> only to add or remove.
• get for untrusted indexes and keys, [] only where the index is known to be valid.
• The entry API for “insert or update”.
• BTreeMap when the order matters in output or tests: reports, file output, snapshots.
• with_capacity(n) when the size is known in advance, as with ArrayList(n).

Red flags in AI output

• contains_key followed by get().unwrap() or insert: two or three lookups and an unwrap, where entry does one.
• v[i] on input data without a bounds check. See S24: Indexing (v[i], s[a..b]) on untrusted input.
• HashMap in code whose output must be stable: a report, a file, a test that compares strings. The order changes between runs.
• &Vec<T> parameters. See S06: &String, &Vec<T>, &Box<T> parameters.
• Index loops over a Vec. See S10: Index-based loops instead of iterators.
• LinkedList: almost never the right choice in Rust, as in Java. Vec or VecDeque is faster.

• S06Severity: Low&String, &Vec<T>, &Box<T> parametersA reference to the container where a slice (&str, &[T]) or &T is more flexible.
• S10Severity: LowIndex-based loops instead of iteratorsfor i in 0..v.len() with v[i], where an iterator is clearer and has no bounds checks.
• S24Severity: HighIndexing (v[i], s[a..b]) on untrusted inputOut-of-range input makes the program panic.

Better vs worse

The task: add items to a shopping cart, and print it.

1. Worsecontains_key, then get().unwrap(), then insert: three lookups. A HashMap, so the printed order changes between runs.

   pub fn add_to_cart(cart: &mut HashMap<String, u32>, item: &str, count: u32) {
       if cart.contains_key(item) {
           let current = *cart.get(item).unwrap(); // second lookup, and an unwrap
           cart.insert(item.to_string(), current + count); // third lookup
       } else {
           cart.insert(item.to_string(), count);
       }
   }
   
   pub fn print_cart(cart: &HashMap<String, u32>) -> Vec<String> {
       cart.iter().map(|(k, v)| format!("{k} x{v}")).collect() // order changes between runs
   }

   Run in Playground (opens the Rust Playground in a new tab)

2. BetterOne entry call. A BTreeMap, so the cart prints in item order.

   pub fn add_to_cart(cart: &mut BTreeMap<String, u32>, item: &str, count: u32) {
       *cart.entry(item.to_string()).or_insert(0) += count;
   }
   
   pub fn print_cart(cart: &BTreeMap<String, u32>) -> Vec<String> {
       cart.iter().map(|(k, v)| format!("{k} x{v}")).collect() // sorted by item name
   }

   Run in Playground (opens the Rust Playground in a new tab)

Both versions give the same counts. The test both_carts_add_the_same must sort the “worse” output before it can compare it, because HashMap order is random. That is a sign that a user or a test of the real program would also see a different order each time.

HashMap is the right choice when the order does not matter and the map is large: it is faster than BTreeMap for lookups.

Check yourself

1. What does prices[10] do on a Vec with 3 elements?

   Show the answer

   It panics: “index out of bounds”. prices.get(10) returns None instead.

2. What is the Rust equivalent of map.computeIfAbsent(k, x -> new ArrayList<>()).add(v)?

   Show the answer

   map.entry(k).or_default().push(v), or .or_insert_with(Vec::new) instead of .or_default().

3. A test compares a report built from a HashMap with an expected string. It passes on some runs and fails on others. Why?

   Show the answer

   HashMap iteration order is not defined, and it changes between runs. Use a BTreeMap, or sort the entries before building the report.

4. A function only reads a list. Should it take &Vec<Order> or &[Order]?

   Show the answer

   &[Order]. It accepts a Vec, an array, and part of either. Clippy reports &Vec<T> parameters with the ptr_arg lint.

Go deeper

• The Rust Programming Language, chapter 8: Common collections
• Standard library: std::collections, with a guide to choosing a collection
• Standard library: the Entry enum of HashMap