zerovec/hashmap/
mod.rs

1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5use crate::map::{MutableZeroVecLike, ZeroMapKV, ZeroVecLike};
6use crate::ZeroVec;
7use alloc::vec::Vec;
8use core::borrow::Borrow;
9use core::hash::Hash;
10
11pub mod algorithms;
12use algorithms::*;
13
14#[cfg(feature = "serde")]
15mod serde;
16
17/// A perfect zerohashmap optimized for lookups over immutable keys.
18///
19/// # Examples
20/// ```
21/// use zerovec::ZeroHashMap;
22///
23/// let hashmap =
24///     ZeroHashMap::<i32, str>::from_iter([(0, "a"), (1, "b"), (2, "c")]);
25/// assert_eq!(hashmap.get(&0), Some("a"));
26/// assert_eq!(hashmap.get(&2), Some("c"));
27/// assert_eq!(hashmap.get(&4), None);
28/// ```
29#[derive(Debug)]
30pub struct ZeroHashMap<'a, K, V>
31where
32    K: ZeroMapKV<'a> + ?Sized,
33    V: ZeroMapKV<'a> + ?Sized,
34{
35    /// Array of (d0, d1) which splits the keys with same first level hash into distinct
36    /// slots.
37    /// The ith index of the array splits the keys with first level hash i.
38    /// If no key with first level hash is found in the original keys, (0, 0) is used as an empty
39    /// placeholder.
40    displacements: ZeroVec<'a, (u32, u32)>,
41    keys: K::Container,
42    values: V::Container,
43}
44
45impl<'a, K, V> ZeroHashMap<'a, K, V>
46where
47    K: ZeroMapKV<'a> + ?Sized,
48    V: ZeroMapKV<'a> + ?Sized,
49{
50    /// The number of elements in the [`ZeroHashMap`].
51    pub fn len(&self) -> usize {
52        self.values.zvl_len()
53    }
54
55    /// Whether the [`ZeroHashMap`] is empty.
56    pub fn is_empty(&self) -> bool {
57        self.len() == 0
58    }
59}
60
61impl<'a, K, V> ZeroHashMap<'a, K, V>
62where
63    K: ZeroMapKV<'a> + ?Sized + Hash + Eq,
64    V: ZeroMapKV<'a> + ?Sized,
65{
66    /// Given a `key` return the index for the key or [`None`] if the key is absent.
67    fn index<A>(&self, key: &A) -> Option<usize>
68    where
69        A: Borrow<K> + ?Sized,
70    {
71        let hash = compute_hash(key.borrow());
72        let (g, f0, f1) = split_hash64(hash, self.len());
73
74        #[expect(clippy::unwrap_used)] // g is in-range
75        let (d0, d1) = self.displacements.get(g).unwrap();
76        let index = compute_index((f0, f1), (d0, d1), self.displacements.len() as u32)?;
77
78        #[expect(clippy::unwrap_used)] // index is in 0..self.keys.len()
79        let found = self.keys.zvl_get(index).unwrap();
80        if K::Container::zvl_get_as_t(found, |found| found == key.borrow()) {
81            Some(index)
82        } else {
83            None
84        }
85    }
86
87    /// Get the value corresponding to `key`.
88    /// If absent [`None`] is returned.
89    ///
90    /// # Example
91    /// ```
92    /// use zerovec::ZeroHashMap;
93    ///
94    /// let hashmap = ZeroHashMap::<str, str>::from_iter([("a", "A"), ("z", "Z")]);
95    ///
96    /// assert_eq!(hashmap.get("a"), Some("A"));
97    /// assert_eq!(hashmap.get("z"), Some("Z"));
98    /// assert_eq!(hashmap.get("0"), None);
99    /// ```
100    pub fn get<'b, A>(&'b self, key: &A) -> Option<&'b V::GetType>
101    where
102        A: Borrow<K> + ?Sized + 'b,
103    {
104        self.index(key).and_then(|i| self.values.zvl_get(i))
105    }
106
107    /// Returns whether `key` is contained in this hashmap
108    ///
109    /// # Example
110    /// ```rust
111    /// use zerovec::ZeroHashMap;
112    ///
113    /// let hashmap = ZeroHashMap::<str, str>::from_iter([("a", "A"), ("z", "Z")]);
114    ///
115    /// assert!(hashmap.contains_key("a"));
116    /// assert!(!hashmap.contains_key("p"));
117    /// ```
118    pub fn contains_key(&self, key: &K) -> bool {
119        self.index(key).is_some()
120    }
121}
122
123impl<'a, K, V> ZeroHashMap<'a, K, V>
124where
125    K: ZeroMapKV<'a> + ?Sized,
126    V: ZeroMapKV<'a> + ?Sized,
127{
128    // Produce an iterator over (key, value) pairs.
129    pub fn iter<'b>(
130        &'b self,
131    ) -> impl ExactSizeIterator<
132        Item = (
133            &'b <K as ZeroMapKV<'a>>::GetType,
134            &'b <V as ZeroMapKV<'a>>::GetType,
135        ),
136    > {
137        (0..self.len()).map(|index| {
138            (
139                #[expect(clippy::unwrap_used)] // index is in range
140                self.keys.zvl_get(index).unwrap(),
141                #[expect(clippy::unwrap_used)] // index is in range
142                self.values.zvl_get(index).unwrap(),
143            )
144        })
145    }
146
147    // Produce an iterator over keys.
148    pub fn iter_keys<'b>(
149        &'b self,
150    ) -> impl ExactSizeIterator<Item = &'b <K as ZeroMapKV<'a>>::GetType> {
151        #[expect(clippy::unwrap_used)] // index is in range
152        (0..self.len()).map(|index| self.keys.zvl_get(index).unwrap())
153    }
154
155    // Produce an iterator over values.
156    pub fn iter_values<'b>(
157        &'b self,
158    ) -> impl ExactSizeIterator<Item = &'b <V as ZeroMapKV<'a>>::GetType> {
159        #[expect(clippy::unwrap_used)] // index is in range
160        (0..self.len()).map(|index| self.values.zvl_get(index).unwrap())
161    }
162}
163
164impl<'a, K, V, A, B> FromIterator<(A, B)> for ZeroHashMap<'a, K, V>
165where
166    K: ZeroMapKV<'a> + ?Sized + Hash + Eq,
167    V: ZeroMapKV<'a> + ?Sized,
168    B: Borrow<V>,
169    A: Borrow<K>,
170{
171    /// Build a [`ZeroHashMap`] from an iterator returning (K, V) tuples.
172    ///
173    /// # Example
174    /// ```
175    /// use zerovec::ZeroHashMap;
176    ///
177    /// let hashmap = ZeroHashMap::<i32, str>::from_iter([
178    ///     (1, "a"),
179    ///     (2, "b"),
180    ///     (3, "c"),
181    ///     (4, "d"),
182    /// ]);
183    /// assert_eq!(hashmap.get(&1), Some("a"));
184    /// assert_eq!(hashmap.get(&2), Some("b"));
185    /// assert_eq!(hashmap.get(&3), Some("c"));
186    /// assert_eq!(hashmap.get(&4), Some("d"));
187    /// ```
188    fn from_iter<T: IntoIterator<Item = (A, B)>>(iter: T) -> Self {
189        let iter = iter.into_iter();
190        let size_hint = match iter.size_hint() {
191            (_, Some(upper)) => upper,
192            (lower, None) => lower,
193        };
194
195        let mut key_hashes = Vec::with_capacity(size_hint);
196        let mut keys = K::Container::zvl_with_capacity(size_hint);
197        let mut values = V::Container::zvl_with_capacity(size_hint);
198        for (k, v) in iter {
199            keys.zvl_push(k.borrow());
200            key_hashes.push(compute_hash(k.borrow()));
201            values.zvl_push(v.borrow());
202        }
203
204        let (displacements, mut reverse_mapping) = compute_displacements(key_hashes.into_iter());
205
206        keys.zvl_permute(&mut reverse_mapping.clone());
207        values.zvl_permute(&mut reverse_mapping);
208
209        Self {
210            displacements: ZeroVec::alloc_from_slice(&displacements),
211            values,
212            keys,
213        }
214    }
215}
216
217#[cfg(test)]
218mod tests {
219    use super::*;
220    use crate::ule::AsULE;
221    use rand::{distr::StandardUniform, Rng, SeedableRng};
222    use rand_pcg::Lcg64Xsh32;
223
224    #[test]
225    fn test_zhms_u64k_u64v() {
226        const N: usize = 65530;
227        let seed = u64::from_le_bytes(*b"testseed");
228        let rng = Lcg64Xsh32::seed_from_u64(seed);
229        let kv: Vec<(u64, u64)> = rng.sample_iter(&StandardUniform).take(N).collect();
230        let hashmap: ZeroHashMap<u64, u64> =
231            ZeroHashMap::from_iter(kv.iter().map(|e| (&e.0, &e.1)));
232        for (k, v) in kv {
233            assert_eq!(
234                hashmap.get(&k).copied().map(<u64 as AsULE>::from_unaligned),
235                Some(v),
236            );
237        }
238    }
239}
zerovec/hashmap/mod.rs

zerovec/hashmap/
mod.rs
