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