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