| 1 |
# indexmap |
| 2 |
|
| 3 |
[](https://github.com/bluss/indexmap/actions) |
| 4 |
[](https://crates.io/crates/indexmap) |
| 5 |
[](https://docs.rs/indexmap) |
| 6 |
[](https://img.shields.io/badge/rust-1.56%2B-orange.svg) |
| 7 |
|
| 8 |
A pure-Rust hash table which preserves (in a limited sense) insertion order. |
| 9 |
|
| 10 |
This crate implements compact map and set data-structures, |
| 11 |
where the iteration order of the keys is independent from their hash or |
| 12 |
value. It preserves insertion order (except after removals), and it |
| 13 |
allows lookup of entries by either hash table key or numerical index. |
| 14 |
|
| 15 |
Note: this crate was originally released under the name `ordermap`, |
| 16 |
but it was renamed to `indexmap` to better reflect its features. |
| 17 |
|
| 18 |
# Background |
| 19 |
|
| 20 |
This was inspired by Python 3.6's new dict implementation (which remembers |
| 21 |
the insertion order and is fast to iterate, and is compact in memory). |
| 22 |
|
| 23 |
Some of those features were translated to Rust, and some were not. The result |
| 24 |
was indexmap, a hash table that has following properties: |
| 25 |
|
| 26 |
- Order is **independent of hash function** and hash values of keys. |
| 27 |
- Fast to iterate. |
| 28 |
- Indexed in compact space. |
| 29 |
- Preserves insertion order **as long** as you don't call `.remove()`. |
| 30 |
- Uses hashbrown for the inner table, just like Rust's libstd `HashMap` does. |
| 31 |
|
| 32 |
## Performance |
| 33 |
|
| 34 |
`IndexMap` derives a couple of performance facts directly from how it is constructed, |
| 35 |
which is roughly: |
| 36 |
|
| 37 |
> A raw hash table of key-value indices, and a vector of key-value pairs. |
| 38 |
|
| 39 |
- Iteration is very fast since it is on the dense key-values. |
| 40 |
- Removal is fast since it moves memory areas only in the table, |
| 41 |
and uses a single swap in the vector. |
| 42 |
- Lookup is fast-ish because the initial 7-bit hash lookup uses SIMD, and indices are |
| 43 |
densely stored. Lookup also is slow-ish since the actual key-value pairs are stored |
| 44 |
separately. (Visible when cpu caches size is limiting.) |
| 45 |
|
| 46 |
- In practice, `IndexMap` has been tested out as the hashmap in rustc in [PR45282] and |
| 47 |
the performance was roughly on par across the whole workload. |
| 48 |
- If you want the properties of `IndexMap`, or its strongest performance points |
| 49 |
fits your workload, it might be the best hash table implementation. |
| 50 |
|
| 51 |
[PR45282]: https://github.com/rust-lang/rust/pull/45282 |
| 52 |
|
| 53 |
# Recent Changes |
| 54 |
|
| 55 |
See [RELEASES.md](https://github.com/bluss/indexmap/blob/master/RELEASES.md). |