src/libcore/hash/mod.rs

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