Struct MuleMap

pub struct MuleMap<K, V, S, const TABLE_MIN_VALUE: i128 = 0, const TABLE_SIZE: usize = { u8::MAX as usize }> { /* private fields */ }

MuleMap is a hybrid between a HashMap and a lookup table. It improves performance for frequently accessed keys in a known range. If a key (integer) is in the user specified range, then its value will be stored directly in the lookup table.

Differences between HashMap and MuleMap

• The key, K, must be an integer type. - The key is directly mapped to the index in the lookup, so it must be an integer.
• The key, K, is passed by value - Because it is a primitive integer type.
• The hash builder, S, does not have a default - You must specify your hash builder. The assumption being that if you need better performance you will likely also want to use a custom hash function.
• TABLE_MIN_VALUE and TABLE_SIZE - If a key is between TABLE_MIN_VALUE and TABLE_MIN_VALUE + TABLE_SIZE, then the value will be stored directly in the lookup table, instead of using the HashMap. NOTE: Currently the type of a const generic can’t depend on another generic type argument, so TABLE_MIN_VALUE can’t use the same type as the key. Because of this, We are using i128, but that means we can’t represent values near u128::MAX. Hopefully having frequent keys near u128::MAX is extremely rare.

Performance

Benchmarks (using random selection) start to show speed improvements when about 50% of the key accesses are in the lookup table. Performance is almost identical to HashMap with less than 50%.

Example

use mule_map::MuleMap;
use std::num::NonZero;
type Hash = fnv_rs::FnvBuildHasher;  // Use whatever hash function you prefer

// Using Entry API
let mut mule_map = MuleMap::<u32, usize, Hash>::new();
assert_eq!(mule_map.get(5), None);
let entry = mule_map.entry(5);
entry.or_insert(10);
assert_eq!(mule_map.get(5), Some(&10));

// Using NonZero and bump
let mut mule_map_non_zero = MuleMap::<u32, NonZero<i32>, Hash>::default();

mule_map_non_zero.bump_non_zero(10);
mule_map_non_zero.bump_non_zero(10);
mule_map_non_zero.bump_non_zero(999_999);
mule_map_non_zero.bump_non_zero(999_999);

Implementations

impl<K, V, S, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize> MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>

where K: PrimInt + Eq + Hash + KeyIndex<K, TABLE_MIN_VALUE> + TryFrom<i128> + 'static, S: Default + BuildHasher, V: PartialEq + Copy, i128: AsPrimitive<K>, usize: AsPrimitive<K>, <K as TryFrom<i128>>::Error: Debug,

pub fn new() -> Self

Creates an empty MuleMap.

Example

let mule_map = mule_map::MuleMap::<u32, usize, fnv_rs::FnvBuildHasher>::new();

See: MuleMap::with_capacity_and_hasher

Analogous to HashMap::new

pub fn with_capacity(capacity: usize) -> Self

Creates an empty MuleMap with at least the provided capacity.

Example

let mule_map = mule_map::MuleMap::<u32, usize, fnv_rs::FnvBuildHasher>::with_capacity(100);

See: MuleMap::with_capacity_and_hasher

Analogous to HashMap::with_capacity

pub fn with_hasher(hash_builder: S) -> Self

Creates an empty MuleMap using hash_builder.

Example

type Hash = fnv_rs::FnvBuildHasher;
let mule_map = mule_map::MuleMap::<u32, usize, fnv_rs::FnvBuildHasher>::with_hasher(Hash::default());

See: MuleMap::with_capacity_and_hasher

Analogous to HashMap::with_hasher

pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self

Creates an empty MuleMap with at least the provided capacity and using hash_builder.

Example

type Hash = fnv_rs::FnvBuildHasher;
let mule_map = mule_map::MuleMap::<u32, usize, fnv_rs::FnvBuildHasher>::with_capacity_and_hasher(100, Hash::default());

Panics

Panics if

• TABLE_MIN_VALUE or TABLE_MIN_VALUE + TABLE_SIZE doesn’t fit into key type, K.

Analogous to HashMap::with_capacity_and_hasher

pub fn capacity(&self) -> usize

Returns capacity of the underlying hash map.

See HashMap::capacity

pub fn get(&self, key: K) -> Option<&V>

Returns a reference to the value corresponding to the key.

Analogous to HashMap::get

pub fn contains_key(&self, key: K) -> bool

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

Analogous to HashMap::contains_key

pub fn modify_or_insert<F>(&mut self, key: K, f: F, default: V)

where F: FnOnce(&mut V),

Modify the values at location key by calling f on its value. If no value present, create a new value set to default.

pub fn bump_int(&mut self, key: K)

where V: AddAssign<V> + One + Zero,

Adds 1 to the value stored at location key. If the value is not present, the value 1 will be set at that location.

NOTE: This method can only be called with values that implement AddAssign, like primitives. For NonZero<T> values use [bump_non_zero] - It uses the niche optimization for better performance.

Panics

May panics if adding 1 results in overflow.

pub fn bump_non_zero(&mut self, key: K)

where V: NonZeroInt + PodInOption, <V as NonZeroInt>::UnderlyingType: AddAssign<V::UnderlyingType> + Pod + PrimInt,

Adds 1 to the value stored at location key. If the value is not present, the value 1 will be set at that location. Uses the niche optimization for better performance with Option<NonZero<T>>.

NOTE: This method can only be called with NonZero<T> values. For primitive values use [bump_int].

Panics

Panics if adding 1 results in overflow.

pub fn entry(&mut self, key: K) -> Entry<'_, K, V>

Gets the given key’s corresponding entry in the map for in-place manipulation.

Analogous to HashMap::entry

Trait Implementations

impl<K: Debug, V: Debug, S: Debug, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize> Debug for MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>

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

Formats the value using the given formatter.

impl<K, V, S, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize> Default for MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>

where K: PrimInt + Eq + Hash + KeyIndex<K, TABLE_MIN_VALUE> + TryFrom<i128> + 'static, S: Default + BuildHasher, V: PartialEq + Copy, i128: AsPrimitive<K>, usize: AsPrimitive<K>, <K as TryFrom<i128>>::Error: Debug,

fn default() -> Self

Creates an empty MuleMap.

Example

let mule_map = mule_map::MuleMap::<u32, usize, fnv_rs::FnvBuildHasher>::default();

See: MuleMap::with_capacity_and_hasher

Analogous to HashMap::default