`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

We call BTreeMap::new() to create a BTreeMap with integer keys and values. 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).

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.

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.