9 releases (4 breaking)
0.5.1 | Dec 13, 2024 |
---|---|
0.5.0 | Dec 12, 2024 |
0.4.1 | Dec 10, 2024 |
0.3.0 | Dec 5, 2024 |
0.1.1 | Nov 26, 2024 |
#265 in Data structures
1,118 downloads per month
205KB
4K
SLoC
HashSlab
HashSlab
is a library inspired by IndexMap
, designed to provide a key-value data structure that allows efficient access by both key and index. Unlike IndexMap
, HashSlabMap
guarantees that the index of a key-value pair remains stable and does not change, even when entries are removed.
Key Features
- Stable Indexes: Once a key-value pair is inserted, its
usize
index is preserved throughout the lifetime of the map, regardless of any removals. - Dual Access: Access values either by key or by their associated index.
- Interface:
HashSlabMap
methods aim to closely resemble those ofIndexMap
.
When to Use HashSlab
This crate is ideal for scenarios where:
- You need predictable and stable indexing of entries.
- Entries are frequently added and removed, but their indexes must remain consistent for external references.
Examples
Basic storing and retrieval:
use hashslab::HashSlabMap;
let mut map = HashSlabMap::new();
map.insert('a', "hello");
assert_eq!(map.get(&'a'), Some(&"hello"));
let (idx, _) = map.insert_full('b', "world");
assert_eq!(idx, 1);
assert_eq!(map[&'b'], "world");
map[idx] = "earth";
assert_eq!(map.get_index(0), Some((&'a', &"hello")));
assert_eq!(map[idx], "earth");
HashSlab preserve value's index:
use hashslab::HashSlabMap;
let mut map = HashSlabMap::new();
map.insert('a', "hello");
map.insert('b', "world");
map.insert('c', "!");
map.remove(&'a');
map.remove_index(1);
assert_eq!(map.get_index_of(&'c'), Some(2));
Implementation
HashSlab
is implemented using a HashMap
for keys and a Slab
for values. The HashMap
stores the keys, while each entry in the Slab
contains both the value and the raw hash (u64
) of the corresponding key. This design allows efficient retrieval of the associated key entry in the HashMap
using the precomputed hash.
Performance
In general, HashSlabMap
has comparable performance to HashMap
and IndexMap
. Below is a summary of its performance characteristics:
-
Creation: Empty created
HashSlabMap
performs worse because internally it creates 2 data structuresHashMap
andSlab
, taking twice as long asHashMap
andIndexMap
. With preallocation, performance is similar, as most time is spent on memory allocation. -
Insertion: Performance is identical across all three data structures.
-
Lookup: Searching with
.get()
performs the same asHashMap
andIndexMap
. However,.get_index()
is about 10 times slower thanIndexMap
becauseIndexMap
stores entries in aVec
-like structure, making index lookups as fast as.get()
in aVec
. InHashSlabMap
, the hash value is first located in theSlab
, followed by the corresponding key in theHashMap
. -
Removal: Removing by key is on par with
HashMap
and faster thanIndexMap
.IndexMap
provides two methods:.swap_remove()
- performs similarly toHashSlabMap::remove()
..shift_remove()
- significantly slower, as it shifts elements in theVec
. This method is not included in benchmarks due to being 50-100 times slower.
Comprehensive benchmarks, including detailed graphs and comparisons, can be found here.
No Standard Library Targets
This crate supports being built without std
. This is chosen by disabling the default "std" cargo feature, by adding default-features = false
to your dependency specification.
Creating maps and sets using .new()
and .with_capacity()
is unavailable without std. Use methods .default()
, .with_hasher()
, .with_capacity_and_hasher()
instead. A no-std compatible hasher will be needed as well, for example from the crate twox-hash.
Dependencies
~0.8–1.4MB
~25K SLoC