random.rs - source
Description: Source of the Rust file `library/std/src/hash/random.rs`.

#
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    #[rustc_const_unstable(feature = "const_default", issue = "143894")]
    109    #[must_use]
    110    pub const fn new() -> DefaultHasher {
    111        DefaultHasher(SipHasher13::new_with_keys(0, 0))
    112    }
    113}
    114
    115#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
    116#[rustc_const_unstable(feature = "const_default", issue = "143894")]
    117impl const Default for DefaultHasher {
    118    /// Creates a new `DefaultHasher` using [`new`].
    119    /// See its documentation for more.
    120    ///
    121    /// [`new`]: DefaultHasher::new
    122    #[inline]
    123    fn default() -> DefaultHasher {
    124        DefaultHasher::new()
    125    }
    126}
    127
    128#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
    129impl Hasher for DefaultHasher {
    130    // The underlying `SipHasher13` doesn't override the other
    131    // `write_*` methods, so it's ok not to forward them here.
    132
    133    #[inline]
    134    fn write(&mut self, msg: &[u8]) {
    135        self.0.write(msg)
    136    }
    137
    138    #[inline]
    139    fn write_str(&mut self, s: &str) {
    140        self.0.write_str(s);
    141    }
    142
    143    #[inline]
    144    fn finish(&self) -> u64 {
    145        self.0.finish()
    146    }
    147}
    148
    149#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
    150impl Default for RandomState {
    151    /// Constructs a new `RandomState`.
    152    #[inline]
    153    fn default() -> RandomState {
    154        RandomState::new()
    155    }
    156}
    157
    158#[stable(feature = "std_debug", since = "1.16.0")]
    159impl fmt::Debug for RandomState {
    160    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    161        f.debug_struct("RandomState").finish_non_exhaustive()
    162    }
    163}