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)]
10use super::{BuildHasher, Hasher, SipHasher13};
11use crate::cell::Cell;
12use crate::fmt;
13use 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)]
35pub struct RandomState {
36 k0: u64,
37 k1: u64,
38}
39
40impl 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")]
80impl 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")]
96pub struct DefaultHasher(SipHasher13);
97
98impl 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")]
115impl 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")]
127impl 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")]
148impl 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")]
157impl 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