sparse-hash-map

Open-addressing hash map and set that stay small at low load factor.

Empty slots in a flat hash table each cost the full size of a bucket. This crate groups buckets into sparse arrays of up to 64 logical indices. Each array stores only its present values, packed together, plus a bitmap marking which indices are occupied. The dense position of an index is the number of occupied bits below it, found with a population count. An empty logical bucket costs about one bit.

The result uses far less memory than a flat table when the table is sparsely filled, and keeps lookup fast.

Install

[dependencies]
sparse-hash-map = "0.1"

Map

use sparse_hash_map::SparseMap;

let mut map: SparseMap<String, i32> = SparseMap::new();
map.insert("a".to_string(), 1);
map.insert("b".to_string(), 2);

assert_eq!(map.get("a"), Some(&1));
assert_eq!(map.len(), 2);

*map.get_mut("a").unwrap() = 10;
assert_eq!(map.get("a"), Some(&10));

for (k, v) in &map {
    println!("{k} = {v}");
}

Iteration yields (&K, &V). The key is never mutable through an iterator, so it cannot change under the map. To mutate a value, use get_mut or iter_mut.

Set

use sparse_hash_map::SparseSet;

let mut set = SparseSet::new();
set.insert(3);
set.insert(7);

assert!(set.contains(&3));
assert_eq!(set.len(), 2);

Growth policies

The default policy keeps the bucket count a power of two and maps a hash with a mask. Two others are available:

• Mod grows by a rational factor and maps with a modulo.
• Prime steps through a table of primes. It spreads values better when the hash function is poor, such as an identity hash of pointers.

SparsePgMap and SparsePgSet are the prime-growth variants.

Serialization

serialize writes a map or set through a Serializer you supply. deserialize_with reads it back. You control the binary layout. The library defines only the order and logical type of each field. Round trips work in two modes: a portable mode that re-hashes on load, and a fast mode that restores slots directly when the hasher and policy match.

License

Licensed under the MIT license.