Enum SmallMap 

pub enum SmallMap<const N: usize, K, V, SH = RandomState, SI = RandomState, const LINEAR_THRESHOLD: usize = DEFAULT_LINEAR_THRESHOLD> {
    Heap(HashMap<K, V, SH>),
    Inline(Inline<N, K, V, SH, SI, LINEAR_THRESHOLD>),
}

A hybrid map that stores data inline when small, and spills to heap when it grows.

Type Parameters

• N: Maximum number of elements to store inline (must be > 0). When the map exceeds this size, it automatically spills to a heap-allocated HashMap.

• K: Key type. Must implement Eq + Hash for most operations.

• V: Value type.

• SH: Hasher for heap storage. Default: RandomState. This hasher is used when the map spills to heap. Note: The standard library’s RandomState provides HashDoS resistance but is not the fastest option. Consider your security vs performance requirements - for non-adversarial workloads, faster alternatives like rapidhash or fxhash can improve performance significantly (though they are not cryptographically secure).

• SI: Hasher for inline storage. Default: DefaultInlineHasher (rapidhash if available, otherwise fxhash, ahash, or RandomState based on features). This hasher is used for SIMD-accelerated lookups in inline mode. Since inline storage only handles a small number of elements, HashDoS resistance is generally not a concern here - performance is the priority. We recommend using the default value and enabling the rapidhash or fxhash feature for best performance.

• LINEAR_THRESHOLD: Threshold for switching between linear and SIMD search. Default: DEFAULT_LINEAR_THRESHOLD (equal to SIMD group width, typically 16 on SSE2). When N < LINEAR_THRESHOLD or len < LINEAR_THRESHOLD, linear search is used; otherwise, SIMD-accelerated hash search is used.

  How to choose this value: The optimal threshold depends on the tradeoff between hash computation cost and key comparison cost:

  • Linear search: len key comparisons (direct equality checks).
  • SIMD search: 1 hash computation + len / GROUP_WIDTH SIMD operations + a few key comparisons.

  If key comparison is cheap (e.g., integers, short strings), a higher threshold favors linear search which avoids hash overhead. If key comparison is expensive (e.g., long strings, complex types), a lower threshold makes SIMD search more attractive.

  Recommendation: Values above 16 are generally not recommended. The default value works well for most use cases. Set to 0 to disable linear search entirely.

Examples

use small_map::SmallMap;

// Basic usage with defaults
let mut map: SmallMap<8, &str, i32> = SmallMap::new();
map.insert("a", 1);

// Custom hasher
use std::collections::hash_map::RandomState;
let mut map: SmallMap<8, &str, i32, RandomState> = SmallMap::new();

// Custom linear threshold (force SIMD search even for small maps)
let mut map: SmallMap<8, &str, i32, RandomState, RandomState, 4> = SmallMap::new();

Variants

Heap(HashMap<K, V, SH>)

Heap-allocated storage using hashbrown::HashMap.

Inline(Inline<N, K, V, SH, SI, LINEAR_THRESHOLD>)

Inline storage with SIMD-accelerated lookups.

Implementations

impl<const N: usize, K, V, SH: Default, SI: Default, const LINEAR_THRESHOLD: usize> SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

pub fn new() -> Self

Creates an empty SmallMap.

pub fn with_capacity(capacity: usize) -> Self

Creates an empty SmallMap with the specified capacity.

The hash map will be able to hold at least capacity elements without reallocating. If capacity is smaller than N, the hash map will not allocate.

impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

pub fn with_hasher(hash_builder: SH) -> Self

where SI: Default,

Creates an empty SmallMap which will use the given hash builder to hash keys. It will be allocated with the given allocator.

The hash map is initially created with a capacity of N, so it will not allocate until it its size bigger than inline size N.

Examples

use std::hash::{BuildHasherDefault, DefaultHasher};

use small_map::SmallMap;

let s = BuildHasherDefault::<DefaultHasher>::default();
let mut map = SmallMap::<8, _, _, _>::with_hasher(s);
map.insert(1, 2);

pub const fn with_hashers(heap_hasher: SH, inline_hasher: SI) -> Self

Creates an empty SmallMap which will use the given hash builders to hash keys. It will be allocated with the given allocator.

Examples

use std::collections::hash_map::RandomState;

use small_map::SmallMap;
let heap_hasher = RandomState::new();
let inline_hasher = RandomState::new();
let mut map = SmallMap::<8, _, _, _, _>::with_hashers(heap_hasher, inline_hasher);
map.insert(1, 2);

pub fn with_capacity_and_hasher(capacity: usize, heap_hasher: SH) -> Self

where SI: Default,

Creates an empty SmallMap with the specified capacity, using heap_hasher to hash the keys.

The hash map will be able to hold at least capacity elements without reallocating. If capacity is smaller than or eq to N, the hash map will not allocate.

pub fn with_capacity_and_hashers( capacity: usize, heap_hasher: SH, inline_hasher: SI, ) -> Self

Creates an empty SmallMap with the specified capacity, using heap_hasher to hash the keys for heap storage, and inline_hasher for inline storage.

Examples

use std::collections::hash_map::RandomState;

use small_map::SmallMap;
let heap_hasher = RandomState::new();
let inline_hasher = RandomState::new();
let mut map =
    SmallMap::<8, _, _, _, _>::with_capacity_and_hashers(16, heap_hasher, inline_hasher);
map.insert(1, 2);

pub fn is_inline(&self) -> bool

What branch it is now.

pub fn capacity(&self) -> usize

Returns the number of elements the map can hold without reallocating.

This number is a lower bound; the SmallMap<N, K, V> might be able to hold more, but is guaranteed to be able to hold at least this many.

Examples

use small_map::SmallMap;

let map: SmallMap<8, i32, i32> = SmallMap::with_capacity(100);
assert_eq!(map.len(), 0);
assert!(map.capacity() >= 100);

let map: SmallMap<8, i32, i32> = SmallMap::with_capacity(2);
assert_eq!(map.len(), 0);
assert!(map.capacity() >= 8);

impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

where K: Eq + Hash, SH: BuildHasher, SI: BuildHasher,

pub fn get<Q>(&self, k: &Q) -> Option<&V>

where Q: ?Sized + Hash + Equivalent<K>,

Returns a reference to the value corresponding to the key.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, &str> = SmallMap::new();
map.insert(1, "a");
assert_eq!(map.get(&1), Some(&"a"));
assert_eq!(map.get(&2), None);

pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>

where Q: ?Sized + Hash + Equivalent<K>,

Returns a mutable reference to the value corresponding to the key.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, i32> = SmallMap::new();
map.insert(1, 10);
if let Some(v) = map.get_mut(&1) {
    *v = 20;
}
assert_eq!(map.get(&1), Some(&20));

pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>

where Q: ?Sized + Hash + Equivalent<K>,

Returns the key-value pair corresponding to the supplied key.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, &str> = SmallMap::new();
map.insert(1, "a");
assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
assert_eq!(map.get_key_value(&2), None);

pub fn contains_key<Q>(&self, k: &Q) -> bool

where Q: ?Sized + Hash + Equivalent<K>,

Returns true if the map contains a value for the specified key.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, &str> = SmallMap::new();
map.insert(1, "a");
assert!(map.contains_key(&1));
assert!(!map.contains_key(&2));

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Inserts a key-value pair into the map.

If the map did not have this key present, None is returned. If the map did have this key present, the value is updated, and the old value is returned.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, &str> = SmallMap::new();
assert_eq!(map.insert(1, "a"), None);
assert_eq!(map.insert(1, "b"), Some("a"));
assert_eq!(map.get(&1), Some(&"b"));

pub unsafe fn insert_unique_unchecked( &mut self, key: K, value: V, ) -> (&K, &mut V)

Inserts a key-value pair into the map without checking if the key already exists.

Returns a reference to the key and a mutable reference to the value.

Safety

The caller must ensure that the key does not already exist in the map. Inserting a duplicate key will result in undefined behavior (e.g., memory leaks, incorrect iteration, or other inconsistencies).

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, &str> = SmallMap::new();
// SAFETY: We know the key doesn't exist because the map is empty.
unsafe { map.insert_unique_unchecked(1, "a") };
assert_eq!(map.get(&1), Some(&"a"));

pub fn remove<Q>(&mut self, k: &Q) -> Option<V>

where Q: ?Sized + Hash + Equivalent<K>,

Removes a key from the map, returning the value at the key if the key was previously in the map.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, &str> = SmallMap::new();
map.insert(1, "a");
assert_eq!(map.remove(&1), Some("a"));
assert_eq!(map.remove(&1), None);

pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>

where Q: ?Sized + Hash + Equivalent<K>,

Removes a key from the map, returning the stored key and value if the key was previously in the map.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, &str> = SmallMap::new();
map.insert(1, "a");
assert_eq!(map.remove_entry(&1), Some((1, "a")));
assert_eq!(map.remove_entry(&1), None);

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&K, &mut V) -> bool,

Retains only the elements specified by the predicate.

In other words, remove all pairs (k, v) for which f(&k, &mut v) returns false.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, i32> = SmallMap::new();
for i in 0..8 {
    map.insert(i, i * 10);
}
map.retain(|&k, _| k % 2 == 0);
assert_eq!(map.len(), 4);

impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

pub fn clear(&mut self)

Clears the map.

This method clears the map and keeps the allocated memory for reuse.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, ()> = SmallMap::new();
for i in 0..16 {
    map.insert(i, ());
}
assert!(!map.is_inline());
assert_eq!(map.len(), 16);

map.clear();
assert!(!map.is_inline());
assert_eq!(map.len(), 0);

impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

pub fn len(&self) -> usize

Returns the number of elements in the map.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, i32> = SmallMap::new();
assert_eq!(map.len(), 0);
map.insert(1, 10);
assert_eq!(map.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, i32, i32> = SmallMap::new();
assert!(map.is_empty());
map.insert(1, 10);
assert!(!map.is_empty());

pub fn iter(&self) -> Iter<'_, N, K, V>

An iterator visiting all key-value pairs in arbitrary order.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, &str, i32> = SmallMap::new();
map.insert("a", 1);
map.insert("b", 2);

for (key, val) in map.iter() {
    println!("key: {key} val: {val}");
}

pub fn keys(&self) -> Keys<'_, N, K, V>

An iterator visiting all keys in arbitrary order.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, &str, i32> = SmallMap::new();
map.insert("a", 1);
map.insert("b", 2);

for key in map.keys() {
    println!("{key}");
}

pub fn values(&self) -> Values<'_, N, K, V>

An iterator visiting all values in arbitrary order.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, &str, i32> = SmallMap::new();
map.insert("a", 1);
map.insert("b", 2);

for val in map.values() {
    println!("{val}");
}

pub fn into_keys(self) -> IntoKeys<N, K, V>

Creates a consuming iterator visiting all the keys in arbitrary order.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, &str, i32> = SmallMap::new();
map.insert("a", 1);
map.insert("b", 2);

let keys: Vec<_> = map.into_keys().collect();

pub fn into_values(self) -> IntoValues<N, K, V>

Creates a consuming iterator visiting all the values in arbitrary order.

Examples

use small_map::SmallMap;

let mut map: SmallMap<8, &str, i32> = SmallMap::new();
map.insert("a", 1);
map.insert("b", 2);

let values: Vec<_> = map.into_values().collect();

Trait Implementations

impl<const N: usize, K: Clone, V: Clone, SH: Clone, SI: Clone, const LINEAR_THRESHOLD: usize> Clone for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

fn clone(&self) -> SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> Debug for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

where K: Debug, V: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<const N: usize, K, V, SH: Default, SI: Default, const LINEAR_THRESHOLD: usize> Default for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

fn default() -> Self

Creates an empty SmallMap<N, K, V, SH, SI>, with the Default value for the hasher.

Examples

use std::collections::hash_map::RandomState;

use small_map::SmallMap;

// You can specify all types of SmallMap, including N and hasher.
// Created map is empty and don't allocate memory
let map: SmallMap<8, u32, String> = SmallMap::default();
assert_eq!(map.capacity(), 8);
let map: SmallMap<8, u32, String, RandomState> = SmallMap::default();
assert_eq!(map.capacity(), 8);

impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> Extend<(K, V)> for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

where K: Eq + Hash, SH: BuildHasher, SI: BuildHasher,

fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> FromIterator<(K, V)> for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

where K: Eq + Hash, SH: BuildHasher + Default, SI: BuildHasher + Default,

fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self

Creates a value from an iterator.

impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize, Q> Index<&Q> for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

where K: Eq + Hash, Q: ?Sized + Hash + Equivalent<K>, SH: BuildHasher, SI: BuildHasher,

fn index(&self, key: &Q) -> &V

Returns a reference to the value corresponding to the supplied key.

Panics

Panics if the key is not present in the SmallMap.

type Output = V

The returned type after indexing.

impl<'a, const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> IntoIterator for &'a SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

fn into_iter(self) -> Iter<'a, N, K, V>

Creates an iterator over the entries of a HashMap in arbitrary order. The iterator element type is (&'a K, &'a V).

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, N, K, V>

Which kind of iterator are we turning this into?

impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> IntoIterator for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

fn into_iter(self) -> IntoIter<N, K, V>

Creates a consuming iterator, that is, one that moves each key-value pair out of the map in arbitrary order. The map cannot be used after calling this.

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<N, K, V>

Which kind of iterator are we turning this into?

impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> PartialEq for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

where K: Eq + Hash, V: PartialEq, SH: BuildHasher, SI: BuildHasher,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> Eq for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>

where K: Eq + Hash, V: Eq, SH: BuildHasher, SI: BuildHasher,