#slab #vec #map #allocator #key-value

slabmap

HashMap-like collection that automatically determines the key

4 releases

0.2.1 May 23, 2024
0.2.0 Aug 19, 2023
0.1.1 Jul 1, 2020
0.1.0 Jul 1, 2020

#281 in Data structures

Download history 56/week @ 2024-02-13 65/week @ 2024-02-20 67/week @ 2024-02-27 53/week @ 2024-03-05 53/week @ 2024-03-12 42/week @ 2024-03-19 49/week @ 2024-03-26 90/week @ 2024-04-02 35/week @ 2024-04-09 40/week @ 2024-04-16 56/week @ 2024-04-23 43/week @ 2024-04-30 45/week @ 2024-05-07 40/week @ 2024-05-14 225/week @ 2024-05-21 90/week @ 2024-05-28

407 downloads per month
Used in 4 crates (3 directly)

MIT/Apache

35KB
741 lines

slabmap

Crates.io Docs.rs Actions Status

This crate provides the type SlabMap. SlabMap is HashMap-like collection that automatically determines the key.

Install

Add this to your Cargo.toml:

[dependencies]
slabmap = "0.2.0"

Examples

use slabmap::SlabMap;

let mut s = SlabMap::new();
let key_a = s.insert("aaa");
let key_b = s.insert("bbb");

assert_eq!(s[key_a], "aaa");
assert_eq!(s[key_b], "bbb");

for (key, value) in &s {
    println!("{} -> {}", key, value);
}

assert_eq!(s.remove(key_a), Some("aaa"));
assert_eq!(s.remove(key_a), None);

The difference between SlabMap and HashMap

  • SlabMap can only use usize as a key.
  • The key of SlabMap is determined automatically.
  • SlabMap runs faster than HashMap.

The difference between SlabMap and Slab

Carl Lerche's slab crate provides a slab implementation with a similar API.

For both Slab and SlabMap, after adding many elements to the collection, removing many element will reduce iterate performance.

However, unlike Slab, SlabMap can improve iterate performance by calling SlabMap::optimize().

Performance

The following chart shows the difference in performance between BTreeMap, HashMap, Slab(version 0.4.2), SlabMap(version 0.1.0) and, Vec,

Insert

insert performance

Remove random elements

remove random elements performance

Random access

random access performance

Sequential access

sequential access performance

Sequential access after removing elements from a 10,000-element collection

  • x-axis : number of remaining elements
  • y-axis : average time (lower is better)

Sequential access after remove many elements performance

License

This project is dual licensed under Apache-2.0/MIT. See the two LICENSE-* files for details.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Dependencies

~0.4–0.9MB
~20K SLoC