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.
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.
11 //! Generic hashing support.
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)]`:
19 //! use std::hash::{Hash, SipHasher, Hasher};
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 };
31 //! assert!(hash(&person1) != hash(&person2));
33 //! fn hash<T: Hash>(t: &T) -> u64 {
34 //! let mut s = SipHasher::new();
40 //! If you need more control over how a value is hashed, you need to implement
44 //! use std::hash::{Hash, Hasher, SipHasher};
48 //! # #[allow(dead_code)]
53 //! impl Hash for Person {
54 //! fn hash<H: Hasher>(&self, state: &mut H) {
55 //! self.id.hash(state);
56 //! self.phone.hash(state);
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 };
63 //! assert_eq!(hash(&person1), hash(&person2));
65 //! fn hash<T: Hash>(t: &T) -> u64 {
66 //! let mut s = SipHasher::new();
72 #![stable(feature = "rust1", since = "1.0.0")]
78 pub use self::sip::SipHasher;
84 /// The `H` type parameter is an abstract hash state that is used by the `Hash`
85 /// to compute the hash.
87 /// If you are also implementing `Eq`, there is an additional property that
91 /// k1 == k2 -> hash(k1) == hash(k2)
94 /// In other words, if two keys are equal, their hashes should also be equal.
95 /// `HashMap` and `HashSet` both rely on this behavior.
97 /// This trait can be used with `#[derive]`.
98 #[stable(feature = "rust1", since = "1.0.0")]
100 /// Feeds this value into the state given, updating the hasher as necessary.
101 #[stable(feature = "rust1", since = "1.0.0")]
102 fn hash<H: Hasher>(&self, state: &mut H);
104 /// Feeds a slice of this type into the state provided.
105 #[stable(feature = "hash_slice", since = "1.3.0")]
106 fn hash_slice<H: Hasher>(data: &[Self], state: &mut H)
115 /// A trait which represents the ability to hash an arbitrary stream of bytes.
116 #[stable(feature = "rust1", since = "1.0.0")]
118 /// Completes a round of hashing, producing the output hash generated.
119 #[stable(feature = "rust1", since = "1.0.0")]
120 fn finish(&self) -> u64;
122 /// Writes some data into this `Hasher`
123 #[stable(feature = "rust1", since = "1.0.0")]
124 fn write(&mut self, bytes: &[u8]);
126 /// Write a single `u8` into this hasher
128 #[stable(feature = "hasher_write", since = "1.3.0")]
129 fn write_u8(&mut self, i: u8) {
132 /// Write a single `u16` into this hasher.
134 #[stable(feature = "hasher_write", since = "1.3.0")]
135 fn write_u16(&mut self, i: u16) {
136 self.write(&unsafe { mem::transmute::<_, [u8; 2]>(i) })
138 /// Write a single `u32` into this hasher.
140 #[stable(feature = "hasher_write", since = "1.3.0")]
141 fn write_u32(&mut self, i: u32) {
142 self.write(&unsafe { mem::transmute::<_, [u8; 4]>(i) })
144 /// Write a single `u64` into this hasher.
146 #[stable(feature = "hasher_write", since = "1.3.0")]
147 fn write_u64(&mut self, i: u64) {
148 self.write(&unsafe { mem::transmute::<_, [u8; 8]>(i) })
150 /// Write a single `usize` into this hasher.
152 #[stable(feature = "hasher_write", since = "1.3.0")]
153 fn write_usize(&mut self, i: usize) {
155 ::slice::from_raw_parts(&i as *const usize as *const u8, mem::size_of::<usize>())
160 /// Write a single `i8` into this hasher.
162 #[stable(feature = "hasher_write", since = "1.3.0")]
163 fn write_i8(&mut self, i: i8) {
164 self.write_u8(i as u8)
166 /// Write a single `i16` into this hasher.
168 #[stable(feature = "hasher_write", since = "1.3.0")]
169 fn write_i16(&mut self, i: i16) {
170 self.write_u16(i as u16)
172 /// Write a single `i32` into this hasher.
174 #[stable(feature = "hasher_write", since = "1.3.0")]
175 fn write_i32(&mut self, i: i32) {
176 self.write_u32(i as u32)
178 /// Write a single `i64` into this hasher.
180 #[stable(feature = "hasher_write", since = "1.3.0")]
181 fn write_i64(&mut self, i: i64) {
182 self.write_u64(i as u64)
184 /// Write a single `isize` into this hasher.
186 #[stable(feature = "hasher_write", since = "1.3.0")]
187 fn write_isize(&mut self, i: isize) {
188 self.write_usize(i as usize)
192 //////////////////////////////////////////////////////////////////////////////
200 macro_rules! impl_write {
201 ($(($ty:ident, $meth:ident),)*) => {$(
202 #[stable(feature = "rust1", since = "1.0.0")]
204 fn hash<H: Hasher>(&self, state: &mut H) {
208 fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
209 // FIXME(#23542) Replace with type ascription.
210 #![allow(trivial_casts)]
211 let newlen = data.len() * ::$ty::BYTES;
212 let ptr = data.as_ptr() as *const u8;
213 state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
224 (usize, write_usize),
229 (isize, write_isize),
232 #[stable(feature = "rust1", since = "1.0.0")]
234 fn hash<H: Hasher>(&self, state: &mut H) {
235 state.write_u8(*self as u8)
239 #[stable(feature = "rust1", since = "1.0.0")]
241 fn hash<H: Hasher>(&self, state: &mut H) {
242 state.write_u32(*self as u32)
246 #[stable(feature = "rust1", since = "1.0.0")]
248 fn hash<H: Hasher>(&self, state: &mut H) {
249 state.write(self.as_bytes());
254 macro_rules! impl_hash_tuple {
256 #[stable(feature = "rust1", since = "1.0.0")]
258 fn hash<H: Hasher>(&self, _state: &mut H) {}
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);)*
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 }
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)
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);
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);
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)
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)