use std::collections::HashMap;
use std::hash::{BuildHasherDefault, Hasher};
pub(crate) type FastMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
pub(crate) type IdMap<K, V> = HashMap<K, V, BuildHasherDefault<IdentityHasher>>;
#[derive(Default)]
pub struct FxHasher {
hash: u64,
}
impl FxHasher {
const SEED: u64 = 0x51_7c_c1_b7_27_22_0a_95;
#[inline]
fn add(&mut self, word: u64) {
self.hash = (self.hash.rotate_left(5) ^ word).wrapping_mul(Self::SEED);
}
}
impl Hasher for FxHasher {
#[inline]
fn write(&mut self, bytes: &[u8]) {
let (chunks, tail) = bytes.as_chunks::<8>();
for chunk in chunks {
self.add(u64::from_le_bytes(*chunk));
}
if !tail.is_empty() {
let mut word = [0u8; 8];
word[..tail.len()].copy_from_slice(tail);
self.add(u64::from_le_bytes(word));
}
}
#[inline]
fn write_u8(&mut self, value: u8) {
self.add(u64::from(value));
}
#[inline]
fn write_u32(&mut self, value: u32) {
self.add(u64::from(value));
}
#[inline]
fn write_u64(&mut self, value: u64) {
self.add(value);
}
#[inline]
fn write_usize(&mut self, value: usize) {
self.add(value as u64);
}
#[inline]
fn finish(&self) -> u64 {
let mut hash = self.hash;
hash ^= hash >> 32;
hash = hash.wrapping_mul(0xd6e8_feb8_6659_fd93);
hash ^= hash >> 32;
hash
}
}
#[derive(Default)]
pub struct IdentityHasher {
hash: u64,
}
impl Hasher for IdentityHasher {
#[inline]
fn write(&mut self, _bytes: &[u8]) {}
#[inline]
fn write_u32(&mut self, value: u32) {
self.hash = u64::from(value);
}
#[inline]
fn finish(&self) -> u64 {
self.hash
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::hash::BuildHasher;
#[test]
fn the_hashers_are_deterministic_on_the_key_shapes_they_serve() {
let fx = BuildHasherDefault::<FxHasher>::default();
assert_eq!(fx.hash_one([0u8; 16]), fx.hash_one([0u8; 16]));
assert_ne!(fx.hash_one([0u8; 16]), fx.hash_one([1u8; 16]));
let id = BuildHasherDefault::<IdentityHasher>::default();
assert_eq!(id.hash_one(7u32), 7u64);
assert_eq!(id.hash_one(u32::MAX), u64::from(u32::MAX));
}
#[test]
fn fx_chunks_its_bytes_eight_at_a_time() {
let mut whole = FxHasher::default();
whole.write(b"12345678ABCDEFGH");
let mut split = FxHasher::default();
split.write(b"12345678");
split.write(b"ABCDEFGH");
assert_eq!(whole.finish(), split.finish());
}
#[test]
fn fx_zero_pads_a_short_tail() {
let mut tail = FxHasher::default();
tail.write(b"abc");
let mut padded = FxHasher::default();
padded.write(b"abc\0\0\0\0\0");
assert_eq!(tail.finish(), padded.finish());
}
#[test]
fn fx_integer_writes_match_their_byte_form() {
let mut from_u32 = FxHasher::default();
from_u32.write_u32(0x0102_0304);
let mut from_bytes = FxHasher::default();
from_bytes.write(&0x0102_0304u32.to_le_bytes());
assert_eq!(from_u32.finish(), from_bytes.finish());
let mut narrow = FxHasher::default();
narrow.write_u8(0xAB);
let mut wide = FxHasher::default();
wide.write_u32(0xAB);
assert_eq!(narrow.finish(), wide.finish());
let mut word = FxHasher::default();
word.write_u64(0xDEAD_BEEF);
let mut sized = FxHasher::default();
sized.write_usize(0xDEAD_BEEF);
assert_eq!(word.finish(), sized.finish());
}
#[test]
fn the_fx_finish_avalanches_the_state() {
let mut hasher = FxHasher::default();
hasher.write_u64(1);
assert_ne!(hasher.finish(), hasher.hash);
}
#[test]
fn consecutive_correlation_ids_do_not_collide() {
let fx = BuildHasherDefault::<FxHasher>::default();
let mut hashes = std::collections::HashSet::new();
for counter in 0..1024u64 {
let mut key = [0u8; 16];
key[..8].copy_from_slice(&4_242u64.to_be_bytes());
key[8..].copy_from_slice(&counter.to_be_bytes());
hashes.insert(fx.hash_one(key));
}
assert_eq!(
hashes.len(),
1024,
"every consecutive id maps to its own hash"
);
}
#[test]
fn the_identity_hasher_ignores_byte_writes() {
let mut hasher = IdentityHasher::default();
hasher.write(b"ignored");
assert_eq!(hasher.finish(), 0);
hasher.write_u32(9);
assert_eq!(hasher.finish(), 9);
hasher.write(b"still ignored");
assert_eq!(
hasher.finish(),
9,
"a byte write must not disturb the value"
);
}
#[test]
fn the_transport_maps_round_trip_their_keys() {
let mut fast: FastMap<[u8; 16], u32> = FastMap::default();
fast.insert([7u8; 16], 42);
assert_eq!(fast.get(&[7u8; 16]), Some(&42));
assert_eq!(fast.get(&[8u8; 16]), None);
let mut ids: IdMap<u32, u32> = IdMap::default();
ids.insert(3, 9);
assert_eq!(ids.get(&3), Some(&9));
}
}