nekolib/ds/
cuckoo_hash_map.rs

1//! Cuckoo hashing による連想配列。
2
3use std::collections::hash_map::RandomState;
4use std::fmt::Debug;
5use std::hash::{BuildHasher, Hash, Hasher};
6use std::iter::FromIterator;
7
8/// Cuckoo hashing による連想配列。
9///
10/// # Idea
11/// `todo!()`
12///
13/// # References
14/// - <http://web.stanford.edu/class/cs166/lectures/07/Slides07.pdf>
15#[derive(Clone, Debug)]
16pub struct CuckooHashMap<K, V> {
17    rs: [RandomState; 2],
18    buf: [Vec<Vec<(K, V)>>; 2],
19    len: usize,
20}
21
22const LOOP_THRESHOLD: usize = 8;
23const LEN_THRESHOLD: usize = 32;
24
25impl<K: Eq + Hash, V> CuckooHashMap<K, V> {
26    pub fn new() -> Self {
27        let r0 = RandomState::new();
28        let r1 = RandomState::new();
29        Self {
30            rs: [r0, r1],
31            buf: [vec![vec![]], vec![vec![]]],
32            len: 0,
33        }
34    }
35
36    pub fn contains_key(&self, key: &K) -> bool { self.find(key).is_some() }
37
38    pub fn insert(&mut self, key: K, val: V) -> Option<V> {
39        if let Some((i, j, k)) = self.find(&key) {
40            let old = std::mem::replace(&mut self.buf[i][j][k].1, val);
41            return Some(old);
42        }
43
44        if let Some(elts) = self.try_insert((key, val), LOOP_THRESHOLD) {
45            self.rehash(elts);
46        }
47        self.len += 1;
48        None
49    }
50
51    pub fn remove(&mut self, key: &K) -> Option<V> {
52        self.find(key).map(|(i, j, k)| {
53            self.len -= 1;
54            self.buf[i][j].swap_remove(k).1
55        })
56    }
57
58    pub fn len(&self) -> usize { self.len }
59    pub fn is_empty(&self) -> bool { self.len == 0 }
60
61    fn try_insert(
62        &mut self,
63        mut keyval: (K, V),
64        thresh: usize,
65    ) -> Option<Vec<(K, V)>> {
66        for _ in 0..thresh {
67            for i in 0..=1 {
68                let j = self.get_hash(&keyval.0, i);
69                if self.buf[i][j].len() < LEN_THRESHOLD {
70                    self.buf[i][j].push(keyval);
71                    return None;
72                }
73                std::mem::swap(&mut keyval, self.buf[i][j].last_mut().unwrap());
74            }
75        }
76
77        let mut elts = vec![keyval];
78        elts.extend(self.buf[0].drain(..).flatten());
79        elts.extend(self.buf[1].drain(..).flatten());
80        Some(elts)
81    }
82
83    fn rehash(&mut self, mut elts: Vec<(K, V)>) {
84        let len = Self::calc_len(elts.len());
85
86        'outer: loop {
87            for i in 0..=1 {
88                self.buf[i] = (0..len).map(|_| vec![]).collect();
89                self.rs[i] = RandomState::new();
90            }
91            while let Some((k, v)) = elts.pop() {
92                if let Some(tmp) = self.try_insert((k, v), LOOP_THRESHOLD) {
93                    elts.extend(tmp);
94                    continue 'outer;
95                }
96            }
97            return;
98        }
99    }
100
101    fn calc_len(n: usize) -> usize { n }
102
103    fn find(&self, key: &K) -> Option<(usize, usize, usize)> {
104        (0..=1).find_map(|i| {
105            let j = self.get_hash(key, i);
106            self.buf[i][j]
107                .iter()
108                .enumerate()
109                .find(|(_, (key0, _))| key0 == key)
110                .map(|(k, _)| (i, j, k))
111        })
112    }
113
114    fn get_hash(&self, key: &K, i: usize) -> usize {
115        let mut h = self.rs[i].build_hasher();
116        key.hash(&mut h);
117        h.finish() as usize % self.buf[i].len()
118    }
119}
120
121impl<K: Eq + Hash, V> FromIterator<(K, V)> for CuckooHashMap<K, V> {
122    fn from_iter<I>(iter: I) -> Self
123    where
124        I: IntoIterator<Item = (K, V)>,
125    {
126        let mut res = CuckooHashMap::new();
127        for (k, v) in iter {
128            res.insert(k, v);
129        }
130        res
131    }
132}
133
134impl<K: Eq + Hash, V> Extend<(K, V)> for CuckooHashMap<K, V> {
135    fn extend<I>(&mut self, iter: I)
136    where
137        I: IntoIterator<Item = (K, V)>,
138    {
139        for (k, v) in iter {
140            self.insert(k, v);
141        }
142    }
143}
nekolib/ds/cuckoo_hash_map.rs

nekolib/ds/
cuckoo_hash_map.rs
