indexmap-amortized 1.6.1

A hash table with consistent order and fast iteration. The indexmap is a hash table where the iteration order of the key-value pairs is independent of the hash values of the keys. It has the usual hash table functionality, it preserves insertion order except after removals, and it allows lookup of its elements by either hash table key or numerical index. A corresponding hash set type is also provided. This crate is an ongoing fork of bluss/indexmap that provides amortized resizes.
Documentation

A variant of the indexmap crate that amortizes the cost of resizes.

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.

Amortization

This crate is an ongoing fork of indexmap that amortizes the cost of resizes. If you're unsure if you need this, take a look at the documentation of griddle and atone, which provide the underlying amortization.

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_amortized::{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.48 or later. This version of indexmap requires Rust 1.48+.

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 without std.
    Use methods IndexMap::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 crate twox-hash.
  • Macros [indexmap!] and [indexset!] are unavailable without std.