prust_lib/
hashmap.rs

1use std::{
2    collections::hash_map::DefaultHasher,
3    fmt::Debug,
4    hash::{Hash, Hasher},
5    marker::PhantomData,
6};
7
8use crate::trie::Trie;
9
10#[derive(Clone)]
11pub struct HashMap<K: PartialEq, V = ()> {
12    trie: Trie<bool, KeyValue<K, V>>,
13    phantom: PhantomData<K>,
14}
15
16pub type HashSet<K> = HashMap<K, ()>;
17
18#[derive(Clone, Debug)]
19struct KeyValue<K, V> {
20    key: K,
21    value: Option<V>,
22}
23
24impl<K: PartialEq, V> PartialEq for KeyValue<K, V> {
25    fn eq(&self, other: &Self) -> bool {
26        self.key == other.key
27    }
28}
29
30pub fn empty<K: PartialEq, V>() -> HashMap<K, V> {
31    HashMap {
32        trie: Trie::empty_store(),
33        phantom: PhantomData,
34    }
35}
36
37impl<K: Hash + PartialEq> HashMap<K> {
38    pub fn insert(&self, value: K) -> Self {
39        self.put(value, ())
40    }
41    pub fn search(&self, value: &K) -> bool {
42        self.get(value).is_some()
43    }
44}
45
46impl<K: Hash + PartialEq, V> HashMap<K, V> {
47    pub fn put(&self, key: K, value: V) -> Self {
48        Self {
49            trie: self.trie.insert_store(
50                Self::get_bits(&key),
51                KeyValue {
52                    key,
53                    value: Some(value),
54                },
55            ),
56            phantom: PhantomData,
57        }
58    }
59
60    pub fn get(&self, k: &K) -> Option<&V> {
61        let store = self.trie.get_store(Self::get_bits(k))?;
62        let store_cloned: Vec<_> = (*store).to_vec();
63        store_cloned
64            .iter()
65            .find(|KeyValue { key, .. }| k == key)
66            .and_then(|kv| kv.value.as_ref())
67    }
68
69    pub fn delete(&self, key: K) -> Option<Self> {
70        self.trie
71            .delete_store(Self::get_bits(&key), &KeyValue { key, value: None })
72            .map(|trie| HashMap {
73                trie,
74                phantom: PhantomData,
75            })
76    }
77
78    fn get_bits(key: &K) -> Vec<bool> {
79        let mut s = DefaultHasher::new();
80        key.hash(&mut s);
81        let hash = s.finish();
82        (0..64).map(|i| hash & (1u64 << i) > 0).collect()
83    }
84}
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89
90    #[test]
91    fn insert_and_retrieve_values_set() {
92        let m1 = empty();
93        let m2 = m1.insert(1238).insert(-1).insert(1238);
94        assert!(m2.search(&1238));
95        assert!(!m1.search(&-1));
96        assert!(!m2.delete(1238).unwrap().search(&1238))
97    }
98
99    #[test]
100    fn insert_and_retrieve_values() {
101        let m1 = empty();
102        let m2 = m1.put(1238, 1).put(-1, 10);
103        assert_eq!(m2.get(&1238), Some(&1));
104        assert_eq!(m1.get(&-1), None);
105    }
106
107    #[test]
108    fn handle_hash_collisions() {
109        #[derive(PartialEq, Clone)]
110        struct K {
111            x: i8,
112        }
113
114        impl Hash for K {
115            fn hash<H: Hasher>(&self, _: &mut H) {}
116        }
117
118        let m = empty().put(K { x: 1 }, 1).put(K { x: -1 }, 10);
119        assert_eq!(m.get(&K { x: 1 }), Some(&1));
120        assert_eq!(m.get(&K { x: -1 }), Some(&10));
121    }
122
123    #[test]
124    fn delete_entries() {
125        #[derive(PartialEq, Clone)]
126        struct K {
127            x: i8,
128        }
129
130        impl Hash for K {
131            fn hash<H: Hasher>(&self, _: &mut H) {}
132        }
133
134        let m = empty()
135            .put(K { x: 1 }, 1)
136            .put(K { x: -1 }, 10)
137            .delete(K { x: 1 });
138        assert!(m.is_some());
139        let m2 = m.unwrap();
140        assert_eq!(m2.get(&K { x: 1 }), None);
141        assert_eq!(m2.get(&K { x: -1 }), Some(&10));
142    }
143}
prust_lib/hashmap.rs

prust_lib/
hashmap.rs
