4 releases
0.2.1 | Sep 25, 2024 |
---|---|
0.2.0 | Aug 27, 2024 |
0.1.1 | May 7, 2024 |
0.1.0 | May 2, 2024 |
#1564 in Data structures
102 downloads per month
24KB
464 lines
MashMap
A flat HashMap that supports multiple entries per key.
This is an adaptation of Rust's standard HashMap
(using hashbrown's RawTable
) to support multiple entries with the same key.
While a common approach is to use a HashMap<K, Vec<V>>
to store the entries corresponding to a key in a Vec
, MashMap
keeps a flat layout and stores all entries in the same table using probing to select the slots.
This approach avoids the memory indirection caused by vector pointers, and reduces memory overhead since it avoids storing the pointer + length + capacity of a vector for each key.
Example usage
use mashmap::MashMap;
let mut map = MashMap::<usize, usize>::new();
map.insert(1, 10);
map.insert(1, 11);
map.insert(1, 12);
map.insert(2, 20);
map.insert(2, 21);
// iterate over the values with key `1` with mutable references and increment them
for val in map.get_mut_iter(&1) {
*val += 1;
}
// collect the values with keys `1` and `2`
// note that the order may differ from the insertion order
let mut values_1: Vec<_> = map.get_iter(&1).copied().collect();
let mut values_2: Vec<_> = map.get_iter(&2).copied().collect();
values_1.sort_unstable();
values_2.sort_unstable();
assert_eq!(values_1, vec![11, 12, 13]);
assert_eq!(values_2, vec![20, 21]);
Acknowledgement
This crate was inspired by the flat-multimap crate which does not have a public repository anymore.
Dependencies
~2MB
~27K SLoC