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