iddqd

Maps where keys are borrowed from values.

This crate consists of several map types, collectively called ID maps:

• IdOrdMap: A B-Tree based map where keys are borrowed from values.
• IdHashMap: A hash map where keys are borrowed from values.
• BiHashMap: A bijective (1:1) hash map with two keys, borrowed from values.
• TriHashMap: A trijective (1:1:1) hash map with three keys, borrowed from values.

Usage

• Pick your ID map type.
• Depending on the ID map type, implement IdOrdItem, IdHashItem, BiHashItem, or TriHashItem for your value type.
• Store values in the ID map type.

Features

This crate was built out a practical need for map types, and addresses issues encountered using Rust’s default map types in practice at Oxide.

• Keys are retrieved from values, not stored separately from them. Separate storage has been a recurring pain point in our codebases: if keys are duplicated within values, it’s proven to be hard to maintain consistency between keys and values. This crate addresses that need.
• Keys may be borrowed from values, which allows for more flexible implementations. (They don’t have to be borrowed, but they can be.)
• There’s no insert method; insertion must be through either insert_overwrite or insert_unique. You must pick an insertion behavior.
• For hash maps, the default hasher is foldhash, which is much faster than SipHash. However, foldhash does not provide the same level of HashDoS resistance as SipHash. If that is important to you, you can use a different hasher. (Disable the default-hasher feature to require a hash builder type parameter to be passed in.)
• The serde implementations reject duplicate keys.

We’ve also sometimes needed to index a set of data by more than one key, or perhaps map one key to another. For that purpose, this crate provides BiHashMap and TriHashMap.

• BiHashMap has two keys, and provides a bijection (1:1 relationship) between the keys.
• TriHashMap has three keys, and provides a trijection (1:1:1 relationship) between the keys.

As a consequence of the general API structure, maps can have arbitrary non-key data associated with them as well.

Examples

An example for IdOrdMap:

use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug)]
struct User {
    name: String,
    age: u8,
}

// Implement IdOrdItem so the map knows how to get the key from the value.
impl IdOrdItem for User {
    // The key type can borrow from the value.
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.name
    }

    id_upcast!();
}

let mut users = IdOrdMap::<User>::new();

// You must pick an insertion behavior. insert_unique returns an error if
// the key already exists.
users.insert_unique(User { name: "Alice".to_string(), age: 30 }).unwrap();
users.insert_unique(User { name: "Bob".to_string(), age: 35 }).unwrap();

// Lookup by name:
assert_eq!(users.get("Alice").unwrap().age, 30);
assert_eq!(users.get("Bob").unwrap().age, 35);

// Iterate over users:
for user in &users {
    println!("User {}: {}", user.name, user.age);
}

Keys don’t have to be borrowed from the value. For smaller Copy types, it’s recommended that you use owned keys. Here’s an example of using IdOrdMap with a small integer key:

struct Record {
    id: u32,
    data: String,
}

impl IdOrdItem for Record {
    // The key type is small, so an owned key is preferred.
    type Key<'a> = u32;

    fn key(&self) -> Self::Key<'_> {
        self.id
    }

    id_upcast!();
}

// ...

An example for IdHashMap, showing a complex borrowed key. Here, “complex” means that the key is not a reference itself, but a struct that returns references to more than one field from the value.

use iddqd::{IdHashItem, IdHashMap, id_upcast};

#[derive(Debug)]
struct Artifact {
    name: String,
    version: String,
    data: Vec<u8>,
}

// The key type is a borrowed form of the name and version. It needs to
// implement `Eq + Hash`.
#[derive(Eq, Hash, PartialEq)]
struct ArtifactKey<'a> {
    name: &'a str,
    version: &'a str,
}

impl IdHashItem for Artifact {
    // The key type can borrow from the value.
    type Key<'a> = ArtifactKey<'a>;

    fn key(&self) -> Self::Key<'_> {
        ArtifactKey { name: &self.name, version: &self.version }
    }

    id_upcast!();
}

let mut artifacts = IdHashMap::<Artifact>::new();

// Add artifacts to the map.
artifacts
    .insert_unique(Artifact {
        name: "artifact1".to_owned(),
        version: "1.0".to_owned(),
        data: b"data1".to_vec(),
    })
    .unwrap();
artifacts
    .insert_unique(Artifact {
        name: "artifact2".to_owned(),
        version: "1.0".to_owned(),
        data: b"data2".to_vec(),
    })
    .unwrap();

// Look up artifacts by name and version.
assert_eq!(
    artifacts
        .get(&ArtifactKey { name: "artifact1", version: "1.0" })
        .unwrap()
        .data,
    b"data1",
);

For more examples, see the examples and extended examples directories.

Equivalent and Comparable

An important feature of the standard library’s maps is that they allow any borrowed form of the key type to be used for lookups; for example, a HashMap<String, T> type can be looked up with a &str key. This is done through the Borrow trait.

But the Borrow trait is a bit too restrictive for complex keys such as ArtifactKey above, requiring workarounds such as dynamic dispatch. To address this, the crates.io ecosystem has standardized on the Equivalent and Comparable traits as generalizations of Borrow. The map types in this crate require these traits.

For a key type T::Key<'_> and a lookup type L:

• The hash map types require L: Hash + Equivalent<T::Key<'_>>. Also, L must hash in the same way as T::Key<'_>. Typically, this is done by ensuring that enum variants and struct fields are in the same order¹.
• IdOrdMap requires L: Comparable<T::Key<'_>>, which in turn requires Equivalent<T::Key<'_>>. (There’s no need for L to implement Ord or Eq itself.)

Continuing the ArtifactKey example from above, we can perform a lookup using a key of this owned form:

use equivalent::Equivalent;

// This is an owned form of ArtifactKey. The fields are in the same
// order as ArtifactKey's fields, so it hashes the same way.
#[derive(Hash)]
struct OwnedArtifactKey {
    name: String,
    version: String,
}

impl Equivalent<ArtifactKey<'_>> for OwnedArtifactKey {
    fn equivalent(&self, other: &ArtifactKey<'_>) -> bool {
        self.name == other.name && self.version == other.version
    }
}

// Now you can use OwnedArtifactKey to look up the artifact.
let owned_key = OwnedArtifactKey {
    name: "artifact1".to_owned(),
    version: "1.0".to_owned(),
};
assert_eq!(artifacts.get(&owned_key).unwrap().data, b"data1",);

There’s a blanket implementation of Equivalent and Comparable for Borrow, so if your type already implements Borrow, there aren’t any extra steps to take.

Testing

This crate is validated through a combination of:

• Unit tests
• Property-based tests using a naive map as an oracle
• Chaos tests for several kinds of buggy Eq and Ord implementations
• Miri tests for unsafe code

If you see a gap in testing, new tests are welcome. Thank you!

No-std compatibility

Most of this crate is no-std compatible, though alloc is required.

The IdOrdMap type is not currently no-std compatible due to its use of a thread-local. This thread-local is just a way to work around a limitation in std’s BTreeMap API, though. Either a custom B-Tree implementation, or a platform-specific notion of thread locals, would suffice to make IdOrdMap no-std compatible.

Optional features

• serde: Enables serde support for all ID map types. Not enabled by default.
• daft: Enables daft support for all ID map types. Not enabled by default.
• std: Enables std support. Enabled by default.
• default-hasher: Enables the DefaultHashBuilder type. Disable this feature to require a hash builder type parameter to be passed into IdHashMap, BiHashMap, and TriHashMap. Enabled by default.
• allocator-api2: Enables support for custom allocators via the allocator_api2 crate. Both global and scoped/arena allocators (such as bumpalo) are supported. Custom allocators are not currently supported by IdOrdMap.

Related work

• bimap provides a bijective map, but does not have a way to associate arbitrary values with each pair of keys. However, it does support an ordered map type without the need for std.

• multi_index_map provides maps with arbitrary indexes on fields, and is more flexible than this crate. However, it doesn’t expose generic traits for map types, and it requires key types to be Clone. In iddqd, we pick a somewhat different point in the design space, but we think multi_index_map is also great.

• In general, this is similar to relational database records with indexes. For sufficiently complex use cases, consider an embedded database like SQLite, or even a networked database like PostgreSQL. iddqd is a good fit for simple in-memory caches of data stored in these databases.

Minimum supported Rust version (MSRV)

This crate’s MSRV is Rust 1.81. In general we aim for 6 months of Rust compatibility.

What does iddqd mean?

The name iddqd is a reference to a cheat code in the classic video game Doom. It has id in the name, and is short and memorable.

License

This project is available under the terms of either the Apache 2.0 license or the MIT license.

Portions adapted from The Rust Programming Language and used under the MIT and Apache 2.0 licenses. The Rust Programming Language is (c) The Rust Project Contributors.

Portions adapted from hashbrown and used under the MIT and Apache 2.0 licenses. hashbrown is (c) 2016-2025 Amanieu d'Antras and others.

Footnotes

1. We recommend that you test this with e.g. a property-based test: see this example. ↩