turbo_prehash/
lib.rs

1//! turbo-prehash
2//!
3//! A small wrapper around `std::hash::Hasher` that allows you to pre-hash a
4//! value before hashing it.
5//!
6//! This is useful for when you want to hash a value that is expensive to
7//! compute (e.g. a large string) but you want to avoid re-hashing it every
8//! time.
9//!
10//! # Example
11//!
12//! ```
13//! use std::{collections::HashMap, hash::{Hash, RandomState}};
14//!
15//! use turbo_prehash::{BuildHasherExt, PreHashed};
16//!
17//! /// hash a key, returning a prehashed value
18//! fn hash_key<T: Hash>(key: T) -> PreHashed<T> {
19//!     RandomState::new().prehash(key)
20//! }
21//!
22//! // create hashmap to hold pre-hashed values
23//! let mut map: HashMap<PreHashed<String>, String> = HashMap::default();
24//!
25//! // insert a prehashed value
26//! let hashed_key = hash_key("hello".to_string());
27//! map.insert(hashed_key.clone(), "world".to_string());
28//!
29//! // get the value
30//! assert_eq!(map.get(&hashed_key), Some(&"world".to_string()));
31//! ```
32
33use std::{
34    fmt,
35    hash::{BuildHasher, Hash, Hasher},
36    ops::Deref,
37};
38
39/// A wrapper type that hashes some `inner` on creation, implementing [Hash]
40/// by simply returning the pre-computed hash.
41#[derive(Copy, Debug, Clone)]
42pub struct PreHashed<I, H = u64> {
43    hash: H,
44    inner: I,
45}
46
47impl<I, H> PreHashed<I, H> {
48    /// Create a new [PreHashed] value with the given hash and inner value.
49    ///
50    /// SAFETY: The hash must be a valid hash of the inner value.
51    pub fn new(hash: H, inner: I) -> Self {
52        Self { hash, inner }
53    }
54
55    /// Split the [PreHashed] value into its hash and inner value.
56    pub fn into_parts(self) -> (H, I) {
57        (self.hash, self.inner)
58    }
59
60    fn inner(&self) -> &I {
61        &self.inner
62    }
63}
64
65impl<I: Hash> PreHashed<I, u64> {
66    /// Create a new [PreHashed] value from a [BuildHasher].
67    fn new_from_builder<B: BuildHasher>(hasher: &B, inner: I) -> Self {
68        Self::new(hasher.hash_one(&inner), inner)
69    }
70}
71
72impl<I> Deref for PreHashed<I> {
73    type Target = I;
74
75    fn deref(&self) -> &Self::Target {
76        self.inner()
77    }
78}
79
80impl<I, H> AsRef<I> for PreHashed<I, H> {
81    fn as_ref(&self) -> &I {
82        self.inner()
83    }
84}
85
86impl<I, H: Hash> Hash for PreHashed<I, H> {
87    fn hash<S: Hasher>(&self, state: &mut S) {
88        self.hash.hash(state)
89    }
90}
91
92impl<I: Eq, H> Eq for PreHashed<I, H> {}
93
94impl<I: PartialEq, H> PartialEq for PreHashed<I, H> {
95    // note: we compare the values, not the hashes
96    fn eq(&self, other: &Self) -> bool {
97        self.inner.eq(&other.inner)
98    }
99}
100
101impl<I: fmt::Display, H> fmt::Display for PreHashed<I, H> {
102    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
103        self.inner.fmt(f)
104    }
105}
106
107/// An implementer of [Hash] that simply returns the pre-computed hash.
108#[derive(Copy, Clone, Debug, Default)]
109pub struct PassThroughHash(u64);
110
111impl PassThroughHash {
112    pub fn new() -> Self {
113        Default::default()
114    }
115}
116
117impl Hasher for PassThroughHash {
118    fn write(&mut self, _bytes: &[u8]) {
119        unimplemented!("do not use")
120    }
121
122    fn write_u64(&mut self, i: u64) {
123        self.0 = i;
124    }
125
126    fn finish(&self) -> u64 {
127        self.0
128    }
129}
130
131/// An extension trait for [BuildHasher] that provides the
132/// [BuildHasherExt::prehash] method.
133pub trait BuildHasherExt: BuildHasher {
134    type Hash;
135
136    fn prehash<T: Hash>(&self, value: T) -> PreHashed<T, Self::Hash>;
137}
138
139impl<B: BuildHasher> BuildHasherExt for B {
140    type Hash = u64;
141
142    fn prehash<T: Hash>(&self, value: T) -> PreHashed<T, Self::Hash> {
143        PreHashed::new_from_builder(self, value)
144    }
145}
turbo_prehash/lib.rs

turbo_prehash/
lib.rs
