Created
April 6, 2021 01:45
-
-
Save hderms/415e3197e4647f8f77432eb65f7e91d9 to your computer and use it in GitHub Desktop.
Writing a hash table in Rust
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| use std::{ | |
| collections::hash_map::DefaultHasher, | |
| hash::{Hash, Hasher}, | |
| }; | |
| const SIZE: usize = 2 << 12; | |
| const CHAIN_CAPACITY: usize = 16; | |
| struct HashTable<K: Hash + PartialEq, V> { | |
| table: Vec<Vec<(K, V)>>, | |
| } | |
| impl<K: Hash + PartialEq, V> HashTable<K, V> { | |
| fn new() -> HashTable<K, V> { | |
| let mut table = Vec::with_capacity(SIZE); | |
| for _ in 0..SIZE { | |
| table.push(Vec::with_capacity(CHAIN_CAPACITY)); | |
| } | |
| HashTable { table } | |
| } | |
| fn get_index(&self, k: &K) -> usize { | |
| let mut s = DefaultHasher::new(); | |
| k.hash(&mut s); | |
| (s.finish() as usize) % SIZE | |
| } | |
| fn insert(&mut self, k: K, v: V) { | |
| let index = self.get_index(&k); | |
| let vec = &mut self.table[index]; | |
| if let Some(position) = vec.iter().position(|el| el.0 == k) { | |
| vec[position] = (k, v); | |
| } else { | |
| vec.push((k, v)); | |
| } | |
| } | |
| fn remove(&mut self, k: K) { | |
| let index = self.get_index(&k); | |
| let vec = &mut self.table[index]; | |
| if let Some(position) = vec.iter().position(|el| el.0 == k) { | |
| vec.remove(position); | |
| } | |
| } | |
| fn get(&self, k: K) -> Option<&V> { | |
| let index = self.get_index(&k); | |
| let vec = &self.table[index]; | |
| if let Some((_k, v)) = vec.iter().find(|el| el.0 == k) { | |
| Some(v) | |
| } else { | |
| None | |
| } | |
| } | |
| } | |
| #[cfg(test)] | |
| mod tests { | |
| use super::*; | |
| #[test] | |
| fn it_works() { | |
| let mut table: HashTable<String, usize> = HashTable::new(); | |
| table.insert(String::from("foo"), 4); | |
| table.insert(String::from("bar"), 5); | |
| table.insert(String::from("foo"), 8); | |
| assert_eq!(table.get(String::from("foo")), Some(&8)); | |
| assert_eq!(table.get(String::from("bar")), Some(&5)); | |
| assert_eq!(table.get(String::from("bing")), None); | |
| table.insert(String::from("bar"), 9); | |
| assert_eq!(table.get(String::from("bar")), Some(&9)); | |
| table.remove(String::from("bar")); | |
| assert_eq!(table.get(String::from("bar")), None); | |
| } | |
| #[test] | |
| fn it_works_with_large_amount_of_keys() { | |
| let mut table: HashTable<usize, usize> = HashTable::new(); | |
| for i in 1..1_000_000 { | |
| table.insert(i, i + 59); | |
| } | |
| for i in 1..1_000_000 { | |
| let result = table.get(i).unwrap(); | |
| let address = &(i + 59); | |
| assert!(result == address); | |
| } | |
| } | |
| } | |
| fn main() { | |
| let mut table: HashTable<usize, usize> = HashTable::new(); | |
| for i in 1..1_000_000 { | |
| table.insert(i, i + 59); | |
| } | |
| for i in 1..1_000_000 { | |
| let result = table.get(i).unwrap(); | |
| let address = &(i + 59); | |
| assert!(result == address); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment