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 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
 157 /// [`HashSet`]: ../../std/collections/struct.HashSet.html
 158 /// [`hash`]: Hash::hash
 159 #[stable(feature = "rust1", since = "1.0.0")]
 160 pub trait Hash {
 161     /// Feeds this value into the given [`Hasher`].
 162     ///
 163     /// # Examples
 164     ///
 165     /// ```
 166     /// use std::collections::hash_map::DefaultHasher;
 167     /// use std::hash::{Hash, Hasher};
 168     ///
 169     /// let mut hasher = DefaultHasher::new();
 170     /// 7920.hash(&mut hasher);
 171     /// println!("Hash is {:x}!", hasher.finish());
 172     /// ```
 173     #[stable(feature = "rust1", since = "1.0.0")]
 174     fn hash<H: Hasher>(&self, state: &mut H);
 175
 176     /// Feeds a slice of this type into the given [`Hasher`].
 177     ///
 178     /// This method is meant as a convenience, but its implementation is
 179     /// also explicitly left unspecified. It isn't guaranteed to be
 180     /// equivalent to repeated calls of [`hash`] and implementations of
 181     /// [`Hash`] should keep that in mind and call [`hash`] themselves
 182     /// if the slice isn't treated as a whole unit in the [`PartialEq`]
 183     /// implementation.
 184     ///
 185     /// For example, a [`VecDeque`] implementation might naïvely call
 186     /// [`as_slices`] and then [`hash_slice`] on each slice, but this
 187     /// is wrong since the two slices can change with a call to
 188     /// [`make_contiguous`] without affecting the [`PartialEq`]
 189     /// result. Since these slices aren't treated as singular
 190     /// units, and instead part of a larger deque, this method cannot
 191     /// be used.
 192     ///
 193     /// # Examples
 194     ///
 195     /// ```
 196     /// use std::collections::hash_map::DefaultHasher;
 197     /// use std::hash::{Hash, Hasher};
 198     ///
 199     /// let mut hasher = DefaultHasher::new();
 200     /// let numbers = [6, 28, 496, 8128];
 201     /// Hash::hash_slice(&numbers, &mut hasher);
 202     /// println!("Hash is {:x}!", hasher.finish());
 203     /// ```
 204     ///
 205     /// [`VecDeque`]: ../../std/collections/struct.VecDeque.html
 206     /// [`as_slices`]: ../../std/collections/struct.VecDeque.html#method.as_slices
 207     /// [`make_contiguous`]: ../../std/collections/struct.VecDeque.html#method.make_contiguous
 208     /// [`hash`]: Hash::hash
 209     /// [`hash_slice`]: Hash::hash_slice
 210     #[stable(feature = "hash_slice", since = "1.3.0")]
 211     fn hash_slice<H: Hasher>(data: &[Self], state: &mut H)
 212     where
 213         Self: Sized,
 214     {
 215         for piece in data {
 216             piece.hash(state);
 217         }
 218     }
 219 }
 220
 221 // Separate module to reexport the macro `Hash` from prelude without the trait `Hash`.
 222 pub(crate) mod macros {
 223     /// Derive macro generating an impl of the trait `Hash`.
 224     #[rustc_builtin_macro]
 225     #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
 226     #[allow_internal_unstable(core_intrinsics)]
 227     pub macro Hash($item:item) {
 228         /* compiler built-in */
 229     }
 230 }
 231 #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
 232 #[doc(inline)]
 233 pub use macros::Hash;
 234
 235 /// A trait for hashing an arbitrary stream of bytes.
 236 ///
 237 /// Instances of `Hasher` usually represent state that is changed while hashing
 238 /// data.
 239 ///
 240 /// `Hasher` provides a fairly basic interface for retrieving the generated hash
 241 /// (with [`finish`]), and writing integers as well as slices of bytes into an
 242 /// instance (with [`write`] and [`write_u8`] etc.). Most of the time, `Hasher`
 243 /// instances are used in conjunction with the [`Hash`] trait.
 244 ///
 245 /// This trait makes no assumptions about how the various `write_*` methods are
 246 /// defined and implementations of [`Hash`] should not assume that they work one
 247 /// way or another. You cannot assume, for example, that a [`write_u32`] call is
 248 /// equivalent to four calls of [`write_u8`].
 249 ///
 250 /// # Examples
 251 ///
 252 /// ```
 253 /// use std::collections::hash_map::DefaultHasher;
 254 /// use std::hash::Hasher;
 255 ///
 256 /// let mut hasher = DefaultHasher::new();
 257 ///
 258 /// hasher.write_u32(1989);
 259 /// hasher.write_u8(11);
 260 /// hasher.write_u8(9);
 261 /// hasher.write(b"Huh?");
 262 ///
 263 /// println!("Hash is {:x}!", hasher.finish());
 264 /// ```
 265 ///
 266 /// [`finish`]: Hasher::finish
 267 /// [`write`]: Hasher::write
 268 /// [`write_u8`]: Hasher::write_u8
 269 /// [`write_u32`]: Hasher::write_u32
 270 #[stable(feature = "rust1", since = "1.0.0")]
 271 pub trait Hasher {
 272     /// Returns the hash value for the values written so far.
 273     ///
 274     /// Despite its name, the method does not reset the hasher’s internal
 275     /// state. Additional [`write`]s will continue from the current value.
 276     /// If you need to start a fresh hash value, you will have to create
 277     /// a new hasher.
 278     ///
 279     /// # Examples
 280     ///
 281     /// ```
 282     /// use std::collections::hash_map::DefaultHasher;
 283     /// use std::hash::Hasher;
 284     ///
 285     /// let mut hasher = DefaultHasher::new();
 286     /// hasher.write(b"Cool!");
 287     ///
 288     /// println!("Hash is {:x}!", hasher.finish());
 289     /// ```
 290     ///
 291     /// [`write`]: Hasher::write
 292     #[stable(feature = "rust1", since = "1.0.0")]
 293     fn finish(&self) -> u64;
 294
 295     /// Writes some data into this `Hasher`.
 296     ///
 297     /// # Examples
 298     ///
 299     /// ```
 300     /// use std::collections::hash_map::DefaultHasher;
 301     /// use std::hash::Hasher;
 302     ///
 303     /// let mut hasher = DefaultHasher::new();
 304     /// let data = [0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef];
 305     ///
 306     /// hasher.write(&data);
 307     ///
 308     /// println!("Hash is {:x}!", hasher.finish());
 309     /// ```
 310     #[stable(feature = "rust1", since = "1.0.0")]
 311     fn write(&mut self, bytes: &[u8]);
 312
 313     /// Writes a single `u8` into this hasher.
 314     #[inline]
 315     #[stable(feature = "hasher_write", since = "1.3.0")]
 316     fn write_u8(&mut self, i: u8) {
 317         self.write(&[i])
 318     }
 319     /// Writes a single `u16` into this hasher.
 320     #[inline]
 321     #[stable(feature = "hasher_write", since = "1.3.0")]
 322     fn write_u16(&mut self, i: u16) {
 323         self.write(&i.to_ne_bytes())
 324     }
 325     /// Writes a single `u32` into this hasher.
 326     #[inline]
 327     #[stable(feature = "hasher_write", since = "1.3.0")]
 328     fn write_u32(&mut self, i: u32) {
 329         self.write(&i.to_ne_bytes())
 330     }
 331     /// Writes a single `u64` into this hasher.
 332     #[inline]
 333     #[stable(feature = "hasher_write", since = "1.3.0")]
 334     fn write_u64(&mut self, i: u64) {
 335         self.write(&i.to_ne_bytes())
 336     }
 337     /// Writes a single `u128` into this hasher.
 338     #[inline]
 339     #[stable(feature = "i128", since = "1.26.0")]
 340     fn write_u128(&mut self, i: u128) {
 341         self.write(&i.to_ne_bytes())
 342     }
 343     /// Writes a single `usize` into this hasher.
 344     #[inline]
 345     #[stable(feature = "hasher_write", since = "1.3.0")]
 346     fn write_usize(&mut self, i: usize) {
 347         self.write(&i.to_ne_bytes())
 348     }
 349
 350     /// Writes a single `i8` into this hasher.
 351     #[inline]
 352     #[stable(feature = "hasher_write", since = "1.3.0")]
 353     fn write_i8(&mut self, i: i8) {
 354         self.write_u8(i as u8)
 355     }
 356     /// Writes a single `i16` into this hasher.
 357     #[inline]
 358     #[stable(feature = "hasher_write", since = "1.3.0")]
 359     fn write_i16(&mut self, i: i16) {
 360         self.write_u16(i as u16)
 361     }
 362     /// Writes a single `i32` into this hasher.
 363     #[inline]
 364     #[stable(feature = "hasher_write", since = "1.3.0")]
 365     fn write_i32(&mut self, i: i32) {
 366         self.write_u32(i as u32)
 367     }
 368     /// Writes a single `i64` into this hasher.
 369     #[inline]
 370     #[stable(feature = "hasher_write", since = "1.3.0")]
 371     fn write_i64(&mut self, i: i64) {
 372         self.write_u64(i as u64)
 373     }
 374     /// Writes a single `i128` into this hasher.
 375     #[inline]
 376     #[stable(feature = "i128", since = "1.26.0")]
 377     fn write_i128(&mut self, i: i128) {
 378         self.write_u128(i as u128)
 379     }
 380     /// Writes a single `isize` into this hasher.
 381     #[inline]
 382     #[stable(feature = "hasher_write", since = "1.3.0")]
 383     fn write_isize(&mut self, i: isize) {
 384         self.write_usize(i as usize)
 385     }
 386 }
 387
 388 #[stable(feature = "indirect_hasher_impl", since = "1.22.0")]
 389 impl<H: Hasher + ?Sized> Hasher for &mut H {
 390     fn finish(&self) -> u64 {
 391         (**self).finish()
 392     }
 393     fn write(&mut self, bytes: &[u8]) {
 394         (**self).write(bytes)
 395     }
 396     fn write_u8(&mut self, i: u8) {
 397         (**self).write_u8(i)
 398     }
 399     fn write_u16(&mut self, i: u16) {
 400         (**self).write_u16(i)
 401     }
 402     fn write_u32(&mut self, i: u32) {
 403         (**self).write_u32(i)
 404     }
 405     fn write_u64(&mut self, i: u64) {
 406         (**self).write_u64(i)
 407     }
 408     fn write_u128(&mut self, i: u128) {
 409         (**self).write_u128(i)
 410     }
 411     fn write_usize(&mut self, i: usize) {
 412         (**self).write_usize(i)
 413     }
 414     fn write_i8(&mut self, i: i8) {
 415         (**self).write_i8(i)
 416     }
 417     fn write_i16(&mut self, i: i16) {
 418         (**self).write_i16(i)
 419     }
 420     fn write_i32(&mut self, i: i32) {
 421         (**self).write_i32(i)
 422     }
 423     fn write_i64(&mut self, i: i64) {
 424         (**self).write_i64(i)
 425     }
 426     fn write_i128(&mut self, i: i128) {
 427         (**self).write_i128(i)
 428     }
 429     fn write_isize(&mut self, i: isize) {
 430         (**self).write_isize(i)
 431     }
 432 }
 433
 434 /// A trait for creating instances of [`Hasher`].
 435 ///
 436 /// A `BuildHasher` is typically used (e.g., by [`HashMap`]) to create
 437 /// [`Hasher`]s for each key such that they are hashed independently of one
 438 /// another, since [`Hasher`]s contain state.
 439 ///
 440 /// For each instance of `BuildHasher`, the [`Hasher`]s created by
 441 /// [`build_hasher`] should be identical. That is, if the same stream of bytes
 442 /// is fed into each hasher, the same output will also be generated.
 443 ///
 444 /// # Examples
 445 ///
 446 /// ```
 447 /// use std::collections::hash_map::RandomState;
 448 /// use std::hash::{BuildHasher, Hasher};
 449 ///
 450 /// let s = RandomState::new();
 451 /// let mut hasher_1 = s.build_hasher();
 452 /// let mut hasher_2 = s.build_hasher();
 453 ///
 454 /// hasher_1.write_u32(8128);
 455 /// hasher_2.write_u32(8128);
 456 ///
 457 /// assert_eq!(hasher_1.finish(), hasher_2.finish());
 458 /// ```
 459 ///
 460 /// [`build_hasher`]: BuildHasher::build_hasher
 461 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
 462 #[stable(since = "1.7.0", feature = "build_hasher")]
 463 pub trait BuildHasher {
 464     /// Type of the hasher that will be created.
 465     #[stable(since = "1.7.0", feature = "build_hasher")]
 466     type Hasher: Hasher;
 467
 468     /// Creates a new hasher.
 469     ///
 470     /// Each call to `build_hasher` on the same instance should produce identical
 471     /// [`Hasher`]s.
 472     ///
 473     /// # Examples
 474     ///
 475     /// ```
 476     /// use std::collections::hash_map::RandomState;
 477     /// use std::hash::BuildHasher;
 478     ///
 479     /// let s = RandomState::new();
 480     /// let new_s = s.build_hasher();
 481     /// ```
 482     #[stable(since = "1.7.0", feature = "build_hasher")]
 483     fn build_hasher(&self) -> Self::Hasher;
 484
 485     /// Calculates the hash of a single value.
 486     ///
 487     /// This is intended as a convenience for code which *consumes* hashes, such
 488     /// as the implementation of a hash table or in unit tests that check
 489     /// whether a custom [`Hash`] implementation behaves as expected.
 490     ///
 491     /// This must not be used in any code which *creates* hashes, such as in an
 492     /// implementation of [`Hash`].  The way to create a combined hash of
 493     /// multiple values is to call [`Hash::hash`] multiple times using the same
 494     /// [`Hasher`], not to call this method repeatedly and combine the results.
 495     ///
 496     /// # Example
 497     ///
 498     /// ```
 499     /// #![feature(build_hasher_simple_hash_one)]
 500     ///
 501     /// use std::cmp::{max, min};
 502     /// use std::hash::{BuildHasher, Hash, Hasher};
 503     /// struct OrderAmbivalentPair<T: Ord>(T, T);
 504     /// impl<T: Ord + Hash> Hash for OrderAmbivalentPair<T> {
 505     ///     fn hash<H: Hasher>(&self, hasher: &mut H) {
 506     ///         min(&self.0, &self.1).hash(hasher);
 507     ///         max(&self.0, &self.1).hash(hasher);
 508     ///     }
 509     /// }
 510     ///
 511     /// // Then later, in a `#[test]` for the type...
 512     /// let bh = std::collections::hash_map::RandomState::new();
 513     /// assert_eq!(
 514     ///     bh.hash_one(OrderAmbivalentPair(1, 2)),
 515     ///     bh.hash_one(OrderAmbivalentPair(2, 1))
 516     /// );
 517     /// assert_eq!(
 518     ///     bh.hash_one(OrderAmbivalentPair(10, 2)),
 519     ///     bh.hash_one(&OrderAmbivalentPair(2, 10))
 520     /// );
 521     /// ```
 522     #[unstable(feature = "build_hasher_simple_hash_one", issue = "86161")]
 523     fn hash_one<T: Hash>(&self, x: T) -> u64
 524     where
 525         Self: Sized,
 526     {
 527         let mut hasher = self.build_hasher();
 528         x.hash(&mut hasher);
 529         hasher.finish()
 530     }
 531 }
 532
 533 /// Used to create a default [`BuildHasher`] instance for types that implement
 534 /// [`Hasher`] and [`Default`].
 535 ///
 536 /// `BuildHasherDefault<H>` can be used when a type `H` implements [`Hasher`] and
 537 /// [`Default`], and you need a corresponding [`BuildHasher`] instance, but none is
 538 /// defined.
 539 ///
 540 /// Any `BuildHasherDefault` is [zero-sized]. It can be created with
 541 /// [`default`][method.default]. When using `BuildHasherDefault` with [`HashMap`] or
 542 /// [`HashSet`], this doesn't need to be done, since they implement appropriate
 543 /// [`Default`] instances themselves.
 544 ///
 545 /// # Examples
 546 ///
 547 /// Using `BuildHasherDefault` to specify a custom [`BuildHasher`] for
 548 /// [`HashMap`]:
 549 ///
 550 /// ```
 551 /// use std::collections::HashMap;
 552 /// use std::hash::{BuildHasherDefault, Hasher};
 553 ///
 554 /// #[derive(Default)]
 555 /// struct MyHasher;
 556 ///
 557 /// impl Hasher for MyHasher {
 558 ///     fn write(&mut self, bytes: &[u8]) {
 559 ///         // Your hashing algorithm goes here!
 560 ///        unimplemented!()
 561 ///     }
 562 ///
 563 ///     fn finish(&self) -> u64 {
 564 ///         // Your hashing algorithm goes here!
 565 ///         unimplemented!()
 566 ///     }
 567 /// }
 568 ///
 569 /// type MyBuildHasher = BuildHasherDefault<MyHasher>;
 570 ///
 571 /// let hash_map = HashMap::<u32, u32, MyBuildHasher>::default();
 572 /// ```
 573 ///
 574 /// [method.default]: BuildHasherDefault::default
 575 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
 576 /// [`HashSet`]: ../../std/collections/struct.HashSet.html
 577 /// [zero-sized]: https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts
 578 #[stable(since = "1.7.0", feature = "build_hasher")]
 579 pub struct BuildHasherDefault<H>(marker::PhantomData<H>);
 580
 581 #[stable(since = "1.9.0", feature = "core_impl_debug")]
 582 impl<H> fmt::Debug for BuildHasherDefault<H> {
 583     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 584         f.debug_struct("BuildHasherDefault").finish()
 585     }
 586 }
 587
 588 #[stable(since = "1.7.0", feature = "build_hasher")]
 589 impl<H: Default + Hasher> BuildHasher for BuildHasherDefault<H> {
 590     type Hasher = H;
 591
 592     fn build_hasher(&self) -> H {
 593         H::default()
 594     }
 595 }
 596
 597 #[stable(since = "1.7.0", feature = "build_hasher")]
 598 impl<H> Clone for BuildHasherDefault<H> {
 599     fn clone(&self) -> BuildHasherDefault<H> {
 600         BuildHasherDefault(marker::PhantomData)
 601     }
 602 }
 603
 604 #[stable(since = "1.7.0", feature = "build_hasher")]
 605 #[rustc_const_unstable(feature = "const_default_impls", issue = "87864")]
 606 impl<H> const Default for BuildHasherDefault<H> {
 607     fn default() -> BuildHasherDefault<H> {
 608         BuildHasherDefault(marker::PhantomData)
 609     }
 610 }
 611
 612 #[stable(since = "1.29.0", feature = "build_hasher_eq")]
 613 impl<H> PartialEq for BuildHasherDefault<H> {
 614     fn eq(&self, _other: &BuildHasherDefault<H>) -> bool {
 615         true
 616     }
 617 }
 618
 619 #[stable(since = "1.29.0", feature = "build_hasher_eq")]
 620 impl<H> Eq for BuildHasherDefault<H> {}
 621
 622 mod impls {
 623     use crate::mem;
 624     use crate::slice;
 625
 626     use super::*;
 627
 628     macro_rules! impl_write {
 629         ($(($ty:ident, $meth:ident),)*) => {$(
 630             #[stable(feature = "rust1", since = "1.0.0")]
 631             impl Hash for $ty {
 632                 #[inline]
 633                 fn hash<H: Hasher>(&self, state: &mut H) {
 634                     state.$meth(*self)
 635                 }
 636
 637                 #[inline]
 638                 fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
 639                     let newlen = data.len() * mem::size_of::<$ty>();
 640                     let ptr = data.as_ptr() as *const u8;
 641                     // SAFETY: `ptr` is valid and aligned, as this macro is only used
 642                     // for numeric primitives which have no padding. The new slice only
 643                     // spans across `data` and is never mutated, and its total size is the
 644                     // same as the original `data` so it can't be over `isize::MAX`.
 645                     state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
 646                 }
 647             }
 648         )*}
 649     }
 650
 651     impl_write! {
 652         (u8, write_u8),
 653         (u16, write_u16),
 654         (u32, write_u32),
 655         (u64, write_u64),
 656         (usize, write_usize),
 657         (i8, write_i8),
 658         (i16, write_i16),
 659         (i32, write_i32),
 660         (i64, write_i64),
 661         (isize, write_isize),
 662         (u128, write_u128),
 663         (i128, write_i128),
 664     }
 665
 666     #[stable(feature = "rust1", since = "1.0.0")]
 667     impl Hash for bool {
 668         #[inline]
 669         fn hash<H: Hasher>(&self, state: &mut H) {
 670             state.write_u8(*self as u8)
 671         }
 672     }
 673
 674     #[stable(feature = "rust1", since = "1.0.0")]
 675     impl Hash for char {
 676         #[inline]
 677         fn hash<H: Hasher>(&self, state: &mut H) {
 678             state.write_u32(*self as u32)
 679         }
 680     }
 681
 682     #[stable(feature = "rust1", since = "1.0.0")]
 683     impl Hash for str {
 684         #[inline]
 685         fn hash<H: Hasher>(&self, state: &mut H) {
 686             state.write(self.as_bytes());
 687             state.write_u8(0xff)
 688         }
 689     }
 690
 691     #[stable(feature = "never_hash", since = "1.29.0")]
 692     impl Hash for ! {
 693         #[inline]
 694         fn hash<H: Hasher>(&self, _: &mut H) {
 695             *self
 696         }
 697     }
 698
 699     macro_rules! impl_hash_tuple {
 700         () => (
 701             #[stable(feature = "rust1", since = "1.0.0")]
 702             impl Hash for () {
 703                 #[inline]
 704                 fn hash<H: Hasher>(&self, _state: &mut H) {}
 705             }
 706         );
 707
 708         ( $($name:ident)+) => (
 709             #[stable(feature = "rust1", since = "1.0.0")]
 710             impl<$($name: Hash),+> Hash for ($($name,)+) where last_type!($($name,)+): ?Sized {
 711                 #[allow(non_snake_case)]
 712                 #[inline]
 713                 fn hash<S: Hasher>(&self, state: &mut S) {
 714                     let ($(ref $name,)+) = *self;
 715                     $($name.hash(state);)+
 716                 }
 717             }
 718         );
 719     }
 720
 721     macro_rules! last_type {
 722         ($a:ident,) => { $a };
 723         ($a:ident, $($rest_a:ident,)+) => { last_type!($($rest_a,)+) };
 724     }
 725
 726     impl_hash_tuple! {}
 727     impl_hash_tuple! { A }
 728     impl_hash_tuple! { A B }
 729     impl_hash_tuple! { A B C }
 730     impl_hash_tuple! { A B C D }
 731     impl_hash_tuple! { A B C D E }
 732     impl_hash_tuple! { A B C D E F }
 733     impl_hash_tuple! { A B C D E F G }
 734     impl_hash_tuple! { A B C D E F G H }
 735     impl_hash_tuple! { A B C D E F G H I }
 736     impl_hash_tuple! { A B C D E F G H I J }
 737     impl_hash_tuple! { A B C D E F G H I J K }
 738     impl_hash_tuple! { A B C D E F G H I J K L }
 739
 740     #[stable(feature = "rust1", since = "1.0.0")]
 741     impl<T: Hash> Hash for [T] {
 742         #[inline]
 743         fn hash<H: Hasher>(&self, state: &mut H) {
 744             self.len().hash(state);
 745             Hash::hash_slice(self, state)
 746         }
 747     }
 748
 749     #[stable(feature = "rust1", since = "1.0.0")]
 750     impl<T: ?Sized + Hash> Hash for &T {
 751         #[inline]
 752         fn hash<H: Hasher>(&self, state: &mut H) {
 753             (**self).hash(state);
 754         }
 755     }
 756
 757     #[stable(feature = "rust1", since = "1.0.0")]
 758     impl<T: ?Sized + Hash> Hash for &mut T {
 759         #[inline]
 760         fn hash<H: Hasher>(&self, state: &mut H) {
 761             (**self).hash(state);
 762         }
 763     }
 764
 765     #[stable(feature = "rust1", since = "1.0.0")]
 766     impl<T: ?Sized> Hash for *const T {
 767         #[inline]
 768         fn hash<H: Hasher>(&self, state: &mut H) {
 769             let (address, metadata) = self.to_raw_parts();
 770             state.write_usize(address as usize);
 771             metadata.hash(state);
 772         }
 773     }
 774
 775     #[stable(feature = "rust1", since = "1.0.0")]
 776     impl<T: ?Sized> Hash for *mut T {
 777         #[inline]
 778         fn hash<H: Hasher>(&self, state: &mut H) {
 779             let (address, metadata) = self.to_raw_parts();
 780             state.write_usize(address as usize);
 781             metadata.hash(state);
 782         }
 783     }
 784 }