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