competitive/data_structure/
fibonacci_hash.rs

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

competitive/data_structure/
fibonacci_hash.rs
