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::hash::{Hash, SipHasher, Hasher};
  20 //!
  21 //! #[derive(Hash)]
  22 //! struct Person {
  23 //!     id: u32,
  24 //!     name: String,
  25 //!     phone: u64,
  26 //! }
  27 //!
  28 //! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
  29 //! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
  30 //!
  31 //! assert!(hash(&person1) != hash(&person2));
  32 //!
  33 //! fn hash<T: Hash>(t: &T) -> u64 {
  34 //!     let mut s = SipHasher::new();
  35 //!     t.hash(&mut s);
  36 //!     s.finish()
  37 //! }
  38 //! ```
  39 //!
  40 //! If you need more control over how a value is hashed, you need to implement
  41 //! the [`Hash`] trait:
  42 //!
  43 //! [`Hash`]: trait.Hash.html
  44 //!
  45 //! ```rust
  46 //! use std::hash::{Hash, Hasher, SipHasher};
  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 { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
  63 //! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
  64 //!
  65 //! assert_eq!(hash(&person1), hash(&person2));
  66 //!
  67 //! fn hash<T: Hash>(t: &T) -> u64 {
  68 //!     let mut s = SipHasher::new();
  69 //!     t.hash(&mut s);
  70 //!     s.finish()
  71 //! }
  72 //! ```
  73
  74 #![stable(feature = "rust1", since = "1.0.0")]
  75
  76 use fmt;
  77 use marker;
  78 use mem;
  79
  80 #[stable(feature = "rust1", since = "1.0.0")]
  81 #[allow(deprecated)]
  82 pub use self::sip::SipHasher;
  83
  84 #[unstable(feature = "sip_hash_13", issue = "29754")]
  85 #[allow(deprecated)]
  86 pub use self::sip::{SipHasher13, SipHasher24};
  87
  88 mod sip;
  89
  90 /// A hashable type.
  91 ///
  92 /// The `H` type parameter is an abstract hash state that is used by the `Hash`
  93 /// to compute the hash.
  94 ///
  95 /// If you are also implementing [`Eq`], there is an additional property that
  96 /// is important:
  97 ///
  98 /// ```text
  99 /// k1 == k2 -> hash(k1) == hash(k2)
 100 /// ```
 101 ///
 102 /// In other words, if two keys are equal, their hashes should also be equal.
 103 /// [`HashMap`] and [`HashSet`] both rely on this behavior.
 104 ///
 105 /// ## Derivable
 106 ///
 107 /// This trait can be used with `#[derive]` if all fields implement `Hash`.
 108 /// When `derive`d, the resulting hash will be the combination of the values
 109 /// from calling [`.hash()`] on each field.
 110 ///
 111 /// ## How can I implement `Hash`?
 112 ///
 113 /// If you need more control over how a value is hashed, you need to implement
 114 /// the `Hash` trait:
 115 ///
 116 /// ```
 117 /// use std::hash::{Hash, Hasher};
 118 ///
 119 /// struct Person {
 120 ///     id: u32,
 121 ///     name: String,
 122 ///     phone: u64,
 123 /// }
 124 ///
 125 /// impl Hash for Person {
 126 ///     fn hash<H: Hasher>(&self, state: &mut H) {
 127 ///         self.id.hash(state);
 128 ///         self.phone.hash(state);
 129 ///     }
 130 /// }
 131 /// ```
 132 ///
 133 /// [`Eq`]: ../../std/cmp/trait.Eq.html
 134 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
 135 /// [`HashSet`]: ../../std/collections/struct.HashSet.html
 136 /// [`.hash()`]: #tymethod.hash
 137 #[stable(feature = "rust1", since = "1.0.0")]
 138 pub trait Hash {
 139     /// Feeds this value into the state given, updating the hasher as necessary.
 140     #[stable(feature = "rust1", since = "1.0.0")]
 141     fn hash<H: Hasher>(&self, state: &mut H);
 142
 143     /// Feeds a slice of this type into the state provided.
 144     #[stable(feature = "hash_slice", since = "1.3.0")]
 145     fn hash_slice<H: Hasher>(data: &[Self], state: &mut H)
 146         where Self: Sized
 147     {
 148         for piece in data {
 149             piece.hash(state);
 150         }
 151     }
 152 }
 153
 154 /// A trait which represents the ability to hash an arbitrary stream of bytes.
 155 #[stable(feature = "rust1", since = "1.0.0")]
 156 pub trait Hasher {
 157     /// Completes a round of hashing, producing the output hash generated.
 158     #[stable(feature = "rust1", since = "1.0.0")]
 159     fn finish(&self) -> u64;
 160
 161     /// Writes some data into this `Hasher`.
 162     #[stable(feature = "rust1", since = "1.0.0")]
 163     fn write(&mut self, bytes: &[u8]);
 164
 165     /// Write a single `u8` into this hasher.
 166     #[inline]
 167     #[stable(feature = "hasher_write", since = "1.3.0")]
 168     fn write_u8(&mut self, i: u8) {
 169         self.write(&[i])
 170     }
 171     /// Writes a single `u16` into this hasher.
 172     #[inline]
 173     #[stable(feature = "hasher_write", since = "1.3.0")]
 174     fn write_u16(&mut self, i: u16) {
 175         self.write(&unsafe { mem::transmute::<_, [u8; 2]>(i) })
 176     }
 177     /// Writes a single `u32` into this hasher.
 178     #[inline]
 179     #[stable(feature = "hasher_write", since = "1.3.0")]
 180     fn write_u32(&mut self, i: u32) {
 181         self.write(&unsafe { mem::transmute::<_, [u8; 4]>(i) })
 182     }
 183     /// Writes a single `u64` into this hasher.
 184     #[inline]
 185     #[stable(feature = "hasher_write", since = "1.3.0")]
 186     fn write_u64(&mut self, i: u64) {
 187         self.write(&unsafe { mem::transmute::<_, [u8; 8]>(i) })
 188     }
 189     #[cfg(not(stage0))]
 190     /// Writes a single `u128` into this hasher.
 191     #[inline]
 192     #[unstable(feature = "i128", issue = "35118")]
 193     fn write_u128(&mut self, i: u128) {
 194         self.write(&unsafe { mem::transmute::<_, [u8; 16]>(i) })
 195     }
 196     /// Writes a single `usize` into this hasher.
 197     #[inline]
 198     #[stable(feature = "hasher_write", since = "1.3.0")]
 199     fn write_usize(&mut self, i: usize) {
 200         let bytes = unsafe {
 201             ::slice::from_raw_parts(&i as *const usize as *const u8, mem::size_of::<usize>())
 202         };
 203         self.write(bytes);
 204     }
 205
 206     /// Writes a single `i8` into this hasher.
 207     #[inline]
 208     #[stable(feature = "hasher_write", since = "1.3.0")]
 209     fn write_i8(&mut self, i: i8) {
 210         self.write_u8(i as u8)
 211     }
 212     /// Writes a single `i16` into this hasher.
 213     #[inline]
 214     #[stable(feature = "hasher_write", since = "1.3.0")]
 215     fn write_i16(&mut self, i: i16) {
 216         self.write_u16(i as u16)
 217     }
 218     /// Writes a single `i32` into this hasher.
 219     #[inline]
 220     #[stable(feature = "hasher_write", since = "1.3.0")]
 221     fn write_i32(&mut self, i: i32) {
 222         self.write_u32(i as u32)
 223     }
 224     /// Writes a single `i64` into this hasher.
 225     #[inline]
 226     #[stable(feature = "hasher_write", since = "1.3.0")]
 227     fn write_i64(&mut self, i: i64) {
 228         self.write_u64(i as u64)
 229     }
 230     #[cfg(not(stage0))]
 231     /// Writes a single `i128` into this hasher.
 232     #[inline]
 233     #[unstable(feature = "i128", issue = "35118")]
 234     fn write_i128(&mut self, i: i128) {
 235         self.write_u128(i as u128)
 236     }
 237     /// Writes a single `isize` into this hasher.
 238     #[inline]
 239     #[stable(feature = "hasher_write", since = "1.3.0")]
 240     fn write_isize(&mut self, i: isize) {
 241         self.write_usize(i as usize)
 242     }
 243 }
 244
 245 /// A `BuildHasher` is typically used as a factory for instances of `Hasher`
 246 /// which a `HashMap` can then use to hash keys independently.
 247 ///
 248 /// Note that for each instance of `BuildHasher`, the created hashers should be
 249 /// identical. That is, if the same stream of bytes is fed into each hasher, the
 250 /// same output will also be generated.
 251 #[stable(since = "1.7.0", feature = "build_hasher")]
 252 pub trait BuildHasher {
 253     /// Type of the hasher that will be created.
 254     #[stable(since = "1.7.0", feature = "build_hasher")]
 255     type Hasher: Hasher;
 256
 257     /// Creates a new hasher.
 258     ///
 259     /// # Examples
 260     ///
 261     /// ```
 262     /// use std::collections::hash_map::RandomState;
 263     /// use std::hash::BuildHasher;
 264     ///
 265     /// let s = RandomState::new();
 266     /// let new_s = s.build_hasher();
 267     /// ```
 268     #[stable(since = "1.7.0", feature = "build_hasher")]
 269     fn build_hasher(&self) -> Self::Hasher;
 270 }
 271
 272 /// The `BuildHasherDefault` structure is used in scenarios where one has a
 273 /// type that implements [`Hasher`] and [`Default`], but needs that type to
 274 /// implement [`BuildHasher`].
 275 ///
 276 /// This structure is zero-sized and does not need construction.
 277 ///
 278 /// # Examples
 279 ///
 280 /// Using `BuildHasherDefault` to specify a custom [`BuildHasher`] for
 281 /// [`HashMap`]:
 282 ///
 283 /// ```
 284 /// use std::collections::HashMap;
 285 /// use std::hash::{BuildHasherDefault, Hasher};
 286 ///
 287 /// #[derive(Default)]
 288 /// struct MyHasher;
 289 ///
 290 /// impl Hasher for MyHasher {
 291 ///     fn write(&mut self, bytes: &[u8]) {
 292 ///         // Your hashing algorithm goes here!
 293 ///        unimplemented!()
 294 ///     }
 295 ///
 296 ///     fn finish(&self) -> u64 {
 297 ///         // Your hashing algorithm goes here!
 298 ///         unimplemented!()
 299 ///     }
 300 /// }
 301 ///
 302 /// type MyBuildHasher = BuildHasherDefault<MyHasher>;
 303 ///
 304 /// let hash_map = HashMap::<u32, u32, MyBuildHasher>::default();
 305 /// ```
 306 ///
 307 /// [`BuildHasher`]: trait.BuildHasher.html
 308 /// [`Default`]: ../default/trait.Default.html
 309 /// [`Hasher`]: trait.Hasher.html
 310 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
 311 #[stable(since = "1.7.0", feature = "build_hasher")]
 312 pub struct BuildHasherDefault<H>(marker::PhantomData<H>);
 313
 314 #[stable(since = "1.9.0", feature = "core_impl_debug")]
 315 impl<H> fmt::Debug for BuildHasherDefault<H> {
 316     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 317         f.pad("BuildHasherDefault")
 318     }
 319 }
 320
 321 #[stable(since = "1.7.0", feature = "build_hasher")]
 322 impl<H: Default + Hasher> BuildHasher for BuildHasherDefault<H> {
 323     type Hasher = H;
 324
 325     fn build_hasher(&self) -> H {
 326         H::default()
 327     }
 328 }
 329
 330 #[stable(since = "1.7.0", feature = "build_hasher")]
 331 impl<H> Clone for BuildHasherDefault<H> {
 332     fn clone(&self) -> BuildHasherDefault<H> {
 333         BuildHasherDefault(marker::PhantomData)
 334     }
 335 }
 336
 337 #[stable(since = "1.7.0", feature = "build_hasher")]
 338 impl<H> Default for BuildHasherDefault<H> {
 339     fn default() -> BuildHasherDefault<H> {
 340         BuildHasherDefault(marker::PhantomData)
 341     }
 342 }
 343
 344 //////////////////////////////////////////////////////////////////////////////
 345
 346 mod impls {
 347     use mem;
 348     use slice;
 349     use super::*;
 350
 351     macro_rules! impl_write {
 352         ($(($ty:ident, $meth:ident),)*) => {$(
 353             #[stable(feature = "rust1", since = "1.0.0")]
 354             impl Hash for $ty {
 355                 fn hash<H: Hasher>(&self, state: &mut H) {
 356                     state.$meth(*self)
 357                 }
 358
 359                 fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
 360                     let newlen = data.len() * mem::size_of::<$ty>();
 361                     let ptr = data.as_ptr() as *const u8;
 362                     state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
 363                 }
 364             }
 365         )*}
 366     }
 367
 368     impl_write! {
 369         (u8, write_u8),
 370         (u16, write_u16),
 371         (u32, write_u32),
 372         (u64, write_u64),
 373         (usize, write_usize),
 374         (i8, write_i8),
 375         (i16, write_i16),
 376         (i32, write_i32),
 377         (i64, write_i64),
 378         (isize, write_isize),
 379     }
 380     #[cfg(not(stage0))]
 381     impl_write! {
 382         (u128, write_u128),
 383         (i128, write_i128),
 384     }
 385
 386     #[stable(feature = "rust1", since = "1.0.0")]
 387     impl Hash for bool {
 388         fn hash<H: Hasher>(&self, state: &mut H) {
 389             state.write_u8(*self as u8)
 390         }
 391     }
 392
 393     #[stable(feature = "rust1", since = "1.0.0")]
 394     impl Hash for char {
 395         fn hash<H: Hasher>(&self, state: &mut H) {
 396             state.write_u32(*self as u32)
 397         }
 398     }
 399
 400     #[stable(feature = "rust1", since = "1.0.0")]
 401     impl Hash for str {
 402         fn hash<H: Hasher>(&self, state: &mut H) {
 403             state.write(self.as_bytes());
 404             state.write_u8(0xff)
 405         }
 406     }
 407
 408     macro_rules! impl_hash_tuple {
 409         () => (
 410             #[stable(feature = "rust1", since = "1.0.0")]
 411             impl Hash for () {
 412                 fn hash<H: Hasher>(&self, _state: &mut H) {}
 413             }
 414         );
 415
 416         ( $($name:ident)+) => (
 417             #[stable(feature = "rust1", since = "1.0.0")]
 418             impl<$($name: Hash),*> Hash for ($($name,)*) {
 419                 #[allow(non_snake_case)]
 420                 fn hash<S: Hasher>(&self, state: &mut S) {
 421                     let ($(ref $name,)*) = *self;
 422                     $($name.hash(state);)*
 423                 }
 424             }
 425         );
 426     }
 427
 428     impl_hash_tuple! {}
 429     impl_hash_tuple! { A }
 430     impl_hash_tuple! { A B }
 431     impl_hash_tuple! { A B C }
 432     impl_hash_tuple! { A B C D }
 433     impl_hash_tuple! { A B C D E }
 434     impl_hash_tuple! { A B C D E F }
 435     impl_hash_tuple! { A B C D E F G }
 436     impl_hash_tuple! { A B C D E F G H }
 437     impl_hash_tuple! { A B C D E F G H I }
 438     impl_hash_tuple! { A B C D E F G H I J }
 439     impl_hash_tuple! { A B C D E F G H I J K }
 440     impl_hash_tuple! { A B C D E F G H I J K L }
 441
 442     #[stable(feature = "rust1", since = "1.0.0")]
 443     impl<T: Hash> Hash for [T] {
 444         fn hash<H: Hasher>(&self, state: &mut H) {
 445             self.len().hash(state);
 446             Hash::hash_slice(self, state)
 447         }
 448     }
 449
 450
 451     #[stable(feature = "rust1", since = "1.0.0")]
 452     impl<'a, T: ?Sized + Hash> Hash for &'a T {
 453         fn hash<H: Hasher>(&self, state: &mut H) {
 454             (**self).hash(state);
 455         }
 456     }
 457
 458     #[stable(feature = "rust1", since = "1.0.0")]
 459     impl<'a, T: ?Sized + Hash> Hash for &'a mut T {
 460         fn hash<H: Hasher>(&self, state: &mut H) {
 461             (**self).hash(state);
 462         }
 463     }
 464
 465     #[stable(feature = "rust1", since = "1.0.0")]
 466     impl<T> Hash for *const T {
 467         fn hash<H: Hasher>(&self, state: &mut H) {
 468             state.write_usize(*self as usize)
 469         }
 470     }
 471
 472     #[stable(feature = "rust1", since = "1.0.0")]
 473     impl<T> Hash for *mut T {
 474         fn hash<H: Hasher>(&self, state: &mut H) {
 475             state.write_usize(*self as usize)
 476         }
 477     }
 478 }