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