rustc_hash/
lib.rs

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
21extern crate byteorder;
22
23use std::collections::{HashMap, HashSet};
24use std::default::Default;
25use std::hash::{Hasher, BuildHasherDefault};
26use std::ops::BitXor;
27use std::mem::size_of;
28
29use byteorder::{ByteOrder, NativeEndian};
30
31/// Type alias for a hashmap using the `fx` hash algorithm.
32pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
33
34/// Type alias for a hashmap using the `fx` hash algorithm.
35pub 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.
48pub struct FxHasher {
49    hash: usize
50}
51
52#[cfg(target_pointer_width = "32")]
53const K: usize = 0x9e3779b9;
54#[cfg(target_pointer_width = "64")]
55const K: usize = 0x517cc1b727220a95;
56
57impl Default for FxHasher {
58    #[inline]
59    fn default() -> FxHasher {
60        FxHasher { hash: 0 }
61    }
62}
63
64impl FxHasher {
65    #[inline]
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
71impl Hasher for FxHasher {
72    #[inline]
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]
100    fn write_u8(&mut self, i: u8) {
101        self.add_to_hash(i as usize);
102    }
103
104    #[inline]
105    fn write_u16(&mut self, i: u16) {
106        self.add_to_hash(i as usize);
107    }
108
109    #[inline]
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]
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]
123    fn write_u64(&mut self, i: u64) {
124        self.add_to_hash(i as usize);
125    }
126
127    #[inline]
128    fn write_usize(&mut self, i: usize) {
129        self.add_to_hash(i);
130    }
131
132    #[inline]
133    fn finish(&self) -> u64 {
134        self.hash as u64
135    }
136}
rustc_hash/lib.rs

rustc_hash/
lib.rs
