indexmap

indexmap is a pure-Rust hash table implementation that keeps entries in insertion order while still offering hash-map-speed lookups by key, and additionally lets you look up entries by their numerical position. Internally it pairs a raw hash table of key-value indices with a dense vector of the actual key-value pairs, built on hashbrown (the same table implementation backing Rust’s standard HashMap).

Because iteration runs over the dense, contiguous vector rather than scattered hash-table slots, indexmap is both fast to iterate and predictable to serialize or diff — a property plain HashMap doesn’t offer. It’s one of the most widely depended-upon crates in the Rust ecosystem (over a billion downloads), used anywhere insertion order matters: config/serialization crates, rustc itself, and general application code that wants map semantics without giving up ordering guarantees.

What You Get

• IndexMap<K, V> and IndexSet<T> types with familiar map/set APIs plus indexed access (.get_index(), .get_index_of())
• Insertion-order iteration that stays stable unless you call an order-changing removal method
• A choice between .swap_remove() (fast, breaks order) and .shift_remove() (preserves relative order, O(n))
• Optional integrations via feature flags: serde, rayon (parallel iterators), arbitrary, quickcheck, borsh, and sval
• no_std support for embedded/constrained environments

Common Use Cases

• Configuration or manifest data structures where output order should match the order keys were declared
• Deduplicating a sequence while retaining first-seen order, using IndexSet
• Data pipelines that need both fast key lookup and stable positional/index access into the same collection
• Compiler and tooling internals (e.g. rustc) where deterministic iteration order matters for reproducible output

Under The Hood

Architecture The crate’s core lives in src/map.rs (~1,890 lines) and src/set.rs (~1,480 lines), each wrapping a shared inner structure (src/inner.rs) that pairs a raw hash table of key-value indices with a dense Vec of the actual entries — lookups hash the key to find its index, then index straight into the vector, giving both hash-map-speed access and vector-speed iteration. src/lib.rs (284 lines) wires up feature-gated modules for serde, rayon, arbitrary, borsh, and sval integrations. Tech Stack Built directly on hashbrown for the underlying SIMD-accelerated table (the same crate Rust’s std HashMap uses), with equivalent for flexible key-borrowing lookups; all other integrations (serde, rayon, quickcheck, borsh, sval) are optional via Cargo feature flags, keeping the default dependency footprint minimal. Code Quality The crate carries a substantial tests/ suite (tests.rs, quick.rs for property-based testing via quickcheck, plus equivalent_trait.rs) alongside separate test-nostd and test-serde sub-crates that validate feature combinations in isolation — a level of cross-feature test isolation uncommon in most libraries. API Design The public API deliberately mirrors std::collections::HashMap/HashSet method-for-method so it’s usable as a near drop-in replacement, while layering on indexed-access methods (get_index, get_index_of) and an explicit choice between swap_remove (fast, reorders) and shift_remove (preserves order) so callers make an informed trade-off rather than being surprised by reordering.