Rust - BTreeMap Example - Dot Net Perls

BTreeMap. In Rust the BTreeMap uses a tree-based algorithm to store keys along with their values. This can be much faster than a linear search through a vector.

vec

Compared to HashMap, the BTreeMap has nearly identical usage. It usually tends to be slower than HashMap, but not always. A benchmark can help determine the faster collection.

HashMap

First example. Consider this example program in Rust. We create a BTreeMap with integer keys and values. With BTreeMap, we could use other types like Strings or even arrays as keys and values.

Note When looping over the keys in a BTreeMap, we can see that they are stored in a sorted way (an ascending sort).

for

Note 2 As with HashMap, we can call get in an if-let statement. This gives us an unwrapped value to use more easily.

use std::collections::BTreeMap; fn main() { // Create BTreeMap. let mut b = BTreeMap::new(); b.insert(200, 20); b.insert(100, 5); // Keys are ordered. for k in b.keys() { println!("KEY: {k}"); } // Get a value. let test = 100; if let Some(value) = b.get(&test) { println!("FOR 100: {value}"); } }

KEY: 100 KEY: 200 FOR 100: 5

BTreeSet. This collection is the same as BTreeMap but does not provide values, and it has helpful additional methods. When values are not needed, BTreeSet can be clearer.

Part 1 We create a BTreeSet with new() and add 2 items to it with the insert function.

Part 2 We can use pop_first to remove an element from the BTreeSet. In a sense, this collection is linear and has a start element.

Part 3 We can get the length of the collection with len(). This tells us the total number of keys.

use std::collections::*; fn main() { // Part 1: create set and add elements. let mut set = BTreeSet::new(); set.insert(10); set.insert(20); // Part 2: We can use pop to remove an element at the start. if let Some(x) = set.pop_first() { println!("{x}"); } // Part 3: Length. println!("{}", set.len()); }

10 1

Benchmark. The important question with BTreeMap is how it performs against HashMap. Both collections are about as easy to use—most code (not all) can be left unchanged.

Version 1 In this version of the code, we look up 6 million keys in a BTreeMap. All of the keys exist in the collection.

Version 2 Here we do the same thing, but use the HashMap. In both versions, a panic macro handles unexpected results.

Result HashMap is about twice as fast as BTreeMap—in most situations, HashMap will have better performance overall.

use std::time::*; use std::collections::*; fn main() { let keys = ["bird", "frog", "dog", "cat", "tree", "house"]; let mut b = BTreeMap::new(); let mut h = HashMap::new(); for k in keys { b.insert(k, true); h.insert(k, true); } // Version 1: use BTreeMap. let t0 = Instant::now(); for _ in 0..1000000 { for k in &keys { if !b.contains_key(k) { panic!("Error"); } } } println!("{}", t0.elapsed().as_millis()); // Version 2: use HashMap. let t1 = Instant::now(); for _ in 0..1000000 { for k in &keys { if !h.contains_key(k) { panic!("Error"); } } } println!("{}", t1.elapsed().as_millis()); }

111 ms BTreeMap 58 ms HashMap

Performance notes. Occasionally, particularly on collections with small keys, the BTreeMap is a better choice. Try it out when integers or small arrays are used as keys.

A summary. BTreeMap is an optimized collection in the Rust standard library (std). It is implemented with a different algorithm than HashMap, and is usually but not always slower.