rust_ds/hash_table/
mod.rs

1mod errors;
2
3pub(super) use errors::{Error, Result};
4use std::collections::hash_map::DefaultHasher;
5use std::fmt::Debug;
6use std::hash::{Hash, Hasher};
7
8type KeyPointer<K, V> = Option<(K, V)>;
9
10/// `Table` is a simple hash table implementation.
11#[derive(Debug)]
12pub struct Table<K, V>
13where
14    K: Clone,
15    V: Clone,
16{
17    pub elements: Vec<KeyPointer<K, V>>,
18    capacity: usize,
19}
20
21impl<K, V> Table<K, V>
22where
23    K: Hash + Eq + Debug + Clone,
24    V: Debug + Clone,
25{
26    /// Create a new `Table` with the given capacity.
27    pub fn new(capacity: usize) -> Self {
28        Self {
29            elements: vec![None; capacity],
30            capacity,
31        }
32    }
33    /// Hash the key and return the index.
34    fn hash<Q>(&self, key: &Q) -> usize
35    where
36        K: std::borrow::Borrow<Q>,
37        Q: Hash + ?Sized,
38    {
39        let mut hasher = DefaultHasher::new();
40        key.hash(&mut hasher);
41        (hasher.finish() as usize) % self.capacity
42    }
43    /// Insert a new key-value pair into the table.
44    pub fn insert(&mut self, key: K, value: V) {
45        let index = self.hash(&key);
46        self.elements[index] = Some((key, value));
47    }
48    /// Get the value for the given key.
49    pub fn get(&self, key: &K) -> Result<&V> {
50        let index = self.hash(key);
51        self.elements[index]
52            .as_ref()
53            .map(|(_, v)| v)
54            .ok_or(Error::KeyNotFound)
55    }
56    /// Remove the key-value pair from the table.
57    pub fn remove(&mut self, key: &K) -> Result<V> {
58        if self.capacity == 0 {
59            return Err(Error::EmptyTable);
60        }
61        let index = self.hash(key);
62        if let Some((_, value)) = self.elements[index].take() {
63            Ok(value)
64        } else {
65            Err(Error::KeyNotFound)
66        }
67    }
68    /// Update the value for the given key.
69    pub fn update(&mut self, key: &K) -> Result<&mut V> {
70        if self.capacity == 0 {
71            return Err(Error::EmptyTable);
72        }
73        let index = self.hash(key);
74        self.elements[index]
75            .as_mut()
76            .map(|(_, v)| v)
77            .ok_or(Error::KeyNotFound)
78    }
79    /// Resize the table to the new capacity.
80    pub fn resize(&mut self, new_capacity: usize) -> Result<()> {
81        if new_capacity == 0 {
82            return Err(Error::InvalidCapacity);
83        }
84
85        let mut new_table = Table::new(new_capacity);
86        for element in self.elements.iter().filter_map(|e| e.as_ref()) {
87            new_table.insert(element.0.clone(), element.1.clone());
88        }
89        self.elements = new_table.elements;
90        self.capacity = new_capacity;
91        Ok(())
92    }
93}
94/// Default implementation for `Table`.
95impl<K, V> Default for Table<K, V>
96where
97    K: Hash + Eq + Debug + Clone,
98    V: Debug + Clone,
99{
100    fn default() -> Self {
101        Self::new(64)
102    }
103}
104
105// region:    --- Tests
106#[cfg(test)]
107mod tests {
108    use super::*;
109
110    #[test]
111    fn test_hash_table_ops() {
112        let mut table = Table::new(16);
113        table.insert("key1", "value1");
114        assert_eq!(table.get(&"key1").unwrap(), &"value1");
115        table.remove(&"key1").unwrap();
116        assert!(table.get(&"key1").is_err());
117        table.insert("key2", "value2");
118        if let Ok(v) = table.update(&"key2") {
119            *v = "value3";
120        }
121        assert_eq!(table.get(&"key2").unwrap(), &"value3");
122    }
123
124    #[test]
125    fn test_hash_table_errors() {
126        let mut table: Table<&str, &str> = Table::new(16);
127        assert!(table.get(&"key1").is_err());
128        assert!(table.remove(&"key1").is_err());
129        assert!(table.update(&"key1").is_err());
130        assert!(table.resize(0).is_err());
131    }
132}
133// endregion: --- Tests
rust_ds/hash_table/mod.rs

rust_ds/hash_table/
mod.rs
