Benchmarking O(n) versus O(1) - https://x.com/zack_overflow/status/1874130688628387886

main.rs

fn main() {
    let mut rng = thread_rng();

    println!("Vector");
    for size in [1_000, 10_000, 50_000].into_iter() {
        let mut xs = Vec::with_capacity(size);
        for _ in 0..size {
            xs.push(rng.gen_range(0..size));
        }

        let t0 = SystemTime::now();
        let mut hits = 0;
        let mut misses = 0;
        for _ in 0..size {
            let candidate = rng.gen_range(0..size);
            if xs.contains(&candidate) {
                hits += 1;
            } else {
                misses += 1;
            }
        }
        let t1 = SystemTime::now();
        println!("size: {size} - hits: {hits}; misses: {misses}; time: {:?}", t1.duration_since(t0).unwrap());
    }

    println!("HashSet");
    for size in [1_000, 10_000, 50_000].into_iter() {
        let mut xs = HashSet::with_capacity(size);
        for _ in 0..size {
            xs.insert(rng.gen_range(0..size));
        }

        let t0 = SystemTime::now();
        let mut hits = 0;
        let mut misses = 0;
        for _ in 0..size {
            let candidate = rng.gen_range(0..size);
            if xs.contains(&candidate) {
                hits += 1;
            } else {
                misses += 1;
            }
        }
        let t1 = SystemTime::now();
        println!("size: {size} - hits: {hits}; misses: {misses}; time: {:?}", t1.duration_since(t0).unwrap());
    }
}