rustc_hash/
random_state.rs

1use std::collections::{HashMap, HashSet};
2
3use crate::FxHasher;
4
5/// Type alias for a hashmap using the `fx` hash algorithm with [`FxRandomState`].
6pub type FxHashMapRand<K, V> = HashMap<K, V, FxRandomState>;
7
8/// Type alias for a hashmap using the `fx` hash algorithm with [`FxRandomState`].
9pub type FxHashSetRand<V> = HashSet<V, FxRandomState>;
10
11/// `FxRandomState` is an alternative state for `HashMap` types.
12///
13/// A particular instance `FxRandomState` will create the same instances of
14/// [`Hasher`], but the hashers created by two different `FxRandomState`
15/// instances are unlikely to produce the same result for the same values.
16#[derive(Clone)]
17pub struct FxRandomState {
18    seed: usize,
19}
20
21impl FxRandomState {
22    /// Constructs a new `FxRandomState` that is initialized with random seed.
23    pub fn new() -> FxRandomState {
24        use rand::Rng;
25        use std::{cell::Cell, thread_local};
26
27        // This mirrors what `std::collections::hash_map::RandomState` does, as of 2024-01-14.
28        //
29        // Basically
30        // 1. Cache result of the rng in a thread local, so repeatedly
31        //    creating maps is cheaper
32        // 2. Change the cached result on every creation, so maps created
33        //    on the same thread don't have the same iteration order
34        thread_local!(static SEED: Cell<usize> = {
35            Cell::new(rand::thread_rng().gen())
36        });
37
38        SEED.with(|seed| {
39            let s = seed.get();
40            seed.set(s.wrapping_add(1));
41            FxRandomState { seed: s }
42        })
43    }
44}
45
46impl core::hash::BuildHasher for FxRandomState {
47    type Hasher = FxHasher;
48
49    fn build_hasher(&self) -> Self::Hasher {
50        FxHasher::with_seed(self.seed)
51    }
52}
53
54impl Default for FxRandomState {
55    fn default() -> Self {
56        Self::new()
57    }
58}
59
60#[cfg(test)]
61mod tests {
62    use std::thread;
63
64    use crate::FxHashMapRand;
65
66    #[test]
67    fn cloned_random_states_are_equal() {
68        let a = FxHashMapRand::<&str, u32>::default();
69        let b = a.clone();
70
71        assert_eq!(a.hasher().seed, b.hasher().seed);
72    }
73
74    #[test]
75    fn random_states_are_different() {
76        let a = FxHashMapRand::<&str, u32>::default();
77        let b = FxHashMapRand::<&str, u32>::default();
78
79        // That's the whole point of them being random!
80        //
81        // N.B.: `FxRandomState` uses a thread-local set to a random value and then incremented,
82        //       which means that this is *guaranteed* to pass :>
83        assert_ne!(a.hasher().seed, b.hasher().seed);
84    }
85
86    #[test]
87    fn random_states_are_different_cross_thread() {
88        // This is similar to the test above, but uses two different threads, so they both get
89        // completely random, unrelated values.
90        //
91        // This means that this test is technically flaky, but the probability of it failing is
92        // `1 / 2.pow(bit_size_of::<usize>())`. Or 1/1.7e19 for 64 bit platforms or 1/4294967295
93        // for 32 bit platforms. I suppose this is acceptable.
94        let a = FxHashMapRand::<&str, u32>::default();
95        let b = thread::spawn(|| FxHashMapRand::<&str, u32>::default())
96            .join()
97            .unwrap();
98
99        assert_ne!(a.hasher().seed, b.hasher().seed);
100    }
101}
rustc_hash/random_state.rs

rustc_hash/
random_state.rs
