std/hash/
random.rs

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
10use super::{BuildHasher, Hasher, SipHasher13};
11use crate::cell::Cell;
12use crate::fmt;
13use crate::sys::random::hashmap_random_keys;
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(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    fn build_hasher(&self) -> DefaultHasher {
84        DefaultHasher(SipHasher13::new_with_keys(self.k0, self.k1))
85    }
86}
87
88/// The default [`Hasher`] used by [`RandomState`].
89///
90/// The internal algorithm is not specified, and so it and its hashes should
91/// not be relied upon over releases.
92#[derive(Clone, Debug)]
93#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
94pub struct DefaultHasher(SipHasher13);
95
96impl DefaultHasher {
97    /// Creates a new `DefaultHasher`.
98    ///
99    /// This hasher is not guaranteed to be the same as all other
100    /// `DefaultHasher` instances, but is the same as all other `DefaultHasher`
101    /// instances created through `new` or `default`.
102    #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
103    #[inline]
104    #[rustc_const_unstable(feature = "const_default", issue = "143894")]
105    #[must_use]
106    pub const fn new() -> DefaultHasher {
107        DefaultHasher(SipHasher13::new_with_keys(0, 0))
108    }
109}
110
111#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
112#[rustc_const_unstable(feature = "const_default", issue = "143894")]
113impl const Default for DefaultHasher {
114    /// Creates a new `DefaultHasher` using [`new`].
115    /// See its documentation for more.
116    ///
117    /// [`new`]: DefaultHasher::new
118    #[inline]
119    fn default() -> DefaultHasher {
120        DefaultHasher::new()
121    }
122}
123
124#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
125impl Hasher for DefaultHasher {
126    // The underlying `SipHasher13` doesn't override the other
127    // `write_*` methods, so it's ok not to forward them here.
128
129    #[inline]
130    fn write(&mut self, msg: &[u8]) {
131        self.0.write(msg)
132    }
133
134    #[inline]
135    fn write_str(&mut self, s: &str) {
136        self.0.write_str(s);
137    }
138
139    #[inline]
140    fn finish(&self) -> u64 {
141        self.0.finish()
142    }
143}
144
145#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
146impl Default for RandomState {
147    /// Constructs a new `RandomState`.
148    #[inline]
149    fn default() -> RandomState {
150        RandomState::new()
151    }
152}
153
154#[stable(feature = "std_debug", since = "1.16.0")]
155impl fmt::Debug for RandomState {
156    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
157        f.debug_struct("RandomState").finish_non_exhaustive()
158    }
159}
std/hash/random.rs

std/hash/
random.rs
