Struct fchashmap::FcHashMap

pub struct FcHashMap<K, V, const CAP: usize> { /* fields omitted */ }

A fixed capacity no_std hashmap.

The realization of the hashmap is based on the Robin Hood hashing algorithm. This method
is simple and robust with reasonable performance. However, the fixed capacity implementation has some limitations:

• The size of the hashmap must be fixed at compile time
• 8 bytes ram are consumed per entry without keys and values
• The maximum capacity is limited to 32768 entries
• The capacity must be chosen as a power of 2
• The hashmap should not be used to its full capacity, otherwise it will become slow. 10 to 20 percent of the capacity should always be kept free.

Example

use fchashmap::FcHashMap;
use hash32_derive::Hash32;
use hash32::Hash;

#[derive(Debug)]
struct Reading {
    temperature: f32,
    humidy: f32,
}

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash32)]
struct DeviceId([u8; 8]);

impl DeviceId {
    fn new(input: &[u8; 8]) -> Self {
        let mut id = [0_u8; 8];
        id.copy_from_slice(input);
        Self(id)
    }
}

let mut fc_hash_map = FcHashMap::<DeviceId, Reading, 128>::new();

let dev1 = DeviceId::new(b"12345678");
let dev2 = DeviceId::new(b"12345679");
let dev3 = DeviceId::new(b"12345680");

fc_hash_map.insert(dev1, Reading { temperature: 23.1, humidy: 76.3 }).unwrap();
fc_hash_map.insert(dev2, Reading { temperature: 22.7, humidy: 55.5 }).unwrap();

let reading = fc_hash_map.get(&dev1).unwrap();
assert_eq!(reading.temperature, 23.1);
assert_eq!(reading.humidy, 76.3);

let reading = fc_hash_map.get(&dev2).unwrap();
assert_eq!(reading.temperature, 22.7);
assert_eq!(reading.humidy, 55.5);

assert!(fc_hash_map.get(&dev3).is_none());

Performance

The following diagram shows the timing behavior on a Cortex M4f system (STM32F3) at 72 MHz. It can be seen that the performance of the hashmap decreases significantly from a fill margin of about 80%.

Implementations

impl<K, V, const CAP: usize> FcHashMap<K, V, CAP>

pub fn new() -> Self

Creates an empty HashMap.

The hash map is initially created with no elements inside. The maximum capacity must be set at complile time.

Example

use fchashmap::FcHashMap;
let mut map: FcHashMap<u32, i32, 16> = FcHashMap::new();

pub fn capacity(&self) -> usize

Returns the number of elements the map can hold.

pub fn clear(&mut self)

Remove all key-value pairs in the map.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 16>::new();
map.insert(1, "a");

map.clear();
assert!(map.is_empty());

pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: Eq + Hash, 

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

The key may be any borrowed form of the map’s key type, but ’HashandEq` on the borrowed form must match those for the key type.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 8>::new();
map.insert(1, "a").unwrap();

assert_eq!(map.contains_key(&1), true);
assert_eq!(map.contains_key(&2), false);

pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where
    K: Borrow<Q>,
    Q: Hash + Eq, 

Returns a reference to the value corresponding to the key.

The key may be any borrowed form of the map’s key type, but Hash and Eq on the borrowed form must match those for the key type.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 16>::new();
map.insert(1, "a").unwrap();

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

pub fn get_mut<'v, Q: ?Sized>(&'v mut self, key: &Q) -> Option<&'v mut V> where
    K: Borrow<Q>,
    Q: Hash + Eq, 

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

The key may be any borrowed form of the map’s key type, but Hash and Eq on the borrowed form must match those for the key type.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 8>::new();
map.insert(1, "a").unwrap();
if let Some(x) = map.get_mut(&1) {
    *x = "b";
}
assert_eq!(map.get(&1), Some(&"b"));

pub fn insert(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)> where
    K: Hash + PartialEq, 

Inserts a key-value pair into the map.

If an equivalent key already exists in the map: the key remains and retains in its place in the order, its corresponding value is updated with value and the older value is returned inside Some(_).

If no equivalent key existed in the map: the new key-value pair is inserted, and None is returned.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 8>::new();
assert_eq!(map.insert(37, "a"), Ok(None));

map.insert(37, "b");
assert_eq!(map.insert(37, "c"), Ok(Some("b")));
assert_eq!(map.get(&37), Some(&"c"));

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 16>::new();
assert_eq!(map.is_empty(), true);

map.insert(1, "a");
assert_eq!(map.is_empty(), false);

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

Return an iterator over the key-value pairs of the map, in their order.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 16>::new();
map.insert("a", 1).unwrap();
map.insert("b", 2).unwrap();
map.insert("c", 3).unwrap();

let v: Vec<_> = map.iter().collect();
assert_eq!(v, vec![(&"a", &1), (&"b", &2), (&"c", &3)]);

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

Return an iterator over the key-value pairs of the map, in their order.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 16>::new();
map.insert("a", 1).unwrap();
map.insert("b", 2).unwrap();
map.insert("c", 3).unwrap();

for (_, val) in map.iter_mut() {
    *val = 23;
}

let v: Vec<_> = map.iter().collect();
assert_eq!(v, vec![(&"a", &23), (&"b", &23), (&"c", &23)]);

pub fn keys(&self) -> impl Iterator<Item = &K>

Return an iterator over the keys of the map, in their order.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 16>::new();
map.insert("a", 1).unwrap();
map.insert("b", 2).unwrap();
map.insert("c", 3).unwrap();

let v: Vec<_> = map.keys().collect();
assert_eq!(v, vec![&"a", &"b", &"c"]);

pub fn len(&self) -> usize

Return the number of key-value pairs in the map.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 16>::new();
assert_eq!(map.len(), 0);

map.insert(1, "a").unwrap();
assert_eq!(map.len(), 1);

pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where
    K: Borrow<Q>,
    Q: Hash + Eq, 

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

The key may be any borrowed form of the map’s key type, but Hash and Eq on the borrowed form must match those for the key type.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 16>::new();
map.insert(1, "a");
assert_eq!(map.remove(&1), Some("a"));
assert_eq!(map.remove(&1), None);

pub fn values(&self) -> impl Iterator<Item = &V>

Return an iterator over the values of the map, in their order.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 16>::new();
map.insert("a", 1).unwrap();
map.insert("b", 2).unwrap();
map.insert("c", 3).unwrap();

let v: Vec<_> = map.values().collect();
assert_eq!(v, vec![&1, &2, &3]);

pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V>

Return an iterator over mutable references to the the values of the map, in their order.

Example

use fchashmap::FcHashMap;

let mut map = FcHashMap::<_, _, 16>::new();
map.insert("a", 1).unwrap();
map.insert("b", 2).unwrap();
map.insert("c", 3).unwrap();

for val in map.values_mut() {
    *val += 10;
}

let v: Vec<_> = map.values().collect();
assert_eq!(v, vec![&11, &12, &13]);

Trait Implementations

impl<K, V, const CAP: usize> Clone for FcHashMap<K, V, CAP> where
    K: Eq + Hash + Clone,
    V: Clone, 

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V, const CAP: usize> Debug for FcHashMap<K, V, CAP> where
    K: Eq + Hash + Debug,
    V: Debug, 

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

Formats the value using the given formatter.

impl<'a, K, V, const CAP: usize> Extend<(&'a K, &'a V)> for FcHashMap<K, V, CAP> where
    K: Eq + Hash + Copy,
    V: Copy, 

fn extend<I>(&mut self, iterable: I) where
    I: IntoIterator<Item = (&'a K, &'a V)>, 

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<K, V, const CAP: usize> Extend<(K, V)> for FcHashMap<K, V, CAP> where
    K: Eq + Hash, 

fn extend<I>(&mut self, iterable: I) where
    I: IntoIterator<Item = (K, V)>, 

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<K, V, const CAP: usize> FromIterator<(K, V)> for FcHashMap<K, V, CAP> where
    K: Eq + Hash, 

fn from_iter<I>(fc_hash_map: I) -> Self where
    I: IntoIterator<Item = (K, V)>, 

Creates a value from an iterator.

impl<'a, K, Q: ?Sized, V, const CAP: usize> Index<&'a Q> for FcHashMap<K, V, CAP> where
    K: Eq + Hash + Borrow<Q>,
    Q: Eq + Hash, 

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<'a, K, Q: ?Sized, V, const N: usize> IndexMut<&'a Q> for FcHashMap<K, V, N> where
    K: Eq + Hash + Borrow<Q>,
    Q: Eq + Hash, 

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

Performs the mutable indexing (container[index]) operation.

impl<'a, K, V, const CAP: usize> IntoIterator for &'a FcHashMap<K, V, CAP> where
    K: Eq + Hash, 

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.