A fingerprint for
anything.

// A hash map with separate chaining, built by hand.
// Buckets is a Vec; each bucket is a Vec of (key, value) entries.
// This is exactly Vec<LinkedList<(K, V)>> in shape: array + linked-list
// chains from the two previous pages, working together.
struct ChainMap<K, V> {
    buckets: Vec<Vec<(K, V)>>,
}

impl<K: std::hash::Hash + Eq, V> ChainMap<K, V> {
    fn new(cap: usize) -> Self {
        Self { buckets: (0..cap).map(|_| Vec::new()).collect() }
    }

    fn bucket_for(&self, key: &K) -> usize {
        use std::collections::hash_map::DefaultHasher;
        use std::hash::{Hash, Hasher};
        let mut h = DefaultHasher::new();
        key.hash(&mut h);
        (h.finish() as usize) % self.buckets.len()
    }

    fn insert(&mut self, key: K, value: V) {
        let i = self.bucket_for(&key);
        let bucket = &mut self.buckets[i];
        // Update if key already present, otherwise push.
        for (k, v) in bucket.iter_mut() {
            if *k == key { *v = value; return; }
        }
        bucket.push((key, value));
    }

    fn get(&self, key: &K) -> Option<&V> {
        let i = self.bucket_for(key);
        self.buckets[i].iter().find(|(k, _)| k == key).map(|(_, v)| v)
    }
}

#include <stdlib.h>
#include <string.h>
#include <stdint.h>

// Same idea in C: array of bucket-heads, each one a singly linked list.
typedef struct Entry {
    char         *key;
    int           value;
    struct Entry *next;       // chain pointer, the linked-list page
} Entry;

#define BUCKETS 256
static Entry *table[BUCKETS] = {0};

uint64_t fnv1a(const char *s);   // from the previous snippet

void put(const char *key, int value) {
    uint64_t h = fnv1a(key) & (BUCKETS - 1);

    // Walk the chain in case the key already exists.
    for (Entry *e = table[h]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) { e->value = value; return; }
    }

    // New entry: prepend to the bucket's chain (O(1)).
    Entry *e = malloc(sizeof *e);
    e->key   = strdup(key);
    e->value = value;
    e->next  = table[h];
    table[h] = e;
}

// Open addressing: NO linked lists. When a bucket is taken, probe the
// next slot. Modern hash maps (Swiss tables, Rust's std HashMap,
// Google's Abseil) use this. Cache-friendly because everything stays
// in one contiguous Vec, exactly what the memory page would approve of.
struct OpenMap<K, V> {
    buckets: Vec<Option<(K, V)>>,
}

impl<K: std::hash::Hash + Eq + Clone, V: Clone> OpenMap<K, V> {
    fn insert(&mut self, key: K, value: V) {
        let cap = self.buckets.len();
        let mut i = self.hash(&key) % cap;
        loop {
            match &self.buckets[i] {
                None => { self.buckets[i] = Some((key, value)); return; }
                Some((k, _)) if *k == key => {
                    self.buckets[i] = Some((key, value));
                    return;
                }
                _ => i = (i + 1) % cap, // linear probe to the next slot
            }
        }
    }

    fn hash(&self, key: &K) -> usize {
        use std::collections::hash_map::DefaultHasher;
        use std::hash::{Hash, Hasher};
        let mut h = DefaultHasher::new();
        key.hash(&mut h);
        h.finish() as usize
    }
}

// Why this beats chaining on real machines:
//   - one contiguous array → every probe step hits prefetched cache lines
//   - no per-entry allocation, no pointer chases
//   - the linked-list page's cache penalty applies to chaining, not here

// Open addressing: NO linked lists. When a bucket is taken, probe the
// next slot. Modern hash maps (Swiss tables, Rust's std HashMap,
// Google's Abseil) use this. Cache-friendly because everything stays
// in one contiguous Vec, exactly what the memory page would approve of.
struct OpenMap<K, V> {
    buckets: Vec<Option<(K, V)>>,
}

impl<K: std::hash::Hash + Eq + Clone, V: Clone> OpenMap<K, V> {
    fn insert(&mut self, key: K, value: V) {
        let cap = self.buckets.len();
        let mut i = self.hash(&key) % cap;
        loop {
            match &self.buckets[i] {
                None => { self.buckets[i] = Some((key, value)); return; }
                Some((k, _)) if *k == key => {
                    self.buckets[i] = Some((key, value));
                    return;
                }
                _ => i = (i + 1) % cap, // linear probe to the next slot
            }
        }
    }

    fn hash(&self, key: &K) -> usize {
        use std::collections::hash_map::DefaultHasher;
        use std::hash::{Hash, Hasher};
        let mut h = DefaultHasher::new();
        key.hash(&mut h);
        h.finish() as usize
    }
}

// Why this beats chaining on real machines:
//   - one contiguous array → every probe step hits prefetched cache lines
//   - no per-entry allocation, no pointer chases
//   - the linked-list page's cache penalty applies to chaining, not here