Hashmap's Friends

Recipe	Crates	Categories
Store Data in an Insertion-ordered Map
Store Data in a multimap
Store Collections of Objects that Need Stable, Safe References

Store Data in an Insertion-ordered Map

IndexMap is a data structure in Rust that combines the features of a hashmap and a vector.

indexmap⮳ offers a hash map that separately keeps track of insertion order and allows you to efficiently iterate over its elements in that order.

use indexmap::IndexMap;

// The indexmap crate in Rust provides a hash table
// where the keys have a consistent order of insertion,
// which is preserved when iterating.
fn main() {
    // Creating an IndexMap
    let mut map = IndexMap::new();

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

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

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

    // Using 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 Data in a multimap

A MultiMap allows you to store multiple values for a single key, which can be useful when you need to associate several items with the same identifier.

multimap⮳ is implemented as a thin wrapper around std::collections::HashMap⮳.

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: {:?}, names: {:?}", cat, names);
    }
    Ok(())
}

Store Collections of Objects that Need Stable, Safe References

Slotmap offers a way to handle collections where items can be added or removed dynamically, and each item is identified by a unique key. Slotmap ensures stable indices, meaning once an item is inserted, its key remains valid until the item is explicitly removed.

Use slotmap⮳ to store collections of objects that need stable, safe references but have no clear ownership otherwise, such as game entities or graph nodes.

slotmap⮳ provides three containers with persistent unique keys to access stored values, SlotMap⮳, HopSlotMap and DenseSlotMap. Two secondary maps, SecondaryMap and SparseSecondaryMap⮳ are also provided that map further objects to the keys created by one of the slot maps.

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 value that was inserted.
    let key2 = sm.insert("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));

    assert_eq!(sm.get(key2), Some(&"value"));

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

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