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 {
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#[stable(since = "1.7.0", feature = "build_hasher")]
637pub trait BuildHasher {
638    /// Type of the hasher that will be created.
639    #[stable(since = "1.7.0", feature = "build_hasher")]
640    type Hasher: Hasher;
641
642    /// Creates a new hasher.
643    ///
644    /// Each call to `build_hasher` on the same instance should produce identical
645    /// [`Hasher`]s.
646    ///
647    /// # Examples
648    ///
649    /// ```
650    /// use std::hash::{BuildHasher, RandomState};
651    ///
652    /// let s = RandomState::new();
653    /// let new_s = s.build_hasher();
654    /// ```
655    #[stable(since = "1.7.0", feature = "build_hasher")]
656    fn build_hasher(&self) -> Self::Hasher;
657
658    /// Calculates the hash of a single value.
659    ///
660    /// This is intended as a convenience for code which *consumes* hashes, such
661    /// as the implementation of a hash table or in unit tests that check
662    /// whether a custom [`Hash`] implementation behaves as expected.
663    ///
664    /// This must not be used in any code which *creates* hashes, such as in an
665    /// implementation of [`Hash`].  The way to create a combined hash of
666    /// multiple values is to call [`Hash::hash`] multiple times using the same
667    /// [`Hasher`], not to call this method repeatedly and combine the results.
668    ///
669    /// # Example
670    ///
671    /// ```
672    /// use std::cmp::{max, min};
673    /// use std::hash::{BuildHasher, Hash, Hasher};
674    /// struct OrderAmbivalentPair<T: Ord>(T, T);
675    /// impl<T: Ord + Hash> Hash for OrderAmbivalentPair<T> {
676    ///     fn hash<H: Hasher>(&self, hasher: &mut H) {
677    ///         min(&self.0, &self.1).hash(hasher);
678    ///         max(&self.0, &self.1).hash(hasher);
679    ///     }
680    /// }
681    ///
682    /// // Then later, in a `#[test]` for the type...
683    /// let bh = std::hash::RandomState::new();
684    /// assert_eq!(
685    ///     bh.hash_one(OrderAmbivalentPair(1, 2)),
686    ///     bh.hash_one(OrderAmbivalentPair(2, 1))
687    /// );
688    /// assert_eq!(
689    ///     bh.hash_one(OrderAmbivalentPair(10, 2)),
690    ///     bh.hash_one(&OrderAmbivalentPair(2, 10))
691    /// );
692    /// ```
693    #[stable(feature = "build_hasher_simple_hash_one", since = "1.71.0")]
694    fn hash_one<T: Hash>(&self, x: T) -> u64
695    where
696        Self: Sized,
697        Self::Hasher: Hasher,
698    {
699        let mut hasher = self.build_hasher();
700        x.hash(&mut hasher);
701        hasher.finish()
702    }
703}
704
705/// Used to create a default [`BuildHasher`] instance for types that implement
706/// [`Hasher`] and [`Default`].
707///
708/// `BuildHasherDefault<H>` can be used when a type `H` implements [`Hasher`] and
709/// [`Default`], and you need a corresponding [`BuildHasher`] instance, but none is
710/// defined.
711///
712/// Any `BuildHasherDefault` is [zero-sized]. It can be created with
713/// [`default`][method.default]. When using `BuildHasherDefault` with [`HashMap`] or
714/// [`HashSet`], this doesn't need to be done, since they implement appropriate
715/// [`Default`] instances themselves.
716///
717/// # Examples
718///
719/// Using `BuildHasherDefault` to specify a custom [`BuildHasher`] for
720/// [`HashMap`]:
721///
722/// ```
723/// use std::collections::HashMap;
724/// use std::hash::{BuildHasherDefault, Hasher};
725///
726/// #[derive(Default)]
727/// struct MyHasher;
728///
729/// impl Hasher for MyHasher {
730///     fn write(&mut self, bytes: &[u8]) {
731///         // Your hashing algorithm goes here!
732///        unimplemented!()
733///     }
734///
735///     fn finish(&self) -> u64 {
736///         // Your hashing algorithm goes here!
737///         unimplemented!()
738///     }
739/// }
740///
741/// type MyBuildHasher = BuildHasherDefault<MyHasher>;
742///
743/// let hash_map = HashMap::<u32, u32, MyBuildHasher>::default();
744/// ```
745///
746/// [method.default]: BuildHasherDefault::default
747/// [`HashMap`]: ../../std/collections/struct.HashMap.html
748/// [`HashSet`]: ../../std/collections/struct.HashSet.html
749/// [zero-sized]: https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts
750#[stable(since = "1.7.0", feature = "build_hasher")]
751pub struct BuildHasherDefault<H>(marker::PhantomData<fn() -> H>);
752
753impl<H> BuildHasherDefault<H> {
754    /// Creates a new BuildHasherDefault for Hasher `H`.
755    #[stable(feature = "build_hasher_default_const_new", since = "1.85.0")]
756    #[rustc_const_stable(feature = "build_hasher_default_const_new", since = "1.85.0")]
757    pub const fn new() -> Self {
758        BuildHasherDefault(marker::PhantomData)
759    }
760}
761
762#[stable(since = "1.9.0", feature = "core_impl_debug")]
763impl<H> fmt::Debug for BuildHasherDefault<H> {
764    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
765        f.debug_struct("BuildHasherDefault").finish()
766    }
767}
768
769#[stable(since = "1.7.0", feature = "build_hasher")]
770impl<H: Default + Hasher> BuildHasher for BuildHasherDefault<H> {
771    type Hasher = H;
772
773    fn build_hasher(&self) -> H {
774        H::default()
775    }
776}
777
778#[stable(since = "1.7.0", feature = "build_hasher")]
779impl<H> Clone for BuildHasherDefault<H> {
780    fn clone(&self) -> BuildHasherDefault<H> {
781        BuildHasherDefault(marker::PhantomData)
782    }
783}
784
785#[stable(since = "1.7.0", feature = "build_hasher")]
786impl<H> Default for BuildHasherDefault<H> {
787    fn default() -> BuildHasherDefault<H> {
788        Self::new()
789    }
790}
791
792#[stable(since = "1.29.0", feature = "build_hasher_eq")]
793impl<H> PartialEq for BuildHasherDefault<H> {
794    fn eq(&self, _other: &BuildHasherDefault<H>) -> bool {
795        true
796    }
797}
798
799#[stable(since = "1.29.0", feature = "build_hasher_eq")]
800impl<H> Eq for BuildHasherDefault<H> {}
801
802mod impls {
803    use super::*;
804    use crate::{mem, slice};
805
806    macro_rules! impl_write {
807        ($(($ty:ident, $meth:ident),)*) => {$(
808            #[stable(feature = "rust1", since = "1.0.0")]
809            impl Hash for $ty {
810                #[inline]
811                fn hash<H: Hasher>(&self, state: &mut H) {
812                    state.$meth(*self)
813                }
814
815                #[inline]
816                fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
817                    let newlen = mem::size_of_val(data);
818                    let ptr = data.as_ptr() as *const u8;
819                    // SAFETY: `ptr` is valid and aligned, as this macro is only used
820                    // for numeric primitives which have no padding. The new slice only
821                    // spans across `data` and is never mutated, and its total size is the
822                    // same as the original `data` so it can't be over `isize::MAX`.
823                    state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
824                }
825            }
826        )*}
827    }
828
829    impl_write! {
830        (u8, write_u8),
831        (u16, write_u16),
832        (u32, write_u32),
833        (u64, write_u64),
834        (usize, write_usize),
835        (i8, write_i8),
836        (i16, write_i16),
837        (i32, write_i32),
838        (i64, write_i64),
839        (isize, write_isize),
840        (u128, write_u128),
841        (i128, write_i128),
842    }
843
844    #[stable(feature = "rust1", since = "1.0.0")]
845    impl Hash for bool {
846        #[inline]
847        fn hash<H: Hasher>(&self, state: &mut H) {
848            state.write_u8(*self as u8)
849        }
850    }
851
852    #[stable(feature = "rust1", since = "1.0.0")]
853    impl Hash for char {
854        #[inline]
855        fn hash<H: Hasher>(&self, state: &mut H) {
856            state.write_u32(*self as u32)
857        }
858    }
859
860    #[stable(feature = "rust1", since = "1.0.0")]
861    impl Hash for str {
862        #[inline]
863        fn hash<H: Hasher>(&self, state: &mut H) {
864            state.write_str(self);
865        }
866    }
867
868    #[stable(feature = "never_hash", since = "1.29.0")]
869    impl Hash for ! {
870        #[inline]
871        fn hash<H: Hasher>(&self, _: &mut H) {
872            *self
873        }
874    }
875
876    macro_rules! impl_hash_tuple {
877        () => (
878            #[stable(feature = "rust1", since = "1.0.0")]
879            impl Hash for () {
880                #[inline]
881                fn hash<H: Hasher>(&self, _state: &mut H) {}
882            }
883        );
884
885        ( $($name:ident)+) => (
886            maybe_tuple_doc! {
887                $($name)+ @
888                #[stable(feature = "rust1", since = "1.0.0")]
889                impl<$($name: Hash),+> Hash for ($($name,)+) where last_type!($($name,)+): ?Sized {
890                    #[allow(non_snake_case)]
891                    #[inline]
892                    fn hash<S: Hasher>(&self, state: &mut S) {
893                        let ($(ref $name,)+) = *self;
894                        $($name.hash(state);)+
895                    }
896                }
897            }
898        );
899    }
900
901    macro_rules! maybe_tuple_doc {
902        ($a:ident @ #[$meta:meta] $item:item) => {
903            #[doc(fake_variadic)]
904            #[doc = "This trait is implemented for tuples up to twelve items long."]
905            #[$meta]
906            $item
907        };
908        ($a:ident $($rest_a:ident)+ @ #[$meta:meta] $item:item) => {
909            #[doc(hidden)]
910            #[$meta]
911            $item
912        };
913    }
914
915    macro_rules! last_type {
916        ($a:ident,) => { $a };
917        ($a:ident, $($rest_a:ident,)+) => { last_type!($($rest_a,)+) };
918    }
919
920    impl_hash_tuple! {}
921    impl_hash_tuple! { T }
922    impl_hash_tuple! { T B }
923    impl_hash_tuple! { T B C }
924    impl_hash_tuple! { T B C D }
925    impl_hash_tuple! { T B C D E }
926    impl_hash_tuple! { T B C D E F }
927    impl_hash_tuple! { T B C D E F G }
928    impl_hash_tuple! { T B C D E F G H }
929    impl_hash_tuple! { T B C D E F G H I }
930    impl_hash_tuple! { T B C D E F G H I J }
931    impl_hash_tuple! { T B C D E F G H I J K }
932    impl_hash_tuple! { T B C D E F G H I J K L }
933
934    #[stable(feature = "rust1", since = "1.0.0")]
935    impl<T: Hash> Hash for [T] {
936        #[inline]
937        fn hash<H: Hasher>(&self, state: &mut H) {
938            state.write_length_prefix(self.len());
939            Hash::hash_slice(self, state)
940        }
941    }
942
943    #[stable(feature = "rust1", since = "1.0.0")]
944    impl<T: ?Sized + Hash> Hash for &T {
945        #[inline]
946        fn hash<H: Hasher>(&self, state: &mut H) {
947            (**self).hash(state);
948        }
949    }
950
951    #[stable(feature = "rust1", since = "1.0.0")]
952    impl<T: ?Sized + Hash> Hash for &mut T {
953        #[inline]
954        fn hash<H: Hasher>(&self, state: &mut H) {
955            (**self).hash(state);
956        }
957    }
958
959    #[stable(feature = "rust1", since = "1.0.0")]
960    impl<T: ?Sized> Hash for *const T {
961        #[inline]
962        fn hash<H: Hasher>(&self, state: &mut H) {
963            let (address, metadata) = self.to_raw_parts();
964            state.write_usize(address.addr());
965            metadata.hash(state);
966        }
967    }
968
969    #[stable(feature = "rust1", since = "1.0.0")]
970    impl<T: ?Sized> Hash for *mut T {
971        #[inline]
972        fn hash<H: Hasher>(&self, state: &mut H) {
973            let (address, metadata) = self.to_raw_parts();
974            state.write_usize(address.addr());
975            metadata.hash(state);
976        }
977    }
978}