summaryrefslogtreecommitdiffstats
path: root/library/std/src/collections/hash
diff options
context:
space:
mode:
Diffstat (limited to 'library/std/src/collections/hash')
-rw-r--r--library/std/src/collections/hash/map.rs157
-rw-r--r--library/std/src/collections/hash/map/tests.rs2
-rw-r--r--library/std/src/collections/hash/set.rs10
-rw-r--r--library/std/src/collections/hash/set/tests.rs2
4 files changed, 11 insertions, 160 deletions
diff --git a/library/std/src/collections/hash/map.rs b/library/std/src/collections/hash/map.rs
index 4d109285d..39e94902c 100644
--- a/library/std/src/collections/hash/map.rs
+++ b/library/std/src/collections/hash/map.rs
@@ -6,16 +6,13 @@ use self::Entry::*;
use hashbrown::hash_map as base;
use crate::borrow::Borrow;
-use crate::cell::Cell;
use crate::collections::TryReserveError;
use crate::collections::TryReserveErrorKind;
use crate::error::Error;
use crate::fmt::{self, Debug};
-#[allow(deprecated)]
-use crate::hash::{BuildHasher, Hash, Hasher, SipHasher13};
+use crate::hash::{BuildHasher, Hash, RandomState};
use crate::iter::FusedIterator;
use crate::ops::Index;
-use crate::sys;
/// A [hash map] implemented with quadratic probing and SIMD lookup.
///
@@ -274,7 +271,7 @@ impl<K, V, S> HashMap<K, V, S> {
///
/// ```
/// use std::collections::HashMap;
- /// use std::collections::hash_map::RandomState;
+ /// use std::hash::RandomState;
///
/// let s = RandomState::new();
/// let mut map = HashMap::with_hasher(s);
@@ -306,7 +303,7 @@ impl<K, V, S> HashMap<K, V, S> {
///
/// ```
/// use std::collections::HashMap;
- /// use std::collections::hash_map::RandomState;
+ /// use std::hash::RandomState;
///
/// let s = RandomState::new();
/// let mut map = HashMap::with_capacity_and_hasher(10, s);
@@ -717,7 +714,7 @@ impl<K, V, S> HashMap<K, V, S> {
///
/// ```
/// use std::collections::HashMap;
- /// use std::collections::hash_map::RandomState;
+ /// use std::hash::RandomState;
///
/// let hasher = RandomState::new();
/// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);
@@ -3072,152 +3069,6 @@ where
}
}
-/// `RandomState` is the default state for [`HashMap`] types.
-///
-/// A particular instance `RandomState` will create the same instances of
-/// [`Hasher`], but the hashers created by two different `RandomState`
-/// instances are unlikely to produce the same result for the same values.
-///
-/// # Examples
-///
-/// ```
-/// use std::collections::HashMap;
-/// use std::collections::hash_map::RandomState;
-///
-/// let s = RandomState::new();
-/// let mut map = HashMap::with_hasher(s);
-/// map.insert(1, 2);
-/// ```
-#[derive(Clone)]
-#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
-pub struct RandomState {
- k0: u64,
- k1: u64,
-}
-
-impl RandomState {
- /// Constructs a new `RandomState` that is initialized with random keys.
- ///
- /// # Examples
- ///
- /// ```
- /// use std::collections::hash_map::RandomState;
- ///
- /// let s = RandomState::new();
- /// ```
- #[inline]
- #[allow(deprecated)]
- // rand
- #[must_use]
- #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
- pub fn new() -> RandomState {
- // Historically this function did not cache keys from the OS and instead
- // simply always called `rand::thread_rng().gen()` twice. In #31356 it
- // was discovered, however, that because we re-seed the thread-local RNG
- // from the OS periodically that this can cause excessive slowdown when
- // many hash maps are created on a thread. To solve this performance
- // trap we cache the first set of randomly generated keys per-thread.
- //
- // Later in #36481 it was discovered that exposing a deterministic
- // iteration order allows a form of DOS attack. To counter that we
- // increment one of the seeds on every RandomState creation, giving
- // every corresponding HashMap a different iteration order.
- thread_local!(static KEYS: Cell<(u64, u64)> = {
- Cell::new(sys::hashmap_random_keys())
- });
-
- KEYS.with(|keys| {
- let (k0, k1) = keys.get();
- keys.set((k0.wrapping_add(1), k1));
- RandomState { k0, k1 }
- })
- }
-}
-
-#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
-impl BuildHasher for RandomState {
- type Hasher = DefaultHasher;
- #[inline]
- #[allow(deprecated)]
- fn build_hasher(&self) -> DefaultHasher {
- DefaultHasher(SipHasher13::new_with_keys(self.k0, self.k1))
- }
-}
-
-/// The default [`Hasher`] used by [`RandomState`].
-///
-/// The internal algorithm is not specified, and so it and its hashes should
-/// not be relied upon over releases.
-#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
-#[allow(deprecated)]
-#[derive(Clone, Debug)]
-pub struct DefaultHasher(SipHasher13);
-
-impl DefaultHasher {
- /// Creates a new `DefaultHasher`.
- ///
- /// This hasher is not guaranteed to be the same as all other
- /// `DefaultHasher` instances, but is the same as all other `DefaultHasher`
- /// instances created through `new` or `default`.
- #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
- #[inline]
- #[allow(deprecated)]
- #[rustc_const_unstable(feature = "const_hash", issue = "104061")]
- #[must_use]
- pub const fn new() -> DefaultHasher {
- DefaultHasher(SipHasher13::new_with_keys(0, 0))
- }
-}
-
-#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
-impl Default for DefaultHasher {
- /// Creates a new `DefaultHasher` using [`new`].
- /// See its documentation for more.
- ///
- /// [`new`]: DefaultHasher::new
- #[inline]
- fn default() -> DefaultHasher {
- DefaultHasher::new()
- }
-}
-
-#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
-impl Hasher for DefaultHasher {
- // The underlying `SipHasher13` doesn't override the other
- // `write_*` methods, so it's ok not to forward them here.
-
- #[inline]
- fn write(&mut self, msg: &[u8]) {
- self.0.write(msg)
- }
-
- #[inline]
- fn write_str(&mut self, s: &str) {
- self.0.write_str(s);
- }
-
- #[inline]
- fn finish(&self) -> u64 {
- self.0.finish()
- }
-}
-
-#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
-impl Default for RandomState {
- /// Constructs a new `RandomState`.
- #[inline]
- fn default() -> RandomState {
- RandomState::new()
- }
-}
-
-#[stable(feature = "std_debug", since = "1.16.0")]
-impl fmt::Debug for RandomState {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- f.debug_struct("RandomState").finish_non_exhaustive()
- }
-}
-
#[inline]
fn map_entry<'a, K: 'a, V: 'a>(raw: base::RustcEntry<'a, K, V>) -> Entry<'a, K, V> {
match raw {
diff --git a/library/std/src/collections/hash/map/tests.rs b/library/std/src/collections/hash/map/tests.rs
index 91a3776e7..8585376ab 100644
--- a/library/std/src/collections/hash/map/tests.rs
+++ b/library/std/src/collections/hash/map/tests.rs
@@ -1,8 +1,8 @@
use super::Entry::{Occupied, Vacant};
use super::HashMap;
-use super::RandomState;
use crate::assert_matches::assert_matches;
use crate::cell::RefCell;
+use crate::hash::RandomState;
use crate::test_helpers::test_rng;
use rand::Rng;
use realstd::collections::TryReserveErrorKind::*;
diff --git a/library/std/src/collections/hash/set.rs b/library/std/src/collections/hash/set.rs
index 6a87f6e5f..8bc596082 100644
--- a/library/std/src/collections/hash/set.rs
+++ b/library/std/src/collections/hash/set.rs
@@ -6,11 +6,11 @@ use hashbrown::hash_set as base;
use crate::borrow::Borrow;
use crate::collections::TryReserveError;
use crate::fmt;
-use crate::hash::{BuildHasher, Hash};
+use crate::hash::{BuildHasher, Hash, RandomState};
use crate::iter::{Chain, FusedIterator};
use crate::ops::{BitAnd, BitOr, BitXor, Sub};
-use super::map::{map_try_reserve_error, RandomState};
+use super::map::map_try_reserve_error;
/// A [hash set] implemented as a `HashMap` where the value is `()`.
///
@@ -361,7 +361,7 @@ impl<T, S> HashSet<T, S> {
///
/// ```
/// use std::collections::HashSet;
- /// use std::collections::hash_map::RandomState;
+ /// use std::hash::RandomState;
///
/// let s = RandomState::new();
/// let mut set = HashSet::with_hasher(s);
@@ -393,7 +393,7 @@ impl<T, S> HashSet<T, S> {
///
/// ```
/// use std::collections::HashSet;
- /// use std::collections::hash_map::RandomState;
+ /// use std::hash::RandomState;
///
/// let s = RandomState::new();
/// let mut set = HashSet::with_capacity_and_hasher(10, s);
@@ -411,7 +411,7 @@ impl<T, S> HashSet<T, S> {
///
/// ```
/// use std::collections::HashSet;
- /// use std::collections::hash_map::RandomState;
+ /// use std::hash::RandomState;
///
/// let hasher = RandomState::new();
/// let set: HashSet<i32> = HashSet::with_hasher(hasher);
diff --git a/library/std/src/collections/hash/set/tests.rs b/library/std/src/collections/hash/set/tests.rs
index e0cd80b44..208f61e75 100644
--- a/library/std/src/collections/hash/set/tests.rs
+++ b/library/std/src/collections/hash/set/tests.rs
@@ -1,6 +1,6 @@
-use super::super::map::RandomState;
use super::HashSet;
+use crate::hash::RandomState;
use crate::panic::{catch_unwind, AssertUnwindSafe};
use crate::sync::atomic::{AtomicU32, Ordering};
use crate::sync::Arc;
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-03 11:29:54 +0000