The Fastest Map with usize Keys and Fixed Capacity

The emap::Map is the fastest possible associative array in Rust, with usize keys. It's by the order of magnitude faster than the standard HashMap<usize, V>. It's also faster than IntMap (we are working on this).

It's essentially Vec<Option<V>> with two extra features:

1. next_key() with O(1) complexity and
2. iterators with O(M) complexity, where M is the number of elements in the array.

You must know the total capacity upfront.

You must account for a memory overhead of 2 * usize per element.

First, add this to Cargo.toml:

[dependencies]
emap = "0.0.13"

Then, use it like a standard hash map... well, almost:

use emap::Map;
let mut m : Map<&str> = Map::with_capacity_init(100); // allocation on heap
m.insert(m.next_key(), "foo");
m.insert(m.next_key(), "bar");
assert_eq!(2, m.len());

If more than 100 keys will be added to the map, it will panic. The map doesn't increase its size automatically, like Vec does (this is one of the reasons why we are faster).

Read the API documentation. The struct emap::Map is designed as closely similar to std::collections::HashMap as possible.

Benchmark

There is a summary of a simple benchmark, where we compared emap::Map with Intmap, changing the total capacity CAP of them (horizontal axis). We applied the same interactions (benchmark.rs) to them both and measured how fast they performed. In the following table, the numbers over 1.0 indicate performance gain of Map against IntMap, while the numbers below 1.0 demonstrate performance loss.

Case	4	16	256	4096
insert_str	6.33	16.46	23.98	24.08
insert_unicode_vals	4.59	5.80	1.02	0.91
insert_u64_scan_keys	7.51	7.03	1.15	0.90
insert_u64_scan_vals	6.31	6.13	0.94	0.76
insert_u64_clear_len	4.52	8.74	9.45	10.67
insert_u64_remove_rev	5.32	12.26	15.57	14.62

Cases

• insert_str: i in 0..CAP { M.insert(i, "Hello, world!") }
• insert_unicode_vals: i in 0..CAP { M.insert(i, "大家好") } for s in M.values() { sum += s.len() }
• insert_u64_scan_keys: i in 0..CAP { M.insert(i, 42) } for k in M.keys() { sum += k }
• insert_u64_scan_vals: i in 0..CAP { M.insert(i, 42) } for s in M.values() { sum += s }
• insert_u64_clear_len: i in 0..CAP { M.insert(i, 42) } M.clear(); M.len();
• insert_u64_remove_rev: i in 0..CAP { M.insert(i, 42) } for i in (0..CAP).rev() { M.remove(i) }

The experiment was performed on 13-05-2025. There were 10000 repetition cycles. The entire benchmark took 1201s.

How to Contribute

First, install Rust and then:

cargo test -vv

If everything goes well, fork repository, make changes, send us a pull request. We will review your changes and apply them to the master branch shortly, provided they don't violate our quality standards. To avoid frustration, before sending us your pull request please run cargo test again. Also, run cargo fmt and cargo clippy.

Also, before you start making changes, run benchmarks:

cargo bench

Then, after the changes you make, run it again. Compare the results. If your changes degrade performance, think twice before submitting a pull request.