hash_hasher/
lib.rs

1//! A [`std::hash::Hasher`](https://doc.rust-lang.org/std/hash/trait.Hasher.html) which is designed
2//! to work with already-hashed or hash-like data.
3//!
4//! The provided hasher does minimal work under the assumption that the input data is already
5//! suitable for use as a key in a `HashSet` or `HashMap`.
6//!
7//! As well as the performance benefit, it also causes `HashSet`s or `HashMap`s to become somewhat
8//! deterministic.  Given two equal `HashSet`s or `HashMap`s containing more than a single element,
9//! iterating them will yield the elements in differing orders.  By using a
10//! [`hash_hasher::HashedSet`](type.HashedSet.html) or
11//! [`hash_hasher::HashedMap`](type.HashedMap.html), then if the same data is inserted and/or
12//! removed *in the same order*, iterating the collection will yield a consistent order.
13//!
14//! # Examples
15//!
16//! Since `new()` and `with_capacity()` aren't available for `HashSet`s or `HashMap`s using custom
17//! hashers, the available constructors are `default()`, `with_hasher()` and
18//! `with_capacity_and_hasher()`.
19//!
20//! ## Using `default()`
21//!
22//! ```
23//! use hash_hasher::HashedMap;
24//!
25//! let mut map = HashedMap::default();
26//! assert!(map.insert(0, "zero").is_none());
27//! ```
28//!
29//! ## Using `with_capacity_and_hasher()`
30//!
31//! ```
32//! use hash_hasher::{HashBuildHasher, HashedSet};
33//!
34//! let mut set = HashedSet::with_capacity_and_hasher(100, HashBuildHasher::default());
35//! assert!(set.insert(0));
36//! ```
37
38#![doc(test(attr(forbid(warnings))))]
39#![warn(unused, missing_copy_implementations, missing_docs)]
40#![deny(
41    deprecated_in_future,
42    future_incompatible,
43    macro_use_extern_crate,
44    rust_2018_idioms,
45    nonstandard_style,
46    single_use_lifetimes,
47    trivial_casts,
48    trivial_numeric_casts,
49    unreachable_pub,
50    unsafe_code,
51    unstable_features,
52    unused_import_braces,
53    unused_lifetimes,
54    unused_qualifications,
55    unused_results,
56    warnings,
57    clippy::all,
58    clippy::pedantic
59)]
60#![forbid(
61    const_err,
62    invalid_type_param_default,
63    macro_expanded_macro_exports_accessed_by_absolute_paths,
64    missing_fragment_specifier,
65    mutable_transmutes,
66    no_mangle_const_items,
67    order_dependent_trait_objects,
68    overflowing_literals,
69    pub_use_of_private_extern_crate,
70    unknown_crate_types
71)]
72
73use std::hash::{BuildHasherDefault, Hasher};
74
75/// A hasher which does minimal work to create the required `u64` output under the assumption that
76/// the input is already a hash digest or otherwise already suitable for use as a key in a `HashSet`
77/// or `HashMap`.
78#[derive(Copy, Clone, Default)]
79pub struct HashHasher(u64);
80
81impl Hasher for HashHasher {
82    #[inline]
83    fn write(&mut self, value: &[u8]) {
84        // A normal use-case (e.g. by a node in a DHT) may well involve handling hashes which are
85        // identical over the most-significant-bits, hence reverse the input message here to use the
86        // least-significant-bits first.
87        for (index, item) in value.iter().rev().enumerate().take(8) {
88            self.0 ^= u64::from(*item) << (index * 8);
89        }
90    }
91
92    #[inline]
93    fn finish(&self) -> u64 {
94        self.0
95    }
96}
97
98/// Alias for a `BuildHasherDefault<HashHasher>`.
99pub type HashBuildHasher = BuildHasherDefault<HashHasher>;
100
101/// Alias for a `std::collections::HashMap<K, V, HashBuildHasher>`.
102pub type HashedMap<K, V> = ::std::collections::HashMap<K, V, HashBuildHasher>;
103
104/// Alias for a `std::collections::HashSet<K, HashBuildHasher>`.
105pub type HashedSet<K> = ::std::collections::HashSet<K, HashBuildHasher>;
106
107#[cfg(test)]
108mod tests {
109    use super::{HashBuildHasher, HashHasher, HashedMap, HashedSet};
110    use rand::{thread_rng, Rng};
111    use std::hash::{Hash, Hasher};
112
113    #[test]
114    fn hasher() {
115        let mut hash_hasher = HashHasher::default();
116        hash_hasher.write(&[9]);
117        assert_eq!(9, hash_hasher.finish());
118        hash_hasher.write(&[4, 0]);
119        assert_eq!(1033, hash_hasher.finish());
120        hash_hasher.write(&[1, 4, 0]);
121        assert_eq!(65545, hash_hasher.finish());
122
123        hash_hasher = HashHasher::default();
124        hash_hasher.write(&[3, 231]);
125        assert_eq!(999, hash_hasher.finish());
126
127        hash_hasher = HashHasher::default();
128        hash_hasher.write(&[0, 0, 0, 0, 255, 255, 255, 255]);
129        assert_eq!(4_294_967_295, hash_hasher.finish());
130
131        hash_hasher = HashHasher::default();
132        hash_hasher.write(&[255, 255, 255, 255, 255, 255, 255, 1]);
133        assert_eq!(18_446_744_073_709_551_361, hash_hasher.finish());
134
135        hash_hasher = HashHasher::default();
136        hash_hasher.write(&[255, 255, 255, 255, 255, 255, 255, 255]);
137        assert_eq!(18_446_744_073_709_551_615, hash_hasher.finish());
138
139        hash_hasher = HashHasher::default();
140        hash_hasher.write(&[0, 255, 255, 255, 255, 255, 255, 255, 255]);
141        assert_eq!(18_446_744_073_709_551_615, hash_hasher.finish());
142
143        hash_hasher = HashHasher::default();
144        hash_hasher.write(&[
145            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 255, 255, 255, 255, 255, 255, 255, 255,
146        ]);
147        assert_eq!(18_446_744_073_709_551_615, hash_hasher.finish());
148    }
149
150    #[test]
151    fn hash_map() {
152        let mut map = HashedMap::with_capacity_and_hasher(3, HashBuildHasher::default());
153        let mut sha1 = [0_u8; 20];
154        assert!(map.insert(sha1, "First").is_none());
155        sha1[19] = 1;
156        assert!(map.insert(sha1, "Second").is_none());
157        sha1[0] = 1;
158        assert!(map.insert(sha1, "Third").is_none());
159        assert_eq!(map.insert(sha1, "Fourth"), Some("Third"));
160    }
161
162    #[test]
163    fn determinism() {
164        let mut set1 = HashedSet::<u64>::default();
165        let mut set2 = HashedSet::default();
166
167        let mut set3 = ::std::collections::HashSet::new();
168        let mut set4 = ::std::collections::HashSet::new();
169
170        let mut rng = thread_rng();
171        for _ in 0..100 {
172            let random_value = rng.gen();
173            let _ = set1.insert(random_value);
174            let _ = set2.insert(random_value);
175            let _ = set3.insert(random_value);
176            let _ = set4.insert(random_value);
177        }
178
179        assert_eq!(
180            set1.into_iter().collect::<Vec<_>>(),
181            set2.into_iter().collect::<Vec<_>>()
182        );
183        assert_ne!(
184            set3.into_iter().collect::<Vec<_>>(),
185            set4.into_iter().collect::<Vec<_>>()
186        );
187    }
188
189    fn hash<H: Hash>(value: H) -> u64 {
190        let mut hasher = HashHasher::default();
191        value.hash(&mut hasher);
192        hasher.finish()
193    }
194
195    #[test]
196    // This checks for regressions to https://github.com/Fraser999/Hash-Hasher/issues/1
197    fn avoid_tending_towards_max_value() {
198        let h1 = hash(&[u64::max_value()]);
199        assert_ne!(u64::max_value(), h1);
200
201        let h2 = hash(&[u64::max_value(), u64::max_value()]);
202        assert_ne!(u64::max_value(), h2);
203        assert_ne!(h1, h2, "\nh1: {:b}\nh2: {:b}\n", h1, h2);
204
205        let h3 = hash(&[
206            [u64::max_value(), u64::max_value()],
207            [u64::max_value(), u64::max_value()],
208        ]);
209        assert_ne!(u64::max_value(), h3);
210        assert_ne!(h1, h3, "\nh1: {:b}\nh3: {:b}\n", h1, h3);
211        assert_ne!(h2, h3, "\nh2: {:b}\nh3: {:b}\n", h2, h3);
212    }
213}
hash_hasher/lib.rs

hash_hasher/
lib.rs
