Crate sparse_hash_map 

Memory-efficient sparse hash map and set.

SparseMap and SparseSet are open-addressing containers whose main goal is low memory use at low load factor. They keep reasonable lookup speed. They fit the same niche as space-efficient sparse hash tables, not dense Swiss tables.

How the memory trick works

A flat table pays the full size of a bucket for every empty slot. Here buckets are grouped into sparse arrays of up to 64 logical indices each. An 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.

Example

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));

Iterator value semantics

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

Growth policies

The default policy keeps the bucket count a power of two and maps a hash with a mask. Mod grows by a rational factor. Prime steps through a table of primes and spreads values better when the hash is poor.

Re-exports

pub use crate::growth_policy::GrowthPolicy;

pub use crate::growth_policy::LengthError;

pub use crate::growth_policy::Mod;

pub use crate::growth_policy::PowerOfTwo;

pub use crate::growth_policy::Prime;

pub use crate::hasher::EqKey;

pub use crate::hasher::FnHash;

pub use crate::hasher::HashKey;

pub use crate::hasher::StdEq;

pub use crate::hasher::StdHash;

pub use crate::serialize::Deserialize;

pub use crate::serialize::DeserializeError;

pub use crate::serialize::Deserializer;

pub use crate::serialize::Serialize;

pub use crate::serialize::Serializer;

pub use crate::serialize::SERIALIZATION_PROTOCOL_VERSION;

pub use crate::sparsity::High;

pub use crate::sparsity::Low;

pub use crate::sparsity::Medium;

pub use crate::sparsity::Sparsity;

Modules

growth_policy

Growth policies that map a hash to a bucket and decide the next table size.

hasher

Hashing and equality traits for keys.

serialize

Serialization protocol for maps and sets.

sparsity

Sparsity levels controlling per-array capacity slack.

Structs

SparseMap

A hash map that trades a little insert speed for low memory use.

SparseSet

A hash set that trades a little insert speed for low memory use.

Constants

BITMAP_NB_BITS

Number of logical buckets per sparse array.

Type Aliases

SparsePgMap

A prime-growth map. Better with poor hash functions.

SparsePgSet

A prime-growth set. Better with poor hash functions.