A simple hashmap: https://edgarluque.com/blog/rust-hashmap/

simple_hashmap.rs

#![deny(clippy::all)]
#![deny(clippy::nursery)]
#![allow(clippy::cast_possible_truncation)]

use std::{
    collections::hash_map::RandomState,
    hash::{BuildHasher, Hash, Hasher},
};

#[derive(Debug, Clone)]
pub struct MyHashmap<K, V, S = RandomState> {
    // Our storage
    storage: Vec<Option<(K, V)>>,
    // Save the length for quick querying
    len: usize,
    // The hasher.
    state: S,
    // Wehther to use quadratic or linear probing.
    quadratic: bool,
}

impl<K, V, S> MyHashmap<K, V, S> {
    pub fn new(hasher: S, quadratic: bool) -> Self {
        Self {
            storage: (0..8).map(|_| None).collect(),
            len: 0,
            state: hasher,
            quadratic,
        }
    }

    pub const fn len(&self) -> usize {
        self.len
    }

    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub const fn is_quadratic(&self) -> bool {
        self.quadratic
    }

    fn should_resize(&self) -> bool {
        (self.len as f64 / self.storage.len() as f64) > 0.7
    }
}

impl<K, V, S> MyHashmap<K, V, S>
where
    K: Eq + Hash,
    S: BuildHasher,
{
    // Should be called with a sensible load factor.
    fn find_slot_linear(&self, key: &K) -> &Option<(K, V)> {
        let mut hasher = self.state.build_hasher();
        key.hash(&mut hasher);
        let start_idx = hasher.finish() as usize;
        let mut iter_idx = 0;
        let len = self.storage.len();

        let slot_idx = loop {
            let idx_mod: usize = (start_idx + iter_idx) % len;
            match &self.storage[idx_mod] {
                Some(kv) if kv.0.eq(key) => break idx_mod,
                None => break idx_mod,
                _ => {
                    iter_idx += 1;

                    assert!(
                        iter_idx <= len,
                        "find_slot called without a matching key and full storage!"
                    );
                }
            }
        };

        &self.storage[slot_idx]
    }

    fn find_slot_linear_mut(&mut self, key: &K) -> &mut Option<(K, V)> {
        let mut hasher = self.state.build_hasher();
        key.hash(&mut hasher);
        let start_idx = hasher.finish() as usize;
        let mut iter_idx = 0;
        let len = self.storage.len();

        let slot_idx = loop {
            let idx_mod: usize = (start_idx + iter_idx) % len;
            match &self.storage[idx_mod] {
                Some(kv) if kv.0.eq(key) => break idx_mod,
                None => break idx_mod,
                _ => {
                    iter_idx += 1;

                    assert!(
                        iter_idx <= len,
                        "find_slot called without a matching key and full storage!"
                    );
                }
            }
        };

        &mut self.storage[slot_idx]
    }

    // Should be called with a sensible load factor.
    fn find_slot_quadratic(&self, key: &K) -> &Option<(K, V)> {
        let mut hasher = self.state.build_hasher();
        key.hash(&mut hasher);
        let start_idx = hasher.finish() as usize;
        let mut iter_idx: usize = 0;
        let len = self.storage.len();

        let slot_idx = loop {
            let idx_mod: usize = (start_idx + (iter_idx + iter_idx.pow(2)) / 2) % len;
            match &self.storage[idx_mod] {
                Some(kv) if kv.0.eq(key) => break idx_mod,
                None => break idx_mod,
                _ => {
                    iter_idx += 1;

                    assert!(
                        iter_idx <= len,
                        "find_slot called without a matching key and full storage!"
                    );
                }
            }
        };

        &self.storage[slot_idx]
    }

    // Should be called with a sensible load factor.
    fn find_slot_quadratic_mut(&mut self, key: &K) -> &mut Option<(K, V)> {
        let mut hasher = self.state.build_hasher();
        key.hash(&mut hasher);
        let start_idx = hasher.finish() as usize;
        let mut iter_idx: usize = 0;
        let len = self.storage.len();

        let slot_idx = loop {
            let idx_mod: usize = (start_idx + (iter_idx + iter_idx.pow(2)) / 2) % len;
            match &self.storage[idx_mod] {
                Some(kv) if kv.0.eq(key) => break idx_mod,
                None => break idx_mod,
                _ => {
                    iter_idx += 1;

                    assert!(
                        iter_idx <= len,
                        "find_slot called without a matching key and full storage!"
                    );
                }
            }
        };

        &mut self.storage[slot_idx]
    }

    fn resize(&mut self) {
        let new_storage: Vec<Option<(K, V)>> = (0..self.storage.len() * 2).map(|_| None).collect();

        let old_storage = std::mem::replace(&mut self.storage, new_storage);

        self.len = 0;

        for (k, v) in old_storage.into_iter().flatten() {
            self.insert(k, v);
        }
    }

    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        if self.should_resize() {
            self.resize();
        }

        let slot = if self.quadratic {
            self.find_slot_quadratic_mut(&key)
        } else {
            self.find_slot_linear_mut(&key)
        };
        let new_slot = Some((key, value));
        let old_slot = std::mem::replace(slot, new_slot).map(|kv| kv.1);

        if old_slot.is_none() {
            self.len += 1;
        }

        old_slot
    }

    pub fn get(&self, key: &K) -> Option<&V> {
        let slot = if self.quadratic {
            self.find_slot_quadratic(key)
        } else {
            self.find_slot_linear(key)
        };
        slot.as_ref().map(|kv| &kv.1)
    }

    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
        let slot = if self.quadratic {
            self.find_slot_quadratic_mut(key)
        } else {
            self.find_slot_linear_mut(key)
        };
        slot.as_mut().map(|kv| &mut kv.1)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn new() {
        let map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), false);
        assert!(map.is_empty());
        assert_eq!(map.len(), 0);
    }

    #[test]
    fn insert() {
        let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), false);
        map.insert(1, 2);
        map.insert(2, 2);
        map.insert(3, 2);
        map.insert(4, 2);
        map.insert(1, 3);
        map.insert(2, 4);
        map.insert(3, 5);
        map.insert(4, 6);
    }

    #[test]
    fn get() {
        let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), false);
        map.insert(1, 3);
        map.insert(2, 2);
        map.insert(3, 1);
        assert_eq!(map.get(&1), Some(&3));
        assert_eq!(map.get(&2), Some(&2));
        assert_eq!(map.get(&3), Some(&1));
        assert_eq!(map.get(&6), None);
    }

    #[test]
    fn get_mut() {
        let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), false);
        map.insert(1, 3);
        map.insert(2, 2);
        map.insert(3, 1);
        assert_eq!(map.get(&1), Some(&3));
        let val = map.get_mut(&1);

        if let Some(val) = val {
            *val = 4;
        }
        assert_eq!(map.get(&1), Some(&4));
    }

    #[test]
    fn insert_lots() {
        let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), false);

        for x in 0..100000 {
            map.insert(x, x);
            assert_eq!(map.get(&x).unwrap(), &x)
        }
    }

    #[test]
    fn insert_quadratic() {
        let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), true);
        map.insert(1, 2);
        map.insert(2, 2);
        map.insert(3, 2);
        map.insert(4, 2);
        map.insert(1, 3);
        map.insert(2, 4);
        map.insert(3, 5);
        map.insert(4, 6);
    }

    #[test]
    fn get_quadratic() {
        let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), true);
        map.insert(1, 3);
        map.insert(2, 2);
        map.insert(3, 1);
        assert_eq!(map.get(&1), Some(&3));
        assert_eq!(map.get(&2), Some(&2));
        assert_eq!(map.get(&3), Some(&1));
        assert_eq!(map.get(&6), None);
    }

    #[test]
    fn get_mut_quadratic() {
        let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), true);
        map.insert(1, 3);
        map.insert(2, 2);
        map.insert(3, 1);
        assert_eq!(map.get(&1), Some(&3));
        let val = map.get_mut(&1);

        if let Some(val) = val {
            *val = 4;
        }
        assert_eq!(map.get(&1), Some(&4));
    }

    #[test]
    fn insert_lots_quadratic() {
        let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), true);

        for x in 0..100000 {
            map.insert(x, x);
            assert_eq!(map.get(&x).unwrap(), &x)
        }
    }
}