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 //! # #![feature(hash)]
  20 //! use std::hash::{hash, Hash, SipHasher};
  21 //!
  22 //! #[derive(Hash)]
  23 //! struct Person {
  24 //!     id: u32,
  25 //!     name: String,
  26 //!     phone: u64,
  27 //! }
  28 //!
  29 //! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
  30 //! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
  31 //!
  32 //! assert!(hash::<_, SipHasher>(&person1) != hash::<_, SipHasher>(&person2));
  33 //! ```
  34 //!
  35 //! If you need more control over how a value is hashed, you need to implement
  36 //! the trait `Hash`:
  37 //!
  38 //! ```rust
  39 //! # #![feature(hash)]
  40 //! use std::hash::{hash, Hash, Hasher, SipHasher};
  41 //!
  42 //! struct Person {
  43 //!     id: u32,
  44 //!     name: String,
  45 //!     phone: u64,
  46 //! }
  47 //!
  48 //! impl Hash for Person {
  49 //!     fn hash<H: Hasher>(&self, state: &mut H) {
  50 //!         self.id.hash(state);
  51 //!         self.phone.hash(state);
  52 //!     }
  53 //! }
  54 //!
  55 //! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
  56 //! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
  57 //!
  58 //! assert_eq!(hash::<_, SipHasher>(&person1), hash::<_, SipHasher>(&person2));
  59 //! ```
  60
  61 #![stable(feature = "rust1", since = "1.0.0")]
  62
  63 use prelude::*;
  64
  65 use default::Default;
  66 use mem;
  67
  68 pub use self::sip::SipHasher;
  69
  70 mod sip;
  71
  72 /// A hashable type.
  73 ///
  74 /// The `H` type parameter is an abstract hash state that is used by the `Hash`
  75 /// to compute the hash.
  76 ///
  77 /// If you are also implementing `Eq`, there is an additional property that
  78 /// is important:
  79 ///
  80 /// ```text
  81 /// k1 == k2 -> hash(k1) == hash(k2)
  82 /// ```
  83 ///
  84 /// In other words, if two keys are equal, their hashes should also be equal.
  85 /// `HashMap` and `HashSet` both rely on this behavior.
  86 #[stable(feature = "rust1", since = "1.0.0")]
  87 pub trait Hash {
  88     /// Feeds this value into the state given, updating the hasher as necessary.
  89     #[stable(feature = "rust1", since = "1.0.0")]
  90     fn hash<H: Hasher>(&self, state: &mut H);
  91
  92     /// Feeds a slice of this type into the state provided.
  93     #[unstable(feature = "hash", reason = "module was recently redesigned")]
  94     fn hash_slice<H: Hasher>(data: &[Self], state: &mut H) where Self: Sized {
  95         for piece in data {
  96             piece.hash(state);
  97         }
  98     }
  99 }
 100
 101 /// A trait which represents the ability to hash an arbitrary stream of bytes.
 102 #[stable(feature = "rust1", since = "1.0.0")]
 103 pub trait Hasher {
 104     /// Completes a round of hashing, producing the output hash generated.
 105     #[stable(feature = "rust1", since = "1.0.0")]
 106     fn finish(&self) -> u64;
 107
 108     /// Writes some data into this `Hasher`
 109     #[stable(feature = "rust1", since = "1.0.0")]
 110     fn write(&mut self, bytes: &[u8]);
 111
 112     /// Write a single `u8` into this hasher
 113     #[inline]
 114     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 115     fn write_u8(&mut self, i: u8) { self.write(&[i]) }
 116     /// Write a single `u16` into this hasher.
 117     #[inline]
 118     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 119     fn write_u16(&mut self, i: u16) {
 120         self.write(&unsafe { mem::transmute::<_, [u8; 2]>(i) })
 121     }
 122     /// Write a single `u32` into this hasher.
 123     #[inline]
 124     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 125     fn write_u32(&mut self, i: u32) {
 126         self.write(&unsafe { mem::transmute::<_, [u8; 4]>(i) })
 127     }
 128     /// Write a single `u64` into this hasher.
 129     #[inline]
 130     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 131     fn write_u64(&mut self, i: u64) {
 132         self.write(&unsafe { mem::transmute::<_, [u8; 8]>(i) })
 133     }
 134     /// Write a single `usize` into this hasher.
 135     #[inline]
 136     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 137     fn write_usize(&mut self, i: usize) {
 138         if cfg!(target_pointer_width = "32") {
 139             self.write_u32(i as u32)
 140         } else {
 141             self.write_u64(i as u64)
 142         }
 143     }
 144
 145     /// Write a single `i8` into this hasher.
 146     #[inline]
 147     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 148     fn write_i8(&mut self, i: i8) { self.write_u8(i as u8) }
 149     /// Write a single `i16` into this hasher.
 150     #[inline]
 151     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 152     fn write_i16(&mut self, i: i16) { self.write_u16(i as u16) }
 153     /// Write a single `i32` into this hasher.
 154     #[inline]
 155     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 156     fn write_i32(&mut self, i: i32) { self.write_u32(i as u32) }
 157     /// Write a single `i64` into this hasher.
 158     #[inline]
 159     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 160     fn write_i64(&mut self, i: i64) { self.write_u64(i as u64) }
 161     /// Write a single `isize` into this hasher.
 162     #[inline]
 163     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 164     fn write_isize(&mut self, i: isize) { self.write_usize(i as usize) }
 165 }
 166
 167 /// Hash a value with the default SipHasher algorithm (two initial keys of 0).
 168 ///
 169 /// The specified value will be hashed with this hasher and then the resulting
 170 /// hash will be returned.
 171 #[unstable(feature = "hash", reason = "module was recently redesigned")]
 172 pub fn hash<T: Hash, H: Hasher + Default>(value: &T) -> u64 {
 173     let mut h: H = Default::default();
 174     value.hash(&mut h);
 175     h.finish()
 176 }
 177
 178 //////////////////////////////////////////////////////////////////////////////
 179
 180 mod impls {
 181     use prelude::*;
 182
 183     use slice;
 184     use super::*;
 185
 186     macro_rules! impl_write {
 187         ($(($ty:ident, $meth:ident),)*) => {$(
 188             #[stable(feature = "rust1", since = "1.0.0")]
 189             impl Hash for $ty {
 190                 fn hash<H: Hasher>(&self, state: &mut H) {
 191                     state.$meth(*self)
 192                 }
 193
 194                 fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
 195                     // FIXME(#23542) Replace with type ascription.
 196                     #![allow(trivial_casts)]
 197                     let newlen = data.len() * ::$ty::BYTES as usize;
 198                     let ptr = data.as_ptr() as *const u8;
 199                     state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
 200                 }
 201             }
 202         )*}
 203     }
 204
 205     impl_write! {
 206         (u8, write_u8),
 207         (u16, write_u16),
 208         (u32, write_u32),
 209         (u64, write_u64),
 210         (usize, write_usize),
 211         (i8, write_i8),
 212         (i16, write_i16),
 213         (i32, write_i32),
 214         (i64, write_i64),
 215         (isize, write_isize),
 216     }
 217
 218     #[stable(feature = "rust1", since = "1.0.0")]
 219     impl Hash for bool {
 220         fn hash<H: Hasher>(&self, state: &mut H) {
 221             state.write_u8(*self as u8)
 222         }
 223     }
 224
 225     #[stable(feature = "rust1", since = "1.0.0")]
 226     impl Hash for char {
 227         fn hash<H: Hasher>(&self, state: &mut H) {
 228             state.write_u32(*self as u32)
 229         }
 230     }
 231
 232     #[stable(feature = "rust1", since = "1.0.0")]
 233     impl Hash for str {
 234         fn hash<H: Hasher>(&self, state: &mut H) {
 235             state.write(self.as_bytes());
 236             state.write_u8(0xff)
 237         }
 238     }
 239
 240     macro_rules! impl_hash_tuple {
 241         () => (
 242             #[stable(feature = "rust1", since = "1.0.0")]
 243             impl Hash for () {
 244                 fn hash<H: Hasher>(&self, _state: &mut H) {}
 245             }
 246         );
 247
 248         ( $($name:ident)+) => (
 249             #[stable(feature = "rust1", since = "1.0.0")]
 250             impl<$($name: Hash),*> Hash for ($($name,)*) {
 251                 #[allow(non_snake_case)]
 252                 fn hash<S: Hasher>(&self, state: &mut S) {
 253                     let ($(ref $name,)*) = *self;
 254                     $($name.hash(state);)*
 255                 }
 256             }
 257         );
 258     }
 259
 260     impl_hash_tuple! {}
 261     impl_hash_tuple! { A }
 262     impl_hash_tuple! { A B }
 263     impl_hash_tuple! { A B C }
 264     impl_hash_tuple! { A B C D }
 265     impl_hash_tuple! { A B C D E }
 266     impl_hash_tuple! { A B C D E F }
 267     impl_hash_tuple! { A B C D E F G }
 268     impl_hash_tuple! { A B C D E F G H }
 269     impl_hash_tuple! { A B C D E F G H I }
 270     impl_hash_tuple! { A B C D E F G H I J }
 271     impl_hash_tuple! { A B C D E F G H I J K }
 272     impl_hash_tuple! { A B C D E F G H I J K L }
 273
 274     #[stable(feature = "rust1", since = "1.0.0")]
 275     impl<T: Hash> Hash for [T] {
 276         fn hash<H: Hasher>(&self, state: &mut H) {
 277             self.len().hash(state);
 278             Hash::hash_slice(self, state)
 279         }
 280     }
 281
 282
 283     #[stable(feature = "rust1", since = "1.0.0")]
 284     impl<'a, T: ?Sized + Hash> Hash for &'a T {
 285         fn hash<H: Hasher>(&self, state: &mut H) {
 286             (**self).hash(state);
 287         }
 288     }
 289
 290     #[stable(feature = "rust1", since = "1.0.0")]
 291     impl<'a, T: ?Sized + Hash> Hash for &'a mut T {
 292         fn hash<H: Hasher>(&self, state: &mut H) {
 293             (**self).hash(state);
 294         }
 295     }
 296
 297     #[stable(feature = "rust1", since = "1.0.0")]
 298     impl<T> Hash for *const T {
 299         fn hash<H: Hasher>(&self, state: &mut H) {
 300             state.write_usize(*self as usize)
 301         }
 302     }
 303
 304     #[stable(feature = "rust1", since = "1.0.0")]
 305     impl<T> Hash for *mut T {
 306         fn hash<H: Hasher>(&self, state: &mut H) {
 307             state.write_usize(*self as usize)
 308         }
 309     }
 310 }