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 //! use rustc_hash::FxHashMap;
17 //! let mut map: FxHashMap<u32, u32> = FxHashMap::default();
18 //! map.insert(22, 44);
19 //! ```
20 
21 extern crate byteorder;
22 
23 use std::collections::{HashMap, HashSet};
24 use std::default::Default;
25 use std::hash::{Hasher, BuildHasherDefault};
26 use std::ops::BitXor;
27 use std::mem::size_of;
28 
29 use byteorder::{ByteOrder, NativeEndian};
30 
31 /// Type alias for a hashmap using the `fx` hash algorithm.
32 pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
33 
34 /// Type alias for a hashmap using the `fx` hash algorithm.
35 pub type FxHashSet<V> = HashSet<V, BuildHasherDefault<FxHasher>>;
36 
37 /// A speedy hash algorithm for use within rustc. The hashmap in liballoc
38 /// by default uses SipHash which isn't quite as speedy as we want. In the
39 /// compiler we're not really worried about DOS attempts, so we use a fast
40 /// non-cryptographic hash.
41 ///
42 /// This is the same as the algorithm used by Firefox -- which is a homespun
43 /// one not based on any widely-known algorithm -- though modified to produce
44 /// 64-bit hash values instead of 32-bit hash values. It consistently
45 /// out-performs an FNV-based hash within rustc itself -- the collision rate is
46 /// similar or slightly worse than FNV, but the speed of the hash function
47 /// itself is much higher because it works on up to 8 bytes at a time.
48 pub struct FxHasher {
49     hash: usize
50 }
51 
52 #[cfg(target_pointer_width = "32")]
53 const K: usize = 0x9e3779b9;
54 #[cfg(target_pointer_width = "64")]
55 const K: usize = 0x517cc1b727220a95;
56 
57 impl Default for FxHasher {
58     #[inline]
default() -> FxHasher59     fn default() -> FxHasher {
60         FxHasher { hash: 0 }
61     }
62 }
63 
64 impl FxHasher {
65     #[inline]
add_to_hash(&mut self, i: usize)66     fn add_to_hash(&mut self, i: usize) {
67         self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(K);
68     }
69 }
70 
71 impl Hasher for FxHasher {
72     #[inline]
write(&mut self, mut bytes: &[u8])73     fn write(&mut self, mut bytes: &[u8]) {
74         #[cfg(target_pointer_width = "32")]
75         let read_usize = |bytes| NativeEndian::read_u32(bytes);
76         #[cfg(target_pointer_width = "64")]
77         let read_usize = |bytes| NativeEndian::read_u64(bytes);
78 
79         let mut hash = FxHasher { hash: self.hash };
80         assert!(size_of::<usize>() <= 8);
81         while bytes.len() >= size_of::<usize>() {
82             hash.add_to_hash(read_usize(bytes) as usize);
83             bytes = &bytes[size_of::<usize>()..];
84         }
85         if (size_of::<usize>() > 4) && (bytes.len() >= 4) {
86             hash.add_to_hash(NativeEndian::read_u32(bytes) as usize);
87             bytes = &bytes[4..];
88         }
89         if (size_of::<usize>() > 2) && bytes.len() >= 2 {
90             hash.add_to_hash(NativeEndian::read_u16(bytes) as usize);
91             bytes = &bytes[2..];
92         }
93         if (size_of::<usize>() > 1) && bytes.len() >= 1 {
94             hash.add_to_hash(bytes[0] as usize);
95         }
96         self.hash = hash.hash;
97     }
98 
99     #[inline]
write_u8(&mut self, i: u8)100     fn write_u8(&mut self, i: u8) {
101         self.add_to_hash(i as usize);
102     }
103 
104     #[inline]
write_u16(&mut self, i: u16)105     fn write_u16(&mut self, i: u16) {
106         self.add_to_hash(i as usize);
107     }
108 
109     #[inline]
write_u32(&mut self, i: u32)110     fn write_u32(&mut self, i: u32) {
111         self.add_to_hash(i as usize);
112     }
113 
114     #[cfg(target_pointer_width = "32")]
115     #[inline]
write_u64(&mut self, i: u64)116     fn write_u64(&mut self, i: u64) {
117         self.add_to_hash(i as usize);
118         self.add_to_hash((i >> 32) as usize);
119     }
120 
121     #[cfg(target_pointer_width = "64")]
122     #[inline]
write_u64(&mut self, i: u64)123     fn write_u64(&mut self, i: u64) {
124         self.add_to_hash(i as usize);
125     }
126 
127     #[inline]
write_usize(&mut self, i: usize)128     fn write_usize(&mut self, i: usize) {
129         self.add_to_hash(i);
130     }
131 
132     #[inline]
finish(&self) -> u64133     fn finish(&self) -> u64 {
134         self.hash as u64
135     }
136 }
137