1 //! Generic hashing support.
3 //! This module provides a generic way to compute the [hash] of a value.
4 //! Hashes are most commonly used with [`HashMap`] and [`HashSet`].
6 //! [hash]: https://en.wikipedia.org/wiki/Hash_function
7 //! [`HashMap`]: ../../std/collections/struct.HashMap.html
8 //! [`HashSet`]: ../../std/collections/struct.HashSet.html
10 //! The simplest way to make a type hashable is to use `#[derive(Hash)]`:
15 //! use std::collections::hash_map::DefaultHasher;
16 //! use std::hash::{Hash, Hasher};
25 //! let person1 = Person {
27 //! name: "Janet".to_string(),
28 //! phone: 555_666_7777,
30 //! let person2 = Person {
32 //! name: "Bob".to_string(),
33 //! phone: 555_666_7777,
36 //! assert!(calculate_hash(&person1) != calculate_hash(&person2));
38 //! fn calculate_hash<T: Hash>(t: &T) -> u64 {
39 //! let mut s = DefaultHasher::new();
45 //! If you need more control over how a value is hashed, you need to implement
46 //! the [`Hash`] trait:
49 //! use std::collections::hash_map::DefaultHasher;
50 //! use std::hash::{Hash, Hasher};
54 //! # #[allow(dead_code)]
59 //! impl Hash for Person {
60 //! fn hash<H: Hasher>(&self, state: &mut H) {
61 //! self.id.hash(state);
62 //! self.phone.hash(state);
66 //! let person1 = Person {
68 //! name: "Janet".to_string(),
69 //! phone: 555_666_7777,
71 //! let person2 = Person {
73 //! name: "Bob".to_string(),
74 //! phone: 555_666_7777,
77 //! assert_eq!(calculate_hash(&person1), calculate_hash(&person2));
79 //! fn calculate_hash<T: Hash>(t: &T) -> u64 {
80 //! let mut s = DefaultHasher::new();
86 #![stable(feature = "rust1", since = "1.0.0")]
91 #[stable(feature = "rust1", since = "1.0.0")]
93 pub use self::sip::SipHasher;
95 #[unstable(feature = "hashmap_internals", issue = "none")]
98 pub use self::sip::SipHasher13;
104 /// Types implementing `Hash` are able to be [`hash`]ed with an instance of
107 /// ## Implementing `Hash`
109 /// You can derive `Hash` with `#[derive(Hash)]` if all fields implement `Hash`.
110 /// The resulting hash will be the combination of the values from calling
111 /// [`hash`] on each field.
115 /// struct Rustacean {
121 /// If you need more control over how a value is hashed, you can of course
122 /// implement the `Hash` trait yourself:
125 /// use std::hash::{Hash, Hasher};
133 /// impl Hash for Person {
134 /// fn hash<H: Hasher>(&self, state: &mut H) {
135 /// self.id.hash(state);
136 /// self.phone.hash(state);
141 /// ## `Hash` and `Eq`
143 /// When implementing both `Hash` and [`Eq`], it is important that the following
147 /// k1 == k2 -> hash(k1) == hash(k2)
150 /// In other words, if two keys are equal, their hashes must also be equal.
151 /// [`HashMap`] and [`HashSet`] both rely on this behavior.
153 /// Thankfully, you won't need to worry about upholding this property when
154 /// deriving both [`Eq`] and `Hash` with `#[derive(PartialEq, Eq, Hash)]`.
156 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
157 /// [`HashSet`]: ../../std/collections/struct.HashSet.html
158 /// [`hash`]: Hash::hash
159 #[stable(feature = "rust1", since = "1.0.0")]
160 #[rustc_diagnostic_item = "Hash"]
162 /// Feeds this value into the given [`Hasher`].
167 /// use std::collections::hash_map::DefaultHasher;
168 /// use std::hash::{Hash, Hasher};
170 /// let mut hasher = DefaultHasher::new();
171 /// 7920.hash(&mut hasher);
172 /// println!("Hash is {:x}!", hasher.finish());
174 #[stable(feature = "rust1", since = "1.0.0")]
175 fn hash<H: Hasher>(&self, state: &mut H);
177 /// Feeds a slice of this type into the given [`Hasher`].
179 /// This method is meant as a convenience, but its implementation is
180 /// also explicitly left unspecified. It isn't guaranteed to be
181 /// equivalent to repeated calls of [`hash`] and implementations of
182 /// [`Hash`] should keep that in mind and call [`hash`] themselves
183 /// if the slice isn't treated as a whole unit in the [`PartialEq`]
186 /// For example, a [`VecDeque`] implementation might naïvely call
187 /// [`as_slices`] and then [`hash_slice`] on each slice, but this
188 /// is wrong since the two slices can change with a call to
189 /// [`make_contiguous`] without affecting the [`PartialEq`]
190 /// result. Since these slices aren't treated as singular
191 /// units, and instead part of a larger deque, this method cannot
197 /// use std::collections::hash_map::DefaultHasher;
198 /// use std::hash::{Hash, Hasher};
200 /// let mut hasher = DefaultHasher::new();
201 /// let numbers = [6, 28, 496, 8128];
202 /// Hash::hash_slice(&numbers, &mut hasher);
203 /// println!("Hash is {:x}!", hasher.finish());
206 /// [`VecDeque`]: ../../std/collections/struct.VecDeque.html
207 /// [`as_slices`]: ../../std/collections/struct.VecDeque.html#method.as_slices
208 /// [`make_contiguous`]: ../../std/collections/struct.VecDeque.html#method.make_contiguous
209 /// [`hash`]: Hash::hash
210 /// [`hash_slice`]: Hash::hash_slice
211 #[stable(feature = "hash_slice", since = "1.3.0")]
212 fn hash_slice<H: Hasher>(data: &[Self], state: &mut H)
222 // Separate module to reexport the macro `Hash` from prelude without the trait `Hash`.
223 pub(crate) mod macros {
224 /// Derive macro generating an impl of the trait `Hash`.
225 #[rustc_builtin_macro]
226 #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
227 #[allow_internal_unstable(core_intrinsics)]
228 pub macro Hash($item:item) {
229 /* compiler built-in */
232 #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
234 pub use macros::Hash;
236 /// A trait for hashing an arbitrary stream of bytes.
238 /// Instances of `Hasher` usually represent state that is changed while hashing
241 /// `Hasher` provides a fairly basic interface for retrieving the generated hash
242 /// (with [`finish`]), and writing integers as well as slices of bytes into an
243 /// instance (with [`write`] and [`write_u8`] etc.). Most of the time, `Hasher`
244 /// instances are used in conjunction with the [`Hash`] trait.
246 /// This trait makes no assumptions about how the various `write_*` methods are
247 /// defined and implementations of [`Hash`] should not assume that they work one
248 /// way or another. You cannot assume, for example, that a [`write_u32`] call is
249 /// equivalent to four calls of [`write_u8`].
254 /// use std::collections::hash_map::DefaultHasher;
255 /// use std::hash::Hasher;
257 /// let mut hasher = DefaultHasher::new();
259 /// hasher.write_u32(1989);
260 /// hasher.write_u8(11);
261 /// hasher.write_u8(9);
262 /// hasher.write(b"Huh?");
264 /// println!("Hash is {:x}!", hasher.finish());
267 /// [`finish`]: Hasher::finish
268 /// [`write`]: Hasher::write
269 /// [`write_u8`]: Hasher::write_u8
270 /// [`write_u32`]: Hasher::write_u32
271 #[stable(feature = "rust1", since = "1.0.0")]
273 /// Returns the hash value for the values written so far.
275 /// Despite its name, the method does not reset the hasher’s internal
276 /// state. Additional [`write`]s will continue from the current value.
277 /// If you need to start a fresh hash value, you will have to create
283 /// use std::collections::hash_map::DefaultHasher;
284 /// use std::hash::Hasher;
286 /// let mut hasher = DefaultHasher::new();
287 /// hasher.write(b"Cool!");
289 /// println!("Hash is {:x}!", hasher.finish());
292 /// [`write`]: Hasher::write
293 #[stable(feature = "rust1", since = "1.0.0")]
294 fn finish(&self) -> u64;
296 /// Writes some data into this `Hasher`.
301 /// use std::collections::hash_map::DefaultHasher;
302 /// use std::hash::Hasher;
304 /// let mut hasher = DefaultHasher::new();
305 /// let data = [0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef];
307 /// hasher.write(&data);
309 /// println!("Hash is {:x}!", hasher.finish());
311 #[stable(feature = "rust1", since = "1.0.0")]
312 fn write(&mut self, bytes: &[u8]);
314 /// Writes a single `u8` into this hasher.
316 #[stable(feature = "hasher_write", since = "1.3.0")]
317 fn write_u8(&mut self, i: u8) {
320 /// Writes a single `u16` into this hasher.
322 #[stable(feature = "hasher_write", since = "1.3.0")]
323 fn write_u16(&mut self, i: u16) {
324 self.write(&i.to_ne_bytes())
326 /// Writes a single `u32` into this hasher.
328 #[stable(feature = "hasher_write", since = "1.3.0")]
329 fn write_u32(&mut self, i: u32) {
330 self.write(&i.to_ne_bytes())
332 /// Writes a single `u64` into this hasher.
334 #[stable(feature = "hasher_write", since = "1.3.0")]
335 fn write_u64(&mut self, i: u64) {
336 self.write(&i.to_ne_bytes())
338 /// Writes a single `u128` into this hasher.
340 #[stable(feature = "i128", since = "1.26.0")]
341 fn write_u128(&mut self, i: u128) {
342 self.write(&i.to_ne_bytes())
344 /// Writes a single `usize` into this hasher.
346 #[stable(feature = "hasher_write", since = "1.3.0")]
347 fn write_usize(&mut self, i: usize) {
348 self.write(&i.to_ne_bytes())
351 /// Writes a single `i8` into this hasher.
353 #[stable(feature = "hasher_write", since = "1.3.0")]
354 fn write_i8(&mut self, i: i8) {
355 self.write_u8(i as u8)
357 /// Writes a single `i16` into this hasher.
359 #[stable(feature = "hasher_write", since = "1.3.0")]
360 fn write_i16(&mut self, i: i16) {
361 self.write_u16(i as u16)
363 /// Writes a single `i32` into this hasher.
365 #[stable(feature = "hasher_write", since = "1.3.0")]
366 fn write_i32(&mut self, i: i32) {
367 self.write_u32(i as u32)
369 /// Writes a single `i64` into this hasher.
371 #[stable(feature = "hasher_write", since = "1.3.0")]
372 fn write_i64(&mut self, i: i64) {
373 self.write_u64(i as u64)
375 /// Writes a single `i128` into this hasher.
377 #[stable(feature = "i128", since = "1.26.0")]
378 fn write_i128(&mut self, i: i128) {
379 self.write_u128(i as u128)
381 /// Writes a single `isize` into this hasher.
383 #[stable(feature = "hasher_write", since = "1.3.0")]
384 fn write_isize(&mut self, i: isize) {
385 self.write_usize(i as usize)
389 #[stable(feature = "indirect_hasher_impl", since = "1.22.0")]
390 impl<H: Hasher + ?Sized> Hasher for &mut H {
391 fn finish(&self) -> u64 {
394 fn write(&mut self, bytes: &[u8]) {
395 (**self).write(bytes)
397 fn write_u8(&mut self, i: u8) {
400 fn write_u16(&mut self, i: u16) {
401 (**self).write_u16(i)
403 fn write_u32(&mut self, i: u32) {
404 (**self).write_u32(i)
406 fn write_u64(&mut self, i: u64) {
407 (**self).write_u64(i)
409 fn write_u128(&mut self, i: u128) {
410 (**self).write_u128(i)
412 fn write_usize(&mut self, i: usize) {
413 (**self).write_usize(i)
415 fn write_i8(&mut self, i: i8) {
418 fn write_i16(&mut self, i: i16) {
419 (**self).write_i16(i)
421 fn write_i32(&mut self, i: i32) {
422 (**self).write_i32(i)
424 fn write_i64(&mut self, i: i64) {
425 (**self).write_i64(i)
427 fn write_i128(&mut self, i: i128) {
428 (**self).write_i128(i)
430 fn write_isize(&mut self, i: isize) {
431 (**self).write_isize(i)
435 /// A trait for creating instances of [`Hasher`].
437 /// A `BuildHasher` is typically used (e.g., by [`HashMap`]) to create
438 /// [`Hasher`]s for each key such that they are hashed independently of one
439 /// another, since [`Hasher`]s contain state.
441 /// For each instance of `BuildHasher`, the [`Hasher`]s created by
442 /// [`build_hasher`] should be identical. That is, if the same stream of bytes
443 /// is fed into each hasher, the same output will also be generated.
448 /// use std::collections::hash_map::RandomState;
449 /// use std::hash::{BuildHasher, Hasher};
451 /// let s = RandomState::new();
452 /// let mut hasher_1 = s.build_hasher();
453 /// let mut hasher_2 = s.build_hasher();
455 /// hasher_1.write_u32(8128);
456 /// hasher_2.write_u32(8128);
458 /// assert_eq!(hasher_1.finish(), hasher_2.finish());
461 /// [`build_hasher`]: BuildHasher::build_hasher
462 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
463 #[stable(since = "1.7.0", feature = "build_hasher")]
464 pub trait BuildHasher {
465 /// Type of the hasher that will be created.
466 #[stable(since = "1.7.0", feature = "build_hasher")]
469 /// Creates a new hasher.
471 /// Each call to `build_hasher` on the same instance should produce identical
477 /// use std::collections::hash_map::RandomState;
478 /// use std::hash::BuildHasher;
480 /// let s = RandomState::new();
481 /// let new_s = s.build_hasher();
483 #[stable(since = "1.7.0", feature = "build_hasher")]
484 fn build_hasher(&self) -> Self::Hasher;
486 /// Calculates the hash of a single value.
488 /// This is intended as a convenience for code which *consumes* hashes, such
489 /// as the implementation of a hash table or in unit tests that check
490 /// whether a custom [`Hash`] implementation behaves as expected.
492 /// This must not be used in any code which *creates* hashes, such as in an
493 /// implementation of [`Hash`]. The way to create a combined hash of
494 /// multiple values is to call [`Hash::hash`] multiple times using the same
495 /// [`Hasher`], not to call this method repeatedly and combine the results.
500 /// #![feature(build_hasher_simple_hash_one)]
502 /// use std::cmp::{max, min};
503 /// use std::hash::{BuildHasher, Hash, Hasher};
504 /// struct OrderAmbivalentPair<T: Ord>(T, T);
505 /// impl<T: Ord + Hash> Hash for OrderAmbivalentPair<T> {
506 /// fn hash<H: Hasher>(&self, hasher: &mut H) {
507 /// min(&self.0, &self.1).hash(hasher);
508 /// max(&self.0, &self.1).hash(hasher);
512 /// // Then later, in a `#[test]` for the type...
513 /// let bh = std::collections::hash_map::RandomState::new();
515 /// bh.hash_one(OrderAmbivalentPair(1, 2)),
516 /// bh.hash_one(OrderAmbivalentPair(2, 1))
519 /// bh.hash_one(OrderAmbivalentPair(10, 2)),
520 /// bh.hash_one(&OrderAmbivalentPair(2, 10))
523 #[unstable(feature = "build_hasher_simple_hash_one", issue = "86161")]
524 fn hash_one<T: Hash>(&self, x: T) -> u64
528 let mut hasher = self.build_hasher();
534 /// Used to create a default [`BuildHasher`] instance for types that implement
535 /// [`Hasher`] and [`Default`].
537 /// `BuildHasherDefault<H>` can be used when a type `H` implements [`Hasher`] and
538 /// [`Default`], and you need a corresponding [`BuildHasher`] instance, but none is
541 /// Any `BuildHasherDefault` is [zero-sized]. It can be created with
542 /// [`default`][method.default]. When using `BuildHasherDefault` with [`HashMap`] or
543 /// [`HashSet`], this doesn't need to be done, since they implement appropriate
544 /// [`Default`] instances themselves.
548 /// Using `BuildHasherDefault` to specify a custom [`BuildHasher`] for
552 /// use std::collections::HashMap;
553 /// use std::hash::{BuildHasherDefault, Hasher};
555 /// #[derive(Default)]
558 /// impl Hasher for MyHasher {
559 /// fn write(&mut self, bytes: &[u8]) {
560 /// // Your hashing algorithm goes here!
564 /// fn finish(&self) -> u64 {
565 /// // Your hashing algorithm goes here!
570 /// type MyBuildHasher = BuildHasherDefault<MyHasher>;
572 /// let hash_map = HashMap::<u32, u32, MyBuildHasher>::default();
575 /// [method.default]: BuildHasherDefault::default
576 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
577 /// [`HashSet`]: ../../std/collections/struct.HashSet.html
578 /// [zero-sized]: https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts
579 #[stable(since = "1.7.0", feature = "build_hasher")]
580 pub struct BuildHasherDefault<H>(marker::PhantomData<H>);
582 #[stable(since = "1.9.0", feature = "core_impl_debug")]
583 impl<H> fmt::Debug for BuildHasherDefault<H> {
584 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
585 f.debug_struct("BuildHasherDefault").finish()
589 #[stable(since = "1.7.0", feature = "build_hasher")]
590 impl<H: Default + Hasher> BuildHasher for BuildHasherDefault<H> {
593 fn build_hasher(&self) -> H {
598 #[stable(since = "1.7.0", feature = "build_hasher")]
599 impl<H> Clone for BuildHasherDefault<H> {
600 fn clone(&self) -> BuildHasherDefault<H> {
601 BuildHasherDefault(marker::PhantomData)
605 #[stable(since = "1.7.0", feature = "build_hasher")]
606 #[rustc_const_unstable(feature = "const_default_impls", issue = "87864")]
607 impl<H> const Default for BuildHasherDefault<H> {
608 fn default() -> BuildHasherDefault<H> {
609 BuildHasherDefault(marker::PhantomData)
613 #[stable(since = "1.29.0", feature = "build_hasher_eq")]
614 impl<H> PartialEq for BuildHasherDefault<H> {
615 fn eq(&self, _other: &BuildHasherDefault<H>) -> bool {
620 #[stable(since = "1.29.0", feature = "build_hasher_eq")]
621 impl<H> Eq for BuildHasherDefault<H> {}
629 macro_rules! impl_write {
630 ($(($ty:ident, $meth:ident),)*) => {$(
631 #[stable(feature = "rust1", since = "1.0.0")]
634 fn hash<H: Hasher>(&self, state: &mut H) {
639 fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
640 let newlen = data.len() * mem::size_of::<$ty>();
641 let ptr = data.as_ptr() as *const u8;
642 // SAFETY: `ptr` is valid and aligned, as this macro is only used
643 // for numeric primitives which have no padding. The new slice only
644 // spans across `data` and is never mutated, and its total size is the
645 // same as the original `data` so it can't be over `isize::MAX`.
646 state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
657 (usize, write_usize),
662 (isize, write_isize),
667 #[stable(feature = "rust1", since = "1.0.0")]
670 fn hash<H: Hasher>(&self, state: &mut H) {
671 state.write_u8(*self as u8)
675 #[stable(feature = "rust1", since = "1.0.0")]
678 fn hash<H: Hasher>(&self, state: &mut H) {
679 state.write_u32(*self as u32)
683 #[stable(feature = "rust1", since = "1.0.0")]
686 fn hash<H: Hasher>(&self, state: &mut H) {
687 state.write(self.as_bytes());
692 #[stable(feature = "never_hash", since = "1.29.0")]
695 fn hash<H: Hasher>(&self, _: &mut H) {
700 macro_rules! impl_hash_tuple {
702 #[stable(feature = "rust1", since = "1.0.0")]
705 fn hash<H: Hasher>(&self, _state: &mut H) {}
709 ( $($name:ident)+) => (
710 #[stable(feature = "rust1", since = "1.0.0")]
711 impl<$($name: Hash),+> Hash for ($($name,)+) where last_type!($($name,)+): ?Sized {
712 #[allow(non_snake_case)]
714 fn hash<S: Hasher>(&self, state: &mut S) {
715 let ($(ref $name,)+) = *self;
716 $($name.hash(state);)+
722 macro_rules! last_type {
723 ($a:ident,) => { $a };
724 ($a:ident, $($rest_a:ident,)+) => { last_type!($($rest_a,)+) };
728 impl_hash_tuple! { A }
729 impl_hash_tuple! { A B }
730 impl_hash_tuple! { A B C }
731 impl_hash_tuple! { A B C D }
732 impl_hash_tuple! { A B C D E }
733 impl_hash_tuple! { A B C D E F }
734 impl_hash_tuple! { A B C D E F G }
735 impl_hash_tuple! { A B C D E F G H }
736 impl_hash_tuple! { A B C D E F G H I }
737 impl_hash_tuple! { A B C D E F G H I J }
738 impl_hash_tuple! { A B C D E F G H I J K }
739 impl_hash_tuple! { A B C D E F G H I J K L }
741 #[stable(feature = "rust1", since = "1.0.0")]
742 impl<T: Hash> Hash for [T] {
744 fn hash<H: Hasher>(&self, state: &mut H) {
745 self.len().hash(state);
746 Hash::hash_slice(self, state)
750 #[stable(feature = "rust1", since = "1.0.0")]
751 impl<T: ?Sized + Hash> Hash for &T {
753 fn hash<H: Hasher>(&self, state: &mut H) {
754 (**self).hash(state);
758 #[stable(feature = "rust1", since = "1.0.0")]
759 impl<T: ?Sized + Hash> Hash for &mut T {
761 fn hash<H: Hasher>(&self, state: &mut H) {
762 (**self).hash(state);
766 #[stable(feature = "rust1", since = "1.0.0")]
767 impl<T: ?Sized> Hash for *const T {
769 fn hash<H: Hasher>(&self, state: &mut H) {
770 let (address, metadata) = self.to_raw_parts();
771 state.write_usize(address as usize);
772 metadata.hash(state);
776 #[stable(feature = "rust1", since = "1.0.0")]
777 impl<T: ?Sized> Hash for *mut T {
779 fn hash<H: Hasher>(&self, state: &mut H) {
780 let (address, metadata) = self.to_raw_parts();
781 state.write_usize(address as usize);
782 metadata.hash(state);