Which collection should you use?

Short answer: Vec for an ordered list you grow at the end, HashMap for key-to-value lookups, BTreeMap when the keys must come back sorted, HashSet when you only need membership. In doubt, start with Vec.

The decision table

What you are doing	Reach for	The catch
A list that grows, read by position	Vec<T>	Middle inserts shift the tail
Values looked up by key	HashMap<K, V>	Keys come back in no particular order
The same, keys sorted	BTreeMap<K, V>	Lookups cost more than a HashMap’s
Membership tests only	HashSet<T>	Holds keys, not key-value pairs

Vec

Vec<T> is a contiguous growable array with heap-allocated contents: one buffer, elements in push order, v[0] to read by position. push appends and pop takes from the end, both cheap.

HashMap

HashMap<K, V> answers “what value goes with this key?” and does not slow down as it grows: tens of nanoseconds per lookup at 1,000 keys and at 1,000,000 (release build, Rust 1.99.0), where a BTreeMap lookup grew from around 100 ns to around 270 ns.

Keys need Hash and Eq: numbers, strings and bools have both, and a struct key gets them from #[derive(Hash, Eq, PartialEq)]. The catch is order: the default hasher is randomly seeded (SipHash 1-3), so iteration comes back in a different order from run to run, which gets its own page later in this chapter.

BTreeMap

BTreeMap<K, V> is an ordered map based on a B-Tree: entries are stored in key order, so keys() and iter() come back sorted. Keys need Ord instead. The price is the lookup: each one walks the tree, so the cost grows with the size. Pick it when sorted iteration is the point.

HashSet

A HashSet<T> answers one question: is this in the set? insert returns false for a value that is already there. Values need Hash and Eq, same as HashMap keys; BTreeSet is the sorted variant.

Related

• Working with collections
• How to loop over a Vec without moving it

Next in this chapter: how to get an element from a Vec without panicking.