Expand description
OrderedHashMap is an insertion‑ordered hash map that provides O(1) insertion, lookup, update and removal while preserving the order in which keys were first inserted.
A new key inserted with insert is appended to the logical end of the
sequence. Updating an
existing key only changes its value; its relative position does not move. Removing a key unlinks
it in O(1) time. If the same key is inserted again later, it is treated as a fresh insertion and
appears at the end of the iteration order.
Internally the structure keeps a HashMap<K, Index> which maps each key to an index inside a
doubly‑linked list IndexList<(K, V)>. The list stores the actual
(K, V) pairs plus linkage (next / prev indices) inside a single slab / arena structure. Each
node is just a slot within that slab; inserting a new element only grows the slab
vector, so there is not a separate heap allocation per entry. Removal uses the stored index to
unlink a node in O(1) without any traversal and without shifting other live elements. This
avoids both the per-node allocation overhead of a classic pointer‑based linked list and the O(n)
element movement costs of a simple vector when deleting from the middle.
The primary iteration methods (iter, keys,
and values) yield items in insertion order.
Operations insert, get, get_mut, contains_key, and remove are all O(1) on average.
The API is intentionally similar to indexmap::IndexMap, but this implementation relies on an
IndexList rather than a simple Vec so that removals don’t cause O(n) shifts.
Re-exports§
pub use crate::entry::Entry;pub use crate::entry::OccupiedEntry;pub use crate::entry::VacantEntry;