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 mem;
 199     use slice;
 200     use super::*;
 201
 202     macro_rules! impl_write {
 203         ($(($ty:ident, $meth:ident),)*) => {$(
 204             #[stable(feature = "rust1", since = "1.0.0")]
 205             impl Hash for $ty {
 206                 fn hash<H: Hasher>(&self, state: &mut H) {
 207                     state.$meth(*self)
 208                 }
 209
 210                 fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
 211                     let newlen = data.len() * mem::size_of::<$ty>();
 212                     let ptr = data.as_ptr() as *const u8;
 213                     state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
 214                 }
 215             }
 216         )*}
 217     }
 218
 219     impl_write! {
 220         (u8, write_u8),
 221         (u16, write_u16),
 222         (u32, write_u32),
 223         (u64, write_u64),
 224         (usize, write_usize),
 225         (i8, write_i8),
 226         (i16, write_i16),
 227         (i32, write_i32),
 228         (i64, write_i64),
 229         (isize, write_isize),
 230     }
 231
 232     #[stable(feature = "rust1", since = "1.0.0")]
 233     impl Hash for bool {
 234         fn hash<H: Hasher>(&self, state: &mut H) {
 235             state.write_u8(*self as u8)
 236         }
 237     }
 238
 239     #[stable(feature = "rust1", since = "1.0.0")]
 240     impl Hash for char {
 241         fn hash<H: Hasher>(&self, state: &mut H) {
 242             state.write_u32(*self as u32)
 243         }
 244     }
 245
 246     #[stable(feature = "rust1", since = "1.0.0")]
 247     impl Hash for str {
 248         fn hash<H: Hasher>(&self, state: &mut H) {
 249             state.write(self.as_bytes());
 250             state.write_u8(0xff)
 251         }
 252     }
 253
 254     macro_rules! impl_hash_tuple {
 255         () => (
 256             #[stable(feature = "rust1", since = "1.0.0")]
 257             impl Hash for () {
 258                 fn hash<H: Hasher>(&self, _state: &mut H) {}
 259             }
 260         );
 261
 262         ( $($name:ident)+) => (
 263             #[stable(feature = "rust1", since = "1.0.0")]
 264             impl<$($name: Hash),*> Hash for ($($name,)*) {
 265                 #[allow(non_snake_case)]
 266                 fn hash<S: Hasher>(&self, state: &mut S) {
 267                     let ($(ref $name,)*) = *self;
 268                     $($name.hash(state);)*
 269                 }
 270             }
 271         );
 272     }
 273
 274     impl_hash_tuple! {}
 275     impl_hash_tuple! { A }
 276     impl_hash_tuple! { A B }
 277     impl_hash_tuple! { A B C }
 278     impl_hash_tuple! { A B C D }
 279     impl_hash_tuple! { A B C D E }
 280     impl_hash_tuple! { A B C D E F }
 281     impl_hash_tuple! { A B C D E F G }
 282     impl_hash_tuple! { A B C D E F G H }
 283     impl_hash_tuple! { A B C D E F G H I }
 284     impl_hash_tuple! { A B C D E F G H I J }
 285     impl_hash_tuple! { A B C D E F G H I J K }
 286     impl_hash_tuple! { A B C D E F G H I J K L }
 287
 288     #[stable(feature = "rust1", since = "1.0.0")]
 289     impl<T: Hash> Hash for [T] {
 290         fn hash<H: Hasher>(&self, state: &mut H) {
 291             self.len().hash(state);
 292             Hash::hash_slice(self, state)
 293         }
 294     }
 295
 296
 297     #[stable(feature = "rust1", since = "1.0.0")]
 298     impl<'a, T: ?Sized + Hash> Hash for &'a T {
 299         fn hash<H: Hasher>(&self, state: &mut H) {
 300             (**self).hash(state);
 301         }
 302     }
 303
 304     #[stable(feature = "rust1", since = "1.0.0")]
 305     impl<'a, T: ?Sized + Hash> Hash for &'a mut T {
 306         fn hash<H: Hasher>(&self, state: &mut H) {
 307             (**self).hash(state);
 308         }
 309     }
 310
 311     #[stable(feature = "rust1", since = "1.0.0")]
 312     impl<T> Hash for *const T {
 313         fn hash<H: Hasher>(&self, state: &mut H) {
 314             state.write_usize(*self as usize)
 315         }
 316     }
 317
 318     #[stable(feature = "rust1", since = "1.0.0")]
 319     impl<T> Hash for *mut T {
 320         fn hash<H: Hasher>(&self, state: &mut H) {
 321             state.write_usize(*self as usize)
 322         }
 323     }
 324 }