1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10 
11 //! Fast, non-cryptographic hash used by rustc and Firefox.
12 //!
13 //! # Example
14 //!
15 //! ```rust
16 //! # #[cfg(feature = "std")]
17 //! # fn main() {
18 //! use rustc_hash::FxHashMap;
19 //! let mut map: FxHashMap<u32, u32> = FxHashMap::default();
20 //! map.insert(22, 44);
21 //! # }
22 //! # #[cfg(not(feature = "std"))]
23 //! # fn main() { }
24 //! ```
25 
26 #![no_std]
27 
28 #[cfg(feature = "std")]
29 extern crate std;
30 
31 use core::convert::TryInto;
32 use core::default::Default;
33 #[cfg(feature = "std")]
34 use core::hash::BuildHasherDefault;
35 use core::hash::Hasher;
36 use core::mem::size_of;
37 use core::ops::BitXor;
38 #[cfg(feature = "std")]
39 use std::collections::{HashMap, HashSet};
40 
41 /// Type alias for a hashmap using the `fx` hash algorithm.
42 #[cfg(feature = "std")]
43 pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
44 
45 /// Type alias for a hashmap using the `fx` hash algorithm.
46 #[cfg(feature = "std")]
47 pub type FxHashSet<V> = HashSet<V, BuildHasherDefault<FxHasher>>;
48 
49 /// A speedy hash algorithm for use within rustc. The hashmap in liballoc
50 /// by default uses SipHash which isn't quite as speedy as we want. In the
51 /// compiler we're not really worried about DOS attempts, so we use a fast
52 /// non-cryptographic hash.
53 ///
54 /// This is the same as the algorithm used by Firefox -- which is a homespun
55 /// one not based on any widely-known algorithm -- though modified to produce
56 /// 64-bit hash values instead of 32-bit hash values. It consistently
57 /// out-performs an FNV-based hash within rustc itself -- the collision rate is
58 /// similar or slightly worse than FNV, but the speed of the hash function
59 /// itself is much higher because it works on up to 8 bytes at a time.
60 pub struct FxHasher {
61     hash: usize,
62 }
63 
64 #[cfg(target_pointer_width = "32")]
65 const K: usize = 0x9e3779b9;
66 #[cfg(target_pointer_width = "64")]
67 const K: usize = 0x517cc1b727220a95;
68 
69 impl Default for FxHasher {
70     #[inline]
default() -> FxHasher71     fn default() -> FxHasher {
72         FxHasher { hash: 0 }
73     }
74 }
75 
76 impl FxHasher {
77     #[inline]
add_to_hash(&mut self, i: usize)78     fn add_to_hash(&mut self, i: usize) {
79         self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(K);
80     }
81 }
82 
83 impl Hasher for FxHasher {
84     #[inline]
write(&mut self, mut bytes: &[u8])85     fn write(&mut self, mut bytes: &[u8]) {
86         #[cfg(target_pointer_width = "32")]
87         let read_usize = |bytes: &[u8]| u32::from_ne_bytes(bytes[..4].try_into().unwrap());
88         #[cfg(target_pointer_width = "64")]
89         let read_usize = |bytes: &[u8]| u64::from_ne_bytes(bytes[..8].try_into().unwrap());
90 
91         let mut hash = FxHasher { hash: self.hash };
92         assert!(size_of::<usize>() <= 8);
93         while bytes.len() >= size_of::<usize>() {
94             hash.add_to_hash(read_usize(bytes) as usize);
95             bytes = &bytes[size_of::<usize>()..];
96         }
97         if (size_of::<usize>() > 4) && (bytes.len() >= 4) {
98             hash.add_to_hash(u32::from_ne_bytes(bytes[..4].try_into().unwrap()) as usize);
99             bytes = &bytes[4..];
100         }
101         if (size_of::<usize>() > 2) && bytes.len() >= 2 {
102             hash.add_to_hash(u16::from_ne_bytes(bytes[..2].try_into().unwrap()) as usize);
103             bytes = &bytes[2..];
104         }
105         if (size_of::<usize>() > 1) && bytes.len() >= 1 {
106             hash.add_to_hash(bytes[0] as usize);
107         }
108         self.hash = hash.hash;
109     }
110 
111     #[inline]
write_u8(&mut self, i: u8)112     fn write_u8(&mut self, i: u8) {
113         self.add_to_hash(i as usize);
114     }
115 
116     #[inline]
write_u16(&mut self, i: u16)117     fn write_u16(&mut self, i: u16) {
118         self.add_to_hash(i as usize);
119     }
120 
121     #[inline]
write_u32(&mut self, i: u32)122     fn write_u32(&mut self, i: u32) {
123         self.add_to_hash(i as usize);
124     }
125 
126     #[cfg(target_pointer_width = "32")]
127     #[inline]
write_u64(&mut self, i: u64)128     fn write_u64(&mut self, i: u64) {
129         self.add_to_hash(i as usize);
130         self.add_to_hash((i >> 32) as usize);
131     }
132 
133     #[cfg(target_pointer_width = "64")]
134     #[inline]
write_u64(&mut self, i: u64)135     fn write_u64(&mut self, i: u64) {
136         self.add_to_hash(i as usize);
137     }
138 
139     #[inline]
write_usize(&mut self, i: usize)140     fn write_usize(&mut self, i: usize) {
141         self.add_to_hash(i);
142     }
143 
144     #[inline]
finish(&self) -> u64145     fn finish(&self) -> u64 {
146         self.hash as u64
147     }
148 }
149