sparse_hash_map/
hasher.rs

1//! Hashing and equality traits for keys.
2//!
3//! A hash here yields a `usize` directly, matching a hash functor that returns a
4//! machine word. This lets an identity hash place a key in a known bucket, which
5//! the collision and precalculated-hash tests rely on.
6//!
7//! [`StdHash`] is the default. It feeds the key to a [`core::hash::Hasher`] built
8//! by a [`core::hash::BuildHasher`] and truncates the 64-bit result to `usize`.
9
10use core::hash::{BuildHasher, Hash};
11use core::marker::PhantomData;
12
13/// Produce a `usize` hash for a borrowed key `Q`.
14pub trait HashKey<Q: ?Sized> {
15    /// Hash `key`.
16    fn hash_key(&self, key: &Q) -> usize;
17}
18
19/// Test two borrowed keys for equality.
20pub trait EqKey<A: ?Sized, B: ?Sized> {
21    /// Whether `a` and `b` are the same key.
22    fn eq_key(&self, a: &A, b: &B) -> bool;
23}
24
25/// A hasher built on the standard [`BuildHasher`] machinery.
26///
27/// The default `B` is [`std::collections::hash_map::RandomState`], the same
28/// builder that backs [`std::collections::HashMap`].
29#[derive(Clone, Default)]
30pub struct StdHash<B = std::collections::hash_map::RandomState> {
31    build: B,
32}
33
34impl<B: BuildHasher> StdHash<B> {
35    /// Wrap an existing [`BuildHasher`].
36    pub fn with_hasher(build: B) -> Self {
37        Self { build }
38    }
39}
40
41impl<B: BuildHasher, Q: Hash + ?Sized> HashKey<Q> for StdHash<B> {
42    #[inline]
43    fn hash_key(&self, key: &Q) -> usize {
44        self.build.hash_one(key) as usize
45    }
46}
47
48/// Equality by the standard [`PartialEq`] relation.
49#[derive(Clone, Default)]
50pub struct StdEq;
51
52impl<A, B> EqKey<A, B> for StdEq
53where
54    A: PartialEq<B> + ?Sized,
55    B: ?Sized,
56{
57    #[inline]
58    fn eq_key(&self, a: &A, b: &B) -> bool {
59        a == b
60    }
61}
62
63/// Adapt a plain closure `Fn(&Q) -> usize` into a [`HashKey`].
64///
65/// Useful for identity and modulo hashers in tests and simple cases.
66#[derive(Clone)]
67pub struct FnHash<F> {
68    f: F,
69    _marker: PhantomData<fn()>,
70}
71
72impl<F> FnHash<F> {
73    /// Wrap a hashing closure.
74    pub fn new(f: F) -> Self {
75        Self {
76            f,
77            _marker: PhantomData,
78        }
79    }
80}
81
82impl<F, Q> HashKey<Q> for FnHash<F>
83where
84    F: Fn(&Q) -> usize,
85    Q: ?Sized,
86{
87    #[inline]
88    fn hash_key(&self, key: &Q) -> usize {
89        (self.f)(key)
90    }
91}
sparse_hash_map/hasher.rs

sparse_hash_map/
hasher.rs
