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