competitive_library/other/
zobrist_hash.rs

1//! Zobrist Hash
2use super::xorshift::XorShift;
3use std::collections::HashSet;
4
5#[derive(Clone, Default)]
6pub struct ZobristHash<T: Eq + std::hash::Hash + Copy> {
7    map: std::collections::HashMap<T, u64>,
8    rand: XorShift<u64>,
9}
10
11impl<T: Eq + std::hash::Hash + Copy> ZobristHash<T> {
12    pub fn new() -> Self {
13        Self {
14            map: std::collections::HashMap::<T, u64>::new(),
15            rand: XorShift::<u64>::new(),
16        }
17    }
18    #[allow(clippy::or_fun_call)]
19    pub fn hash(&mut self, hash: u64, add: T) -> u64 {
20        hash ^ *self.map.entry(add).or_insert(self.rand.next().unwrap())
21    }
22    pub fn hash_vec_from_vec(&mut self, v: &[T]) -> Vec<u64> {
23        let mut set = std::collections::HashSet::new();
24        let mut ret = vec![];
25
26        let mut hash = 0;
27        for &value in v.iter() {
28            if !set.contains(&value) {
29                set.insert(value);
30                hash = self.hash(hash, value);
31            }
32            ret.push(hash);
33        }
34        ret
35    }
36    pub fn hash_from_set(&mut self, set: &HashSet<T>) -> u64 {
37        set.iter()
38            .scan(0, |s, &x| {
39                *s = self.hash(*s, x);
40                Some(*s)
41            })
42            .last()
43            .unwrap()
44    }
45}
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50    use std::collections::HashSet;
51    #[test]
52    fn test() {
53        let mut zh = ZobristHash::new();
54        let v = vec![1, 2, 3, 4, 5];
55        let hash_vec = zh.hash_vec_from_vec(&v);
56
57        assert_eq!(hash_vec.len(), 5);
58        assert_eq!(hash_vec[0], zh.hash_from_set(&to_set(1, &v)));
59        assert_eq!(hash_vec[1], zh.hash_from_set(&to_set(2, &v)));
60        assert_eq!(hash_vec[2], zh.hash_from_set(&to_set(3, &v)));
61        assert_eq!(hash_vec[3], zh.hash_from_set(&to_set(4, &v)));
62        assert_eq!(hash_vec[4], zh.hash_from_set(&to_set(5, &v)));
63    }
64    fn to_set(n: usize, v: &[i32]) -> HashSet<i32> {
65        v.iter().cloned().take(n).collect::<HashSet<_>>()
66    }
67    #[test]
68    fn rand() {
69        let mut rand = XorShift::<u64>::new();
70
71        let v = (0..10000).map(|_| rand.next().unwrap()).collect::<Vec<_>>();
72        let mut vv = v.clone();
73        vv.sort_unstable();
74        let mut zh = ZobristHash::new();
75        assert_eq!(
76            zh.hash_from_set(&v.into_iter().collect::<HashSet::<_>>()),
77            zh.hash_from_set(&vv.into_iter().collect::<HashSet::<_>>())
78        );
79    }
80}
competitive_library/other/zobrist_hash.rs

competitive_library/other/
zobrist_hash.rs
