1 | //! This module exists to isolate [`RandomState`] and [`DefaultHasher`] outside of the |
2 | //! [`collections`] module without actually publicly exporting them, so that parts of that |
3 | //! implementation can more easily be moved to the [`alloc`] crate. |
4 | //! |
5 | //! Although its items are public and contain stability attributes, they can't actually be accessed |
6 | //! outside this crate. |
7 | //! |
8 | //! [`collections`]: crate::collections |
9 | #[allow (deprecated)] |
10 | use super::{BuildHasher, Hasher, SipHasher13}; |
11 | use crate::cell::Cell; |
12 | use crate::fmt; |
13 | use crate::sys; |
14 | |
15 | /// `RandomState` is the default state for [`HashMap`] types. |
16 | /// |
17 | /// A particular instance `RandomState` will create the same instances of |
18 | /// [`Hasher`], but the hashers created by two different `RandomState` |
19 | /// instances are unlikely to produce the same result for the same values. |
20 | /// |
21 | /// [`HashMap`]: crate::collections::HashMap |
22 | /// |
23 | /// # Examples |
24 | /// |
25 | /// ``` |
26 | /// use std::collections::HashMap; |
27 | /// use std::hash::RandomState; |
28 | /// |
29 | /// let s = RandomState::new(); |
30 | /// let mut map = HashMap::with_hasher(s); |
31 | /// map.insert(1, 2); |
32 | /// ``` |
33 | #[stable (feature = "hashmap_build_hasher" , since = "1.7.0" )] |
34 | #[derive (Clone)] |
35 | pub struct RandomState { |
36 | k0: u64, |
37 | k1: u64, |
38 | } |
39 | |
40 | impl RandomState { |
41 | /// Constructs a new `RandomState` that is initialized with random keys. |
42 | /// |
43 | /// # Examples |
44 | /// |
45 | /// ``` |
46 | /// use std::hash::RandomState; |
47 | /// |
48 | /// let s = RandomState::new(); |
49 | /// ``` |
50 | #[inline ] |
51 | #[allow (deprecated)] |
52 | // rand |
53 | #[must_use ] |
54 | #[stable (feature = "hashmap_build_hasher" , since = "1.7.0" )] |
55 | pub fn new() -> RandomState { |
56 | // Historically this function did not cache keys from the OS and instead |
57 | // simply always called `rand::thread_rng().gen()` twice. In #31356 it |
58 | // was discovered, however, that because we re-seed the thread-local RNG |
59 | // from the OS periodically that this can cause excessive slowdown when |
60 | // many hash maps are created on a thread. To solve this performance |
61 | // trap we cache the first set of randomly generated keys per-thread. |
62 | // |
63 | // Later in #36481 it was discovered that exposing a deterministic |
64 | // iteration order allows a form of DOS attack. To counter that we |
65 | // increment one of the seeds on every RandomState creation, giving |
66 | // every corresponding HashMap a different iteration order. |
67 | thread_local!(static KEYS: Cell<(u64, u64)> = { |
68 | Cell::new(sys::hashmap_random_keys()) |
69 | }); |
70 | |
71 | KEYS.with(|keys| { |
72 | let (k0, k1) = keys.get(); |
73 | keys.set((k0.wrapping_add(1), k1)); |
74 | RandomState { k0, k1 } |
75 | }) |
76 | } |
77 | } |
78 | |
79 | #[stable (feature = "hashmap_build_hasher" , since = "1.7.0" )] |
80 | impl BuildHasher for RandomState { |
81 | type Hasher = DefaultHasher; |
82 | #[inline ] |
83 | #[allow (deprecated)] |
84 | fn build_hasher(&self) -> DefaultHasher { |
85 | DefaultHasher(SipHasher13::new_with_keys(self.k0, self.k1)) |
86 | } |
87 | } |
88 | |
89 | /// The default [`Hasher`] used by [`RandomState`]. |
90 | /// |
91 | /// The internal algorithm is not specified, and so it and its hashes should |
92 | /// not be relied upon over releases. |
93 | #[allow (deprecated)] |
94 | #[derive (Clone, Debug)] |
95 | #[stable (feature = "hashmap_build_hasher" , since = "1.7.0" )] |
96 | pub struct DefaultHasher(SipHasher13); |
97 | |
98 | impl DefaultHasher { |
99 | /// Creates a new `DefaultHasher`. |
100 | /// |
101 | /// This hasher is not guaranteed to be the same as all other |
102 | /// `DefaultHasher` instances, but is the same as all other `DefaultHasher` |
103 | /// instances created through `new` or `default`. |
104 | #[stable (feature = "hashmap_default_hasher" , since = "1.13.0" )] |
105 | #[inline ] |
106 | #[allow (deprecated)] |
107 | #[rustc_const_unstable (feature = "const_hash" , issue = "104061" )] |
108 | #[must_use ] |
109 | pub const fn new() -> DefaultHasher { |
110 | DefaultHasher(SipHasher13::new_with_keys(key0:0, key1:0)) |
111 | } |
112 | } |
113 | |
114 | #[stable (feature = "hashmap_default_hasher" , since = "1.13.0" )] |
115 | impl Default for DefaultHasher { |
116 | /// Creates a new `DefaultHasher` using [`new`]. |
117 | /// See its documentation for more. |
118 | /// |
119 | /// [`new`]: DefaultHasher::new |
120 | #[inline ] |
121 | fn default() -> DefaultHasher { |
122 | DefaultHasher::new() |
123 | } |
124 | } |
125 | |
126 | #[stable (feature = "hashmap_default_hasher" , since = "1.13.0" )] |
127 | impl Hasher for DefaultHasher { |
128 | // The underlying `SipHasher13` doesn't override the other |
129 | // `write_*` methods, so it's ok not to forward them here. |
130 | |
131 | #[inline ] |
132 | fn write(&mut self, msg: &[u8]) { |
133 | self.0.write(bytes:msg) |
134 | } |
135 | |
136 | #[inline ] |
137 | fn write_str(&mut self, s: &str) { |
138 | self.0.write_str(s); |
139 | } |
140 | |
141 | #[inline ] |
142 | fn finish(&self) -> u64 { |
143 | self.0.finish() |
144 | } |
145 | } |
146 | |
147 | #[stable (feature = "hashmap_build_hasher" , since = "1.7.0" )] |
148 | impl Default for RandomState { |
149 | /// Constructs a new `RandomState`. |
150 | #[inline ] |
151 | fn default() -> RandomState { |
152 | RandomState::new() |
153 | } |
154 | } |
155 | |
156 | #[stable (feature = "std_debug" , since = "1.16.0" )] |
157 | impl fmt::Debug for RandomState { |
158 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
159 | f.debug_struct(name:"RandomState" ).finish_non_exhaustive() |
160 | } |
161 | } |
162 | |