]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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 | |
e9174d1e | 19 | //! use std::hash::{Hash, SipHasher, Hasher}; |
1a4d82fc JJ |
20 | //! |
21 | //! #[derive(Hash)] | |
22 | //! struct Person { | |
c34b1796 | 23 | //! id: u32, |
1a4d82fc JJ |
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 | //! | |
e9174d1e SL |
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 | //! } | |
1a4d82fc JJ |
38 | //! ``` |
39 | //! | |
40 | //! If you need more control over how a value is hashed, you need to implement | |
3157f602 | 41 | //! the `Hash` trait: |
1a4d82fc JJ |
42 | //! |
43 | //! ```rust | |
e9174d1e | 44 | //! use std::hash::{Hash, Hasher, SipHasher}; |
1a4d82fc JJ |
45 | //! |
46 | //! struct Person { | |
c34b1796 | 47 | //! id: u32, |
92a42be0 | 48 | //! # #[allow(dead_code)] |
1a4d82fc JJ |
49 | //! name: String, |
50 | //! phone: u64, | |
51 | //! } | |
52 | //! | |
85aaf69f SL |
53 | //! impl Hash for Person { |
54 | //! fn hash<H: Hasher>(&self, state: &mut H) { | |
1a4d82fc JJ |
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 | //! | |
e9174d1e SL |
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 | //! } | |
1a4d82fc JJ |
70 | //! ``` |
71 | ||
85aaf69f SL |
72 | #![stable(feature = "rust1", since = "1.0.0")] |
73 | ||
e9174d1e | 74 | use prelude::v1::*; |
1a4d82fc | 75 | |
54a0048b | 76 | use fmt; |
9cc50fc6 | 77 | use marker; |
85aaf69f | 78 | use mem; |
1a4d82fc | 79 | |
92a42be0 | 80 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
81 | pub use self::sip::SipHasher; |
82 | ||
3157f602 XL |
83 | #[unstable(feature = "sip_hash_13", issue = "29754")] |
84 | pub use self::sip::{SipHasher13, SipHasher24}; | |
85 | ||
1a4d82fc JJ |
86 | mod sip; |
87 | ||
88 | /// A hashable type. | |
89 | /// | |
90 | /// The `H` type parameter is an abstract hash state that is used by the `Hash` | |
c34b1796 AL |
91 | /// to compute the hash. |
92 | /// | |
93 | /// If you are also implementing `Eq`, there is an additional property that | |
94 | /// is important: | |
95 | /// | |
96 | /// ```text | |
97 | /// k1 == k2 -> hash(k1) == hash(k2) | |
98 | /// ``` | |
99 | /// | |
100 | /// In other words, if two keys are equal, their hashes should also be equal. | |
101 | /// `HashMap` and `HashSet` both rely on this behavior. | |
92a42be0 | 102 | /// |
3157f602 XL |
103 | /// ## Derivable |
104 | /// | |
105 | /// This trait can be used with `#[derive]` if all fields implement `Hash`. | |
106 | /// When `derive`d, the resulting hash will be the combination of the values | |
107 | /// from calling `.hash()` on each field. | |
108 | /// | |
109 | /// ## How can I implement `Hash`? | |
110 | /// | |
111 | /// If you need more control over how a value is hashed, you need to implement | |
112 | /// the `Hash` trait: | |
113 | /// | |
114 | /// ``` | |
115 | /// use std::hash::{Hash, Hasher}; | |
116 | /// | |
117 | /// struct Person { | |
118 | /// id: u32, | |
119 | /// name: String, | |
120 | /// phone: u64, | |
121 | /// } | |
122 | /// | |
123 | /// impl Hash for Person { | |
124 | /// fn hash<H: Hasher>(&self, state: &mut H) { | |
125 | /// self.id.hash(state); | |
126 | /// self.phone.hash(state); | |
127 | /// } | |
128 | /// } | |
129 | /// ``` | |
85aaf69f SL |
130 | #[stable(feature = "rust1", since = "1.0.0")] |
131 | pub trait Hash { | |
1a4d82fc | 132 | /// Feeds this value into the state given, updating the hasher as necessary. |
85aaf69f SL |
133 | #[stable(feature = "rust1", since = "1.0.0")] |
134 | fn hash<H: Hasher>(&self, state: &mut H); | |
135 | ||
136 | /// Feeds a slice of this type into the state provided. | |
c1a9b12d | 137 | #[stable(feature = "hash_slice", since = "1.3.0")] |
b039eaaf SL |
138 | fn hash_slice<H: Hasher>(data: &[Self], state: &mut H) |
139 | where Self: Sized | |
140 | { | |
85aaf69f SL |
141 | for piece in data { |
142 | piece.hash(state); | |
143 | } | |
144 | } | |
1a4d82fc JJ |
145 | } |
146 | ||
1a4d82fc | 147 | /// A trait which represents the ability to hash an arbitrary stream of bytes. |
85aaf69f | 148 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 149 | pub trait Hasher { |
85aaf69f | 150 | /// Completes a round of hashing, producing the output hash generated. |
c34b1796 | 151 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
152 | fn finish(&self) -> u64; |
153 | ||
154 | /// Writes some data into this `Hasher` | |
85aaf69f SL |
155 | #[stable(feature = "rust1", since = "1.0.0")] |
156 | fn write(&mut self, bytes: &[u8]); | |
157 | ||
158 | /// Write a single `u8` into this hasher | |
85aaf69f | 159 | #[inline] |
c1a9b12d | 160 | #[stable(feature = "hasher_write", since = "1.3.0")] |
b039eaaf SL |
161 | fn write_u8(&mut self, i: u8) { |
162 | self.write(&[i]) | |
163 | } | |
85aaf69f | 164 | /// Write a single `u16` into this hasher. |
85aaf69f | 165 | #[inline] |
c1a9b12d | 166 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
167 | fn write_u16(&mut self, i: u16) { |
168 | self.write(&unsafe { mem::transmute::<_, [u8; 2]>(i) }) | |
169 | } | |
170 | /// Write a single `u32` into this hasher. | |
85aaf69f | 171 | #[inline] |
c1a9b12d | 172 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
173 | fn write_u32(&mut self, i: u32) { |
174 | self.write(&unsafe { mem::transmute::<_, [u8; 4]>(i) }) | |
175 | } | |
176 | /// Write a single `u64` into this hasher. | |
85aaf69f | 177 | #[inline] |
c1a9b12d | 178 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
179 | fn write_u64(&mut self, i: u64) { |
180 | self.write(&unsafe { mem::transmute::<_, [u8; 8]>(i) }) | |
181 | } | |
182 | /// Write a single `usize` into this hasher. | |
85aaf69f | 183 | #[inline] |
c1a9b12d | 184 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f | 185 | fn write_usize(&mut self, i: usize) { |
e9174d1e | 186 | let bytes = unsafe { |
b039eaaf | 187 | ::slice::from_raw_parts(&i as *const usize as *const u8, mem::size_of::<usize>()) |
e9174d1e SL |
188 | }; |
189 | self.write(bytes); | |
85aaf69f SL |
190 | } |
191 | ||
192 | /// Write a single `i8` into this hasher. | |
85aaf69f | 193 | #[inline] |
c1a9b12d | 194 | #[stable(feature = "hasher_write", since = "1.3.0")] |
b039eaaf SL |
195 | fn write_i8(&mut self, i: i8) { |
196 | self.write_u8(i as u8) | |
197 | } | |
85aaf69f | 198 | /// Write a single `i16` into this hasher. |
85aaf69f | 199 | #[inline] |
c1a9b12d | 200 | #[stable(feature = "hasher_write", since = "1.3.0")] |
b039eaaf SL |
201 | fn write_i16(&mut self, i: i16) { |
202 | self.write_u16(i as u16) | |
203 | } | |
85aaf69f | 204 | /// Write a single `i32` into this hasher. |
85aaf69f | 205 | #[inline] |
c1a9b12d | 206 | #[stable(feature = "hasher_write", since = "1.3.0")] |
b039eaaf SL |
207 | fn write_i32(&mut self, i: i32) { |
208 | self.write_u32(i as u32) | |
209 | } | |
85aaf69f | 210 | /// Write a single `i64` into this hasher. |
85aaf69f | 211 | #[inline] |
c1a9b12d | 212 | #[stable(feature = "hasher_write", since = "1.3.0")] |
b039eaaf SL |
213 | fn write_i64(&mut self, i: i64) { |
214 | self.write_u64(i as u64) | |
215 | } | |
85aaf69f | 216 | /// Write a single `isize` into this hasher. |
85aaf69f | 217 | #[inline] |
c1a9b12d | 218 | #[stable(feature = "hasher_write", since = "1.3.0")] |
b039eaaf SL |
219 | fn write_isize(&mut self, i: isize) { |
220 | self.write_usize(i as usize) | |
221 | } | |
1a4d82fc JJ |
222 | } |
223 | ||
9cc50fc6 SL |
224 | /// A `BuildHasher` is typically used as a factory for instances of `Hasher` |
225 | /// which a `HashMap` can then use to hash keys independently. | |
226 | /// | |
7453a54e SL |
227 | /// Note that for each instance of `BuildHasher`, the created hashers should be |
228 | /// identical. That is, if the same stream of bytes is fed into each hasher, the | |
9cc50fc6 SL |
229 | /// same output will also be generated. |
230 | #[stable(since = "1.7.0", feature = "build_hasher")] | |
231 | pub trait BuildHasher { | |
232 | /// Type of the hasher that will be created. | |
233 | #[stable(since = "1.7.0", feature = "build_hasher")] | |
234 | type Hasher: Hasher; | |
235 | ||
236 | /// Creates a new hasher. | |
237 | #[stable(since = "1.7.0", feature = "build_hasher")] | |
238 | fn build_hasher(&self) -> Self::Hasher; | |
239 | } | |
240 | ||
241 | /// A structure which implements `BuildHasher` for all `Hasher` types which also | |
242 | /// implement `Default`. | |
243 | /// | |
244 | /// This struct is 0-sized and does not need construction. | |
245 | #[stable(since = "1.7.0", feature = "build_hasher")] | |
246 | pub struct BuildHasherDefault<H>(marker::PhantomData<H>); | |
247 | ||
54a0048b SL |
248 | #[stable(since = "1.9.0", feature = "core_impl_debug")] |
249 | impl<H> fmt::Debug for BuildHasherDefault<H> { | |
250 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
251 | f.pad("BuildHasherDefault") | |
252 | } | |
253 | } | |
254 | ||
9cc50fc6 SL |
255 | #[stable(since = "1.7.0", feature = "build_hasher")] |
256 | impl<H: Default + Hasher> BuildHasher for BuildHasherDefault<H> { | |
257 | type Hasher = H; | |
258 | ||
259 | fn build_hasher(&self) -> H { | |
260 | H::default() | |
261 | } | |
262 | } | |
263 | ||
264 | #[stable(since = "1.7.0", feature = "build_hasher")] | |
265 | impl<H> Clone for BuildHasherDefault<H> { | |
266 | fn clone(&self) -> BuildHasherDefault<H> { | |
267 | BuildHasherDefault(marker::PhantomData) | |
268 | } | |
269 | } | |
270 | ||
271 | #[stable(since = "1.7.0", feature = "build_hasher")] | |
272 | impl<H> Default for BuildHasherDefault<H> { | |
273 | fn default() -> BuildHasherDefault<H> { | |
274 | BuildHasherDefault(marker::PhantomData) | |
275 | } | |
276 | } | |
277 | ||
1a4d82fc JJ |
278 | ////////////////////////////////////////////////////////////////////////////// |
279 | ||
1a4d82fc | 280 | mod impls { |
e9174d1e | 281 | use prelude::v1::*; |
1a4d82fc | 282 | |
9cc50fc6 | 283 | use mem; |
85aaf69f SL |
284 | use slice; |
285 | use super::*; | |
1a4d82fc | 286 | |
85aaf69f SL |
287 | macro_rules! impl_write { |
288 | ($(($ty:ident, $meth:ident),)*) => {$( | |
289 | #[stable(feature = "rust1", since = "1.0.0")] | |
290 | impl Hash for $ty { | |
291 | fn hash<H: Hasher>(&self, state: &mut H) { | |
292 | state.$meth(*self) | |
293 | } | |
294 | ||
295 | fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) { | |
9cc50fc6 | 296 | let newlen = data.len() * mem::size_of::<$ty>(); |
85aaf69f SL |
297 | let ptr = data.as_ptr() as *const u8; |
298 | state.write(unsafe { slice::from_raw_parts(ptr, newlen) }) | |
1a4d82fc JJ |
299 | } |
300 | } | |
85aaf69f | 301 | )*} |
1a4d82fc JJ |
302 | } |
303 | ||
85aaf69f SL |
304 | impl_write! { |
305 | (u8, write_u8), | |
306 | (u16, write_u16), | |
307 | (u32, write_u32), | |
308 | (u64, write_u64), | |
309 | (usize, write_usize), | |
310 | (i8, write_i8), | |
311 | (i16, write_i16), | |
312 | (i32, write_i32), | |
313 | (i64, write_i64), | |
314 | (isize, write_isize), | |
315 | } | |
1a4d82fc | 316 | |
85aaf69f SL |
317 | #[stable(feature = "rust1", since = "1.0.0")] |
318 | impl Hash for bool { | |
319 | fn hash<H: Hasher>(&self, state: &mut H) { | |
320 | state.write_u8(*self as u8) | |
1a4d82fc JJ |
321 | } |
322 | } | |
323 | ||
85aaf69f SL |
324 | #[stable(feature = "rust1", since = "1.0.0")] |
325 | impl Hash for char { | |
326 | fn hash<H: Hasher>(&self, state: &mut H) { | |
327 | state.write_u32(*self as u32) | |
1a4d82fc JJ |
328 | } |
329 | } | |
330 | ||
85aaf69f SL |
331 | #[stable(feature = "rust1", since = "1.0.0")] |
332 | impl Hash for str { | |
333 | fn hash<H: Hasher>(&self, state: &mut H) { | |
1a4d82fc | 334 | state.write(self.as_bytes()); |
85aaf69f | 335 | state.write_u8(0xff) |
1a4d82fc JJ |
336 | } |
337 | } | |
338 | ||
339 | macro_rules! impl_hash_tuple { | |
340 | () => ( | |
85aaf69f SL |
341 | #[stable(feature = "rust1", since = "1.0.0")] |
342 | impl Hash for () { | |
343 | fn hash<H: Hasher>(&self, _state: &mut H) {} | |
1a4d82fc JJ |
344 | } |
345 | ); | |
346 | ||
347 | ( $($name:ident)+) => ( | |
85aaf69f SL |
348 | #[stable(feature = "rust1", since = "1.0.0")] |
349 | impl<$($name: Hash),*> Hash for ($($name,)*) { | |
1a4d82fc | 350 | #[allow(non_snake_case)] |
85aaf69f SL |
351 | fn hash<S: Hasher>(&self, state: &mut S) { |
352 | let ($(ref $name,)*) = *self; | |
353 | $($name.hash(state);)* | |
1a4d82fc JJ |
354 | } |
355 | } | |
356 | ); | |
357 | } | |
358 | ||
359 | impl_hash_tuple! {} | |
360 | impl_hash_tuple! { A } | |
361 | impl_hash_tuple! { A B } | |
362 | impl_hash_tuple! { A B C } | |
363 | impl_hash_tuple! { A B C D } | |
364 | impl_hash_tuple! { A B C D E } | |
365 | impl_hash_tuple! { A B C D E F } | |
366 | impl_hash_tuple! { A B C D E F G } | |
367 | impl_hash_tuple! { A B C D E F G H } | |
368 | impl_hash_tuple! { A B C D E F G H I } | |
369 | impl_hash_tuple! { A B C D E F G H I J } | |
370 | impl_hash_tuple! { A B C D E F G H I J K } | |
371 | impl_hash_tuple! { A B C D E F G H I J K L } | |
372 | ||
85aaf69f SL |
373 | #[stable(feature = "rust1", since = "1.0.0")] |
374 | impl<T: Hash> Hash for [T] { | |
375 | fn hash<H: Hasher>(&self, state: &mut H) { | |
1a4d82fc | 376 | self.len().hash(state); |
85aaf69f | 377 | Hash::hash_slice(self, state) |
1a4d82fc JJ |
378 | } |
379 | } | |
380 | ||
381 | ||
85aaf69f SL |
382 | #[stable(feature = "rust1", since = "1.0.0")] |
383 | impl<'a, T: ?Sized + Hash> Hash for &'a T { | |
384 | fn hash<H: Hasher>(&self, state: &mut H) { | |
1a4d82fc JJ |
385 | (**self).hash(state); |
386 | } | |
387 | } | |
388 | ||
85aaf69f SL |
389 | #[stable(feature = "rust1", since = "1.0.0")] |
390 | impl<'a, T: ?Sized + Hash> Hash for &'a mut T { | |
391 | fn hash<H: Hasher>(&self, state: &mut H) { | |
1a4d82fc JJ |
392 | (**self).hash(state); |
393 | } | |
394 | } | |
395 | ||
85aaf69f SL |
396 | #[stable(feature = "rust1", since = "1.0.0")] |
397 | impl<T> Hash for *const T { | |
398 | fn hash<H: Hasher>(&self, state: &mut H) { | |
399 | state.write_usize(*self as usize) | |
1a4d82fc JJ |
400 | } |
401 | } | |
402 | ||
85aaf69f SL |
403 | #[stable(feature = "rust1", since = "1.0.0")] |
404 | impl<T> Hash for *mut T { | |
405 | fn hash<H: Hasher>(&self, state: &mut H) { | |
406 | state.write_usize(*self as usize) | |
1a4d82fc JJ |
407 | } |
408 | } | |
409 | } |