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 #[stable(since = "1.7.0", feature = "build_hasher")]
 311 pub struct BuildHasherDefault<H>(marker::PhantomData<H>);
 312
 313 #[stable(since = "1.9.0", feature = "core_impl_debug")]
 314 impl<H> fmt::Debug for BuildHasherDefault<H> {
 315     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 316         f.pad("BuildHasherDefault")
 317     }
 318 }
 319
 320 #[stable(since = "1.7.0", feature = "build_hasher")]
 321 impl<H: Default + Hasher> BuildHasher for BuildHasherDefault<H> {
 322     type Hasher = H;
 323
 324     fn build_hasher(&self) -> H {
 325         H::default()
 326     }
 327 }
 328
 329 #[stable(since = "1.7.0", feature = "build_hasher")]
 330 impl<H> Clone for BuildHasherDefault<H> {
 331     fn clone(&self) -> BuildHasherDefault<H> {
 332         BuildHasherDefault(marker::PhantomData)
 333     }
 334 }
 335
 336 #[stable(since = "1.7.0", feature = "build_hasher")]
 337 impl<H> Default for BuildHasherDefault<H> {
 338     fn default() -> BuildHasherDefault<H> {
 339         BuildHasherDefault(marker::PhantomData)
 340     }
 341 }
 342
 343 //////////////////////////////////////////////////////////////////////////////
 344
 345 mod impls {
 346     use mem;
 347     use slice;
 348     use super::*;
 349
 350     macro_rules! impl_write {
 351         ($(($ty:ident, $meth:ident),)*) => {$(
 352             #[stable(feature = "rust1", since = "1.0.0")]
 353             impl Hash for $ty {
 354                 fn hash<H: Hasher>(&self, state: &mut H) {
 355                     state.$meth(*self)
 356                 }
 357
 358                 fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
 359                     let newlen = data.len() * mem::size_of::<$ty>();
 360                     let ptr = data.as_ptr() as *const u8;
 361                     state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
 362                 }
 363             }
 364         )*}
 365     }
 366
 367     impl_write! {
 368         (u8, write_u8),
 369         (u16, write_u16),
 370         (u32, write_u32),
 371         (u64, write_u64),
 372         (usize, write_usize),
 373         (i8, write_i8),
 374         (i16, write_i16),
 375         (i32, write_i32),
 376         (i64, write_i64),
 377         (isize, write_isize),
 378     }
 379     #[cfg(not(stage0))]
 380     impl_write! {
 381         (u128, write_u128),
 382         (i128, write_i128),
 383     }
 384
 385     #[stable(feature = "rust1", since = "1.0.0")]
 386     impl Hash for bool {
 387         fn hash<H: Hasher>(&self, state: &mut H) {
 388             state.write_u8(*self as u8)
 389         }
 390     }
 391
 392     #[stable(feature = "rust1", since = "1.0.0")]
 393     impl Hash for char {
 394         fn hash<H: Hasher>(&self, state: &mut H) {
 395             state.write_u32(*self as u32)
 396         }
 397     }
 398
 399     #[stable(feature = "rust1", since = "1.0.0")]
 400     impl Hash for str {
 401         fn hash<H: Hasher>(&self, state: &mut H) {
 402             state.write(self.as_bytes());
 403             state.write_u8(0xff)
 404         }
 405     }
 406
 407     macro_rules! impl_hash_tuple {
 408         () => (
 409             #[stable(feature = "rust1", since = "1.0.0")]
 410             impl Hash for () {
 411                 fn hash<H: Hasher>(&self, _state: &mut H) {}
 412             }
 413         );
 414
 415         ( $($name:ident)+) => (
 416             #[stable(feature = "rust1", since = "1.0.0")]
 417             impl<$($name: Hash),*> Hash for ($($name,)*) {
 418                 #[allow(non_snake_case)]
 419                 fn hash<S: Hasher>(&self, state: &mut S) {
 420                     let ($(ref $name,)*) = *self;
 421                     $($name.hash(state);)*
 422                 }
 423             }
 424         );
 425     }
 426
 427     impl_hash_tuple! {}
 428     impl_hash_tuple! { A }
 429     impl_hash_tuple! { A B }
 430     impl_hash_tuple! { A B C }
 431     impl_hash_tuple! { A B C D }
 432     impl_hash_tuple! { A B C D E }
 433     impl_hash_tuple! { A B C D E F }
 434     impl_hash_tuple! { A B C D E F G }
 435     impl_hash_tuple! { A B C D E F G H }
 436     impl_hash_tuple! { A B C D E F G H I }
 437     impl_hash_tuple! { A B C D E F G H I J }
 438     impl_hash_tuple! { A B C D E F G H I J K }
 439     impl_hash_tuple! { A B C D E F G H I J K L }
 440
 441     #[stable(feature = "rust1", since = "1.0.0")]
 442     impl<T: Hash> Hash for [T] {
 443         fn hash<H: Hasher>(&self, state: &mut H) {
 444             self.len().hash(state);
 445             Hash::hash_slice(self, state)
 446         }
 447     }
 448
 449
 450     #[stable(feature = "rust1", since = "1.0.0")]
 451     impl<'a, T: ?Sized + Hash> Hash for &'a T {
 452         fn hash<H: Hasher>(&self, state: &mut H) {
 453             (**self).hash(state);
 454         }
 455     }
 456
 457     #[stable(feature = "rust1", since = "1.0.0")]
 458     impl<'a, T: ?Sized + Hash> Hash for &'a mut T {
 459         fn hash<H: Hasher>(&self, state: &mut H) {
 460             (**self).hash(state);
 461         }
 462     }
 463
 464     #[stable(feature = "rust1", since = "1.0.0")]
 465     impl<T> Hash for *const T {
 466         fn hash<H: Hasher>(&self, state: &mut H) {
 467             state.write_usize(*self as usize)
 468         }
 469     }
 470
 471     #[stable(feature = "rust1", since = "1.0.0")]
 472     impl<T> Hash for *mut T {
 473         fn hash<H: Hasher>(&self, state: &mut H) {
 474             state.write_usize(*self as usize)
 475         }
 476     }
 477 }