Hashing Benchmarks for u64 keys

============================================== PROJECT_DIR/Cargo.toml ========================================

[package]
name = "tests"
version = "0.1.0"
edition = "2018"

[dev-dependencies]
criterion = { version = "0.3", features = ["real_blackbox"] } # you can remove this feature if you're not on nightly

[dependencies]
ahash = "0.7"
rustc-hash = "1"
rand = "0.8"

[[bench]]
name = "benchmark"
harness = false


============================================== PROJECT_DIR/benches/benchmark.rs ===============================

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

use ahash::AHasher;
use rand::distributions::Standard;
use rand::prelude::Distribution;
use rand::prelude::SliceRandom;
use rand::Rng;
use rustc_hash::FxHasher;
use std::collections::HashSet;
use std::hash::{BuildHasher, BuildHasherDefault, Hash, Hasher};
use std::iter::FromIterator;

pub trait Set {
    type Item;

    fn from_iterator<I: IntoIterator<Item = Self::Item>>(values: I) -> Self;

    fn get(&self, item: &Self::Item) -> bool;
}

impl<T, S> Set for HashSet<T, S>
where
    T: Eq + Hash,
    S: Default + BuildHasher,
{
    type Item = T;

    #[inline]
    fn from_iterator<I: IntoIterator<Item = Self::Item>>(values: I) -> Self {
        FromIterator::from_iter(values)
    }

    #[inline]
    fn get(&self, item: &Self::Item) -> bool {
        self.contains(item)
    }
}

pub struct LinearSearch<T>(pub Vec<T>);

impl<T> Set for LinearSearch<T>
where
    T: PartialEq,
{
    type Item = T;

    #[inline]
    fn from_iterator<I: IntoIterator<Item = Self::Item>>(values: I) -> Self {
        Self(FromIterator::from_iter(values))
    }

    #[inline]
    fn get(&self, item: &Self::Item) -> bool {
        self.0.contains(item)
    }
}

pub struct BinarySearch<T>(pub Vec<T>);

impl<T> Set for BinarySearch<T>
where
    T: Ord,
{
    type Item = T;

    #[inline]
    fn from_iterator<I: IntoIterator<Item = Self::Item>>(values: I) -> Self {
        let mut vec = Vec::from_iter(values);
        vec.sort_unstable();
        Self(vec)
    }

    #[inline]
    fn get(&self, item: &Self::Item) -> bool {
        self.0.binary_search(item).is_ok()
    }
}

#[derive(Default)]
pub struct NoHasher(pub u64);

impl Hasher for NoHasher {
    #[inline]
    fn finish(&self) -> u64 {
        self.0
    }

    #[inline]
    fn write_u64(&mut self, i: u64) {
        self.0 = i;
    }

    fn write(&mut self, _bytes: &[u8]) {
        unreachable!();
    }

    fn write_i128(&mut self, _i: i128) {
        unreachable!();
    }

    fn write_i16(&mut self, _i: i16) {
        unreachable!();
    }

    fn write_i32(&mut self, _i: i32) {
        unreachable!();
    }

    fn write_i64(&mut self, _i: i64) {
        unreachable!();
    }

    fn write_i8(&mut self, _i: i8) {
        unreachable!();
    }

    fn write_isize(&mut self, _i: isize) {
        unreachable!();
    }
    fn write_u128(&mut self, _i: u128) {
        unreachable!();
    }
    fn write_u16(&mut self, _i: u16) {
        unreachable!();
    }

    fn write_u32(&mut self, _i: u32) {
        unreachable!();
    }
    fn write_u8(&mut self, _i: u8) {
        unreachable!();
    }

    fn write_usize(&mut self, _i: usize) {
        unreachable!();
    }
}

fn bench_set<S>(items: &[S::Item], b: &mut Bencher)
where
    S: Set,
    S::Item: Clone,
    Standard: Distribution<S::Item>,
{
    let set = S::from_iterator(items.iter().cloned());
    let against = items.choose(&mut rand::thread_rng()).unwrap();
    b.iter(|| black_box(set.get(black_box(&against))))
}

pub fn bench(c: &mut Criterion) {
    let mut group = c.benchmark_group("Hit");

    let items: Vec<u64> = rand::thread_rng().sample_iter(Standard).take(32).collect();

    let nums = [1usize, 2, 4, 8, 16, 32];
    for i in nums {
        group.bench_with_input(BenchmarkId::new("ahash", i), &i, |b, i| {
            bench_set::<HashSet<u64, BuildHasherDefault<AHasher>>>(&items[..*i], b)
        });

        group.bench_with_input(BenchmarkId::new("fxhash", i), &i, |b, i| {
            bench_set::<HashSet<u64, BuildHasherDefault<FxHasher>>>(&items[..*i], b)
        });

        group.bench_with_input(BenchmarkId::new("nohash", i), &i, |b, i| {
            bench_set::<HashSet<u64, BuildHasherDefault<NoHasher>>>(&items[..*i], b)
        });

        group.bench_with_input(BenchmarkId::new("linear", i), &i, |b, i| {
            bench_set::<LinearSearch<u64>>(&items[..*i], b)
        });

        group.bench_with_input(BenchmarkId::new("binary", i), &i, |b, i| {
            bench_set::<BinarySearch<u64>>(&items[..*i], b)
        });
    }
}

criterion_group!(benches, bench);
criterion_main!(benches);