1 //! Generic hashing support.
3 //! This module provides a generic way to compute the hash of a value. The
4 //! simplest way to make a type hashable is to use `#[derive(Hash)]`:
9 //! use std::collections::hash_map::DefaultHasher;
10 //! use std::hash::{Hash, Hasher};
19 //! let person1 = Person {
21 //! name: "Janet".to_string(),
22 //! phone: 555_666_7777,
24 //! let person2 = Person {
26 //! name: "Bob".to_string(),
27 //! phone: 555_666_7777,
30 //! assert!(calculate_hash(&person1) != calculate_hash(&person2));
32 //! fn calculate_hash<T: Hash>(t: &T) -> u64 {
33 //! let mut s = DefaultHasher::new();
39 //! If you need more control over how a value is hashed, you need to implement
40 //! the [`Hash`] trait:
42 //! [`Hash`]: trait.Hash.html
45 //! use std::collections::hash_map::DefaultHasher;
46 //! use std::hash::{Hash, Hasher};
50 //! # #[allow(dead_code)]
55 //! impl Hash for Person {
56 //! fn hash<H: Hasher>(&self, state: &mut H) {
57 //! self.id.hash(state);
58 //! self.phone.hash(state);
62 //! let person1 = Person {
64 //! name: "Janet".to_string(),
65 //! phone: 555_666_7777,
67 //! let person2 = Person {
69 //! name: "Bob".to_string(),
70 //! phone: 555_666_7777,
73 //! assert_eq!(calculate_hash(&person1), calculate_hash(&person2));
75 //! fn calculate_hash<T: Hash>(t: &T) -> u64 {
76 //! let mut s = DefaultHasher::new();
82 #![stable(feature = "rust1", since = "1.0.0")]
87 #[stable(feature = "rust1", since = "1.0.0")]
89 pub use self::sip
::SipHasher
;
91 #[unstable(feature = "hashmap_internals", issue = "0")]
94 pub use self::sip
::SipHasher13
;
100 /// Types implementing `Hash` are able to be [`hash`]ed with an instance of
103 /// ## Implementing `Hash`
105 /// You can derive `Hash` with `#[derive(Hash)]` if all fields implement `Hash`.
106 /// The resulting hash will be the combination of the values from calling
107 /// [`hash`] on each field.
111 /// struct Rustacean {
117 /// If you need more control over how a value is hashed, you can of course
118 /// implement the `Hash` trait yourself:
121 /// use std::hash::{Hash, Hasher};
129 /// impl Hash for Person {
130 /// fn hash<H: Hasher>(&self, state: &mut H) {
131 /// self.id.hash(state);
132 /// self.phone.hash(state);
137 /// ## `Hash` and `Eq`
139 /// When implementing both `Hash` and [`Eq`], it is important that the following
143 /// k1 == k2 -> hash(k1) == hash(k2)
146 /// In other words, if two keys are equal, their hashes must also be equal.
147 /// [`HashMap`] and [`HashSet`] both rely on this behavior.
149 /// Thankfully, you won't need to worry about upholding this property when
150 /// deriving both [`Eq`] and `Hash` with `#[derive(PartialEq, Eq, Hash)]`.
152 /// [`Eq`]: ../../std/cmp/trait.Eq.html
153 /// [`Hasher`]: trait.Hasher.html
154 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
155 /// [`HashSet`]: ../../std/collections/struct.HashSet.html
156 /// [`hash`]: #tymethod.hash
157 #[stable(feature = "rust1", since = "1.0.0")]
159 /// Feeds this value into the given [`Hasher`].
164 /// use std::collections::hash_map::DefaultHasher;
165 /// use std::hash::{Hash, Hasher};
167 /// let mut hasher = DefaultHasher::new();
168 /// 7920.hash(&mut hasher);
169 /// println!("Hash is {:x}!", hasher.finish());
172 /// [`Hasher`]: trait.Hasher.html
173 #[stable(feature = "rust1", since = "1.0.0")]
174 fn hash
<H
: Hasher
>(&self, state
: &mut H
);
176 /// Feeds a slice of this type into the given [`Hasher`].
181 /// use std::collections::hash_map::DefaultHasher;
182 /// use std::hash::{Hash, Hasher};
184 /// let mut hasher = DefaultHasher::new();
185 /// let numbers = [6, 28, 496, 8128];
186 /// Hash::hash_slice(&numbers, &mut hasher);
187 /// println!("Hash is {:x}!", hasher.finish());
190 /// [`Hasher`]: trait.Hasher.html
191 #[stable(feature = "hash_slice", since = "1.3.0")]
192 fn hash_slice
<H
: Hasher
>(data
: &[Self], state
: &mut H
)
201 // Separate module to reexport the macro `Hash` from prelude without the trait `Hash`.
202 #[cfg(not(bootstrap))]
203 pub(crate) mod macros
{
204 /// Derive macro generating an impl of the trait `Hash`.
205 #[rustc_builtin_macro]
206 #[rustc_macro_transparency = "semitransparent"]
207 #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
208 #[allow_internal_unstable(core_intrinsics)]
209 pub macro Hash($item
:item
) { /* compiler built-in */ }
211 #[cfg(not(bootstrap))]
212 #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
214 pub use macros
::Hash
;
216 /// A trait for hashing an arbitrary stream of bytes.
218 /// Instances of `Hasher` usually represent state that is changed while hashing
221 /// `Hasher` provides a fairly basic interface for retrieving the generated hash
222 /// (with [`finish`]), and writing integers as well as slices of bytes into an
223 /// instance (with [`write`] and [`write_u8`] etc.). Most of the time, `Hasher`
224 /// instances are used in conjunction with the [`Hash`] trait.
229 /// use std::collections::hash_map::DefaultHasher;
230 /// use std::hash::Hasher;
232 /// let mut hasher = DefaultHasher::new();
234 /// hasher.write_u32(1989);
235 /// hasher.write_u8(11);
236 /// hasher.write_u8(9);
237 /// hasher.write(b"Huh?");
239 /// println!("Hash is {:x}!", hasher.finish());
242 /// [`Hash`]: trait.Hash.html
243 /// [`finish`]: #tymethod.finish
244 /// [`write`]: #tymethod.write
245 /// [`write_u8`]: #method.write_u8
246 #[stable(feature = "rust1", since = "1.0.0")]
248 /// Returns the hash value for the values written so far.
250 /// Despite its name, the method does not reset the hasher’s internal
251 /// state. Additional [`write`]s will continue from the current value.
252 /// If you need to start a fresh hash value, you will have to create
258 /// use std::collections::hash_map::DefaultHasher;
259 /// use std::hash::Hasher;
261 /// let mut hasher = DefaultHasher::new();
262 /// hasher.write(b"Cool!");
264 /// println!("Hash is {:x}!", hasher.finish());
267 /// [`write`]: #tymethod.write
268 #[stable(feature = "rust1", since = "1.0.0")]
269 fn finish(&self) -> u64;
271 /// Writes some data into this `Hasher`.
276 /// use std::collections::hash_map::DefaultHasher;
277 /// use std::hash::Hasher;
279 /// let mut hasher = DefaultHasher::new();
280 /// let data = [0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef];
282 /// hasher.write(&data);
284 /// println!("Hash is {:x}!", hasher.finish());
286 #[stable(feature = "rust1", since = "1.0.0")]
287 fn write(&mut self, bytes
: &[u8]);
289 /// Writes a single `u8` into this hasher.
291 #[stable(feature = "hasher_write", since = "1.3.0")]
292 fn write_u8(&mut self, i
: u8) {
295 /// Writes a single `u16` into this hasher.
297 #[stable(feature = "hasher_write", since = "1.3.0")]
298 fn write_u16(&mut self, i
: u16) {
299 self.write(&i
.to_ne_bytes())
301 /// Writes a single `u32` into this hasher.
303 #[stable(feature = "hasher_write", since = "1.3.0")]
304 fn write_u32(&mut self, i
: u32) {
305 self.write(&i
.to_ne_bytes())
307 /// Writes a single `u64` into this hasher.
309 #[stable(feature = "hasher_write", since = "1.3.0")]
310 fn write_u64(&mut self, i
: u64) {
311 self.write(&i
.to_ne_bytes())
313 /// Writes a single `u128` into this hasher.
315 #[stable(feature = "i128", since = "1.26.0")]
316 fn write_u128(&mut self, i
: u128
) {
317 self.write(&i
.to_ne_bytes())
319 /// Writes a single `usize` into this hasher.
321 #[stable(feature = "hasher_write", since = "1.3.0")]
322 fn write_usize(&mut self, i
: usize) {
323 self.write(&i
.to_ne_bytes())
326 /// Writes a single `i8` into this hasher.
328 #[stable(feature = "hasher_write", since = "1.3.0")]
329 fn write_i8(&mut self, i
: i8) {
330 self.write_u8(i
as u8)
332 /// Writes a single `i16` into this hasher.
334 #[stable(feature = "hasher_write", since = "1.3.0")]
335 fn write_i16(&mut self, i
: i16) {
336 self.write(&i
.to_ne_bytes())
338 /// Writes a single `i32` into this hasher.
340 #[stable(feature = "hasher_write", since = "1.3.0")]
341 fn write_i32(&mut self, i
: i32) {
342 self.write(&i
.to_ne_bytes())
344 /// Writes a single `i64` into this hasher.
346 #[stable(feature = "hasher_write", since = "1.3.0")]
347 fn write_i64(&mut self, i
: i64) {
348 self.write(&i
.to_ne_bytes())
350 /// Writes a single `i128` into this hasher.
352 #[stable(feature = "i128", since = "1.26.0")]
353 fn write_i128(&mut self, i
: i128
) {
354 self.write(&i
.to_ne_bytes())
356 /// Writes a single `isize` into this hasher.
358 #[stable(feature = "hasher_write", since = "1.3.0")]
359 fn write_isize(&mut self, i
: isize) {
360 self.write(&i
.to_ne_bytes())
364 #[stable(feature = "indirect_hasher_impl", since = "1.22.0")]
365 impl<H
: Hasher
+ ?Sized
> Hasher
for &mut H
{
366 fn finish(&self) -> u64 {
369 fn write(&mut self, bytes
: &[u8]) {
370 (**self).write(bytes
)
372 fn write_u8(&mut self, i
: u8) {
375 fn write_u16(&mut self, i
: u16) {
376 (**self).write_u16(i
)
378 fn write_u32(&mut self, i
: u32) {
379 (**self).write_u32(i
)
381 fn write_u64(&mut self, i
: u64) {
382 (**self).write_u64(i
)
384 fn write_u128(&mut self, i
: u128
) {
385 (**self).write_u128(i
)
387 fn write_usize(&mut self, i
: usize) {
388 (**self).write_usize(i
)
390 fn write_i8(&mut self, i
: i8) {
393 fn write_i16(&mut self, i
: i16) {
394 (**self).write_i16(i
)
396 fn write_i32(&mut self, i
: i32) {
397 (**self).write_i32(i
)
399 fn write_i64(&mut self, i
: i64) {
400 (**self).write_i64(i
)
402 fn write_i128(&mut self, i
: i128
) {
403 (**self).write_i128(i
)
405 fn write_isize(&mut self, i
: isize) {
406 (**self).write_isize(i
)
410 /// A trait for creating instances of [`Hasher`].
412 /// A `BuildHasher` is typically used (e.g., by [`HashMap`]) to create
413 /// [`Hasher`]s for each key such that they are hashed independently of one
414 /// another, since [`Hasher`]s contain state.
416 /// For each instance of `BuildHasher`, the [`Hasher`]s created by
417 /// [`build_hasher`] should be identical. That is, if the same stream of bytes
418 /// is fed into each hasher, the same output will also be generated.
423 /// use std::collections::hash_map::RandomState;
424 /// use std::hash::{BuildHasher, Hasher};
426 /// let s = RandomState::new();
427 /// let mut hasher_1 = s.build_hasher();
428 /// let mut hasher_2 = s.build_hasher();
430 /// hasher_1.write_u32(8128);
431 /// hasher_2.write_u32(8128);
433 /// assert_eq!(hasher_1.finish(), hasher_2.finish());
436 /// [`build_hasher`]: #tymethod.build_hasher
437 /// [`Hasher`]: trait.Hasher.html
438 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
439 #[stable(since = "1.7.0", feature = "build_hasher")]
440 pub trait BuildHasher
{
441 /// Type of the hasher that will be created.
442 #[stable(since = "1.7.0", feature = "build_hasher")]
445 /// Creates a new hasher.
447 /// Each call to `build_hasher` on the same instance should produce identical
453 /// use std::collections::hash_map::RandomState;
454 /// use std::hash::BuildHasher;
456 /// let s = RandomState::new();
457 /// let new_s = s.build_hasher();
460 /// [`Hasher`]: trait.Hasher.html
461 #[stable(since = "1.7.0", feature = "build_hasher")]
462 fn build_hasher(&self) -> Self::Hasher
;
465 /// Used to create a default [`BuildHasher`] instance for types that implement
466 /// [`Hasher`] and [`Default`].
468 /// `BuildHasherDefault<H>` can be used when a type `H` implements [`Hasher`] and
469 /// [`Default`], and you need a corresponding [`BuildHasher`] instance, but none is
472 /// Any `BuildHasherDefault` is [zero-sized]. It can be created with
473 /// [`default`][method.Default]. When using `BuildHasherDefault` with [`HashMap`] or
474 /// [`HashSet`], this doesn't need to be done, since they implement appropriate
475 /// [`Default`] instances themselves.
479 /// Using `BuildHasherDefault` to specify a custom [`BuildHasher`] for
483 /// use std::collections::HashMap;
484 /// use std::hash::{BuildHasherDefault, Hasher};
486 /// #[derive(Default)]
489 /// impl Hasher for MyHasher {
490 /// fn write(&mut self, bytes: &[u8]) {
491 /// // Your hashing algorithm goes here!
495 /// fn finish(&self) -> u64 {
496 /// // Your hashing algorithm goes here!
501 /// type MyBuildHasher = BuildHasherDefault<MyHasher>;
503 /// let hash_map = HashMap::<u32, u32, MyBuildHasher>::default();
506 /// [`BuildHasher`]: trait.BuildHasher.html
507 /// [`Default`]: ../default/trait.Default.html
508 /// [method.default]: #method.default
509 /// [`Hasher`]: trait.Hasher.html
510 /// [`HashMap`]: ../../std/collections/struct.HashMap.html
511 /// [`HashSet`]: ../../std/collections/struct.HashSet.html
512 /// [zero-sized]: https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts
513 #[stable(since = "1.7.0", feature = "build_hasher")]
514 pub struct BuildHasherDefault
<H
>(marker
::PhantomData
<H
>);
516 #[stable(since = "1.9.0", feature = "core_impl_debug")]
517 impl<H
> fmt
::Debug
for BuildHasherDefault
<H
> {
518 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
519 f
.pad("BuildHasherDefault")
523 #[stable(since = "1.7.0", feature = "build_hasher")]
524 impl<H
: Default
+ Hasher
> BuildHasher
for BuildHasherDefault
<H
> {
527 fn build_hasher(&self) -> H
{
532 #[stable(since = "1.7.0", feature = "build_hasher")]
533 impl<H
> Clone
for BuildHasherDefault
<H
> {
534 fn clone(&self) -> BuildHasherDefault
<H
> {
535 BuildHasherDefault(marker
::PhantomData
)
539 #[stable(since = "1.7.0", feature = "build_hasher")]
540 impl<H
> Default
for BuildHasherDefault
<H
> {
541 fn default() -> BuildHasherDefault
<H
> {
542 BuildHasherDefault(marker
::PhantomData
)
546 #[stable(since = "1.29.0", feature = "build_hasher_eq")]
547 impl<H
> PartialEq
for BuildHasherDefault
<H
> {
548 fn eq(&self, _other
: &BuildHasherDefault
<H
>) -> bool
{
553 #[stable(since = "1.29.0", feature = "build_hasher_eq")]
554 impl<H
> Eq
for BuildHasherDefault
<H
> {}
556 //////////////////////////////////////////////////////////////////////////////
564 macro_rules
! impl_write
{
565 ($
(($ty
:ident
, $meth
:ident
),)*) => {$
(
566 #[stable(feature = "rust1", since = "1.0.0")]
568 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
572 fn hash_slice
<H
: Hasher
>(data
: &[$ty
], state
: &mut H
) {
573 let newlen
= data
.len() * mem
::size_of
::<$ty
>();
574 let ptr
= data
.as_ptr() as *const u8;
575 state
.write(unsafe { slice::from_raw_parts(ptr, newlen) }
)
586 (usize, write_usize
),
591 (isize, write_isize
),
596 #[stable(feature = "rust1", since = "1.0.0")]
598 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
599 state
.write_u8(*self as u8)
603 #[stable(feature = "rust1", since = "1.0.0")]
605 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
606 state
.write_u32(*self as u32)
610 #[stable(feature = "rust1", since = "1.0.0")]
612 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
613 state
.write(self.as_bytes());
618 #[stable(feature = "never_hash", since = "1.29.0")]
620 fn hash
<H
: Hasher
>(&self, _
: &mut H
) {
625 macro_rules
! impl_hash_tuple
{
627 #[stable(feature = "rust1", since = "1.0.0")]
629 fn hash
<H
: Hasher
>(&self, _state
: &mut H
) {}
633 ( $
($name
:ident
)+) => (
634 #[stable(feature = "rust1", since = "1.0.0")]
635 impl<$
($name
: Hash
),+> Hash
for ($
($name
,)+) where last_type
!($
($name
,)+): ?Sized
{
636 #[allow(non_snake_case)]
637 fn hash
<S
: Hasher
>(&self, state
: &mut S
) {
638 let ($
(ref $name
,)+) = *self;
639 $
($name
.hash(state
);)+
645 macro_rules
! last_type
{
646 ($a
:ident
,) => { $a }
;
647 ($a
:ident
, $
($rest_a
:ident
,)+) => { last_type!($($rest_a,)+) }
;
651 impl_hash_tuple
! { A }
652 impl_hash_tuple
! { A B }
653 impl_hash_tuple
! { A B C }
654 impl_hash_tuple
! { A B C D }
655 impl_hash_tuple
! { A B C D E }
656 impl_hash_tuple
! { A B C D E F }
657 impl_hash_tuple
! { A B C D E F G }
658 impl_hash_tuple
! { A B C D E F G H }
659 impl_hash_tuple
! { A B C D E F G H I }
660 impl_hash_tuple
! { A B C D E F G H I J }
661 impl_hash_tuple
! { A B C D E F G H I J K }
662 impl_hash_tuple
! { A B C D E F G H I J K L }
664 #[stable(feature = "rust1", since = "1.0.0")]
665 impl<T
: Hash
> Hash
for [T
] {
666 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
667 self.len().hash(state
);
668 Hash
::hash_slice(self, state
)
673 #[stable(feature = "rust1", since = "1.0.0")]
674 impl<T
: ?Sized
+ Hash
> Hash
for &T
{
675 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
676 (**self).hash(state
);
680 #[stable(feature = "rust1", since = "1.0.0")]
681 impl<T
: ?Sized
+ Hash
> Hash
for &mut T
{
682 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
683 (**self).hash(state
);
687 #[stable(feature = "rust1", since = "1.0.0")]
688 impl<T
: ?Sized
> Hash
for *const T
{
689 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
690 if mem
::size_of
::<Self>() == mem
::size_of
::<usize>() {
692 state
.write_usize(*self as *const () as usize);
695 let (a
, b
) = unsafe {
696 *(self as *const Self as *const (usize, usize))
698 state
.write_usize(a
);
699 state
.write_usize(b
);
704 #[stable(feature = "rust1", since = "1.0.0")]
705 impl<T
: ?Sized
> Hash
for *mut T
{
706 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
707 if mem
::size_of
::<Self>() == mem
::size_of
::<usize>() {
709 state
.write_usize(*self as *const () as usize);
712 let (a
, b
) = unsafe {
713 *(self as *const Self as *const (usize, usize))
715 state
.write_usize(a
);
716 state
.write_usize(b
);