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.
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.
Note When looping over the keys in a BTreeMap, we can see that they are stored in a sorted way (an ascending sort).
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.
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 Mar 27, 2023 (edit link).
