src/libcore/hash/mod.rs

   1 //! Generic hashing support.
   2 //!
   3 //! This module provides a generic way to compute the hash of a value. The
   4 //! simplest way to make a type hashable is to use `#[derive(Hash)]`:
   5 //!
   6 //! # Examples
   7 //!
   8 //! ```rust
   9 //! use std::collections::hash_map::DefaultHasher;
  10 //! use std::hash::{Hash, Hasher};
  11 //!
  12 //! #[derive(Hash)]
  13 //! struct Person {
  14 //!     id: u32,
  15 //!     name: String,
  16 //!     phone: u64,
  17 //! }
  18 //!
  19 //! let person1 = Person {
  20 //!     id: 5,
  21 //!     name: "Janet".to_string(),
  22 //!     phone: 555_666_7777,
  23 //! };
  24 //! let person2 = Person {
  25 //!     id: 5,
  26 //!     name: "Bob".to_string(),
  27 //!     phone: 555_666_7777,
  28 //! };
  29 //!
  30 //! assert!(calculate_hash(&person1) != calculate_hash(&person2));
  31 //!
  32 //! fn calculate_hash<T: Hash>(t: &T) -> u64 {
  33 //!     let mut s = DefaultHasher::new();
  34 //!     t.hash(&mut s);
  35 //!     s.finish()
  36 //! }
  37 //! ```
  38 //!
  39 //! If you need more control over how a value is hashed, you need to implement
  40 //! the [`Hash`] trait:
  41 //!
  42 //! [`Hash`]: trait.Hash.html
  43 //!
  44 //! ```rust
  45 //! use std::collections::hash_map::DefaultHasher;
  46 //! use std::hash::{Hash, Hasher};
  47 //!
  48 //! struct Person {
  49 //!     id: u32,
  50 //!     # #[allow(dead_code)]
  51 //!     name: String,
  52 //!     phone: u64,
  53 //! }
  54 //!
  55 //! impl Hash for Person {
  56 //!     fn hash<H: Hasher>(&self, state: &mut H) {
  57 //!         self.id.hash(state);
  58 //!         self.phone.hash(state);
  59 //!     }
  60 //! }
  61 //!
  62 //! let person1 = Person {
  63 //!     id: 5,
  64 //!     name: "Janet".to_string(),
  65 //!     phone: 555_666_7777,
  66 //! };
  67 //! let person2 = Person {
  68 //!     id: 5,
  69 //!     name: "Bob".to_string(),
  70 //!     phone: 555_666_7777,
  71 //! };
  72 //!
  73 //! assert_eq!(calculate_hash(&person1), calculate_hash(&person2));
  74 //!
  75 //! fn calculate_hash<T: Hash>(t: &T) -> u64 {
  76 //!     let mut s = DefaultHasher::new();
  77 //!     t.hash(&mut s);
  78 //!     s.finish()
  79 //! }
  80 //! ```
  81
  82 // ignore-tidy-undocumented-unsafe
  83
  84 #![stable(feature = "rust1", since = "1.0.0")]
  85
  86 use crate::fmt;
  87 use crate::marker;
  88
  89 #[stable(feature = "rust1", since = "1.0.0")]
  90 #[allow(deprecated)]
  91 pub use self::sip::SipHasher;
  92
  93 #[unstable(feature = "hashmap_internals", issue = "none")]
  94 #[allow(deprecated)]
  95 #[doc(hidden)]
  96 pub use self::sip::SipHasher13;
  97
  98 mod sip;
  99
 100 /// A hashable type.
 101 ///
 102 /// Types implementing `Hash` are able to be [`hash`]ed with an instance of
 103 /// [`Hasher`].
 104 ///
 105 /// ## Implementing `Hash`
 106 ///
 107 /// You can derive `Hash` with `#[derive(Hash)]` if all fields implement `Hash`.
 108 /// The resulting hash will be the combination of the values from calling
 109 /// [`hash`] on each field.
 110 ///
 111 /// ```
 112 /// #[derive(Hash)]
 113 /// struct Rustacean {
 114 ///     name: String,
 115 ///     country: String,
 116 /// }
 117 /// ```
 118 ///
 119 /// If you need more control over how a value is hashed, you can of course
 120 /// implement the `Hash` trait yourself:
 121 ///
 122 /// ```
 123 /// use std::hash::{Hash, Hasher};
 124 ///
 125 /// struct Person {
 126 ///     id: u32,
 127 ///     name: String,
 128 ///     phone: u64,
 129 /// }
 130 ///
 131 /// impl Hash for Person {
 132 ///     fn hash<H: Hasher>(&self, state: &mut H) {
 133 ///         self.id.hash(state);
 134 ///         self.phone.hash(state);
 135 ///     }
 136 /// }
 137 /// ```
 138 ///
 139 /// ## `Hash` and `Eq`
 140 ///
 141 /// When implementing both `Hash` and [`Eq`], it is important that the following
 142 /// property holds:
 143 ///
 144 /// ```text
 145 /// k1 == k2 -> hash(k1) == hash(k2)
 146 /// ```
 147 ///
 148 /// In other words, if two keys are equal, their hashes must also be equal.
 149 /// [`HashMap`] and [`HashSet`] both rely on this behavior.
 150 ///
 151 /// Thankfully, you won't need to worry about upholding this property when
 152 /// deriving both [`Eq`] and `Hash` with `#[derive(PartialEq, Eq, Hash)]`.
 153 ///
 154 /// [`Eq`]: ../../std/cmp/trait.Eq.html
 155 /// [`Hasher`]: trait.Hasher.html
 156 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
 157 /// [`HashSet`]: ../../std/collections/struct.HashSet.html
 158 /// [`hash`]: #tymethod.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     ///
 174     /// [`Hasher`]: trait.Hasher.html
 175     #[stable(feature = "rust1", since = "1.0.0")]
 176     fn hash<H: Hasher>(&self, state: &mut H);
 177
 178     /// Feeds a slice of this type into the given [`Hasher`].
 179     ///
 180     /// # Examples
 181     ///
 182     /// ```
 183     /// use std::collections::hash_map::DefaultHasher;
 184     /// use std::hash::{Hash, Hasher};
 185     ///
 186     /// let mut hasher = DefaultHasher::new();
 187     /// let numbers = [6, 28, 496, 8128];
 188     /// Hash::hash_slice(&numbers, &mut hasher);
 189     /// println!("Hash is {:x}!", hasher.finish());
 190     /// ```
 191     ///
 192     /// [`Hasher`]: trait.Hasher.html
 193     #[stable(feature = "hash_slice", since = "1.3.0")]
 194     fn hash_slice<H: Hasher>(data: &[Self], state: &mut H)
 195     where
 196         Self: Sized,
 197     {
 198         for piece in data {
 199             piece.hash(state);
 200         }
 201     }
 202 }
 203
 204 // Separate module to reexport the macro `Hash` from prelude without the trait `Hash`.
 205 pub(crate) mod macros {
 206     /// Derive macro generating an impl of the trait `Hash`.
 207     #[rustc_builtin_macro]
 208     #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
 209     #[allow_internal_unstable(core_intrinsics)]
 210     pub macro Hash($item:item) {
 211         /* compiler built-in */
 212     }
 213 }
 214 #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
 215 #[doc(inline)]
 216 pub use macros::Hash;
 217
 218 /// A trait for hashing an arbitrary stream of bytes.
 219 ///
 220 /// Instances of `Hasher` usually represent state that is changed while hashing
 221 /// data.
 222 ///
 223 /// `Hasher` provides a fairly basic interface for retrieving the generated hash
 224 /// (with [`finish`]), and writing integers as well as slices of bytes into an
 225 /// instance (with [`write`] and [`write_u8`] etc.). Most of the time, `Hasher`
 226 /// instances are used in conjunction with the [`Hash`] trait.
 227 ///
 228 /// # Examples
 229 ///
 230 /// ```
 231 /// use std::collections::hash_map::DefaultHasher;
 232 /// use std::hash::Hasher;
 233 ///
 234 /// let mut hasher = DefaultHasher::new();
 235 ///
 236 /// hasher.write_u32(1989);
 237 /// hasher.write_u8(11);
 238 /// hasher.write_u8(9);
 239 /// hasher.write(b"Huh?");
 240 ///
 241 /// println!("Hash is {:x}!", hasher.finish());
 242 /// ```
 243 ///
 244 /// [`Hash`]: trait.Hash.html
 245 /// [`finish`]: #tymethod.finish
 246 /// [`write`]: #tymethod.write
 247 /// [`write_u8`]: #method.write_u8
 248 #[stable(feature = "rust1", since = "1.0.0")]
 249 pub trait Hasher {
 250     /// Returns the hash value for the values written so far.
 251     ///
 252     /// Despite its name, the method does not reset the hasher’s internal
 253     /// state. Additional [`write`]s will continue from the current value.
 254     /// If you need to start a fresh hash value, you will have to create
 255     /// a new hasher.
 256     ///
 257     /// # Examples
 258     ///
 259     /// ```
 260     /// use std::collections::hash_map::DefaultHasher;
 261     /// use std::hash::Hasher;
 262     ///
 263     /// let mut hasher = DefaultHasher::new();
 264     /// hasher.write(b"Cool!");
 265     ///
 266     /// println!("Hash is {:x}!", hasher.finish());
 267     /// ```
 268     ///
 269     /// [`write`]: #tymethod.write
 270     #[stable(feature = "rust1", since = "1.0.0")]
 271     fn finish(&self) -> u64;
 272
 273     /// Writes some data into this `Hasher`.
 274     ///
 275     /// # Examples
 276     ///
 277     /// ```
 278     /// use std::collections::hash_map::DefaultHasher;
 279     /// use std::hash::Hasher;
 280     ///
 281     /// let mut hasher = DefaultHasher::new();
 282     /// let data = [0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef];
 283     ///
 284     /// hasher.write(&data);
 285     ///
 286     /// println!("Hash is {:x}!", hasher.finish());
 287     /// ```
 288     #[stable(feature = "rust1", since = "1.0.0")]
 289     fn write(&mut self, bytes: &[u8]);
 290
 291     /// Writes a single `u8` into this hasher.
 292     #[inline]
 293     #[stable(feature = "hasher_write", since = "1.3.0")]
 294     fn write_u8(&mut self, i: u8) {
 295         self.write(&[i])
 296     }
 297     /// Writes a single `u16` into this hasher.
 298     #[inline]
 299     #[stable(feature = "hasher_write", since = "1.3.0")]
 300     fn write_u16(&mut self, i: u16) {
 301         self.write(&i.to_ne_bytes())
 302     }
 303     /// Writes a single `u32` into this hasher.
 304     #[inline]
 305     #[stable(feature = "hasher_write", since = "1.3.0")]
 306     fn write_u32(&mut self, i: u32) {
 307         self.write(&i.to_ne_bytes())
 308     }
 309     /// Writes a single `u64` into this hasher.
 310     #[inline]
 311     #[stable(feature = "hasher_write", since = "1.3.0")]
 312     fn write_u64(&mut self, i: u64) {
 313         self.write(&i.to_ne_bytes())
 314     }
 315     /// Writes a single `u128` into this hasher.
 316     #[inline]
 317     #[stable(feature = "i128", since = "1.26.0")]
 318     fn write_u128(&mut self, i: u128) {
 319         self.write(&i.to_ne_bytes())
 320     }
 321     /// Writes a single `usize` into this hasher.
 322     #[inline]
 323     #[stable(feature = "hasher_write", since = "1.3.0")]
 324     fn write_usize(&mut self, i: usize) {
 325         self.write(&i.to_ne_bytes())
 326     }
 327
 328     /// Writes a single `i8` into this hasher.
 329     #[inline]
 330     #[stable(feature = "hasher_write", since = "1.3.0")]
 331     fn write_i8(&mut self, i: i8) {
 332         self.write_u8(i as u8)
 333     }
 334     /// Writes a single `i16` into this hasher.
 335     #[inline]
 336     #[stable(feature = "hasher_write", since = "1.3.0")]
 337     fn write_i16(&mut self, i: i16) {
 338         self.write(&i.to_ne_bytes())
 339     }
 340     /// Writes a single `i32` into this hasher.
 341     #[inline]
 342     #[stable(feature = "hasher_write", since = "1.3.0")]
 343     fn write_i32(&mut self, i: i32) {
 344         self.write(&i.to_ne_bytes())
 345     }
 346     /// Writes a single `i64` into this hasher.
 347     #[inline]
 348     #[stable(feature = "hasher_write", since = "1.3.0")]
 349     fn write_i64(&mut self, i: i64) {
 350         self.write(&i.to_ne_bytes())
 351     }
 352     /// Writes a single `i128` into this hasher.
 353     #[inline]
 354     #[stable(feature = "i128", since = "1.26.0")]
 355     fn write_i128(&mut self, i: i128) {
 356         self.write(&i.to_ne_bytes())
 357     }
 358     /// Writes a single `isize` into this hasher.
 359     #[inline]
 360     #[stable(feature = "hasher_write", since = "1.3.0")]
 361     fn write_isize(&mut self, i: isize) {
 362         self.write(&i.to_ne_bytes())
 363     }
 364 }
 365
 366 #[stable(feature = "indirect_hasher_impl", since = "1.22.0")]
 367 impl<H: Hasher + ?Sized> Hasher for &mut H {
 368     fn finish(&self) -> u64 {
 369         (**self).finish()
 370     }
 371     fn write(&mut self, bytes: &[u8]) {
 372         (**self).write(bytes)
 373     }
 374     fn write_u8(&mut self, i: u8) {
 375         (**self).write_u8(i)
 376     }
 377     fn write_u16(&mut self, i: u16) {
 378         (**self).write_u16(i)
 379     }
 380     fn write_u32(&mut self, i: u32) {
 381         (**self).write_u32(i)
 382     }
 383     fn write_u64(&mut self, i: u64) {
 384         (**self).write_u64(i)
 385     }
 386     fn write_u128(&mut self, i: u128) {
 387         (**self).write_u128(i)
 388     }
 389     fn write_usize(&mut self, i: usize) {
 390         (**self).write_usize(i)
 391     }
 392     fn write_i8(&mut self, i: i8) {
 393         (**self).write_i8(i)
 394     }
 395     fn write_i16(&mut self, i: i16) {
 396         (**self).write_i16(i)
 397     }
 398     fn write_i32(&mut self, i: i32) {
 399         (**self).write_i32(i)
 400     }
 401     fn write_i64(&mut self, i: i64) {
 402         (**self).write_i64(i)
 403     }
 404     fn write_i128(&mut self, i: i128) {
 405         (**self).write_i128(i)
 406     }
 407     fn write_isize(&mut self, i: isize) {
 408         (**self).write_isize(i)
 409     }
 410 }
 411
 412 /// A trait for creating instances of [`Hasher`].
 413 ///
 414 /// A `BuildHasher` is typically used (e.g., by [`HashMap`]) to create
 415 /// [`Hasher`]s for each key such that they are hashed independently of one
 416 /// another, since [`Hasher`]s contain state.
 417 ///
 418 /// For each instance of `BuildHasher`, the [`Hasher`]s created by
 419 /// [`build_hasher`] should be identical. That is, if the same stream of bytes
 420 /// is fed into each hasher, the same output will also be generated.
 421 ///
 422 /// # Examples
 423 ///
 424 /// ```
 425 /// use std::collections::hash_map::RandomState;
 426 /// use std::hash::{BuildHasher, Hasher};
 427 ///
 428 /// let s = RandomState::new();
 429 /// let mut hasher_1 = s.build_hasher();
 430 /// let mut hasher_2 = s.build_hasher();
 431 ///
 432 /// hasher_1.write_u32(8128);
 433 /// hasher_2.write_u32(8128);
 434 ///
 435 /// assert_eq!(hasher_1.finish(), hasher_2.finish());
 436 /// ```
 437 ///
 438 /// [`build_hasher`]: #tymethod.build_hasher
 439 /// [`Hasher`]: trait.Hasher.html
 440 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
 441 #[stable(since = "1.7.0", feature = "build_hasher")]
 442 pub trait BuildHasher {
 443     /// Type of the hasher that will be created.
 444     #[stable(since = "1.7.0", feature = "build_hasher")]
 445     type Hasher: Hasher;
 446
 447     /// Creates a new hasher.
 448     ///
 449     /// Each call to `build_hasher` on the same instance should produce identical
 450     /// [`Hasher`]s.
 451     ///
 452     /// # Examples
 453     ///
 454     /// ```
 455     /// use std::collections::hash_map::RandomState;
 456     /// use std::hash::BuildHasher;
 457     ///
 458     /// let s = RandomState::new();
 459     /// let new_s = s.build_hasher();
 460     /// ```
 461     ///
 462     /// [`Hasher`]: trait.Hasher.html
 463     #[stable(since = "1.7.0", feature = "build_hasher")]
 464     fn build_hasher(&self) -> Self::Hasher;
 465 }
 466
 467 /// Used to create a default [`BuildHasher`] instance for types that implement
 468 /// [`Hasher`] and [`Default`].
 469 ///
 470 /// `BuildHasherDefault<H>` can be used when a type `H` implements [`Hasher`] and
 471 /// [`Default`], and you need a corresponding [`BuildHasher`] instance, but none is
 472 /// defined.
 473 ///
 474 /// Any `BuildHasherDefault` is [zero-sized]. It can be created with
 475 /// [`default`][method.Default]. When using `BuildHasherDefault` with [`HashMap`] or
 476 /// [`HashSet`], this doesn't need to be done, since they implement appropriate
 477 /// [`Default`] instances themselves.
 478 ///
 479 /// # Examples
 480 ///
 481 /// Using `BuildHasherDefault` to specify a custom [`BuildHasher`] for
 482 /// [`HashMap`]:
 483 ///
 484 /// ```
 485 /// use std::collections::HashMap;
 486 /// use std::hash::{BuildHasherDefault, Hasher};
 487 ///
 488 /// #[derive(Default)]
 489 /// struct MyHasher;
 490 ///
 491 /// impl Hasher for MyHasher {
 492 ///     fn write(&mut self, bytes: &[u8]) {
 493 ///         // Your hashing algorithm goes here!
 494 ///        unimplemented!()
 495 ///     }
 496 ///
 497 ///     fn finish(&self) -> u64 {
 498 ///         // Your hashing algorithm goes here!
 499 ///         unimplemented!()
 500 ///     }
 501 /// }
 502 ///
 503 /// type MyBuildHasher = BuildHasherDefault<MyHasher>;
 504 ///
 505 /// let hash_map = HashMap::<u32, u32, MyBuildHasher>::default();
 506 /// ```
 507 ///
 508 /// [`BuildHasher`]: trait.BuildHasher.html
 509 /// [`Default`]: ../default/trait.Default.html
 510 /// [method.default]: #method.default
 511 /// [`Hasher`]: trait.Hasher.html
 512 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
 513 /// [`HashSet`]: ../../std/collections/struct.HashSet.html
 514 /// [zero-sized]: https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts
 515 #[stable(since = "1.7.0", feature = "build_hasher")]
 516 pub struct BuildHasherDefault<H>(marker::PhantomData<H>);
 517
 518 #[stable(since = "1.9.0", feature = "core_impl_debug")]
 519 impl<H> fmt::Debug for BuildHasherDefault<H> {
 520     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 521         f.pad("BuildHasherDefault")
 522     }
 523 }
 524
 525 #[stable(since = "1.7.0", feature = "build_hasher")]
 526 impl<H: Default + Hasher> BuildHasher for BuildHasherDefault<H> {
 527     type Hasher = H;
 528
 529     fn build_hasher(&self) -> H {
 530         H::default()
 531     }
 532 }
 533
 534 #[stable(since = "1.7.0", feature = "build_hasher")]
 535 impl<H> Clone for BuildHasherDefault<H> {
 536     fn clone(&self) -> BuildHasherDefault<H> {
 537         BuildHasherDefault(marker::PhantomData)
 538     }
 539 }
 540
 541 #[stable(since = "1.7.0", feature = "build_hasher")]
 542 impl<H> Default for BuildHasherDefault<H> {
 543     fn default() -> BuildHasherDefault<H> {
 544         BuildHasherDefault(marker::PhantomData)
 545     }
 546 }
 547
 548 #[stable(since = "1.29.0", feature = "build_hasher_eq")]
 549 impl<H> PartialEq for BuildHasherDefault<H> {
 550     fn eq(&self, _other: &BuildHasherDefault<H>) -> bool {
 551         true
 552     }
 553 }
 554
 555 #[stable(since = "1.29.0", feature = "build_hasher_eq")]
 556 impl<H> Eq for BuildHasherDefault<H> {}
 557
 558 mod impls {
 559     use crate::mem;
 560     use crate::slice;
 561
 562     use super::*;
 563
 564     macro_rules! impl_write {
 565         ($(($ty:ident, $meth:ident),)*) => {$(
 566             #[stable(feature = "rust1", since = "1.0.0")]
 567             impl Hash for $ty {
 568                 fn hash<H: Hasher>(&self, state: &mut H) {
 569                     state.$meth(*self)
 570                 }
 571
 572                 fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
 573                     let newlen = data.len() * mem::size_of::<$ty>();
 574                     let ptr = data.as_ptr() as *const u8;
 575                     state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
 576                 }
 577             }
 578         )*}
 579     }
 580
 581     impl_write! {
 582         (u8, write_u8),
 583         (u16, write_u16),
 584         (u32, write_u32),
 585         (u64, write_u64),
 586         (usize, write_usize),
 587         (i8, write_i8),
 588         (i16, write_i16),
 589         (i32, write_i32),
 590         (i64, write_i64),
 591         (isize, write_isize),
 592         (u128, write_u128),
 593         (i128, write_i128),
 594     }
 595
 596     #[stable(feature = "rust1", since = "1.0.0")]
 597     impl Hash for bool {
 598         fn hash<H: Hasher>(&self, state: &mut H) {
 599             state.write_u8(*self as u8)
 600         }
 601     }
 602
 603     #[stable(feature = "rust1", since = "1.0.0")]
 604     impl Hash for char {
 605         fn hash<H: Hasher>(&self, state: &mut H) {
 606             state.write_u32(*self as u32)
 607         }
 608     }
 609
 610     #[stable(feature = "rust1", since = "1.0.0")]
 611     impl Hash for str {
 612         fn hash<H: Hasher>(&self, state: &mut H) {
 613             state.write(self.as_bytes());
 614             state.write_u8(0xff)
 615         }
 616     }
 617
 618     #[stable(feature = "never_hash", since = "1.29.0")]
 619     impl Hash for ! {
 620         fn hash<H: Hasher>(&self, _: &mut H) {
 621             *self
 622         }
 623     }
 624
 625     macro_rules! impl_hash_tuple {
 626         () => (
 627             #[stable(feature = "rust1", since = "1.0.0")]
 628             impl Hash for () {
 629                 fn hash<H: Hasher>(&self, _state: &mut H) {}
 630             }
 631         );
 632
 633         ( $($name:ident)+) => (
 634             #[stable(feature = "rust1", since = "1.0.0")]
 635             impl<$($name: Hash),+> Hash for ($($name,)+) where last_type!($($name,)+): ?Sized {
 636                 #[allow(non_snake_case)]
 637                 fn hash<S: Hasher>(&self, state: &mut S) {
 638                     let ($(ref $name,)+) = *self;
 639                     $($name.hash(state);)+
 640                 }
 641             }
 642         );
 643     }
 644
 645     macro_rules! last_type {
 646         ($a:ident,) => { $a };
 647         ($a:ident, $($rest_a:ident,)+) => { last_type!($($rest_a,)+) };
 648     }
 649
 650     impl_hash_tuple! {}
 651     impl_hash_tuple! { A }
 652     impl_hash_tuple! { A B }
 653     impl_hash_tuple! { A B C }
 654     impl_hash_tuple! { A B C D }
 655     impl_hash_tuple! { A B C D E }
 656     impl_hash_tuple! { A B C D E F }
 657     impl_hash_tuple! { A B C D E F G }
 658     impl_hash_tuple! { A B C D E F G H }
 659     impl_hash_tuple! { A B C D E F G H I }
 660     impl_hash_tuple! { A B C D E F G H I J }
 661     impl_hash_tuple! { A B C D E F G H I J K }
 662     impl_hash_tuple! { A B C D E F G H I J K L }
 663
 664     #[stable(feature = "rust1", since = "1.0.0")]
 665     impl<T: Hash> Hash for [T] {
 666         fn hash<H: Hasher>(&self, state: &mut H) {
 667             self.len().hash(state);
 668             Hash::hash_slice(self, state)
 669         }
 670     }
 671
 672     #[stable(feature = "rust1", since = "1.0.0")]
 673     impl<T: ?Sized + Hash> Hash for &T {
 674         fn hash<H: Hasher>(&self, state: &mut H) {
 675             (**self).hash(state);
 676         }
 677     }
 678
 679     #[stable(feature = "rust1", since = "1.0.0")]
 680     impl<T: ?Sized + Hash> Hash for &mut T {
 681         fn hash<H: Hasher>(&self, state: &mut H) {
 682             (**self).hash(state);
 683         }
 684     }
 685
 686     #[stable(feature = "rust1", since = "1.0.0")]
 687     impl<T: ?Sized> Hash for *const T {
 688         fn hash<H: Hasher>(&self, state: &mut H) {
 689             if mem::size_of::<Self>() == mem::size_of::<usize>() {
 690                 // Thin pointer
 691                 state.write_usize(*self as *const () as usize);
 692             } else {
 693                 // Fat pointer
 694                 let (a, b) = unsafe { *(self as *const Self as *const (usize, usize)) };
 695                 state.write_usize(a);
 696                 state.write_usize(b);
 697             }
 698         }
 699     }
 700
 701     #[stable(feature = "rust1", since = "1.0.0")]
 702     impl<T: ?Sized> Hash for *mut T {
 703         fn hash<H: Hasher>(&self, state: &mut H) {
 704             if mem::size_of::<Self>() == mem::size_of::<usize>() {
 705                 // Thin pointer
 706                 state.write_usize(*self as *const () as usize);
 707             } else {
 708                 // Fat pointer
 709                 let (a, b) = unsafe { *(self as *const Self as *const (usize, usize)) };
 710                 state.write_usize(a);
 711                 state.write_usize(b);
 712             }
 713         }
 714     }
 715 }