pipa/util/
fxhash.rs

1use std::collections::HashMap;
2use std::hash::{BuildHasherDefault, Hasher};
3
4#[derive(Default)]
5pub struct FxHasher {
6    hash: u64,
7}
8
9impl Hasher for FxHasher {
10    #[inline]
11    fn finish(&self) -> u64 {
12        self.hash
13    }
14
15    #[inline]
16    fn write(&mut self, bytes: &[u8]) {
17        let mut hash = self.hash;
18        let mut i = 0;
19
20        while i + 8 <= bytes.len() {
21            let chunk = u64::from_ne_bytes(bytes[i..i + 8].try_into().unwrap());
22            hash = hash.rotate_left(5) ^ chunk.wrapping_mul(0x517cc1b727220a95);
23            i += 8;
24        }
25
26        if i < bytes.len() {
27            let mut last = 0u64;
28            let mut shift = 0;
29            for &b in &bytes[i..] {
30                last |= (b as u64) << shift;
31                shift += 8;
32            }
33            hash = hash.rotate_left(5) ^ last.wrapping_mul(0x517cc1b727220a95);
34        }
35        self.hash = hash;
36    }
37
38    #[inline]
39    fn write_u8(&mut self, i: u8) {
40        self.write(&[i])
41    }
42
43    #[inline]
44    fn write_u16(&mut self, i: u16) {
45        self.write(&i.to_ne_bytes())
46    }
47
48    #[inline]
49    fn write_u32(&mut self, i: u32) {
50        self.write(&i.to_ne_bytes())
51    }
52
53    #[inline]
54    fn write_u64(&mut self, i: u64) {
55        self.hash = self.hash.rotate_left(5) ^ i.wrapping_mul(0x517cc1b727220a95);
56    }
57
58    #[inline]
59    fn write_usize(&mut self, i: usize) {
60        self.write_u64(i as u64);
61    }
62
63    #[inline]
64    fn write_i8(&mut self, i: i8) {
65        self.write_u8(i as u8)
66    }
67
68    #[inline]
69    fn write_i16(&mut self, i: i16) {
70        self.write_u16(i as u16)
71    }
72
73    #[inline]
74    fn write_i32(&mut self, i: i32) {
75        self.write_u32(i as u32)
76    }
77
78    #[inline]
79    fn write_i64(&mut self, i: i64) {
80        self.write_u64(i as u64)
81    }
82
83    #[inline]
84    fn write_isize(&mut self, i: isize) {
85        self.write_usize(i as usize)
86    }
87}
88
89pub type FxBuildHasher = BuildHasherDefault<FxHasher>;
90
91pub type FxHashMap<K, V> = HashMap<K, V, FxBuildHasher>;
92
93pub type FxHashSet<K> = std::collections::HashSet<K, FxBuildHasher>;
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn test_basic_insert_lookup() {
101        let mut map: FxHashMap<u32, &str> = FxHashMap::default();
102        map.insert(1, "one");
103        map.insert(2, "two");
104        map.insert(42, "answer");
105        assert_eq!(map.get(&1), Some(&"one"));
106        assert_eq!(map.get(&2), Some(&"two"));
107        assert_eq!(map.get(&42), Some(&"answer"));
108        assert_eq!(map.get(&99), None);
109    }
110
111    #[test]
112    fn test_string_keys() {
113        let mut map: FxHashMap<String, u32> = FxHashMap::default();
114        map.insert("hello".to_string(), 1);
115        map.insert("world".to_string(), 2);
116        assert_eq!(map.get("hello"), Some(&1));
117        assert_eq!(map.get("world"), Some(&2));
118    }
119
120    #[test]
121    fn test_tuple_keys() {
122        let mut map: FxHashMap<(u32, u32), &str> = FxHashMap::default();
123        map.insert((1, 2), "a");
124        map.insert((3, 4), "b");
125        assert_eq!(map.get(&(1, 2)), Some(&"a"));
126        assert_eq!(map.get(&(3, 4)), Some(&"b"));
127    }
128
129    #[test]
130    fn test_overwrite() {
131        let mut map: FxHashMap<u32, u32> = FxHashMap::default();
132        map.insert(1, 10);
133        map.insert(1, 20);
134        assert_eq!(map.get(&1), Some(&20));
135    }
136
137    #[test]
138    fn test_remove() {
139        let mut map: FxHashMap<u32, u32> = FxHashMap::default();
140        map.insert(1, 10);
141        map.insert(2, 20);
142        map.remove(&1);
143        assert_eq!(map.get(&1), None);
144        assert_eq!(map.len(), 1);
145    }
146
147    #[test]
148    fn test_large_map() {
149        let mut map: FxHashMap<u64, u64> = FxHashMap::default();
150        for i in 0..10000u64 {
151            map.insert(i, i * 2);
152        }
153        for i in 0..10000u64 {
154            assert_eq!(map.get(&i), Some(&(i * 2)));
155        }
156    }
157}
pipa/util/fxhash.rs

pipa/util/
fxhash.rs
