Generic Hash Table — Rust Lecture Notes

A generic open-addressed hash table stores key-value pairs in a single contiguous bucket array and resolves collisions via Robin Hood linear probing, tracking each entry's probe sequence length (PSL) so entries far from their ideal home bucket displace entries closer to theirs. Maintaining a maximum load factor (such as $0.75$) and cached 64-bit hashes delivers $O(1)$ expected lookup, insertion, and deletion with low probe variance.

Robin Hood Probing Architecture

Home bucket index = (hash as usize) & (capacity - 1)

Insertion of (K_new, psl=2) into Slot i currently holding (K_existing, psl=1):
  Because psl_new (2) > psl_existing (1), K_new steals Slot i,
  and K_existing continues probing at Slot i + 1 with psl = 2.

Deletion at Slot i (Backshift Deletion — no tombstones required):
  While Slot (i + 1) is Occupied with psl > 0:
    Move Slot (i + 1) left into Slot i with psl - 1

Design Choice	Mechanism	Advantage
Power-of-two capacity	Bitmask `(hash as usize) & (cap - 1)`	Replaces expensive integer modulo `%` with single-cycle bitwise AND
Robin Hood swap rule	Swap when incoming `psl > occupant.psl`	Minimizes probe length variance and prevents clustering pathologies
Backshift deletion	Shift subsequent entries with `psl > 0` backward by 1	Eliminates tombstones that degrade probe performance over time
Cached `u64` hash	Stored inside `Entry<K, V>`	Avoids recomputing `K::hash` during probing and table resizing

Complete Implementation

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

#[derive(Clone)]
struct OccupiedEntry<K, V> {
    hash: u64,
    psl: usize,
    key: K,
    value: V,
}

#[derive(Clone)]
enum Bucket<K, V> {
    Empty,
    Occupied(OccupiedEntry<K, V>),
}

pub struct RobinHoodMap<K, V> {
    buckets: Vec<Bucket<K, V>>,
    len: usize,
}

impl<K: Hash + Eq, V> RobinHoodMap<K, V> {
    pub fn new() -> Self {
        Self::with_capacity(8)
    }

    pub fn with_capacity(capacity: usize) -> Self {
        let cap = capacity.max(8).next_power_of_two();
        let mut buckets = Vec::with_capacity(cap);
        buckets.resize_with(cap, || Bucket::Empty);
        Self { buckets, len: 0 }
    }

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

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

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

    fn hash_key<Q: Hash + ?Sized>(key: &Q) -> u64 {
        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        hasher.finish()
    }

    fn mask(&self) -> usize {
        self.buckets.len() - 1
    }

    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        if (self.len + 1) * 4 >= self.buckets.len() * 3 {
            self.resize(self.buckets.len() * 2);
        }

        let hash = Self::hash_key(&key);
        let mask = self.mask();
        let mut idx = (hash as usize) & mask;
        let mut incoming = OccupiedEntry {
            hash,
            psl: 0,
            key,
            value,
        };

        loop {
            match &mut self.buckets[idx] {
                Bucket::Empty => {
                    self.buckets[idx] = Bucket::Occupied(incoming);
                    self.len += 1;
                    return None;
                }
                Bucket::Occupied(existing) => {
                    if existing.hash == incoming.hash && existing.key == incoming.key {
                        let old_val = std::mem::replace(&mut existing.value, incoming.value);
                        return Some(old_val);
                    }
                    if incoming.psl > existing.psl {
                        std::mem::swap(existing, &mut incoming);
                    }
                    incoming.psl += 1;
                    idx = (idx + 1) & mask;
                }
            }
        }
    }

    pub fn get(&self, key: &K) -> Option<&V> {
        let hash = Self::hash_key(key);
        let mask = self.mask();
        let mut idx = (hash as usize) & mask;
        let mut psl = 0;

        loop {
            match &self.buckets[idx] {
                Bucket::Empty => return None,
                Bucket::Occupied(entry) => {
                    if psl > entry.psl {
                        // Early termination: if our key were present, it would have displaced this entry.
                        return None;
                    }
                    if entry.hash == hash && &entry.key == key {
                        return Some(&entry.value);
                    }
                    psl += 1;
                    idx = (idx + 1) & mask;
                }
            }
        }
    }

    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
        let hash = Self::hash_key(key);
        let mask = self.mask();
        let mut idx = (hash as usize) & mask;
        let mut psl = 0;

        loop {
            let stop = match &self.buckets[idx] {
                Bucket::Empty => true,
                Bucket::Occupied(entry) => psl > entry.psl,
            };
            if stop {
                return None;
            }
            if let Bucket::Occupied(entry) = &self.buckets[idx] {
                if entry.hash == hash && &entry.key == key {
                    if let Bucket::Occupied(entry_mut) = &mut self.buckets[idx] {
                        return Some(&mut entry_mut.value);
                    }
                }
            }
            psl += 1;
            idx = (idx + 1) & mask;
        }
    }

    pub fn remove(&mut self, key: &K) -> Option<V> {
        let hash = Self::hash_key(key);
        let mask = self.mask();
        let mut idx = (hash as usize) & mask;
        let mut psl = 0;

        loop {
            match &self.buckets[idx] {
                Bucket::Empty => return None,
                Bucket::Occupied(entry) => {
                    if psl > entry.psl {
                        return None;
                    }
                    if entry.hash == hash && &entry.key == key {
                        break;
                    }
                    psl += 1;
                    idx = (idx + 1) & mask;
                }
            }
        }

        let removed = match std::mem::replace(&mut self.buckets[idx], Bucket::Empty) {
            Bucket::Occupied(entry) => entry.value,
            Bucket::Empty => unreachable!(),
        };
        self.len -= 1;

        // Backshift subsequent entries whose PSL > 0
        loop {
            let next_idx = (idx + 1) & mask;
            let should_shift = match &self.buckets[next_idx] {
                Bucket::Occupied(next_entry) => next_entry.psl > 0,
                Bucket::Empty => false,
            };
            if !should_shift {
                break;
            }
            if let Bucket::Occupied(mut next_entry) =
                std::mem::replace(&mut self.buckets[next_idx], Bucket::Empty)
            {
                next_entry.psl -= 1;
                self.buckets[idx] = Bucket::Occupied(next_entry);
            }
            idx = next_idx;
        }

        Some(removed)
    }

    pub fn max_probe_length(&self) -> usize {
        self.buckets
            .iter()
            .filter_map(|b| match b {
                Bucket::Occupied(e) => Some(e.psl),
                Bucket::Empty => None,
            })
            .max()
            .unwrap_or(0)
    }

    fn resize(&mut self, new_cap: usize) {
        let mut new_buckets = Vec::with_capacity(new_cap);
        new_buckets.resize_with(new_cap, || Bucket::Empty);
        let old_buckets = std::mem::replace(&mut self.buckets, new_buckets);
        self.len = 0;

        for bucket in old_buckets {
            if let Bucket::Occupied(entry) = bucket {
                self.insert(entry.key, entry.value);
            }
        }
    }
}

fn main() {
    let mut map = RobinHoodMap::new();

    for i in 0..20 {
        map.insert(format!("service-{i:02}"), i * 10);
    }

    println!(
        "Inserted {} entries (capacity={}, max_psl={})",
        map.len(),
        map.capacity(),
        map.max_probe_length()
    );

    println!("Lookup 'service-07': {:?}", map.get(&"service-07".to_string()));
    if let Some(val) = map.get_mut(&"service-07".to_string()) {
        *val += 5;
    }
    println!(
        "After mutation 'service-07': {:?}",
        map.get(&"service-07".to_string())
    );

    let removed = map.remove(&"service-07".to_string());
    println!(
        "Removed 'service-07' -> {:?}, subsequent lookup -> {:?}",
        removed,
        map.get(&"service-07".to_string())
    );
    println!("Remaining count: {}", map.len());
}

Inserted 20 entries (capacity=32, max_psl=4)
Lookup 'service-07': Some(70)
After mutation 'service-07': Some(75)
Removed 'service-07' -> Some(75), subsequent lookup -> None
Remaining count: 19