1//! Generic hashing support.
2//!
3//! This module provides a generic way to compute the [hash] of a value.
4//! Hashes are most commonly used with [`HashMap`] and [`HashSet`].
5//!
6//! [hash]: https://en.wikipedia.org/wiki/Hash_function
7//! [`HashMap`]: ../../std/collections/struct.HashMap.html
8//! [`HashSet`]: ../../std/collections/struct.HashSet.html
9//!
10//! The simplest way to make a type hashable is to use `#[derive(Hash)]`:
11//!
12//! # Examples
13//!
14//! ```rust
15//! use std::hash::{DefaultHasher, Hash, Hasher};
16//!
17//! #[derive(Hash)]
18//! struct Person {
19//! id: u32,
20//! name: String,
21//! phone: u64,
22//! }
23//!
24//! let person1 = Person {
25//! id: 5,
26//! name: "Janet".to_string(),
27//! phone: 555_666_7777,
28//! };
29//! let person2 = Person {
30//! id: 5,
31//! name: "Bob".to_string(),
32//! phone: 555_666_7777,
33//! };
34//!
35//! assert!(calculate_hash(&person1) != calculate_hash(&person2));
36//!
37//! fn calculate_hash<T: Hash>(t: &T) -> u64 {
38//! let mut s = DefaultHasher::new();
39//! t.hash(&mut s);
40//! s.finish()
41//! }
42//! ```
43//!
44//! If you need more control over how a value is hashed, you need to implement
45//! the [`Hash`] trait:
46//!
47//! ```rust
48//! use std::hash::{DefaultHasher, Hash, Hasher};
49//!
50//! struct Person {
51//! id: u32,
52//! # #[allow(dead_code)]
53//! name: String,
54//! phone: u64,
55//! }
56//!
57//! impl Hash for Person {
58//! fn hash<H: Hasher>(&self, state: &mut H) {
59//! self.id.hash(state);
60//! self.phone.hash(state);
61//! }
62//! }
63//!
64//! let person1 = Person {
65//! id: 5,
66//! name: "Janet".to_string(),
67//! phone: 555_666_7777,
68//! };
69//! let person2 = Person {
70//! id: 5,
71//! name: "Bob".to_string(),
72//! phone: 555_666_7777,
73//! };
74//!
75//! assert_eq!(calculate_hash(&person1), calculate_hash(&person2));
76//!
77//! fn calculate_hash<T: Hash>(t: &T) -> u64 {
78//! let mut s = DefaultHasher::new();
79//! t.hash(&mut s);
80//! s.finish()
81//! }
82//! ```
83
84#![stable(feature = "rust1", since = "1.0.0")]
85
86use crate::fmt;
87use crate::marker;
88
89#[stable(feature = "rust1", since = "1.0.0")]
90#[allow(deprecated)]
91pub use self::sip::SipHasher;
92
93#[unstable(feature = "hashmap_internals", issue = "none")]
94#[allow(deprecated)]
95#[doc(hidden)]
96pub use self::sip::SipHasher13;
97
98mod sip;
99
100/// A hashable type.
101///
102/// Types implementing `Hash` are able to be [`hash`]ed with an instance of
103/// [`Hasher`].
104///
105/// ## Implementing `Hash`
106///
107/// You can derive `Hash` with `#[derive(Hash)]` if all fields implement `Hash`.
108/// The resulting hash will be the combination of the values from calling
109/// [`hash`] on each field.
110///
111/// ```
112/// #[derive(Hash)]
113/// struct Rustacean {
114/// name: String,
115/// country: String,
116/// }
117/// ```
118///
119/// If you need more control over how a value is hashed, you can of course
120/// implement the `Hash` trait yourself:
121///
122/// ```
123/// use std::hash::{Hash, Hasher};
124///
125/// struct Person {
126/// id: u32,
127/// name: String,
128/// phone: u64,
129/// }
130///
131/// impl Hash for Person {
132/// fn hash<H: Hasher>(&self, state: &mut H) {
133/// self.id.hash(state);
134/// self.phone.hash(state);
135/// }
136/// }
137/// ```
138///
139/// ## `Hash` and `Eq`
140///
141/// When implementing both `Hash` and [`Eq`], it is important that the following
142/// property holds:
143///
144/// ```text
145/// k1 == k2 -> hash(k1) == hash(k2)
146/// ```
147///
148/// In other words, if two keys are equal, their hashes must also be equal.
149/// [`HashMap`] and [`HashSet`] both rely on this behavior.
150///
151/// Thankfully, you won't need to worry about upholding this property when
152/// deriving both [`Eq`] and `Hash` with `#[derive(PartialEq, Eq, Hash)]`.
153///
154/// Violating this property is a logic error. The behavior resulting from a logic error is not
155/// specified, but users of the trait must ensure that such logic errors do *not* result in
156/// undefined behavior. This means that `unsafe` code **must not** rely on the correctness of these
157/// methods.
158///
159/// ## Prefix collisions
160///
161/// Implementations of `hash` should ensure that the data they
162/// pass to the `Hasher` are prefix-free. That is,
163/// values which are not equal should cause two different sequences of values to be written,
164/// and neither of the two sequences should be a prefix of the other.
165///
166/// For example, the standard implementation of [`Hash` for `&str`][impl] passes an extra
167/// `0xFF` byte to the `Hasher` so that the values `("ab", "c")` and `("a",
168/// "bc")` hash differently.
169///
170/// ## Portability
171///
172/// Due to differences in endianness and type sizes, data fed by `Hash` to a `Hasher`
173/// should not be considered portable across platforms. Additionally the data passed by most
174/// standard library types should not be considered stable between compiler versions.
175///
176/// This means tests shouldn't probe hard-coded hash values or data fed to a `Hasher` and
177/// instead should check consistency with `Eq`.
178///
179/// Serialization formats intended to be portable between platforms or compiler versions should
180/// either avoid encoding hashes or only rely on `Hash` and `Hasher` implementations that
181/// provide additional guarantees.
182///
183/// [`HashMap`]: ../../std/collections/struct.HashMap.html
184/// [`HashSet`]: ../../std/collections/struct.HashSet.html
185/// [`hash`]: Hash::hash
186/// [impl]: ../../std/primitive.str.html#impl-Hash-for-str
187#[stable(feature = "rust1", since = "1.0.0")]
188#[rustc_diagnostic_item = "Hash"]
189pub trait Hash {
190 /// Feeds this value into the given [`Hasher`].
191 ///
192 /// # Examples
193 ///
194 /// ```
195 /// use std::hash::{DefaultHasher, Hash, Hasher};
196 ///
197 /// let mut hasher = DefaultHasher::new();
198 /// 7920.hash(&mut hasher);
199 /// println!("Hash is {:x}!", hasher.finish());
200 /// ```
201 #[stable(feature = "rust1", since = "1.0.0")]
202 fn hash<H: Hasher>(&self, state: &mut H);
203
204 /// Feeds a slice of this type into the given [`Hasher`].
205 ///
206 /// This method is meant as a convenience, but its implementation is
207 /// also explicitly left unspecified. It isn't guaranteed to be
208 /// equivalent to repeated calls of [`hash`] and implementations of
209 /// [`Hash`] should keep that in mind and call [`hash`] themselves
210 /// if the slice isn't treated as a whole unit in the [`PartialEq`]
211 /// implementation.
212 ///
213 /// For example, a [`VecDeque`] implementation might naïvely call
214 /// [`as_slices`] and then [`hash_slice`] on each slice, but this
215 /// is wrong since the two slices can change with a call to
216 /// [`make_contiguous`] without affecting the [`PartialEq`]
217 /// result. Since these slices aren't treated as singular
218 /// units, and instead part of a larger deque, this method cannot
219 /// be used.
220 ///
221 /// # Examples
222 ///
223 /// ```
224 /// use std::hash::{DefaultHasher, Hash, Hasher};
225 ///
226 /// let mut hasher = DefaultHasher::new();
227 /// let numbers = [6, 28, 496, 8128];
228 /// Hash::hash_slice(&numbers, &mut hasher);
229 /// println!("Hash is {:x}!", hasher.finish());
230 /// ```
231 ///
232 /// [`VecDeque`]: ../../std/collections/struct.VecDeque.html
233 /// [`as_slices`]: ../../std/collections/struct.VecDeque.html#method.as_slices
234 /// [`make_contiguous`]: ../../std/collections/struct.VecDeque.html#method.make_contiguous
235 /// [`hash`]: Hash::hash
236 /// [`hash_slice`]: Hash::hash_slice
237 #[stable(feature = "hash_slice", since = "1.3.0")]
238 fn hash_slice<H: Hasher>(data: &[Self], state: &mut H)
239 where
240 Self: Sized,
241 {
242 for piece in data {
243 piece.hash(state)
244 }
245 }
246}
247
248// Separate module to reexport the macro `Hash` from prelude without the trait `Hash`.
249pub(crate) mod macros {
250 /// Derive macro generating an impl of the trait `Hash`.
251 #[rustc_builtin_macro]
252 #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
253 #[allow_internal_unstable(core_intrinsics)]
254 pub macro Hash($item:item) {
255 /* compiler built-in */
256 }
257}
258#[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
259#[doc(inline)]
260pub use macros::Hash;
261
262/// A trait for hashing an arbitrary stream of bytes.
263///
264/// Instances of `Hasher` usually represent state that is changed while hashing
265/// data.
266///
267/// `Hasher` provides a fairly basic interface for retrieving the generated hash
268/// (with [`finish`]), and writing integers as well as slices of bytes into an
269/// instance (with [`write`] and [`write_u8`] etc.). Most of the time, `Hasher`
270/// instances are used in conjunction with the [`Hash`] trait.
271///
272/// This trait provides no guarantees about how the various `write_*` methods are
273/// defined and implementations of [`Hash`] should not assume that they work one
274/// way or another. You cannot assume, for example, that a [`write_u32`] call is
275/// equivalent to four calls of [`write_u8`]. Nor can you assume that adjacent
276/// `write` calls are merged, so it's possible, for example, that
277/// ```
278/// # fn foo(hasher: &mut impl std::hash::Hasher) {
279/// hasher.write(&[1, 2]);
280/// hasher.write(&[3, 4, 5, 6]);
281/// # }
282/// ```
283/// and
284/// ```
285/// # fn foo(hasher: &mut impl std::hash::Hasher) {
286/// hasher.write(&[1, 2, 3, 4]);
287/// hasher.write(&[5, 6]);
288/// # }
289/// ```
290/// end up producing different hashes.
291///
292/// Thus to produce the same hash value, [`Hash`] implementations must ensure
293/// for equivalent items that exactly the same sequence of calls is made -- the
294/// same methods with the same parameters in the same order.
295///
296/// # Examples
297///
298/// ```
299/// use std::hash::{DefaultHasher, Hasher};
300///
301/// let mut hasher = DefaultHasher::new();
302///
303/// hasher.write_u32(1989);
304/// hasher.write_u8(11);
305/// hasher.write_u8(9);
306/// hasher.write(b"Huh?");
307///
308/// println!("Hash is {:x}!", hasher.finish());
309/// ```
310///
311/// [`finish`]: Hasher::finish
312/// [`write`]: Hasher::write
313/// [`write_u8`]: Hasher::write_u8
314/// [`write_u32`]: Hasher::write_u32
315#[stable(feature = "rust1", since = "1.0.0")]
316pub trait Hasher {
317 /// Returns the hash value for the values written so far.
318 ///
319 /// Despite its name, the method does not reset the hasher’s internal
320 /// state. Additional [`write`]s will continue from the current value.
321 /// If you need to start a fresh hash value, you will have to create
322 /// a new hasher.
323 ///
324 /// # Examples
325 ///
326 /// ```
327 /// use std::hash::{DefaultHasher, Hasher};
328 ///
329 /// let mut hasher = DefaultHasher::new();
330 /// hasher.write(b"Cool!");
331 ///
332 /// println!("Hash is {:x}!", hasher.finish());
333 /// ```
334 ///
335 /// [`write`]: Hasher::write
336 #[stable(feature = "rust1", since = "1.0.0")]
337 fn finish(&self) -> u64;
338
339 /// Writes some data into this `Hasher`.
340 ///
341 /// # Examples
342 ///
343 /// ```
344 /// use std::hash::{DefaultHasher, Hasher};
345 ///
346 /// let mut hasher = DefaultHasher::new();
347 /// let data = [0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef];
348 ///
349 /// hasher.write(&data);
350 ///
351 /// println!("Hash is {:x}!", hasher.finish());
352 /// ```
353 ///
354 /// # Note to Implementers
355 ///
356 /// You generally should not do length-prefixing as part of implementing
357 /// this method. It's up to the [`Hash`] implementation to call
358 /// [`Hasher::write_length_prefix`] before sequences that need it.
359 #[stable(feature = "rust1", since = "1.0.0")]
360 fn write(&mut self, bytes: &[u8]);
361
362 /// Writes a single `u8` into this hasher.
363 #[inline]
364 #[stable(feature = "hasher_write", since = "1.3.0")]
365 fn write_u8(&mut self, i: u8) {
366 self.write(&[i])
367 }
368 /// Writes a single `u16` into this hasher.
369 #[inline]
370 #[stable(feature = "hasher_write", since = "1.3.0")]
371 fn write_u16(&mut self, i: u16) {
372 self.write(&i.to_ne_bytes())
373 }
374 /// Writes a single `u32` into this hasher.
375 #[inline]
376 #[stable(feature = "hasher_write", since = "1.3.0")]
377 fn write_u32(&mut self, i: u32) {
378 self.write(&i.to_ne_bytes())
379 }
380 /// Writes a single `u64` into this hasher.
381 #[inline]
382 #[stable(feature = "hasher_write", since = "1.3.0")]
383 fn write_u64(&mut self, i: u64) {
384 self.write(&i.to_ne_bytes())
385 }
386 /// Writes a single `u128` into this hasher.
387 #[inline]
388 #[stable(feature = "i128", since = "1.26.0")]
389 fn write_u128(&mut self, i: u128) {
390 self.write(&i.to_ne_bytes())
391 }
392 /// Writes a single `usize` into this hasher.
393 #[inline]
394 #[stable(feature = "hasher_write", since = "1.3.0")]
395 fn write_usize(&mut self, i: usize) {
396 self.write(&i.to_ne_bytes())
397 }
398
399 /// Writes a single `i8` into this hasher.
400 #[inline]
401 #[stable(feature = "hasher_write", since = "1.3.0")]
402 fn write_i8(&mut self, i: i8) {
403 self.write_u8(i as u8)
404 }
405 /// Writes a single `i16` into this hasher.
406 #[inline]
407 #[stable(feature = "hasher_write", since = "1.3.0")]
408 fn write_i16(&mut self, i: i16) {
409 self.write_u16(i as u16)
410 }
411 /// Writes a single `i32` into this hasher.
412 #[inline]
413 #[stable(feature = "hasher_write", since = "1.3.0")]
414 fn write_i32(&mut self, i: i32) {
415 self.write_u32(i as u32)
416 }
417 /// Writes a single `i64` into this hasher.
418 #[inline]
419 #[stable(feature = "hasher_write", since = "1.3.0")]
420 fn write_i64(&mut self, i: i64) {
421 self.write_u64(i as u64)
422 }
423 /// Writes a single `i128` into this hasher.
424 #[inline]
425 #[stable(feature = "i128", since = "1.26.0")]
426 fn write_i128(&mut self, i: i128) {
427 self.write_u128(i as u128)
428 }
429 /// Writes a single `isize` into this hasher.
430 #[inline]
431 #[stable(feature = "hasher_write", since = "1.3.0")]
432 fn write_isize(&mut self, i: isize) {
433 self.write_usize(i as usize)
434 }
435
436 /// Writes a length prefix into this hasher, as part of being prefix-free.
437 ///
438 /// If you're implementing [`Hash`] for a custom collection, call this before
439 /// writing its contents to this `Hasher`. That way
440 /// `(collection![1, 2, 3], collection![4, 5])` and
441 /// `(collection![1, 2], collection![3, 4, 5])` will provide different
442 /// sequences of values to the `Hasher`
443 ///
444 /// The `impl<T> Hash for [T]` includes a call to this method, so if you're
445 /// hashing a slice (or array or vector) via its `Hash::hash` method,
446 /// you should **not** call this yourself.
447 ///
448 /// This method is only for providing domain separation. If you want to
449 /// hash a `usize` that represents part of the *data*, then it's important
450 /// that you pass it to [`Hasher::write_usize`] instead of to this method.
451 ///
452 /// # Examples
453 ///
454 /// ```
455 /// #![feature(hasher_prefixfree_extras)]
456 /// # // Stubs to make the `impl` below pass the compiler
457 /// # #![allow(non_local_definitions)]
458 /// # struct MyCollection<T>(Option<T>);
459 /// # impl<T> MyCollection<T> {
460 /// # fn len(&self) -> usize { todo!() }
461 /// # }
462 /// # impl<'a, T> IntoIterator for &'a MyCollection<T> {
463 /// # type Item = T;
464 /// # type IntoIter = std::iter::Empty<T>;
465 /// # fn into_iter(self) -> Self::IntoIter { todo!() }
466 /// # }
467 ///
468 /// use std::hash::{Hash, Hasher};
469 /// impl<T: Hash> Hash for MyCollection<T> {
470 /// fn hash<H: Hasher>(&self, state: &mut H) {
471 /// state.write_length_prefix(self.len());
472 /// for elt in self {
473 /// elt.hash(state);
474 /// }
475 /// }
476 /// }
477 /// ```
478 ///
479 /// # Note to Implementers
480 ///
481 /// If you've decided that your `Hasher` is willing to be susceptible to
482 /// Hash-DoS attacks, then you might consider skipping hashing some or all
483 /// of the `len` provided in the name of increased performance.
484 #[inline]
485 #[unstable(feature = "hasher_prefixfree_extras", issue = "96762")]
486 fn write_length_prefix(&mut self, len: usize) {
487 self.write_usize(len);
488 }
489
490 /// Writes a single `str` into this hasher.
491 ///
492 /// If you're implementing [`Hash`], you generally do not need to call this,
493 /// as the `impl Hash for str` does, so you should prefer that instead.
494 ///
495 /// This includes the domain separator for prefix-freedom, so you should
496 /// **not** call `Self::write_length_prefix` before calling this.
497 ///
498 /// # Note to Implementers
499 ///
500 /// There are at least two reasonable default ways to implement this.
501 /// Which one will be the default is not yet decided, so for now
502 /// you probably want to override it specifically.
503 ///
504 /// ## The general answer
505 ///
506 /// It's always correct to implement this with a length prefix:
507 ///
508 /// ```
509 /// # #![feature(hasher_prefixfree_extras)]
510 /// # struct Foo;
511 /// # impl std::hash::Hasher for Foo {
512 /// # fn finish(&self) -> u64 { unimplemented!() }
513 /// # fn write(&mut self, _bytes: &[u8]) { unimplemented!() }
514 /// fn write_str(&mut self, s: &str) {
515 /// self.write_length_prefix(s.len());
516 /// self.write(s.as_bytes());
517 /// }
518 /// # }
519 /// ```
520 ///
521 /// And, if your `Hasher` works in `usize` chunks, this is likely a very
522 /// efficient way to do it, as anything more complicated may well end up
523 /// slower than just running the round with the length.
524 ///
525 /// ## If your `Hasher` works byte-wise
526 ///
527 /// One nice thing about `str` being UTF-8 is that the `b'\xFF'` byte
528 /// never happens. That means that you can append that to the byte stream
529 /// being hashed and maintain prefix-freedom:
530 ///
531 /// ```
532 /// # #![feature(hasher_prefixfree_extras)]
533 /// # struct Foo;
534 /// # impl std::hash::Hasher for Foo {
535 /// # fn finish(&self) -> u64 { unimplemented!() }
536 /// # fn write(&mut self, _bytes: &[u8]) { unimplemented!() }
537 /// fn write_str(&mut self, s: &str) {
538 /// self.write(s.as_bytes());
539 /// self.write_u8(0xff);
540 /// }
541 /// # }
542 /// ```
543 ///
544 /// This does require that your implementation not add extra padding, and
545 /// thus generally requires that you maintain a buffer, running a round
546 /// only once that buffer is full (or `finish` is called).
547 ///
548 /// That's because if `write` pads data out to a fixed chunk size, it's
549 /// likely that it does it in such a way that `"a"` and `"a\x00"` would
550 /// end up hashing the same sequence of things, introducing conflicts.
551 #[inline]
552 #[unstable(feature = "hasher_prefixfree_extras", issue = "96762")]
553 fn write_str(&mut self, s: &str) {
554 self.write(s.as_bytes());
555 self.write_u8(0xff);
556 }
557}
558
559#[stable(feature = "indirect_hasher_impl", since = "1.22.0")]
560impl<H: Hasher + ?Sized> Hasher for &mut H {
561 fn finish(&self) -> u64 {
562 (**self).finish()
563 }
564 fn write(&mut self, bytes: &[u8]) {
565 (**self).write(bytes)
566 }
567 fn write_u8(&mut self, i: u8) {
568 (**self).write_u8(i)
569 }
570 fn write_u16(&mut self, i: u16) {
571 (**self).write_u16(i)
572 }
573 fn write_u32(&mut self, i: u32) {
574 (**self).write_u32(i)
575 }
576 fn write_u64(&mut self, i: u64) {
577 (**self).write_u64(i)
578 }
579 fn write_u128(&mut self, i: u128) {
580 (**self).write_u128(i)
581 }
582 fn write_usize(&mut self, i: usize) {
583 (**self).write_usize(i)
584 }
585 fn write_i8(&mut self, i: i8) {
586 (**self).write_i8(i)
587 }
588 fn write_i16(&mut self, i: i16) {
589 (**self).write_i16(i)
590 }
591 fn write_i32(&mut self, i: i32) {
592 (**self).write_i32(i)
593 }
594 fn write_i64(&mut self, i: i64) {
595 (**self).write_i64(i)
596 }
597 fn write_i128(&mut self, i: i128) {
598 (**self).write_i128(i)
599 }
600 fn write_isize(&mut self, i: isize) {
601 (**self).write_isize(i)
602 }
603 fn write_length_prefix(&mut self, len: usize) {
604 (**self).write_length_prefix(len)
605 }
606 fn write_str(&mut self, s: &str) {
607 (**self).write_str(s)
608 }
609}
610
611/// A trait for creating instances of [`Hasher`].
612///
613/// A `BuildHasher` is typically used (e.g., by [`HashMap`]) to create
614/// [`Hasher`]s for each key such that they are hashed independently of one
615/// another, since [`Hasher`]s contain state.
616///
617/// For each instance of `BuildHasher`, the [`Hasher`]s created by
618/// [`build_hasher`] should be identical. That is, if the same stream of bytes
619/// is fed into each hasher, the same output will also be generated.
620///
621/// # Examples
622///
623/// ```
624/// use std::hash::{BuildHasher, Hasher, RandomState};
625///
626/// let s = RandomState::new();
627/// let mut hasher_1 = s.build_hasher();
628/// let mut hasher_2 = s.build_hasher();
629///
630/// hasher_1.write_u32(8128);
631/// hasher_2.write_u32(8128);
632///
633/// assert_eq!(hasher_1.finish(), hasher_2.finish());
634/// ```
635///
636/// [`build_hasher`]: BuildHasher::build_hasher
637/// [`HashMap`]: ../../std/collections/struct.HashMap.html
638#[stable(since = "1.7.0", feature = "build_hasher")]
639pub trait BuildHasher {
640 /// Type of the hasher that will be created.
641 #[stable(since = "1.7.0", feature = "build_hasher")]
642 type Hasher: Hasher;
643
644 /// Creates a new hasher.
645 ///
646 /// Each call to `build_hasher` on the same instance should produce identical
647 /// [`Hasher`]s.
648 ///
649 /// # Examples
650 ///
651 /// ```
652 /// use std::hash::{BuildHasher, RandomState};
653 ///
654 /// let s = RandomState::new();
655 /// let new_s = s.build_hasher();
656 /// ```
657 #[stable(since = "1.7.0", feature = "build_hasher")]
658 fn build_hasher(&self) -> Self::Hasher;
659
660 /// Calculates the hash of a single value.
661 ///
662 /// This is intended as a convenience for code which *consumes* hashes, such
663 /// as the implementation of a hash table or in unit tests that check
664 /// whether a custom [`Hash`] implementation behaves as expected.
665 ///
666 /// This must not be used in any code which *creates* hashes, such as in an
667 /// implementation of [`Hash`]. The way to create a combined hash of
668 /// multiple values is to call [`Hash::hash`] multiple times using the same
669 /// [`Hasher`], not to call this method repeatedly and combine the results.
670 ///
671 /// # Example
672 ///
673 /// ```
674 /// use std::cmp::{max, min};
675 /// use std::hash::{BuildHasher, Hash, Hasher};
676 /// struct OrderAmbivalentPair<T: Ord>(T, T);
677 /// impl<T: Ord + Hash> Hash for OrderAmbivalentPair<T> {
678 /// fn hash<H: Hasher>(&self, hasher: &mut H) {
679 /// min(&self.0, &self.1).hash(hasher);
680 /// max(&self.0, &self.1).hash(hasher);
681 /// }
682 /// }
683 ///
684 /// // Then later, in a `#[test]` for the type...
685 /// let bh = std::hash::RandomState::new();
686 /// assert_eq!(
687 /// bh.hash_one(OrderAmbivalentPair(1, 2)),
688 /// bh.hash_one(OrderAmbivalentPair(2, 1))
689 /// );
690 /// assert_eq!(
691 /// bh.hash_one(OrderAmbivalentPair(10, 2)),
692 /// bh.hash_one(&OrderAmbivalentPair(2, 10))
693 /// );
694 /// ```
695 #[stable(feature = "build_hasher_simple_hash_one", since = "1.71.0")]
696 fn hash_one<T: Hash>(&self, x: T) -> u64
697 where
698 Self: Sized,
699 Self::Hasher: Hasher,
700 {
701 let mut hasher = self.build_hasher();
702 x.hash(&mut hasher);
703 hasher.finish()
704 }
705}
706
707/// Used to create a default [`BuildHasher`] instance for types that implement
708/// [`Hasher`] and [`Default`].
709///
710/// `BuildHasherDefault<H>` can be used when a type `H` implements [`Hasher`] and
711/// [`Default`], and you need a corresponding [`BuildHasher`] instance, but none is
712/// defined.
713///
714/// Any `BuildHasherDefault` is [zero-sized]. It can be created with
715/// [`default`][method.default]. When using `BuildHasherDefault` with [`HashMap`] or
716/// [`HashSet`], this doesn't need to be done, since they implement appropriate
717/// [`Default`] instances themselves.
718///
719/// # Examples
720///
721/// Using `BuildHasherDefault` to specify a custom [`BuildHasher`] for
722/// [`HashMap`]:
723///
724/// ```
725/// use std::collections::HashMap;
726/// use std::hash::{BuildHasherDefault, Hasher};
727///
728/// #[derive(Default)]
729/// struct MyHasher;
730///
731/// impl Hasher for MyHasher {
732/// fn write(&mut self, bytes: &[u8]) {
733/// // Your hashing algorithm goes here!
734/// unimplemented!()
735/// }
736///
737/// fn finish(&self) -> u64 {
738/// // Your hashing algorithm goes here!
739/// unimplemented!()
740/// }
741/// }
742///
743/// type MyBuildHasher = BuildHasherDefault<MyHasher>;
744///
745/// let hash_map = HashMap::<u32, u32, MyBuildHasher>::default();
746/// ```
747///
748/// [method.default]: BuildHasherDefault::default
749/// [`HashMap`]: ../../std/collections/struct.HashMap.html
750/// [`HashSet`]: ../../std/collections/struct.HashSet.html
751/// [zero-sized]: https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts
752#[stable(since = "1.7.0", feature = "build_hasher")]
753pub struct BuildHasherDefault<H>(marker::PhantomData<fn() -> H>);
754
755impl<H> BuildHasherDefault<H> {
756 /// Creates a new BuildHasherDefault for Hasher `H`.
757 #[unstable(
758 feature = "build_hasher_default_const_new",
759 issue = "123197",
760 reason = "recently added"
761 )]
762 pub const fn new() -> Self {
763 BuildHasherDefault(marker::PhantomData)
764 }
765}
766
767#[stable(since = "1.9.0", feature = "core_impl_debug")]
768impl<H> fmt::Debug for BuildHasherDefault<H> {
769 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
770 f.debug_struct(name:"BuildHasherDefault").finish()
771 }
772}
773
774#[stable(since = "1.7.0", feature = "build_hasher")]
775impl<H: Default + Hasher> BuildHasher for BuildHasherDefault<H> {
776 type Hasher = H;
777
778 fn build_hasher(&self) -> H {
779 H::default()
780 }
781}
782
783#[stable(since = "1.7.0", feature = "build_hasher")]
784impl<H> Clone for BuildHasherDefault<H> {
785 fn clone(&self) -> BuildHasherDefault<H> {
786 BuildHasherDefault(marker::PhantomData)
787 }
788}
789
790#[stable(since = "1.7.0", feature = "build_hasher")]
791impl<H> Default for BuildHasherDefault<H> {
792 fn default() -> BuildHasherDefault<H> {
793 Self::new()
794 }
795}
796
797#[stable(since = "1.29.0", feature = "build_hasher_eq")]
798impl<H> PartialEq for BuildHasherDefault<H> {
799 fn eq(&self, _other: &BuildHasherDefault<H>) -> bool {
800 true
801 }
802}
803
804#[stable(since = "1.29.0", feature = "build_hasher_eq")]
805impl<H> Eq for BuildHasherDefault<H> {}
806
807mod impls {
808 use crate::mem;
809 use crate::slice;
810
811 use super::*;
812
813 macro_rules! impl_write {
814 ($(($ty:ident, $meth:ident),)*) => {$(
815 #[stable(feature = "rust1", since = "1.0.0")]
816 impl Hash for $ty {
817 #[inline]
818 fn hash<H: Hasher>(&self, state: &mut H) {
819 state.$meth(*self)
820 }
821
822 #[inline]
823 fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
824 let newlen = mem::size_of_val(data);
825 let ptr = data.as_ptr() as *const u8;
826 // SAFETY: `ptr` is valid and aligned, as this macro is only used
827 // for numeric primitives which have no padding. The new slice only
828 // spans across `data` and is never mutated, and its total size is the
829 // same as the original `data` so it can't be over `isize::MAX`.
830 state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
831 }
832 }
833 )*}
834 }
835
836 impl_write! {
837 (u8, write_u8),
838 (u16, write_u16),
839 (u32, write_u32),
840 (u64, write_u64),
841 (usize, write_usize),
842 (i8, write_i8),
843 (i16, write_i16),
844 (i32, write_i32),
845 (i64, write_i64),
846 (isize, write_isize),
847 (u128, write_u128),
848 (i128, write_i128),
849 }
850
851 #[stable(feature = "rust1", since = "1.0.0")]
852 impl Hash for bool {
853 #[inline]
854 fn hash<H: Hasher>(&self, state: &mut H) {
855 state.write_u8(*self as u8)
856 }
857 }
858
859 #[stable(feature = "rust1", since = "1.0.0")]
860 impl Hash for char {
861 #[inline]
862 fn hash<H: Hasher>(&self, state: &mut H) {
863 state.write_u32(*self as u32)
864 }
865 }
866
867 #[stable(feature = "rust1", since = "1.0.0")]
868 impl Hash for str {
869 #[inline]
870 fn hash<H: Hasher>(&self, state: &mut H) {
871 state.write_str(self);
872 }
873 }
874
875 #[stable(feature = "never_hash", since = "1.29.0")]
876 impl Hash for ! {
877 #[inline]
878 fn hash<H: Hasher>(&self, _: &mut H) {
879 *self
880 }
881 }
882
883 macro_rules! impl_hash_tuple {
884 () => (
885 #[stable(feature = "rust1", since = "1.0.0")]
886 impl Hash for () {
887 #[inline]
888 fn hash<H: Hasher>(&self, _state: &mut H) {}
889 }
890 );
891
892 ( $($name:ident)+) => (
893 maybe_tuple_doc! {
894 $($name)+ @
895 #[stable(feature = "rust1", since = "1.0.0")]
896 impl<$($name: Hash),+> Hash for ($($name,)+) where last_type!($($name,)+): ?Sized {
897 #[allow(non_snake_case)]
898 #[inline]
899 fn hash<S: Hasher>(&self, state: &mut S) {
900 let ($(ref $name,)+) = *self;
901 $($name.hash(state);)+
902 }
903 }
904 }
905 );
906 }
907
908 macro_rules! maybe_tuple_doc {
909 ($a:ident @ #[$meta:meta] $item:item) => {
910 #[doc(fake_variadic)]
911 #[doc = "This trait is implemented for tuples up to twelve items long."]
912 #[$meta]
913 $item
914 };
915 ($a:ident $($rest_a:ident)+ @ #[$meta:meta] $item:item) => {
916 #[doc(hidden)]
917 #[$meta]
918 $item
919 };
920 }
921
922 macro_rules! last_type {
923 ($a:ident,) => { $a };
924 ($a:ident, $($rest_a:ident,)+) => { last_type!($($rest_a,)+) };
925 }
926
927 impl_hash_tuple! {}
928 impl_hash_tuple! { T }
929 impl_hash_tuple! { T B }
930 impl_hash_tuple! { T B C }
931 impl_hash_tuple! { T B C D }
932 impl_hash_tuple! { T B C D E }
933 impl_hash_tuple! { T B C D E F }
934 impl_hash_tuple! { T B C D E F G }
935 impl_hash_tuple! { T B C D E F G H }
936 impl_hash_tuple! { T B C D E F G H I }
937 impl_hash_tuple! { T B C D E F G H I J }
938 impl_hash_tuple! { T B C D E F G H I J K }
939 impl_hash_tuple! { T B C D E F G H I J K L }
940
941 #[stable(feature = "rust1", since = "1.0.0")]
942 impl<T: Hash> Hash for [T] {
943 #[inline]
944 fn hash<H: Hasher>(&self, state: &mut H) {
945 state.write_length_prefix(self.len());
946 Hash::hash_slice(self, state)
947 }
948 }
949
950 #[stable(feature = "rust1", since = "1.0.0")]
951 impl<T: ?Sized + Hash> Hash for &T {
952 #[inline]
953 fn hash<H: Hasher>(&self, state: &mut H) {
954 (**self).hash(state);
955 }
956 }
957
958 #[stable(feature = "rust1", since = "1.0.0")]
959 impl<T: ?Sized + Hash> Hash for &mut T {
960 #[inline]
961 fn hash<H: Hasher>(&self, state: &mut H) {
962 (**self).hash(state);
963 }
964 }
965
966 #[stable(feature = "rust1", since = "1.0.0")]
967 impl<T: ?Sized> Hash for *const T {
968 #[inline]
969 fn hash<H: Hasher>(&self, state: &mut H) {
970 let (address, metadata) = self.to_raw_parts();
971 state.write_usize(address.addr());
972 metadata.hash(state);
973 }
974 }
975
976 #[stable(feature = "rust1", since = "1.0.0")]
977 impl<T: ?Sized> Hash for *mut T {
978 #[inline]
979 fn hash<H: Hasher>(&self, state: &mut H) {
980 let (address, metadata) = self.to_raw_parts();
981 state.write_usize(address.addr());
982 metadata.hash(state);
983 }
984 }
985}
986