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
10#[allow(deprecated)]
11use super::{BuildHasher, Hasher, SipHasher13};
12use crate::cell::Cell;
13use crate::fmt;
14use crate::sys::random::hashmap_random_keys;
15
16/// `RandomState` is the default state for [`HashMap`] types.
17///
18/// A particular instance `RandomState` will create the same instances of
19/// [`Hasher`], but the hashers created by two different `RandomState`
20/// instances are unlikely to produce the same result for the same values.
21///
22/// [`HashMap`]: crate::collections::HashMap
23///
24/// # Examples
25///
26/// ```
27/// use std::collections::HashMap;
28/// use std::hash::RandomState;
29///
30/// let s = RandomState::new();
31/// let mut map = HashMap::with_hasher(s);
32/// map.insert(1, 2);
33/// ```
34#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
35#[derive(Clone)]
36pub struct RandomState {
37    k0: u64,
38    k1: u64,
39}
40
41impl RandomState {
42    /// Constructs a new `RandomState` that is initialized with random keys.
43    ///
44    /// # Examples
45    ///
46    /// ```
47    /// use std::hash::RandomState;
48    ///
49    /// let s = RandomState::new();
50    /// ```
51    #[inline]
52    #[allow(deprecated)]
53    // rand
54    #[must_use]
55    #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
56    pub fn new() -> RandomState {
57        // Historically this function did not cache keys from the OS and instead
58        // simply always called `rand::thread_rng().gen()` twice. In #31356 it
59        // was discovered, however, that because we re-seed the thread-local RNG
60        // from the OS periodically that this can cause excessive slowdown when
61        // many hash maps are created on a thread. To solve this performance
62        // trap we cache the first set of randomly generated keys per-thread.
63        //
64        // Later in #36481 it was discovered that exposing a deterministic
65        // iteration order allows a form of DOS attack. To counter that we
66        // increment one of the seeds on every RandomState creation, giving
67        // every corresponding HashMap a different iteration order.
68        thread_local!(static KEYS: Cell<(u64, u64)> = {
69            Cell::new(hashmap_random_keys())
70        });
71
72        KEYS.with(|keys| {
73            let (k0, k1) = keys.get();
74            keys.set((k0.wrapping_add(1), k1));
75            RandomState { k0, k1 }
76        })
77    }
78}
79
80#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
81impl BuildHasher for RandomState {
82    type Hasher = DefaultHasher;
83    #[inline]
84    #[allow(deprecated)]
85    fn build_hasher(&self) -> DefaultHasher {
86        DefaultHasher(SipHasher13::new_with_keys(self.k0, self.k1))
87    }
88}
89
90/// The default [`Hasher`] used by [`RandomState`].
91///
92/// The internal algorithm is not specified, and so it and its hashes should
93/// not be relied upon over releases.
94#[allow(deprecated)]
95#[derive(Clone, Debug)]
96#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
97pub struct DefaultHasher(SipHasher13);
98
99impl DefaultHasher {
100    /// Creates a new `DefaultHasher`.
101    ///
102    /// This hasher is not guaranteed to be the same as all other
103    /// `DefaultHasher` instances, but is the same as all other `DefaultHasher`
104    /// instances created through `new` or `default`.
105    #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
106    #[inline]
107    #[allow(deprecated)]
108    #[must_use]
109    pub fn new() -> DefaultHasher {
110        DefaultHasher(SipHasher13::new_with_keys(0, 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(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("RandomState").finish_non_exhaustive()
160    }
161}