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