competitive/data_structure/
fibonacci_hash.rs

1use std::{
2    collections::{HashMap, HashSet},
3    hash::{BuildHasherDefault, Hasher},
4};
5
6#[cfg(target_pointer_width = "32")]
7pub type FibonacciHasher = FibonacciHasheru32;
8#[cfg(not(target_pointer_width = "32"))]
9pub type FibonacciHasher = FibonacciHasheru64;
10pub type FibHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FibonacciHasher>>;
11pub type FibHashSet<V> = HashSet<V, BuildHasherDefault<FibonacciHasher>>;
12
13#[derive(Debug, Default)]
14pub struct FibonacciHasheru32 {
15    hash: u32,
16}
17impl FibonacciHasheru32 {
18    const A: u32 = 2654435769;
19    const B: u32 = 5;
20    fn push(&mut self, x: u32) {
21        self.hash = (self.hash.rotate_right(Self::B) ^ x).wrapping_mul(Self::A);
22    }
23}
24impl Hasher for FibonacciHasheru32 {
25    fn finish(&self) -> u64 {
26        self.hash as u64
27    }
28    fn write(&mut self, mut bytes: &[u8]) {
29        if bytes.len() % 4 >= 2 {
30            let (chunk, rest) = bytes.split_first_chunk::<2>().unwrap();
31            self.push(u16::from_ne_bytes(*chunk) as u32);
32            bytes = rest;
33        }
34        if bytes.len() % 2 >= 1 {
35            let (chunk, rest) = bytes.split_first_chunk::<1>().unwrap();
36            self.push(u8::from_ne_bytes(*chunk) as u32);
37            bytes = rest;
38        }
39        for chunk in bytes.as_chunks::<4>().0 {
40            self.push(u32::from_ne_bytes(*chunk));
41        }
42    }
43    fn write_u8(&mut self, i: u8) {
44        self.push(i as u32)
45    }
46    fn write_u16(&mut self, i: u16) {
47        self.push(i as u32)
48    }
49    fn write_u32(&mut self, i: u32) {
50        self.push(i)
51    }
52    fn write_u64(&mut self, i: u64) {
53        self.push(i as u32);
54        self.push((i >> 32) as u32);
55    }
56    fn write_u128(&mut self, i: u128) {
57        self.push(i as u32);
58        self.push((i >> 32) as u32);
59        self.push((i >> 64) as u32);
60        self.push((i >> 96) as u32);
61    }
62    #[cfg(target_pointer_width = "32")]
63    fn write_usize(&mut self, i: usize) {
64        self.write_u32(i as u32)
65    }
66    #[cfg(target_pointer_width = "64")]
67    fn write_usize(&mut self, i: usize) {
68        self.write_u64(i as u64)
69    }
70    fn write_i8(&mut self, i: i8) {
71        self.write_u8(i as u8)
72    }
73    fn write_i16(&mut self, i: i16) {
74        self.write_u16(i as u16)
75    }
76    fn write_i32(&mut self, i: i32) {
77        self.write_u32(i as u32)
78    }
79    fn write_i64(&mut self, i: i64) {
80        self.write_u64(i as u64)
81    }
82    fn write_i128(&mut self, i: i128) {
83        self.write_u128(i as u128)
84    }
85    fn write_isize(&mut self, i: isize) {
86        self.write_usize(i as usize)
87    }
88}
89
90#[derive(Debug, Default)]
91pub struct FibonacciHasheru64 {
92    hash: u64,
93}
94impl FibonacciHasheru64 {
95    const A: u64 = 11400714819323198485;
96    const B: u32 = 5;
97    fn push(&mut self, x: u64) {
98        self.hash = (self.hash.rotate_right(Self::B) ^ x).wrapping_mul(Self::A);
99    }
100}
101impl Hasher for FibonacciHasheru64 {
102    fn finish(&self) -> u64 {
103        self.hash
104    }
105    fn write(&mut self, mut bytes: &[u8]) {
106        if bytes.len() % 8 >= 4 {
107            let (chunk, rest) = bytes.split_first_chunk::<4>().unwrap();
108            self.push(u32::from_ne_bytes(*chunk) as u64);
109            bytes = rest;
110        }
111        if bytes.len() % 4 >= 2 {
112            let (chunk, rest) = bytes.split_first_chunk::<2>().unwrap();
113            self.push(u16::from_ne_bytes(*chunk) as u64);
114            bytes = rest;
115        }
116        if bytes.len() % 2 >= 1 {
117            let (chunk, rest) = bytes.split_first_chunk::<1>().unwrap();
118            self.push(u8::from_ne_bytes(*chunk) as u64);
119            bytes = rest;
120        }
121        for chunk in bytes.as_chunks::<8>().0 {
122            self.push(u64::from_ne_bytes(*chunk));
123        }
124    }
125    fn write_u8(&mut self, i: u8) {
126        self.push(i as u64)
127    }
128    fn write_u16(&mut self, i: u16) {
129        self.push(i as u64)
130    }
131    fn write_u32(&mut self, i: u32) {
132        self.push(i as u64)
133    }
134    fn write_u64(&mut self, i: u64) {
135        self.push(i);
136    }
137    fn write_u128(&mut self, i: u128) {
138        self.push(i as u64);
139        self.push((i >> 64) as u64);
140    }
141    fn write_usize(&mut self, i: usize) {
142        self.write_u64(i as u64)
143    }
144    fn write_i8(&mut self, i: i8) {
145        self.write_u8(i as u8)
146    }
147    fn write_i16(&mut self, i: i16) {
148        self.write_u16(i as u16)
149    }
150    fn write_i32(&mut self, i: i32) {
151        self.write_u32(i as u32)
152    }
153    fn write_i64(&mut self, i: i64) {
154        self.write_u64(i as u64)
155    }
156    fn write_i128(&mut self, i: i128) {
157        self.write_u128(i as u128)
158    }
159    fn write_isize(&mut self, i: isize) {
160        self.write_usize(i as usize)
161    }
162}
163
164#[cfg(test)]
165mod tests {
166    use super::*;
167    use crate::tools::Xorshift;
168    use std::collections::BTreeSet;
169
170    #[test]
171    fn test_hash_slice() {
172        const Q: usize = 50_000;
173
174        let mut rng = Xorshift::default();
175        let mut fh = FibHashSet::default();
176        let mut rh = HashSet::new();
177        for _ in 0..Q {
178            let n = rng.random(0..20);
179            let a: Vec<_> = rng
180                .random_iter(0u64..)
181                .take(n)
182                .map(|x| (x, x.to_string()))
183                .collect();
184            fh.insert(a.to_vec());
185            rh.insert(a.to_vec());
186        }
187
188        let fh = fh.into_iter().collect::<BTreeSet<_>>();
189        let rh = rh.into_iter().collect::<BTreeSet<_>>();
190        assert_eq!(fh, rh);
191    }
192}
competitive/data_structure/fibonacci_hash.rs

competitive/data_structure/
fibonacci_hash.rs
