IndexMap
is a hash table where the iteration order of the key-value
pairs is independent of the hash values of the keys.
IndexSet
is a corresponding hash set using the same implementation and
with similar properties.
Feature Highlights
IndexMap
and IndexSet
are drop-in compatible with the std HashMap
and HashSet
, but they also have some features of note:
- The ordering semantics (see their documentation for details)
- Sorting methods and the [
.pop()
][IndexMap::pop] methods. - The [
Equivalent
] trait, which offers more flexible equality definitions between borrowed and owned versions of keys. - The [
MutableKeys
][map::MutableKeys] trait, which gives opt-in mutable access to hash map keys.
Alternate Hashers
IndexMap
and IndexSet
have a default hasher type S = RandomState
,
just like the standard HashMap
and HashSet
, which is resistant to
HashDoS attacks but not the most performant. Type aliases can make it easier
to use alternate hashers:
use fnv::FnvBuildHasher;
use fxhash::FxBuildHasher;
use indexmap::{IndexMap, IndexSet};
type FnvIndexMap<K, V> = IndexMap<K, V, FnvBuildHasher>;
type FnvIndexSet<T> = IndexSet<T, FnvBuildHasher>;
type FxIndexMap<K, V> = IndexMap<K, V, FxBuildHasher>;
type FxIndexSet<T> = IndexSet<T, FxBuildHasher>;
let std: IndexSet<i32> = (0..100).collect();
let fnv: FnvIndexSet<i32> = (0..100).collect();
let fx: FxIndexSet<i32> = (0..100).collect();
assert_eq!(std, fnv);
assert_eq!(std, fx);
Rust Version
This version of indexmap requires Rust 1.36 or later.
The indexmap 1.x release series will use a carefully considered version upgrade policy, where in a later 1.x version, we will raise the minimum required Rust version.
No Standard Library Targets
This crate supports being built without std
, requiring
alloc
instead. This is enabled automatically when it is detected that
std
is not available. There is no crate feature to enable/disable to
trigger this. It can be tested by building for a std-less target.
- Creating maps and sets using [
new
][IndexMap::new] and [with_capacity
][IndexMap::with_capacity] is unavailable withoutstd
.
Use methodsIndexMap::default
, [with_hasher
][IndexMap::with_hasher], [with_capacity_and_hasher
][IndexMap::with_capacity_and_hasher] instead. A no-std compatible hasher will be needed as well, for example from the cratetwox-hash
. - Macros [
indexmap!
] and [indexset!
] are unavailable withoutstd
.