title: “Testing and Benchmarking HashMap in Rust” meta_description: “Comprehensive testing strategies, benchmarks, and Miri validation for HashMap implementations in Rust.” keywords: [“rust hashmap testing”, “miri hashmap”, “benchmark hashmap”, “property testing”, “criterion benchmarks”]

🧪 Reinventing from Scratch: Building HashMap

Chapter 8 — “Tests, Benchmarks, and Miri”

“If you haven’t run it under Miri, you haven’t tested it.”

🧭 8.1. Testing Strategy

A robust HashMap needs multiple layers of testing:

1. Unit tests — Individual operations
2. Integration tests — Combined operations
3. Property tests — Invariant checking
4. Benchmarks — Performance validation
5. Miri — Undefined behavior detection

✅ 8.2. Unit Tests

Test: Basic Insert and Get

#[test]
fn test_insert_and_get() {
    let mut map = MyHashMap::new();
    
    map.insert("apple", 1);
    map.insert("banana", 2);
    
    assert_eq!(map.get("apple"), Some(&1));
    assert_eq!(map.get("banana"), Some(&2));
    assert_eq!(map.get("cherry"), None);
}

Test: Update Existing Key

#[test]
fn test_insert_updates_existing() {
    let mut map = MyHashMap::new();
    
    assert_eq!(map.insert("key", 1), None);
    assert_eq!(map.insert("key", 2), Some(1));  // Returns old value
    assert_eq!(map.get("key"), Some(&2));
}

Test: Remove

#[test]
fn test_remove() {
    let mut map = MyHashMap::new();
    
    map.insert("a", 1);
    map.insert("b", 2);
    
    assert_eq!(map.remove("a"), Some(1));
    assert_eq!(map.remove("a"), None);  // Already removed
    assert_eq!(map.get("b"), Some(&2));  // Other entries intact
}

🔄 8.3. Collision and Probe Tests

Test: Forced Collisions

#[test]
fn test_handles_collisions() {
    use std::hash::{BuildHasherDefault, Hasher};
    
    // Custom hasher that returns predictable values
    struct PredictableHasher(u64);
    
    impl Hasher for PredictableHasher {
        fn finish(&self) -> u64 { self.0 }
        fn write(&mut self, _: &[u8]) { }
        fn write_u64(&mut self, i: u64) { self.0 = i; }
    }
    
    struct PredictableBuilder;
    impl BuildHasher for PredictableBuilder {
        type Hasher = PredictableHasher;
        fn build_hasher(&self) -> Self::Hasher {
            PredictableHasher(0)
        }
    }
    
    let mut map = MyHashMap::with_hasher(PredictableBuilder);
    
    // All these will hash to the same bucket!
    map.insert(0, "zero");
    map.insert(16, "sixteen");   // 16 % 16 = 0
    map.insert(32, "thirty-two"); // 32 % 16 = 0
    
    // All should still be retrievable
    assert_eq!(map.get(&0), Some(&"zero"));
    assert_eq!(map.get(&16), Some(&"sixteen"));
    assert_eq!(map.get(&32), Some(&"thirty-two"));
}

📈 8.4. Resize and Growth Tests

Test: Automatic Growth

#[test]
fn test_grows_automatically() {
    let mut map = MyHashMap::with_capacity(4);
    
    map.insert(1, "a");
    map.insert(2, "b");
    map.insert(3, "c");
    assert!(map.capacity() == 4);
    
    map.insert(4, "d");  // Should trigger growth (load > 0.75)
    assert!(map.capacity() > 4);
    
    // All entries still findable
    assert_eq!(map.get(&1), Some(&"a"));
    assert_eq!(map.get(&4), Some(&"d"));
}

🎲 8.5. Property-Based Testing

Using proptest or quickcheck:

use proptest::prelude::*;

proptest! {
    #[test]
    fn test_insert_then_get_returns_value(key: String, value: i32) {
        let mut map = MyHashMap::new();
        map.insert(key.clone(), value);
        assert_eq!(map.get(&key), Some(&value));
    }
    
    #[test]
    fn test_len_matches_actual_count(ops: Vec<(String, i32)>) {
        let mut map = MyHashMap::new();
        
        for (k, v) in ops {
            map.insert(k, v);
        }
        
        let actual_count = map.iter().count();
        assert_eq!(map.len(), actual_count);
    }
    
    #[test]
    fn test_remove_then_get_returns_none(
        inserts: Vec<(String, i32)>,
        remove_keys: Vec<String>
    ) {
        let mut map = MyHashMap::new();
        
        for (k, v) in inserts {
            map.insert(k, v);
        }
        
        for key in &remove_keys {
            map.remove(key);
        }
        
        for key in &remove_keys {
            assert_eq!(map.get(key), None);
        }
    }
}

⚡ 8.6. Benchmarking with Criterion

use criterion::{black_box, criterion_group, criterion_main, Criterion};

fn bench_insert(c: &mut Criterion) {
    c.bench_function("insert 1000", |b| {
        b.iter(|| {
            let mut map = MyHashMap::new();
            for i in 0..1000 {
                map.insert(black_box(i), black_box(i * 2));
            }
        });
    });
}

fn bench_get(c: &mut Criterion) {
    let mut map = MyHashMap::new();
    for i in 0..10000 {
        map.insert(i, i * 2);
    }
    
    c.bench_function("get from 10k", |b| {
        b.iter(|| {
            for i in 0..1000 {
                black_box(map.get(&black_box(i)));
            }
        });
    });
}

fn bench_iterate(c: &mut Criterion) {
    let mut map = MyHashMap::new();
    for i in 0..10000 {
        map.insert(i, i);
    }
    
    c.bench_function("iterate 10k", |b| {
        b.iter(|| {
            for (k, v) in &map {
                black_box(k);
                black_box(v);
            }
        });
    });
}

criterion_group!(benches, bench_insert, bench_get, bench_iterate);
criterion_main!(benches);

🔬 8.7. Miri: The Ultimate Test

Miri detects undefined behavior:

cargo +nightly miri test

What Miri Catches

• Use-after-free
• Uninitialized memory reads
• Invalid pointer arithmetic
• Data races (even in single-threaded code via interior mutability)
• Alignment violations

Example Test Under Miri

#[test]
fn test_miri_safe_insert_remove() {
    let mut map = MyHashMap::new();
    
    // Fill map
    for i in 0..100 {
        map.insert(i, format!("value_{}", i));
    }
    
    // Remove half
    for i in (0..100).step_by(2) {
        map.remove(&i);
    }
    
    // Verify remaining
    for i in (1..100).step_by(2) {
        assert!(map.get(&i).is_some());
    }
    
    // Drop map (Miri checks Drop implementation)
}

If there’s any UB (wrong pointer arithmetic, etc.), Miri will catch it!

📊 8.8. Performance Comparison

Compare your HashMap against std:

fn bench_comparison(c: &mut Criterion) {
    let mut group = c.benchmark_group("hashmap_comparison");
    
    group.bench_function("std::HashMap insert", |b| {
        b.iter(|| {
            let mut map = std::collections::HashMap::new();
            for i in 0..1000 {
                map.insert(i, i);
            }
        });
    });
    
    group.bench_function("MyHashMap insert", |b| {
        b.iter(|| {
            let mut map = MyHashMap::new();
            for i in 0..1000 {
                map.insert(i, i);
            }
        });
    });
    
    group.finish();
}

Expected: Your HashMap will be 2-10x slower (that’s OK! Learning > performance).

🎯 8.9. Load Factor Analysis

Measure how probe distance increases with load:

#[test]
fn measure_probe_distances() {
    let mut map = MyHashMap::with_capacity(1000);
    let mut max_distance = 0;
    
    for i in 0..750 {  // Fill to 75%
        map.insert(i, i);
        
        // Check max distance
        for (idx, entry) in map.entries.iter().enumerate() {
            if let Occupied(e) = entry {
                let dist = map.probe_distance(e.hash, idx);
                max_distance = max_distance.max(dist);
            }
        }
    }
    
    println!("Max probe distance at 75% load: {}", max_distance);
    assert!(max_distance < 20, "Probe distances too high!");
}

🧠 8.10. Chapter Takeaways

🚀 8.11. What’s Next

We’ve built a complete, tested HashMap!

Final chapter: Appendix — Implementation Skeleton

Get the complete reference implementation with all the pieces assembled.

💡 Exercises

1. Write 20+ unit tests covering all operations
2. Add property tests for insert/remove/get invariants
3. Benchmark against std::HashMap
4. Run under Miri and fix any issues
5. Measure probe distance distribution across different load factors
6. Test with complex types (String, Vec, custom structs)

Next: Chapter 9 — Appendix: Implementation Skeleton 📝