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