1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
use BuildHasher;
use Hasher;
use PhantomData;
pub type BuildFixedHasher = FixedState;
/// A [`BuildHasher`] that builds a hasher specialized in hashing small keys containing
/// only primitive types. The exact hasher implementation provided by this [`BuildHasher`]
/// may change over time if better algorithms are discovered or implemented.
;
/// Used to mark a type as able to be used with a [`NoHashHasher`]-based hash map or hash set.
///
/// In order to implement this trait for a type, that type should call [`Hasher::write_u64`] exactly *once*
/// in its [`Hash`] implementation. In writing that `u64`, it should *distribute the entropy of the key space*\[1\] across
/// the *whole 64 bits* (but in particular the very lowest and very highest bits are most important)!
/// Actually distributing entropy well is very important if you are going to use a [`NoHashHasher`] with the
/// Rust `std::HashMap` implementation, which is used internally by all the hash-based maps and sets provided by this crate.
/// In addition, it's important to note that this *should not* be used in cases where hash DOS attacks are a concern, and that it is
/// possible to get [unintentionally quadratic behavior] when reading from one map and writing to another when they both use a
/// [`NoHashHasher`].
///
/// You likely **should not** use a raw u8, u16 or u32 cast to a u64, or even an incrementing u64 counter and write it to the `NoHashHasher`,
/// because while you may get good entropy in the lowest bits (good!) you will get no entropy in the highest 7 bits (bad!), which are used
/// by the SwissTable-type implementation to disambiguate between items within the same "group" in parallel.
/// In particular, it is important to have good entropy both in the *lowest* and *highest* bits
/// of the u64, since the lowest bits will be used to select the index of the bucket (after truncating via modulo arithmetic to the capacity
/// of the collection) and the highest 7 bits will be used to quickly disambiguate collisions that end up at the same index after that
/// modulus.
///
/// That being said, sometimes in a particular use case can still be faster using a [`NoHashHasher`], so if you suspect it might then try benchmarking
/// and see :)
///
/// The best way to guarantee those properties is if you've already used a good hash function and the type you want to make [`NoHashable`] is therefore
/// already *in itself* a "cached" u64 hash. This is possible if you are generating and handing out handles yourself or are already precomputing hashes
/// for another reason. Otherwise, it may be better to use an `IntegralHasher` (TODO: actually expose this once `ahash` PR lands)
/// which *does* do hashing, but in a way specialized to be fast and high-quality for integer types.
///
/// \[1\] this means that for all the possible values of the set of keys you may want to insert into the table,
/// the bits changed by those values get distributed to change a uniform distribution of the full 64 bits.
///
/// # Example
///
/// ```
/// use core::hash::{Hash, Hasher};
/// use kollect::UnorderedNoHashMap;
/// use kollect::NoHashable;
///
/// /// Stores the pre-hashed hash of a string
/// #[derive(PartialEq, Eq, Clone, Copy)]
/// struct MyNoHashKey(u64);
///
/// // to create a key, we hash a string
/// impl<'a> From<&'a str> for MyNoHashKey {
/// fn from(string: &'a str) -> Self {
/// // the std hashmap DefaultHasher is guaranteed to be the same/deterministic hash when created through `new`
/// let mut hasher = std::collections::hash_map::DefaultHasher::new();
/// string.hash(&mut hasher);
/// Self(hasher.finish())
/// }
/// }
///
/// // just pass through the already-hashed u64. it's best to implement manually so we ensure it actually just calls `write_u64` once.
/// impl Hash for MyNoHashKey {
/// fn hash<H: Hasher>(&self, hasher: &mut H) {
/// hasher.write_u64(self.0)
/// }
/// }
///
/// // since our type is indeed writing a well-distributed u64, this is okay to implement!
/// impl NoHashable for MyNoHashKey {}
///
/// let mut m = UnorderedNoHashMap::<MyNoHashKey, String>::default();
///
/// let string1 = "some string";
/// let string1_key = MyNoHashKey::from(string1);
///
/// let string2 = "some other string";
/// let string2_key = MyNoHashKey::from(string2);
///
/// // this doesn't actually do any hashing!
/// m.insert(string1_key, string1.to_owned());
/// m.insert(string2_key, string2.to_owned());
///
/// // and neither does accessing!
/// assert_eq!(Some("some string"), m.get(&string1_key).map(String::as_str));
/// assert_eq!(Some("some other string"), m.get(&string2_key).map(String::as_str));
/// ```
///
/// [unintentionally quadratic behavior]: https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion
/// A hasher that does nothing. Use one as the hasher in a hash-table-based collection by using a [`BuildNoHashHasher`] as the third generic type
/// of the collection. See [`NoHashable`] for more information on which types can be hashed by this type of hasher.
;
/// A [`BuildHasher`] that creates [`NoHashHasher`]s. See docs of [`NoHashable`] for more information and an example.
;