sparse_hash_map/
lib.rs

1//! Memory-efficient sparse hash map and set.
2//!
3//! [`SparseMap`] and [`SparseSet`] are open-addressing containers whose main
4//! goal is low memory use at low load factor. They keep reasonable lookup speed.
5//! They fit the same niche as space-efficient sparse hash tables, not dense
6//! Swiss tables.
7//!
8//! # How the memory trick works
9//!
10//! A flat table pays the full size of a bucket for every empty slot. Here
11//! buckets are grouped into sparse arrays of up to 64 logical indices each. An
12//! array stores only its present values, packed together, plus a bitmap marking
13//! which indices are occupied. The dense position of an index is the number of
14//! occupied bits below it, found with a population count. An empty logical
15//! bucket costs about one bit.
16//!
17//! # Example
18//!
19//! ```
20//! use sparse_hash_map::SparseMap;
21//!
22//! let mut map: SparseMap<String, i32> = SparseMap::new();
23//! map.insert("a".to_string(), 1);
24//! map.insert("b".to_string(), 2);
25//!
26//! assert_eq!(map.get("a"), Some(&1));
27//! assert_eq!(map.len(), 2);
28//!
29//! *map.get_mut("a").unwrap() = 10;
30//! assert_eq!(map.get("a"), Some(&10));
31//! ```
32//!
33//! # Iterator value semantics
34//!
35//! Map iteration yields `(&K, &V)`. The key is never mutable through an
36//! iterator, so it cannot change under the map. To mutate a value, use
37//! [`SparseMap::get_mut`] or [`SparseMap::iter_mut`].
38//!
39//! # Growth policies
40//!
41//! The default policy keeps the bucket count a power of two and maps a hash with
42//! a mask. [`Mod`] grows by a rational factor. [`Prime`] steps through a table
43//! of primes and spreads values better when the hash is poor.
44
45#![forbid(unsafe_code)]
46#![warn(missing_docs)]
47
48pub mod growth_policy;
49pub mod hasher;
50mod map;
51mod popcount;
52pub mod serialize;
53mod set;
54mod sparse_array;
55mod sparse_hash;
56pub mod sparsity;
57mod util;
58
59pub use crate::growth_policy::{GrowthPolicy, LengthError, Mod, PowerOfTwo, Prime};
60pub use crate::hasher::{EqKey, FnHash, HashKey, StdEq, StdHash};
61pub use crate::map::SparseMap;
62pub use crate::serialize::{
63    Deserialize, DeserializeError, Deserializer, Serialize, Serializer,
64    SERIALIZATION_PROTOCOL_VERSION,
65};
66pub use crate::set::SparseSet;
67pub use crate::sparse_array::BITMAP_NB_BITS;
68pub use crate::sparsity::{High, Low, Medium, Sparsity};
69
70/// A prime-growth map. Better with poor hash functions.
71pub type SparsePgMap<K, V, H = StdHash, E = StdEq, S = Medium> = SparseMap<K, V, H, E, Prime, S>;
72
73/// A prime-growth set. Better with poor hash functions.
74pub type SparsePgSet<K, H = StdHash, E = StdEq, S = Medium> = SparseSet<K, H, E, Prime, S>;
75
76use core::hash::Hash;
77
78impl<K, V> FromIterator<(K, V)> for SparseMap<K, V>
79where
80    K: Hash + Eq,
81{
82    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
83        let mut map = SparseMap::new();
84        map.extend(iter);
85        map
86    }
87}
88
89impl<K, V, const N: usize> From<[(K, V); N]> for SparseMap<K, V>
90where
91    K: Hash + Eq,
92{
93    fn from(array: [(K, V); N]) -> Self {
94        array.into_iter().collect()
95    }
96}
97
98impl<K> FromIterator<K> for SparseSet<K>
99where
100    K: Hash + Eq,
101{
102    fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self {
103        let mut set = SparseSet::new();
104        set.extend(iter);
105        set
106    }
107}
108
109impl<K, const N: usize> From<[K; N]> for SparseSet<K>
110where
111    K: Hash + Eq,
112{
113    fn from(array: [K; N]) -> Self {
114        array.into_iter().collect()
115    }
116}
sparse_hash_map/lib.rs

sparse_hash_map/
lib.rs
