HashMap's Friends: IndexMap, MultiMap, and SlotMap

Recipe	Crates	Categories
Store Data in an Insertion-ordered Map
Store Multiple Values for a Single Key with multimap
Store Collections of Objects that Need Unique, Stable, Safe Identifiers

Store Data in an Insertion-ordered Map

indexmap↗ offers the IndexMap data structure that combines the features of a hashmap and a vector. It is a hash table that keeps track of insertion order and allows efficiently iteration over its elements in that order.

This example demonstrates the usage of IndexMap, including methods for accessing elements by index and using the entry API:

use indexmap::IndexMap;

fn main() {
    // Create an IndexMap:
    let mut map = IndexMap::new();

    // Insert elements:
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);

    // Iterate in insertion order:
    println!("Iterating over `IndexMap` in insertion order:");
    for (key, value) in &map {
        println!("{key}: {value}");
    }

    // Access elements by index:
    if let Some((key, value)) = map.get_index(1) {
        println!("Element at index 1: {key}: {value}");
    }

    // Use the `entry` API:
    map.entry("d").or_insert(4);
    map.entry("a").or_insert(10); // This won't change "a" because it already exists.
    println!("IndexMap after using entry API:");
    for (key, value) in &map {
        println!("{key}: {value}");
    }
}

Store Multiple Values for a Single Key with multimap

A MultiMap allows storing multiple values for a single key, which can be useful to associate several items with the same identifier. multimap↗ is implemented as a thin wrapper around std::collections::HashMap↗.

The following example demonstrates how to use a MultiMap:

use anyhow::Result;
use crates_io_api::Category;
use crates_io_api::SyncClient;
use multimap::MultiMap;

// Calls the `crates.io` API client and retrieve the categories a given crate
// belongs to.
fn get_categories_for_crate(crate_name: &str) -> Result<Vec<Category>> {
    let client = SyncClient::new(
        "my-user-agent (my-contact@domain.com)",
        std::time::Duration::from_millis(1000), // Rate limit interval.
    )?;
    // Retrieve the crate's information:
    let crt = client.get_crate(crate_name)?;
    Ok(crt.categories)
}

fn main() -> Result<()> {
    let crate_names = vec!["toml", "config", "nom", "pest"];

    let mut m: MultiMap<String, &str> = MultiMap::new();
    for name in crate_names {
        for cat in get_categories_for_crate(name)? {
            // There can be multiple crates in the same category.
            // A multimap allows multiple values for the same key.
            m.insert(cat.slug, name);
        }
    }

    // Get all values for a given key:
    println!(
        "List of crates in the `config` category: {:?}",
        m.get_vec("config")
    );

    // Or iterate over all keys and the key's vector:
    for (cat, names) in m.iter_all() {
        println!("Category: {cat:?}, names: {names:?}");
    }
    Ok(())
}

Store Collections of Objects that Need Unique, Stable, Safe Identifiers

Use slotmap↗ to store collections of objects that need generated, unique, persistent identifiers ("keys"), but have no clear ownership otherwise, such as game entities or graph nodes.

slotmap items can be added or removed dynamically. Slotmap ensures stable indices, meaning once an item is inserted, its key remains valid until the item is explicitly removed.

slotmap↗ provides three containers: SlotMap↗, HopSlotMap and DenseSlotMap. Two secondary maps, SecondaryMap and SparseSecondaryMap↗ are also provided to map additional objects to the keys created by one of the slot maps.

This example showcases how to create, insert, access, and remove elements from a SlotMap, and how to use a SecondaryMap to associate additional data with the elements in the SlotMap:

use slotmap::SecondaryMap;
use slotmap::SlotMap;

fn main() {
    // Create a new `SlotMap`:
    let mut sm = SlotMap::new();

    // Upon insertion, a unique key is generated.
    // It can be used to later access or remove the values.
    // Insertion, removal and access all take O(1) time.
    let key1 = sm.insert("value");

    // The difference between a `BTreeMap` or `HashMap` and a slot map is that
    // the key is generated, always unique,
    // and will only refer to the entity that was inserted.

    let key2 = sm.insert("value");
    // `key1` and `key2` are not the same, even though they contain the same
    // value:
    assert_ne!(key1, key2);

    // Access values by key:
    assert_eq!(sm[key1], "value");
    println!("Value for `key1`: {:?}", sm.get(key1));

    // Remove a value.
    // The keys returned by `slotmap` are versioned.
    // This means that once a key is removed, it stays removed,
    // even if the physical storage inside the `SlotMap` is reused for new
    // elements.
    sm.remove(key1);
    assert!(!sm.contains_key(key1));

    // Try to access the removed value:
    println!("`key1` after removal: {:?}", sm.get(key1));

    // `key2` is not affected.
    assert_eq!(sm.get(key2), Some(&"value"));

    // We can also create (multiple) secondary maps that can map the keys
    // returned by `SlotMap` to other values, to associate additional arbitrary
    // data with objects stored in slot maps.
    let mut sec = SecondaryMap::new();
    // Insert a value into the secondary map, associated with `key2`.
    sec.insert(key2, "secondary");

    for (key, val) in sm {
        println!("In slotmap: {}; in secondary map: {}", val, sec[key]);
    }
}

Related Topics

• Graphs.
• Hashmaps.
• Vectors.