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

#
core/hash/
mod.rs

    1//! Generic hashing support.
    2//!
    3//! This module provides a generic way to compute the [hash] of a value.
    4//! Hashes are most commonly used with [`HashMap`] and [`HashSet`].
    5//!
    6//! [hash]: https://en.wikipedia.org/wiki/Hash_function
    7//! [`HashMap`]: ../../std/collections/struct.HashMap.html
    8//! [`HashSet`]: ../../std/collections/struct.HashSet.html
    9//!
    10//! The simplest way to make a type hashable is to use `#[derive(Hash)]`:
    11//!
    12//! # Examples
    13//!
    14//! ```rust
    15//! use std::hash::{DefaultHasher, Hash, Hasher};
    16//!
    17//! #[derive(Hash)]
    18//! struct Person {
    19//!     id: u32,
    20//!     name: String,
    21//!     phone: u64,
    22//! }
    23//!
    24//! let person1 = Person {
    25//!     id: 5,
    26//!     name: "Janet".to_string(),
    27//!     phone: 555_666_7777,
    28//! };
    29//! let person2 = Person {
    30//!     id: 5,
    31//!     name: "Bob".to_string(),
    32//!     phone: 555_666_7777,
    33//! };
    34//!
    35//! assert!(calculate_hash(&person1) != calculate_hash(&person2));
    36//!
    37//! fn calculate_hash<T: Hash>(t: &T) -> u64 {
    38//!     let mut s = DefaultHasher::new();
    39//!     t.hash(&mut s);
    40//!     s.finish()
    41//! }
    42//! ```
    43//!
    44//! If you need more control over how a value is hashed, you need to implement
    45//! the [`Hash`] trait:
    46//!
    47//! ```rust
    48//! use std::hash::{DefaultHasher, Hash, Hasher};
    49//!
    50//! struct Person {
    51//!     id: u32,
    52//!     # #[allow(dead_code)]
    53//!     name: String,
    54//!     phone: u64,
    55//! }
    56//!
    57//! impl Hash for Person {
    58//!     fn hash<H: Hasher>(&self, state: &mut H) {
    59//!         self.id.hash(state);
    60//!         self.phone.hash(state);
    61//!     }
    62//! }
    63//!
    64//! let person1 = Person {
    65//!     id: 5,
    66//!     name: "Janet".to_string(),
    67//!     phone: 555_666_7777,
    68//! };
    69//! let person2 = Person {
    70//!     id: 5,
    71//!     name: "Bob".to_string(),
    72//!     phone: 555_666_7777,
    73//! };
    74//!
    75//! assert_eq!(calculate_hash(&person1), calculate_hash(&person2));
    76//!
    77//! fn calculate_hash<T: Hash>(t: &T) -> u64 {
    78//!     let mut s = DefaultHasher::new();
    79//!     t.hash(&mut s);
    80//!     s.finish()
    81//! }
    82//! ```
    83
    84#![stable(feature = "rust1", since = "1.0.0")]
    85
    86#[stable(feature = "rust1", since = "1.0.0")]
    87#[allow(deprecated)]
    88pub use self::sip::SipHasher;
    89#[unstable(feature = "hashmap_internals", issue = "none")]
    90#[allow(deprecated)]
    91#[doc(hidden)]
    92pub use self::sip::SipHasher13;
    93use crate::{fmt, marker};
    94
    95mod sip;
    96
    97/// A hashable type.
    98///
    99/// Types implementing `Hash` are able to be [`hash`]ed with an instance of
    100/// [`Hasher`].
    101///
    102/// ## Implementing `Hash`
    103///
    104/// You can derive `Hash` with `#[derive(Hash)]` if all fields implement `Hash`.
    105/// The resulting hash will be the combination of the values from calling
    106/// [`hash`] on each field.
    107///
    108/// ```
    109/// #[derive(Hash)]
    110/// struct Rustacean {
    111///     name: String,
    112///     country: String,
    113/// }
    114/// ```
    115///
    116/// If you need more control over how a value is hashed, you can of course
    117/// implement the `Hash` trait yourself:
    118///
    119/// ```
    120/// use std::hash::{Hash, Hasher};
    121///
    122/// struct Person {
    123///     id: u32,
    124///     name: String,
    125///     phone: u64,
    126/// }
    127///
    128/// impl Hash for Person {
    129///     fn hash<H: Hasher>(&self, state: &mut H) {
    130///         self.id.hash(state);
    131///         self.phone.hash(state);
    132///     }
    133/// }
    134/// ```
    135///
    136/// ## `Hash` and `Eq`
    137///
    138/// When implementing both `Hash` and [`Eq`], it is important that the following
    139/// property holds:
    140///
    141/// ```text
    142/// k1 == k2 -> hash(k1) == hash(k2)
    143/// ```
    144///
    145/// In other words, if two keys are equal, their hashes must also be equal.
    146/// [`HashMap`] and [`HashSet`] both rely on this behavior.
    147///
    148/// Thankfully, you won't need to worry about upholding this property when
    149/// deriving both [`Eq`] and `Hash` with `#[derive(PartialEq, Eq, Hash)]`.
    150///
    151/// Violating this property is a logic error. The behavior resulting from a logic error is not
    152/// specified, but users of the trait must ensure that such logic errors do *not* result in
    153/// undefined behavior. This means that `unsafe` code **must not** rely on the correctness of these
    154/// methods.
    155///
    156/// ## Prefix collisions
    157///
    158/// Implementations of `hash` should ensure that the data they
    159/// pass to the `Hasher` are prefix-free. That is,
    160/// values which are not equal should cause two different sequences of values to be written,
    161/// and neither of the two sequences should be a prefix of the other.
    162///
    163/// For example, the standard implementation of [`Hash` for `&str`][impl] passes an extra
    164/// `0xFF` byte to the `Hasher` so that the values `("ab", "c")` and `("a",
    165/// "bc")` hash differently.
    166///
    167/// ## Portability
    168///
    169/// Due to differences in endianness and type sizes, data fed by `Hash` to a `Hasher`
    170/// should not be considered portable across platforms. Additionally the data passed by most
    171/// standard library types should not be considered stable between compiler versions.
    172///
    173/// This means tests shouldn't probe hard-coded hash values or data fed to a `Hasher` and
    174/// instead should check consistency with `Eq`.
    175///
    176/// Serialization formats intended to be portable between platforms or compiler versions should
    177/// either avoid encoding hashes or only rely on `Hash` and `Hasher` implementations that
    178/// provide additional guarantees.
    179///
    180/// [`HashMap`]: ../../std/collections/struct.HashMap.html
    181/// [`HashSet`]: ../../std/collections/struct.HashSet.html
    182/// [`hash`]: Hash::hash
    183/// [impl]: ../../std/primitive.str.html#impl-Hash-for-str
    184#[stable(feature = "rust1", since = "1.0.0")]
    185#[rustc_diagnostic_item = "Hash"]
    186pub trait Hash: marker::PointeeSized {
    187    /// Feeds this value into the given [`Hasher`].
    188    ///
    189    /// # Examples
    190    ///
    191    /// ```
    192    /// use std::hash::{DefaultHasher, Hash, Hasher};
    193    ///
    194    /// let mut hasher = DefaultHasher::new();
    195    /// 7920.hash(&mut hasher);
    196    /// println!("Hash is {:x}!", hasher.finish());
    197    /// ```
    198    #[stable(feature = "rust1", since = "1.0.0")]
    199    fn hash<H: Hasher>(&self, state: &mut H);
    200
    201    /// Feeds a slice of this type into the given [`Hasher`].
    202    ///
    203    /// This method is meant as a convenience, but its implementation is
    204    /// also explicitly left unspecified. It isn't guaranteed to be
    205    /// equivalent to repeated calls of [`hash`] and implementations of
    206    /// [`Hash`] should keep that in mind and call [`hash`] themselves
    207    /// if the slice isn't treated as a whole unit in the [`PartialEq`]
    208    /// implementation.
    209    ///
    210    /// For example, a [`VecDeque`] implementation might naïvely call
    211    /// [`as_slices`] and then [`hash_slice`] on each slice, but this
    212    /// is wrong since the two slices can change with a call to
    213    /// [`make_contiguous`] without affecting the [`PartialEq`]
    214    /// result. Since these slices aren't treated as singular
    215    /// units, and instead part of a larger deque, this method cannot
    216    /// be used.
    217    ///
    218    /// # Examples
    219    ///
    220    /// ```
    221    /// use std::hash::{DefaultHasher, Hash, Hasher};
    222    ///
    223    /// let mut hasher = DefaultHasher::new();
    224    /// let numbers = [6, 28, 496, 8128];
    225    /// Hash::hash_slice(&numbers, &mut hasher);
    226    /// println!("Hash is {:x}!", hasher.finish());
    227    /// ```
    228    ///
    229    /// [`VecDeque`]: ../../std/collections/struct.VecDeque.html
    230    /// [`as_slices`]: ../../std/collections/struct.VecDeque.html#method.as_slices
    231    /// [`make_contiguous`]: ../../std/collections/struct.VecDeque.html#method.make_contiguous
    232    /// [`hash`]: Hash::hash
    233    /// [`hash_slice`]: Hash::hash_slice
    234    #[stable(feature = "hash_slice", since = "1.3.0")]
    235    fn hash_slice<H: Hasher>(data: &[Self], state: &mut H)
    236    where
    237        Self: Sized,
    238    {
    239        for piece in data {
    240            piece.hash(state)
    241        }
    242    }
    243}
    244
    245// Separate module to reexport the macro `Hash` from prelude without the trait `Hash`.
    246pub(crate) mod macros {
    247    /// Derive macro generating an impl of the trait `Hash`.
    248    #[rustc_builtin_macro]
    249    #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
    250    #[allow_internal_unstable(core_intrinsics)]
    251    pub macro Hash($item:item) {
    252        /* compiler built-in */
    253    }
    254}
    255#[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
    256#[doc(inline)]
    257pub use macros::Hash;
    258
    259/// A trait for hashing an arbitrary stream of bytes.
    260///
    261/// Instances of `Hasher` usually represent state that is changed while hashing
    262/// data.
    263///
    264/// `Hasher` provides a fairly basic interface for retrieving the generated hash
    265/// (with [`finish`]), and writing integers as well as slices of bytes into an
    266/// instance (with [`write`] and [`write_u8`] etc.). Most of the time, `Hasher`
    267/// instances are used in conjunction with the [`Hash`] trait.
    268///
    269/// This trait provides no guarantees about how the various `write_*` methods are
    270/// defined and implementations of [`Hash`] should not assume that they work one
    271/// way or another. You cannot assume, for example, that a [`write_u32`] call is
    272/// equivalent to four calls of [`write_u8`].  Nor can you assume that adjacent
    273/// `write` calls are merged, so it's possible, for example, that
    274/// ```
    275/// # fn foo(hasher: &mut impl std::hash::Hasher) {
    276/// hasher.write(&[1, 2]);
    277/// hasher.write(&[3, 4, 5, 6]);
    278/// # }
    279/// ```
    280/// and
    281/// ```
    282/// # fn foo(hasher: &mut impl std::hash::Hasher) {
    283/// hasher.write(&[1, 2, 3, 4]);
    284/// hasher.write(&[5, 6]);
    285/// # }
    286/// ```
    287/// end up producing different hashes.
    288///
    289/// Thus to produce the same hash value, [`Hash`] implementations must ensure
    290/// for equivalent items that exactly the same sequence of calls is made -- the
    291/// same methods with the same parameters in the same order.
    292///
    293/// # Examples
    294///
    295/// ```
    296/// use std::hash::{DefaultHasher, Hasher};
    297///
    298/// let mut hasher = DefaultHasher::new();
    299///
    300/// hasher.write_u32(1989);
    301/// hasher.write_u8(11);
    302/// hasher.write_u8(9);
    303/// hasher.write(b"Huh?");
    304///
    305/// println!("Hash is {:x}!", hasher.finish());
    306/// ```
    307///
    308/// [`finish`]: Hasher::finish
    309/// [`write`]: Hasher::write
    310/// [`write_u8`]: Hasher::write_u8
    311/// [`write_u32`]: Hasher::write_u32
    312#[stable(feature = "rust1", since = "1.0.0")]
    313pub trait Hasher {
    314    /// Returns the hash value for the values written so far.
    315    ///
    316    /// Despite its name, the method does not reset the hasher’s internal
    317    /// state. Additional [`write`]s will continue from the current value.
    318    /// If you need to start a fresh hash value, you will have to create
    319    /// a new hasher.
    320    ///
    321    /// # Examples
    322    ///
    323    /// ```
    324    /// use std::hash::{DefaultHasher, Hasher};
    325    ///
    326    /// let mut hasher = DefaultHasher::new();
    327    /// hasher.write(b"Cool!");
    328    ///
    329    /// println!("Hash is {:x}!", hasher.finish());
    330    /// ```
    331    ///
    332    /// [`write`]: Hasher::write
    333    #[stable(feature = "rust1", since = "1.0.0")]
    334    #[must_use]
    335    fn finish(&self) -> u64;
    336
    337    /// Writes some data into this `Hasher`.
    338    ///
    339    /// # Examples
    340    ///
    341    /// ```
    342    /// use std::hash::{DefaultHasher, Hasher};
    343    ///
    344    /// let mut hasher = DefaultHasher::new();
    345    /// let data = [0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef];
    346    ///
    347    /// hasher.write(&data);
    348    ///
    349    /// println!("Hash is {:x}!", hasher.finish());
    350    /// ```
    351    ///
    352    /// # Note to Implementers
    353    ///
    354    /// You generally should not do length-prefixing as part of implementing
    355    /// this method.  It's up to the [`Hash`] implementation to call
    356    /// [`Hasher::write_length_prefix`] before sequences that need it.
    357    #[stable(feature = "rust1", since = "1.0.0")]
    358    fn write(&mut self, bytes: &[u8]);
    359
    360    /// Writes a single `u8` into this hasher.
    361    #[inline]
    362    #[stable(feature = "hasher_write", since = "1.3.0")]
    363    fn write_u8(&mut self, i: u8) {
    364        self.write(&[i])
    365    }
    366    /// Writes a single `u16` into this hasher.
    367    #[inline]
    368    #[stable(feature = "hasher_write", since = "1.3.0")]
    369    fn write_u16(&mut self, i: u16) {
    370        self.write(&i.to_ne_bytes())
    371    }
    372    /// Writes a single `u32` into this hasher.
    373    #[inline]
    374    #[stable(feature = "hasher_write", since = "1.3.0")]
    375    fn write_u32(&mut self, i: u32) {
    376        self.write(&i.to_ne_bytes())
    377    }
    378    /// Writes a single `u64` into this hasher.
    379    #[inline]
    380    #[stable(feature = "hasher_write", since = "1.3.0")]
    381    fn write_u64(&mut self, i: u64) {
    382        self.write(&i.to_ne_bytes())
    383    }
    384    /// Writes a single `u128` into this hasher.
    385    #[inline]
    386    #[stable(feature = "i128", since = "1.26.0")]
    387    fn write_u128(&mut self, i: u128) {
    388        self.write(&i.to_ne_bytes())
    389    }
    390    /// Writes a single `usize` into this hasher.
    391    #[inline]
    392    #[stable(feature = "hasher_write", since = "1.3.0")]
    393    fn write_usize(&mut self, i: usize) {
    394        self.write(&i.to_ne_bytes())
    395    }
    396
    397    /// Writes a single `i8` into this hasher.
    398    #[inline]
    399    #[stable(feature = "hasher_write", since = "1.3.0")]
    400    fn write_i8(&mut self, i: i8) {
    401        self.write_u8(i as u8)
    402    }
    403    /// Writes a single `i16` into this hasher.
    404    #[inline]
    405    #[stable(feature = "hasher_write", since = "1.3.0")]
    406    fn write_i16(&mut self, i: i16) {
    407        self.write_u16(i as u16)
    408    }
    409    /// Writes a single `i32` into this hasher.
    410    #[inline]
    411    #[stable(feature = "hasher_write", since = "1.3.0")]
    412    fn write_i32(&mut self, i: i32) {
    413        self.write_u32(i as u32)
    414    }
    415    /// Writes a single `i64` into this hasher.
    416    #[inline]
    417    #[stable(feature = "hasher_write", since = "1.3.0")]
    418    fn write_i64(&mut self, i: i64) {
    419        self.write_u64(i as u64)
    420    }
    421    /// Writes a single `i128` into this hasher.
    422    #[inline]
    423    #[stable(feature = "i128", since = "1.26.0")]
    424    fn write_i128(&mut self, i: i128) {
    425        self.write_u128(i as u128)
    426    }
    427    /// Writes a single `isize` into this hasher.
    428    #[inline]
    429    #[stable(feature = "hasher_write", since = "1.3.0")]
    430    fn write_isize(&mut self, i: isize) {
    431        self.write_usize(i as usize)
    432    }
    433
    434    /// Writes a length prefix into this hasher, as part of being prefix-free.
    435    ///
    436    /// If you're implementing [`Hash`] for a custom collection, call this before
    437    /// writing its contents to this `Hasher`.  That way
    438    /// `(collection![1, 2, 3], collection![4, 5])` and
    439    /// `(collection![1, 2], collection![3, 4, 5])` will provide different
    440    /// sequences of values to the `Hasher`
    441    ///
    442    /// The `impl<T> Hash for [T]` includes a call to this method, so if you're
    443    /// hashing a slice (or array or vector) via its `Hash::hash` method,
    444    /// you should **not** call this yourself.
    445    ///
    446    /// This method is only for providing domain separation.  If you want to
    447    /// hash a `usize` that represents part of the *data*, then it's important
    448    /// that you pass it to [`Hasher::write_usize`] instead of to this method.
    449    ///
    450    /// # Examples
    451    ///
    452    /// ```
    453    /// #![feature(hasher_prefixfree_extras)]
    454    /// # // Stubs to make the `impl` below pass the compiler
    455    /// # #![allow(non_local_definitions)]
    456    /// # struct MyCollection<T>(Option<T>);
    457    /// # impl<T> MyCollection<T> {
    458    /// #     fn len(&self) -> usize { todo!() }
    459    /// # }
    460    /// # impl<'a, T> IntoIterator for &'a MyCollection<T> {
    461    /// #     type Item = T;
    462    /// #     type IntoIter = std::iter::Empty<T>;
    463    /// #     fn into_iter(self) -> Self::IntoIter { todo!() }
    464    /// # }
    465    ///
    466    /// use std::hash::{Hash, Hasher};
    467    /// impl<T: Hash> Hash for MyCollection<T> {
    468    ///     fn hash<H: Hasher>(&self, state: &mut H) {
    469    ///         state.write_length_prefix(self.len());
    470    ///         for elt in self {
    471    ///             elt.hash(state);
    472    ///         }
    473    ///     }
    474    /// }
    475    /// ```
    476    ///
    477    /// # Note to Implementers
    478    ///
    479    /// If you've decided that your `Hasher` is willing to be susceptible to
    480    /// Hash-DoS attacks, then you might consider skipping hashing some or all
    481    /// of the `len` provided in the name of increased performance.
    482    #[inline]
    483    #[unstable(feature = "hasher_prefixfree_extras", issue = "96762")]
    484    fn write_length_prefix(&mut self, len: usize) {
    485        self.write_usize(len);
    486    }
    487
    488    /// Writes a single `str` into this hasher.
    489    ///
    490    /// If you're implementing [`Hash`], you generally do not need to call this,
    491    /// as the `impl Hash for str` does, so you should prefer that instead.
    492    ///
    493    /// This includes the domain separator for prefix-freedom, so you should
    494    /// **not** call `Self::write_length_prefix` before calling this.
    495    ///
    496    /// # Note to Implementers
    497    ///
    498    /// There are at least two reasonable default ways to implement this.
    499    /// Which one will be the default is not yet decided, so for now
    500    /// you probably want to override it specifically.
    501    ///
    502    /// ## The general answer
    503    ///
    504    /// It's always correct to implement this with a length prefix:
    505    ///
    506    /// ```
    507    /// # #![feature(hasher_prefixfree_extras)]
    508    /// # struct Foo;
    509    /// # impl std::hash::Hasher for Foo {
    510    /// # fn finish(&self) -> u64 { unimplemented!() }
    511    /// # fn write(&mut self, _bytes: &[u8]) { unimplemented!() }
    512    /// fn write_str(&mut self, s: &str) {
    513    ///     self.write_length_prefix(s.len());
    514    ///     self.write(s.as_bytes());
    515    /// }
    516    /// # }
    517    /// ```
    518    ///
    519    /// And, if your `Hasher` works in `usize` chunks, this is likely a very
    520    /// efficient way to do it, as anything more complicated may well end up
    521    /// slower than just running the round with the length.
    522    ///
    523    /// ## If your `Hasher` works byte-wise
    524    ///
    525    /// One nice thing about `str` being UTF-8 is that the `b'\xFF'` byte
    526    /// never happens.  That means that you can append that to the byte stream
    527    /// being hashed and maintain prefix-freedom:
    528    ///
    529    /// ```
    530    /// # #![feature(hasher_prefixfree_extras)]
    531    /// # struct Foo;
    532    /// # impl std::hash::Hasher for Foo {
    533    /// # fn finish(&self) -> u64 { unimplemented!() }
    534    /// # fn write(&mut self, _bytes: &[u8]) { unimplemented!() }
    535    /// fn write_str(&mut self, s: &str) {
    536    ///     self.write(s.as_bytes());
    537    ///     self.write_u8(0xff);
    538    /// }
    539    /// # }
    540    /// ```
    541    ///
    542    /// This does require that your implementation not add extra padding, and
    543    /// thus generally requires that you maintain a buffer, running a round
    544    /// only once that buffer is full (or `finish` is called).
    545    ///
    546    /// That's because if `write` pads data out to a fixed chunk size, it's
    547    /// likely that it does it in such a way that `"a"` and `"a\x00"` would
    548    /// end up hashing the same sequence of things, introducing conflicts.
    549    #[inline]
    550    #[unstable(feature = "hasher_prefixfree_extras", issue = "96762")]
    551    fn write_str(&mut self, s: &str) {
    552        self.write(s.as_bytes());
    553        self.write_u8(0xff);
    554    }
    555}
    556
    557#[stable(feature = "indirect_hasher_impl", since = "1.22.0")]
    558impl<H: Hasher + ?Sized> Hasher for &mut H {
    559    fn finish(&self) -> u64 {
    560        (**self).finish()
    561    }
    562    fn write(&mut self, bytes: &[u8]) {
    563        (**self).write(bytes)
    564    }
    565    fn write_u8(&mut self, i: u8) {
    566        (**self).write_u8(i)
    567    }
    568    fn write_u16(&mut self, i: u16) {
    569        (**self).write_u16(i)
    570    }
    571    fn write_u32(&mut self, i: u32) {
    572        (**self).write_u32(i)
    573    }
    574    fn write_u64(&mut self, i: u64) {
    575        (**self).write_u64(i)
    576    }
    577    fn write_u128(&mut self, i: u128) {
    578        (**self).write_u128(i)
    579    }
    580    fn write_usize(&mut self, i: usize) {
    581        (**self).write_usize(i)
    582    }
    583    fn write_i8(&mut self, i: i8) {
    584        (**self).write_i8(i)
    585    }
    586    fn write_i16(&mut self, i: i16) {
    587        (**self).write_i16(i)
    588    }
    589    fn write_i32(&mut self, i: i32) {
    590        (**self).write_i32(i)
    591    }
    592    fn write_i64(&mut self, i: i64) {
    593        (**self).write_i64(i)
    594    }
    595    fn write_i128(&mut self, i: i128) {
    596        (**self).write_i128(i)
    597    }
    598    fn write_isize(&mut self, i: isize) {
    599        (**self).write_isize(i)
    600    }
    601    fn write_length_prefix(&mut self, len: usize) {
    602        (**self).write_length_prefix(len)
    603    }
    604    fn write_str(&mut self, s: &str) {
    605        (**self).write_str(s)
    606    }
    607}
    608
    609/// A trait for creating instances of [`Hasher`].
    610///
    611/// A `BuildHasher` is typically used (e.g., by [`HashMap`]) to create
    612/// [`Hasher`]s for each key such that they are hashed independently of one
    613/// another, since [`Hasher`]s contain state.
    614///
    615/// For each instance of `BuildHasher`, the [`Hasher`]s created by
    616/// [`build_hasher`] should be identical. That is, if the same stream of bytes
    617/// is fed into each hasher, the same output will also be generated.
    618///
    619/// # Examples
    620///
    621/// ```
    622/// use std::hash::{BuildHasher, Hasher, RandomState};
    623///
    624/// let s = RandomState::new();
    625/// let mut hasher_1 = s.build_hasher();
    626/// let mut hasher_2 = s.build_hasher();
    627///
    628/// hasher_1.write_u32(8128);
    629/// hasher_2.write_u32(8128);
    630///
    631/// assert_eq!(hasher_1.finish(), hasher_2.finish());
    632/// ```
    633///
    634/// [`build_hasher`]: BuildHasher::build_hasher
    635/// [`HashMap`]: ../../std/collections/struct.HashMap.html
    636#[cfg_attr(not(test), rustc_diagnostic_item = "BuildHasher")]
    637#[stable(since = "1.7.0", feature = "build_hasher")]
    638pub trait BuildHasher {
    639    /// Type of the hasher that will be created.
    640    #[stable(since = "1.7.0", feature = "build_hasher")]
    641    type Hasher: Hasher;
    642
    643    /// Creates a new hasher.
    644    ///
    645    /// Each call to `build_hasher` on the same instance should produce identical
    646    /// [`Hasher`]s.
    647    ///
    648    /// # Examples
    649    ///
    650    /// ```
    651    /// use std::hash::{BuildHasher, RandomState};
    652    ///
    653    /// let s = RandomState::new();
    654    /// let new_s = s.build_hasher();
    655    /// ```
    656    #[stable(since = "1.7.0", feature = "build_hasher")]
    657    fn build_hasher(&self) -> Self::Hasher;
    658
    659    /// Calculates the hash of a single value.
    660    ///
    661    /// This is intended as a convenience for code which *consumes* hashes, such
    662    /// as the implementation of a hash table or in unit tests that check
    663    /// whether a custom [`Hash`] implementation behaves as expected.
    664    ///
    665    /// This must not be used in any code which *creates* hashes, such as in an
    666    /// implementation of [`Hash`].  The way to create a combined hash of
    667    /// multiple values is to call [`Hash::hash`] multiple times using the same
    668    /// [`Hasher`], not to call this method repeatedly and combine the results.
    669    ///
    670    /// # Example
    671    ///
    672    /// ```
    673    /// use std::cmp::{max, min};
    674    /// use std::hash::{BuildHasher, Hash, Hasher};
    675    /// struct OrderAmbivalentPair<T: Ord>(T, T);
    676    /// impl<T: Ord + Hash> Hash for OrderAmbivalentPair<T> {
    677    ///     fn hash<H: Hasher>(&self, hasher: &mut H) {
    678    ///         min(&self.0, &self.1).hash(hasher);
    679    ///         max(&self.0, &self.1).hash(hasher);
    680    ///     }
    681    /// }
    682    ///
    683    /// // Then later, in a `#[test]` for the type...
    684    /// let bh = std::hash::RandomState::new();
    685    /// assert_eq!(
    686    ///     bh.hash_one(OrderAmbivalentPair(1, 2)),
    687    ///     bh.hash_one(OrderAmbivalentPair(2, 1))
    688    /// );
    689    /// assert_eq!(
    690    ///     bh.hash_one(OrderAmbivalentPair(10, 2)),
    691    ///     bh.hash_one(&OrderAmbivalentPair(2, 10))
    692    /// );
    693    /// ```
    694    #[stable(feature = "build_hasher_simple_hash_one", since = "1.71.0")]
    695    fn hash_one<T: Hash>(&self, x: T) -> u64
    696    where
    697        Self: Sized,
    698        Self::Hasher: Hasher,
    699    {
    700        let mut hasher = self.build_hasher();
    701        x.hash(&mut hasher);
    702        hasher.finish()
    703    }
    704}
    705
    706/// Used to create a default [`BuildHasher`] instance for types that implement
    707/// [`Hasher`] and [`Default`].
    708///
    709/// `BuildHasherDefault<H>` can be used when a type `H` implements [`Hasher`] and
    710/// [`Default`], and you need a corresponding [`BuildHasher`] instance, but none is
    711/// defined.
    712///
    713/// Any `BuildHasherDefault` is [zero-sized]. It can be created with
    714/// [`default`][method.default]. When using `BuildHasherDefault` with [`HashMap`] or
    715/// [`HashSet`], this doesn't need to be done, since they implement appropriate
    716/// [`Default`] instances themselves.
    717///
    718/// # Examples
    719///
    720/// Using `BuildHasherDefault` to specify a custom [`BuildHasher`] for
    721/// [`HashMap`]:
    722///
    723/// ```
    724/// use std::collections::HashMap;
    725/// use std::hash::{BuildHasherDefault, Hasher};
    726///
    727/// #[derive(Default)]
    728/// struct MyHasher;
    729///
    730/// impl Hasher for MyHasher {
    731///     fn write(&mut self, bytes: &[u8]) {
    732///         // Your hashing algorithm goes here!
    733///        unimplemented!()
    734///     }
    735///
    736///     fn finish(&self) -> u64 {
    737///         // Your hashing algorithm goes here!
    738///         unimplemented!()
    739///     }
    740/// }
    741///
    742/// type MyBuildHasher = BuildHasherDefault<MyHasher>;
    743///
    744/// let hash_map = HashMap::<u32, u32, MyBuildHasher>::default();
    745/// ```
    746///
    747/// [method.default]: BuildHasherDefault::default
    748/// [`HashMap`]: ../../std/collections/struct.HashMap.html
    749/// [`HashSet`]: ../../std/collections/struct.HashSet.html
    750/// [zero-sized]: https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts
    751#[stable(since = "1.7.0", feature = "build_hasher")]
    752pub struct BuildHasherDefault<H>(marker::PhantomData<fn() -> H>);
    753
    754impl<H> BuildHasherDefault<H> {
    755    /// Creates a new BuildHasherDefault for Hasher `H`.
    756    #[stable(feature = "build_hasher_default_const_new", since = "1.85.0")]
    757    #[rustc_const_stable(feature = "build_hasher_default_const_new", since = "1.85.0")]
    758    pub const fn new() -> Self {
    759        BuildHasherDefault(marker::PhantomData)
    760    }
    761}
    762
    763#[stable(since = "1.9.0", feature = "core_impl_debug")]
    764impl<H> fmt::Debug for BuildHasherDefault<H> {
    765    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    766        f.debug_struct("BuildHasherDefault").finish()
    767    }
    768}
    769
    770#[stable(since = "1.7.0", feature = "build_hasher")]
    771impl<H: Default + Hasher> BuildHasher for BuildHasherDefault<H> {
    772    type Hasher = H;
    773
    774    fn build_hasher(&self) -> H {
    775        H::default()
    776    }
    777}
    778
    779#[stable(since = "1.7.0", feature = "build_hasher")]
    780impl<H> Clone for BuildHasherDefault<H> {
    781    fn clone(&self) -> BuildHasherDefault<H> {
    782        BuildHasherDefault(marker::PhantomData)
    783    }
    784}
    785
    786#[stable(since = "1.7.0", feature = "build_hasher")]
    787#[rustc_const_unstable(feature = "const_default", issue = "143894")]
    788impl<H> const Default for BuildHasherDefault<H> {
    789    fn default() -> BuildHasherDefault<H> {
    790        Self::new()
    791    }
    792}
    793
    794#[stable(since = "1.29.0", feature = "build_hasher_eq")]
    795impl<H> PartialEq for BuildHasherDefault<H> {
    796    fn eq(&self, _other: &BuildHasherDefault<H>) -> bool {
    797        true
    798    }
    799}
    800
    801#[stable(since = "1.29.0", feature = "build_hasher_eq")]
    802impl<H> Eq for BuildHasherDefault<H> {}
    803
    804mod impls {
    805    use super::*;
    806    use crate::slice;
    807
    808    macro_rules! impl_write {
    809        ($(($ty:ident, $meth:ident),)*) => {$(
    810            #[stable(feature = "rust1", since = "1.0.0")]
    811            impl Hash for $ty {
    812                #[inline]
    813                fn hash<H: Hasher>(&self, state: &mut H) {
    814                    state.$meth(*self)
    815                }
    816
    817                #[inline]
    818                fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
    819                    let newlen = size_of_val(data);
    820                    let ptr = data.as_ptr() as *const u8;
    821                    // SAFETY: `ptr` is valid and aligned, as this macro is only used
    822                    // for numeric primitives which have no padding. The new slice only
    823                    // spans across `data` and is never mutated, and its total size is the
    824                    // same as the original `data` so it can't be over `isize::MAX`.
    825                    state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
    826                }
    827            }
    828        )*}
    829    }
    830
    831    impl_write! {
    832        (u8, write_u8),
    833        (u16, write_u16),
    834        (u32, write_u32),
    835        (u64, write_u64),
    836        (usize, write_usize),
    837        (i8, write_i8),
    838        (i16, write_i16),
    839        (i32, write_i32),
    840        (i64, write_i64),
    841        (isize, write_isize),
    842        (u128, write_u128),
    843        (i128, write_i128),
    844    }
    845
    846    #[stable(feature = "rust1", since = "1.0.0")]
    847    impl Hash for bool {
    848        #[inline]
    849        fn hash<H: Hasher>(&self, state: &mut H) {
    850            state.write_u8(*self as u8)
    851        }
    852    }
    853
    854    #[stable(feature = "rust1", since = "1.0.0")]
    855    impl Hash for char {
    856        #[inline]
    857        fn hash<H: Hasher>(&self, state: &mut H) {
    858            state.write_u32(*self as u32)
    859        }
    860    }
    861
    862    #[stable(feature = "rust1", since = "1.0.0")]
    863    impl Hash for str {
    864        #[inline]
    865        fn hash<H: Hasher>(&self, state: &mut H) {
    866            state.write_str(self);
    867        }
    868    }
    869
    870    #[stable(feature = "never_hash", since = "1.29.0")]
    871    impl Hash for ! {
    872        #[inline]
    873        fn hash<H: Hasher>(&self, _: &mut H) {
    874            *self
    875        }
    876    }
    877
    878    macro_rules! impl_hash_tuple {
    879        () => (
    880            #[stable(feature = "rust1", since = "1.0.0")]
    881            impl Hash for () {
    882                #[inline]
    883                fn hash<H: Hasher>(&self, _state: &mut H) {}
    884            }
    885        );
    886
    887        ( $($name:ident)+) => (
    888            maybe_tuple_doc! {
    889                $($name)+ @
    890                #[stable(feature = "rust1", since = "1.0.0")]
    891                impl<$($name: Hash),+> Hash for ($($name,)+) {
    892                    #[allow(non_snake_case)]
    893                    #[inline]
    894                    fn hash<S: Hasher>(&self, state: &mut S) {
    895                        let ($(ref $name,)+) = *self;
    896                        $($name.hash(state);)+
    897                    }
    898                }
    899            }
    900        );
    901    }
    902
    903    macro_rules! maybe_tuple_doc {
    904        ($a:ident @ #[$meta:meta] $item:item) => {
    905            #[doc(fake_variadic)]
    906            #[doc = "This trait is implemented for tuples up to twelve items long."]
    907            #[$meta]
    908            $item
    909        };
    910        ($a:ident $($rest_a:ident)+ @ #[$meta:meta] $item:item) => {
    911            #[doc(hidden)]
    912            #[$meta]
    913            $item
    914        };
    915    }
    916
    917    impl_hash_tuple! {}
    918    impl_hash_tuple! { T }
    919    impl_hash_tuple! { T B }
    920    impl_hash_tuple! { T B C }
    921    impl_hash_tuple! { T B C D }
    922    impl_hash_tuple! { T B C D E }
    923    impl_hash_tuple! { T B C D E F }
    924    impl_hash_tuple! { T B C D E F G }
    925    impl_hash_tuple! { T B C D E F G H }
    926    impl_hash_tuple! { T B C D E F G H I }
    927    impl_hash_tuple! { T B C D E F G H I J }
    928    impl_hash_tuple! { T B C D E F G H I J K }
    929    impl_hash_tuple! { T B C D E F G H I J K L }
    930
    931    #[stable(feature = "rust1", since = "1.0.0")]
    932    impl<T: Hash> Hash for [T] {
    933        #[inline]
    934        fn hash<H: Hasher>(&self, state: &mut H) {
    935            state.write_length_prefix(self.len());
    936            Hash::hash_slice(self, state)
    937        }
    938    }
    939
    940    #[stable(feature = "rust1", since = "1.0.0")]
    941    impl<T: ?Sized + marker::PointeeSized + Hash> Hash for &T {
    942        #[inline]
    943        fn hash<H: Hasher>(&self, state: &mut H) {
    944            (**self).hash(state);
    945        }
    946    }
    947
    948    #[stable(feature = "rust1", since = "1.0.0")]
    949    impl<T: ?Sized + marker::PointeeSized + Hash> Hash for &mut T {
    950        #[inline]
    951        fn hash<H: Hasher>(&self, state: &mut H) {
    952            (**self).hash(state);
    953        }
    954    }
    955
    956    #[stable(feature = "rust1", since = "1.0.0")]
    957    impl<T: ?Sized + marker::PointeeSized> Hash for *const T {
    958        #[inline]
    959        fn hash<H: Hasher>(&self, state: &mut H) {
    960            let (address, metadata) = self.to_raw_parts();
    961            state.write_usize(address.addr());
    962            metadata.hash(state);
    963        }
    964    }
    965
    966    #[stable(feature = "rust1", since = "1.0.0")]
    967    impl<T: ?Sized + marker::PointeeSized> Hash for *mut T {
    968        #[inline]
    969        fn hash<H: Hasher>(&self, state: &mut H) {
    970            let (address, metadata) = self.to_raw_parts();
    971            state.write_usize(address.addr());
    972            metadata.hash(state);
    973        }
    974    }
    975}