hashbrown/
lib.rs

1//! This crate is a Rust port of Google's high-performance [SwissTable] hash
2//! map, adapted to make it a drop-in replacement for Rust's standard `HashMap`
3//! and `HashSet` types.
4//!
5//! The original C++ version of [SwissTable] can be found [here], and this
6//! [CppCon talk] gives an overview of how the algorithm works.
7//!
8//! [SwissTable]: https://abseil.io/blog/20180927-swisstables
9//! [here]: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h
10//! [CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4
11
12#![no_std]
13#![cfg_attr(
14    feature = "nightly",
15    feature(
16        test,
17        core_intrinsics,
18        dropck_eyepatch,
19        min_specialization,
20        extend_one,
21        allocator_api,
22        slice_ptr_get,
23        maybe_uninit_array_assume_init,
24        strict_provenance
25    )
26)]
27#![allow(
28    clippy::doc_markdown,
29    clippy::module_name_repetitions,
30    clippy::must_use_candidate,
31    clippy::option_if_let_else,
32    clippy::redundant_else,
33    clippy::manual_map,
34    clippy::missing_safety_doc,
35    clippy::missing_errors_doc
36)]
37#![warn(missing_docs)]
38#![warn(rust_2018_idioms)]
39#![cfg_attr(feature = "nightly", warn(fuzzy_provenance_casts))]
40#![cfg_attr(feature = "nightly", allow(internal_features))]
41
42/// Default hasher for [`HashMap`] and [`HashSet`].
43#[cfg(feature = "default-hasher")]
44pub type DefaultHashBuilder = foldhash::fast::RandomState;
45
46/// Dummy default hasher for [`HashMap`] and [`HashSet`].
47#[cfg(not(feature = "default-hasher"))]
48pub enum DefaultHashBuilder {}
49
50#[cfg(test)]
51#[macro_use]
52extern crate std;
53
54#[cfg_attr(test, macro_use)]
55extern crate alloc;
56
57#[cfg(feature = "nightly")]
58#[cfg(doctest)]
59doc_comment::doctest!("../README.md");
60
61#[macro_use]
62mod macros;
63
64mod raw;
65
66mod external_trait_impls;
67mod map;
68#[cfg(feature = "raw-entry")]
69mod raw_entry;
70#[cfg(feature = "rustc-internal-api")]
71mod rustc_entry;
72mod scopeguard;
73mod set;
74mod table;
75
76pub mod hash_map {
77    //! A hash map implemented with quadratic probing and SIMD lookup.
78    pub use crate::map::*;
79
80    #[cfg(feature = "rustc-internal-api")]
81    pub use crate::rustc_entry::*;
82
83    #[cfg(feature = "rayon")]
84    /// [rayon]-based parallel iterator types for hash maps.
85    /// You will rarely need to interact with it directly unless you have need
86    /// to name one of the iterator types.
87    ///
88    /// [rayon]: https://docs.rs/rayon/1.0/rayon
89    pub mod rayon {
90        pub use crate::external_trait_impls::rayon::map::*;
91    }
92}
93pub mod hash_set {
94    //! A hash set implemented as a `HashMap` where the value is `()`.
95    pub use crate::set::*;
96
97    #[cfg(feature = "rayon")]
98    /// [rayon]-based parallel iterator types for hash sets.
99    /// You will rarely need to interact with it directly unless you have need
100    /// to name one of the iterator types.
101    ///
102    /// [rayon]: https://docs.rs/rayon/1.0/rayon
103    pub mod rayon {
104        pub use crate::external_trait_impls::rayon::set::*;
105    }
106}
107pub mod hash_table {
108    //! A hash table implemented with quadratic probing and SIMD lookup.
109    pub use crate::table::*;
110
111    #[cfg(feature = "rayon")]
112    /// [rayon]-based parallel iterator types for hash tables.
113    /// You will rarely need to interact with it directly unless you have need
114    /// to name one of the iterator types.
115    ///
116    /// [rayon]: https://docs.rs/rayon/1.0/rayon
117    pub mod rayon {
118        pub use crate::external_trait_impls::rayon::table::*;
119    }
120}
121
122pub use crate::map::HashMap;
123pub use crate::set::HashSet;
124pub use crate::table::HashTable;
125
126#[cfg(feature = "equivalent")]
127pub use equivalent::Equivalent;
128
129// This is only used as a fallback when building as part of `std`.
130#[cfg(not(feature = "equivalent"))]
131/// Key equivalence trait.
132///
133/// This trait defines the function used to compare the input value with the
134/// map keys (or set values) during a lookup operation such as [`HashMap::get`]
135/// or [`HashSet::contains`].
136/// It is provided with a blanket implementation based on the
137/// [`Borrow`](core::borrow::Borrow) trait.
138///
139/// # Correctness
140///
141/// Equivalent values must hash to the same value.
142pub trait Equivalent<K: ?Sized> {
143    /// Checks if this value is equivalent to the given key.
144    ///
145    /// Returns `true` if both values are equivalent, and `false` otherwise.
146    ///
147    /// # Correctness
148    ///
149    /// When this function returns `true`, both `self` and `key` must hash to
150    /// the same value.
151    fn equivalent(&self, key: &K) -> bool;
152}
153
154#[cfg(not(feature = "equivalent"))]
155impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q
156where
157    Q: Eq,
158    K: core::borrow::Borrow<Q>,
159{
160    fn equivalent(&self, key: &K) -> bool {
161        self == key.borrow()
162    }
163}
164
165/// The error type for `try_reserve` methods.
166#[derive(Clone, PartialEq, Eq, Debug)]
167pub enum TryReserveError {
168    /// Error due to the computed capacity exceeding the collection's maximum
169    /// (usually `isize::MAX` bytes).
170    CapacityOverflow,
171
172    /// The memory allocator returned an error
173    AllocError {
174        /// The layout of the allocation request that failed.
175        layout: alloc::alloc::Layout,
176    },
177}
hashbrown/lib.rs

hashbrown/
lib.rs
