Ordered map

rusty-js-indexmap is Cruft's insertion-ordered map, the structure behind JavaScript object property order. An ordered vector is the source of truth for iteration, with a hash index added above 16 entries as an accelerator that every lookup re-verifies, so a hash collision can never return the wrong value.

You write const o = {}; o.b = 1; o.a = 2; and Object.keys(o) comes back ["b", "a"]: not sorted, not hash-bucket-shuffled. Insertion order is a language guarantee, so a plain hash map cannot back a JS object, because a HashMap throws iteration order away. The Node-world answer is the indexmap crate, the crates.io map that keeps entries in insertion order. Cruft does not depend on it. It ships its own, rusty-js-indexmap. It inserts and gets fine; the question this page answers is what it traded away, and whether untrusted input is safe in it.

Alpha, do not rely on in production. rusty-js-indexmap (Cruft 0.0.10) replaces the crates.io indexmap crate. It is not externally audited, and has near-zero interop testing. Trust it for correctness before you trust it against a determined adversary.

The ordered Vec is the source of truth

A natural picture of indexmap is "a HashMap plus a Vec of keys for order." That is roughly what crates.io indexmap is. Cruft's is the other way around. The ordered Vec of entries is the source of truth: iteration, enumeration, and ownKeys order are served straight from it. There is no separate authoritative hash table that could ever disagree with the order. This is a deliberately smaller shape: a vector-backed ordered map, with a hash layer added only as an accelerator.

You can watch the order hold. const o = {}; o.b = 1; o.a = 2; o.c = 3 enumerates as ["b","a","c"], and an object built by assigning k30 down to k0 enumerates k30 first and k0 last, even well past the point where the accelerator kicks in.

The hash index is only a hint

If order lives in the Vec, why hash at all? Because a pure linear scan is O(n) per lookup, and a big object would be quadratic to build. So above a threshold of 16 entries the map lazily builds a hash index mapping key-hash to candidate positions. Below 16 it stays a plain scan: no hashing, cache friendly, and most JS objects are small.

The property that matters is this. That index is a hint only. Every lookup that consults it still re-verifies key equality against the candidate entries. A hash collision, or a stale position after a remove, can never return the wrong value: the worst a bad hash can do is send the lookup to a candidate that fails the equality check. Force 64 keys that all hash identically, and get, miss, and overwrite still resolve correctly.

Correctness safety and performance safety differ

Separate the two. Because equality is always re-verified, a hostile key set can never corrupt a result. But it can make every colliding lookup fall back to scanning a long candidate list, which is O(n) per access and O(n^2) to fill an object from attacker-chosen keys. This map backs JS object property storage and the mapped-arguments parameter map, and adversarial keys are reachable from untrusted input: JSON.parse of a hostile body, a request turned into an object. That is the classic HashDoS surface.

The accelerator hashes with Rust's DefaultHasher (SipHash). An earlier version used fixed-seed FNV-1a, which handed an attacker a deterministic way to precompute keys that all land in one bucket. SipHash removes that trivial collision recipe while keeping the verify-on-lookup semantics unchanged, and the forced-collision behavior above still holds. For this crate the hasher choice is the HashDoS posture, and the easy FNV recipe is closed.

What it does not do, and where the original wins

  • No per-process random seed. DefaultHasher::new() uses fixed internal keys, not a randomized seed like RandomState. So the easy deterministic recipe is gone, yet the hash is not per-process randomized the way a std::collections::HashMap is. A determined attacker who precomputes against the fixed SipHash keys could still find collisions, so worst-case performance under that adversary is unmeasured. Read "trivial FNV recipe removed, correctness collision-proof" as solid; read "fully HashDoS-hardened against a precomputing attacker" as not yet true.
  • Not a feature-complete indexmap. It implements only what Cruft consumes: insert, get/get_mut, contains_key, entry, shift_remove, ordered iterators (keys/values/iter), get_index, retain, FromIterator, and Index. The crates.io original carries far more (swap_remove, sort_*, MutableKeys, rayon, serde, a randomized RandomState by default) plus years of production and fuzzing. Prefer the original's breadth and battle-testing when you are outside Cruft.
  • Memory safety. The crate contains no unsafe. It is a safe reimplementation over Vec and std HashMap, so the memory-safety story is Rust's, not a pointer scheme of its own.

Limitations

The narrow claim holds: order is authoritative in the Vec, and every lookup re-verifies key equality, so no hash behavior can return a wrong or aliased entry. Removes keep the index correct without rehashing, and shrinking below 16 drops the index cleanly. What remains unproven for a shipping runtime: the hasher is SipHash but not per-process randomized, so worst-case performance under a determined precomputing adversary is unmeasured here; there is no fuzzing or interop corpus behind it; and the API is a subset. Correctness is the strength; adversarial-performance hardening and breadth are the gaps.