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