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