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.
12 * Generic hashing support.
14 * This module provides a generic way to compute the hash of a value. The
15 * simplest way to make a type hashable is to use `#[deriving(Hash)]`:
21 * use std::hash::Hash;
30 * let person1 = Person { id: 5, name: ~"Janet", phone: 555_666_7777 };
31 * let person2 = Person { id: 5, name: ~"Bob", phone: 555_666_7777 };
33 * assert!(hash::hash(&person1) != hash::hash(&person2));
36 * If you need more control over how a value is hashed, you need to implement
41 * use std::hash::Hash;
42 * use std::hash::sip::SipState;
50 * impl Hash for Person {
51 * fn hash(&self, state: &mut SipState) {
52 * self.id.hash(state);
53 * self.phone.hash(state);
57 * let person1 = Person { id: 5, name: ~"Janet", phone: 555_666_7777 };
58 * let person2 = Person { id: 5, name: ~"Bob", phone: 555_666_7777 };
60 * assert!(hash::hash(&person1) == hash::hash(&person2));
64 #[allow(unused_must_use)];
66 use container::Container;
69 use option::{Option, Some, None};
71 use str::{Str, StrSlice};
72 use vec::{Vector, ImmutableVector};
75 /// Reexport the `sip::hash` function as our default hasher.
76 pub use hash = self::sip::hash;
80 /// A trait that represents a hashable type. The `S` type parameter is an
81 /// abstract hash state that is used by the `Hash` to compute the hash.
82 /// It defaults to `std::hash::sip::SipState`.
83 pub trait Hash<S = sip::SipState> {
84 /// Compute a hash of the value.
85 fn hash(&self, state: &mut S);
88 /// A trait that computes a hash for a value. The main users of this trait are
89 /// containers like `HashMap`, which need a generic way hash multiple types.
91 /// Compute a hash of the value.
92 fn hash<T: Hash<S>>(&self, value: &T) -> u64;
95 //////////////////////////////////////////////////////////////////////////////
97 macro_rules! impl_hash(
98 ( $( $ty:ty => $method:ident;)* ) => (
100 impl<S: Writer> Hash<S> for $ty {
102 fn hash(&self, state: &mut S) {
103 state.$method(*self);
115 uint => write_le_uint;
123 impl<S: Writer> Hash<S> for bool {
125 fn hash(&self, state: &mut S) {
126 (*self as u8).hash(state);
130 impl<S: Writer> Hash<S> for char {
132 fn hash(&self, state: &mut S) {
133 (*self as u32).hash(state);
137 impl<'a, S: Writer> Hash<S> for &'a str {
139 fn hash(&self, state: &mut S) {
140 state.write(self.as_bytes());
141 state.write_u8(0xFF);
145 impl<S: Writer> Hash<S> for ~str {
147 fn hash(&self, state: &mut S) {
148 self.as_slice().hash(state);
152 macro_rules! impl_hash_tuple(
154 impl<S: Writer> Hash<S> for () {
156 fn hash(&self, state: &mut S) {
162 ($A:ident $($B:ident)*) => (
165 $A: Hash<S> $(, $B: Hash<S>)*
166 > Hash<S> for ($A, $($B),*) {
168 fn hash(&self, state: &mut S) {
170 (ref $A, $(ref $B),*) => {
180 impl_hash_tuple!($($B)*)
184 impl_hash_tuple!(A0 A1 A2 A3 A4 A5 A6 A7)
186 impl<'a, S: Writer, T: Hash<S>> Hash<S> for &'a [T] {
188 fn hash(&self, state: &mut S) {
189 self.len().hash(state);
190 for elt in self.iter() {
197 impl<'a, S: Writer, T: Hash<S>> Hash<S> for &'a mut [T] {
199 fn hash(&self, state: &mut S) {
200 self.as_slice().hash(state);
204 impl<S: Writer, T: Hash<S>> Hash<S> for ~[T] {
206 fn hash(&self, state: &mut S) {
207 self.as_slice().hash(state);
211 impl<S: Writer, T: Hash<S>> Hash<S> for Vec<T> {
213 fn hash(&self, state: &mut S) {
214 self.as_slice().hash(state);
218 impl<'a, S: Writer, T: Hash<S>> Hash<S> for &'a T {
220 fn hash(&self, state: &mut S) {
221 (**self).hash(state);
225 impl<'a, S: Writer, T: Hash<S>> Hash<S> for &'a mut T {
227 fn hash(&self, state: &mut S) {
228 (**self).hash(state);
232 impl<S: Writer, T: Hash<S>> Hash<S> for ~T {
234 fn hash(&self, state: &mut S) {
235 (**self).hash(state);
239 impl<S: Writer, T: Hash<S>> Hash<S> for @T {
241 fn hash(&self, state: &mut S) {
242 (**self).hash(state);
246 impl<S: Writer, T: Hash<S>> Hash<S> for Rc<T> {
248 fn hash(&self, state: &mut S) {
249 self.borrow().hash(state);
253 impl<S: Writer, T: Hash<S>> Hash<S> for Option<T> {
255 fn hash(&self, state: &mut S) {
268 impl<S: Writer, T> Hash<S> for *T {
270 fn hash(&self, state: &mut S) {
271 // NB: raw-pointer Hash does _not_ dereference
272 // to the target; it just gives you the pointer-bytes.
273 (*self as uint).hash(state);
277 impl<S: Writer, T> Hash<S> for *mut T {
279 fn hash(&self, state: &mut S) {
280 // NB: raw-pointer Hash does _not_ dereference
281 // to the target; it just gives you the pointer-bytes.
282 (*self as uint).hash(state);
286 //////////////////////////////////////////////////////////////////////////////
291 use io::{IoResult, Writer};
292 use iter::{Iterator};
293 use option::{Some, None};
295 use vec::ImmutableVector;
297 use super::{Hash, Hasher};
299 struct MyWriterHasher;
301 impl Hasher<MyWriter> for MyWriterHasher {
302 fn hash<T: Hash<MyWriter>>(&self, value: &T) -> u64 {
303 let mut state = MyWriter { hash: 0 };
304 value.hash(&mut state);
313 impl Writer for MyWriter {
314 // Most things we'll just add up the bytes.
315 fn write(&mut self, buf: &[u8]) -> IoResult<()> {
316 for byte in buf.iter() {
317 self.hash += *byte as u64;
324 fn test_writer_hasher() {
325 let hasher = MyWriterHasher;
327 assert_eq!(hasher.hash(&()), 0);
329 assert_eq!(hasher.hash(&5u8), 5);
330 assert_eq!(hasher.hash(&5u16), 5);
331 assert_eq!(hasher.hash(&5u32), 5);
332 assert_eq!(hasher.hash(&5u64), 5);
333 assert_eq!(hasher.hash(&5u), 5);
335 assert_eq!(hasher.hash(&5i8), 5);
336 assert_eq!(hasher.hash(&5i16), 5);
337 assert_eq!(hasher.hash(&5i32), 5);
338 assert_eq!(hasher.hash(&5i64), 5);
339 assert_eq!(hasher.hash(&5i), 5);
341 assert_eq!(hasher.hash(&false), 0);
342 assert_eq!(hasher.hash(&true), 1);
344 assert_eq!(hasher.hash(&'a'), 97);
346 assert_eq!(hasher.hash(& &"a"), 97 + 0xFF);
347 assert_eq!(hasher.hash(& &[1u8, 2u8, 3u8]), 9);
350 let ptr: *int = cast::transmute(5);
351 assert_eq!(hasher.hash(&ptr), 5);
355 let ptr: *mut int = cast::transmute(5);
356 assert_eq!(hasher.hash(&ptr), 5);
364 impl Hash<u64> for Custom {
365 fn hash(&self, state: &mut u64) {
371 fn test_custom_state() {
372 let custom = Custom { hash: 5 };
374 custom.hash(&mut state);
375 assert_eq!(state, 5);