Home
Search
Rust BTreeMap ExampleUse BTreeMap to store keys and values in a collection. Benchmark BTreeMap against HashMap.
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.
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.
Keys When looping over the keys in a BTreeMap, we can see that they are stored in a sorted way (an ascending sort).
for
Get As with HashMap, we can call get in an if-let statement. This gives us an unwrapped value to use more easily.
if
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
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.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on 9/22/2022 (image).
Home
© 2007-2022 sam allen.
see site info on the changelog.