5
\$\begingroup\$

This is an implementation of a dictionary (hash map) in Rust. It is loosely based on Python's dictionary implementation, using the same "random" probing and capacity/size management. Does it use too much memory or waste too many CPU cycles? Is it documented enough to be easily understood? I tried to mitigate the use of clone(), so let me know if I could have done more in that department.

This is not meant to be a package, so it does not necessarily follow Cargo package guidelines. lib.rs contains unit tests, and dictionary.rs contains the struct and its methods.

dictionary.rs

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
use std::clone::Clone;
use std::fmt;
use std::fmt::Write;

#[derive(Copy, Clone)]
enum Bucket<K: Clone, V: Clone> {
    Entry((K, V, usize, usize)),
    Empty,
    Tombstone
}

/* capacity is the number of objects the dict can hold, resizes when 
 *      it is at 2/3 capacity
 *      
 * size is the number of items in the dict, will never be more than
 *      2/3 capacity
 *
 * table is where the data is stored. it is in the format of a vec
 *      full of Bucket enums, which either encode an empty spot, a
 *      spot where an item was deleted, or an item
 *
 * This is meant to be a hashmap for keys that can be hashed 
 */
pub struct Dictionary<K: Clone + Hash, V: Clone> {
    capacity: usize,
    size: usize,
    table: Vec<Bucket<K, V>>
}

#[allow(dead_code)]
impl<K: Clone + Hash + PartialEq, V: Clone> Dictionary<K, V>{
    pub fn new() -> Dictionary<K, V> {
        Dictionary {
            capacity: 8,
            size: 0,
            table: vec![Bucket::Empty; 8]
        }
    }

    pub fn with_capacity(size: usize) -> Dictionary<K, V> {
        if size == 0 {
            panic!("Cannot create a zero-sized dict");
        }

        Dictionary {
            capacity: size,
            size: 0,
            table: vec![Bucket::Empty; size]
        }
    }

    /* Performs a lookup using almost the exact same algorithm as insertion
     * Returns an Some(value) if the key exists, and None otherwise
     * Probing uses two numbers that are used in the calculation of each index: perturb and PERTURB_SHIFT
     * perturb is used in the calculating of the "random" probing and is shifted to the right by PERTURB_SHIFT
     * bits after every iteration in the probing
     */
    fn lookup(&self, key: &K) -> Option<(K, V, usize)> { 
        let key_hash: usize = self.get_hash(&key);

        let mut index = (key_hash % self.capacity) as usize;
        const PERTURB_SHIFT: u8 = 5;
        let mut perturb: usize = key_hash;

        loop {
            let current: Bucket<K, V> = self.table.get(index).unwrap().clone();

            match current {
                Bucket::Entry(d) => {
                    if d.0 == *key {
                        break Some((d.0, d.1, index));
                    } else {
                        perturb >>= PERTURB_SHIFT;
                        index = ((5*index) + 1 + perturb) % self.capacity as usize;
                        continue;
                    }
                },

                Bucket::Tombstone => {
                    perturb >>= PERTURB_SHIFT;
                    index = ((5*index) + 1 + perturb) % self.capacity as usize;
                    continue;
                }, 

                Bucket::Empty => {
                    break None;
                }
            };
        }
    }

    // Inserts new items without regard for size of the dict, it is separated from 
    // the insert() function to prevent recursion on resizing. 
    fn force_insert(&mut self, key: K, value: V, key_hash: usize) {
        let mut index = (key_hash % self.capacity) as usize;
        const PERTURB_SHIFT: u8 = 5;
        let mut perturb: usize = key_hash; 

        loop {
            let current: Bucket<K, V> = self.table.get(index).unwrap().clone();

            match current {
                Bucket::Entry(d) => {
                    if d.0 == key {
                        self.table[index] = Bucket::Entry((d.0, value, d.2, index));
                        break;
                    } else {
                        perturb >>= PERTURB_SHIFT;
                        index = ((5*index) + 1 + perturb) % self.capacity as usize;
                        continue
                    }
                },

                _ => {
                    self.table[index] = Bucket::Entry((key, value, key_hash, index));
                    break;
                }
            };
        }
    }

    // Empties the table and makes a table twice the size, then reinserts all the entries
    fn resize(&mut self, new_capacity: usize) {
        self.capacity = new_capacity;
        let _table = self.table.clone();
        self.table = vec![Bucket::Empty; self.capacity];
        for entry in _table.iter() {    
            if let Bucket::Entry(d) = entry.clone() {
                self.force_insert(d.0, d.1, d.2);
            }
        }
    }

    //Checks if a resize is needed before inserting the new item, resizes if needed
    pub fn insert(&mut self, key: K, value: V) {
        self.size += 1;
        if 2 * (self.capacity/3) < self.size { // Double capacity if 2/3 full or more
            self.resize(2 * self.capacity);
        }
        let hash = self.get_hash(&key);
        self.force_insert(key, value, hash);
    }

    //Returns a Result::Err if the vectors are different sizes
    pub fn from_vecs(mut key_vec: Vec<K>, mut value_vec: Vec<V>) -> Dictionary<K, V> {
        if key_vec.len() != value_vec.len() {
            panic!("Differently sized vecs");
        } else if key_vec.is_empty() {
            panic!("Cannot create a zero-sized dict");
        } else {
            let mut dict: Dictionary<K, V> = Dictionary::with_capacity(key_vec.len());
            for _ in 0..key_vec.len() {
                let key = key_vec.pop().unwrap();
                let value = value_vec.pop().unwrap();
                dict.insert(key, value);
            }

            dict
        }
    }
    
    pub fn from_tuples(tuples: Vec<(K, V)>) -> Dictionary<K, V> {
        if tuples.is_empty() {
            panic!("Cannot create a zero-sized vec");
        }
        let mut dict: Dictionary<K, V> = Dictionary::with_capacity(tuples.len());

        for (key, value) in tuples {
            dict.insert(key, value);
        }

        dict
    }

    pub fn size(&self) -> usize {
        self.size
    }

    pub fn capacity(&self) -> usize {
        self.capacity
    }

    pub fn get(&self, key: &K) -> Result<V, String> {
       match self.lookup(key) {
           Some(v) => Ok(v.1),
           None => Err(format!("Key does not exist"))
       }
    }

    pub fn remove (&mut self, key: &K) -> Option<(K, V)>{
        let output: Option<(K, V)>;
        // If the key exists, remove it from the dictionary and add the key and value to the output
        match self.lookup(key) {
            Some(v) => {
                self.table[v.2] = Bucket::Tombstone;
                self.size -= 1;
                output = Some((v.0, v.1));
            },
            None => {output = None;}
        };

        if self.size < self.capacity/3 + 1 { // If current size is less than 2/3 half capacity, aka less than 1/3 capacity
            self.resize(self.capacity/2); 
        }

        output
    }

    pub fn contains(&self, key: &K) -> bool {
        self.lookup(key).is_some()
    }

    fn get_hash(&self, key: &K) -> usize {
        let mut s = DefaultHasher::new();
        key.hash(&mut s);
        s.finish() as usize
    }

    // Returns a vector of keys contained in the dict
    pub fn keys(&self) -> Vec<&K> {
        let mut key_vec: Vec<&K> = Vec::new();
        for item in self.table.iter() {
            if let Bucket::Entry(n) = item {
                key_vec.push(&n.0);
            }
        }
        key_vec
    }

    // Returns a vector of values contained in the dict
    pub fn values(&self) -> Vec<&V> {
        let mut value_vec: Vec<&V> = Vec::new();
        for item in self.table.iter() {
            if let Bucket::Entry(n) = item {
                value_vec.push(&n.1);
            }
        }
        value_vec
    }
    
    // Returns a vector of (key, value) tuples containing every
    // key value pairing in the dict
    pub fn items(&self) -> Vec<(&K, &V)> {
        let mut item_vec: Vec<(&K, &V)> = Vec::new();
        for item in self.table.iter() {
            if let Bucket::Entry(n) = item {
                item_vec.push((&n.0, &n.1));
            }
        }
        item_vec
    }
}

impl<K, V> fmt::Display for Dictionary<K, V>
    where K: fmt::Display + Clone + Hash,
          V: fmt::Display + Clone {

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut output_str = String::new();
        output_str.push_str("{");

        for k in self.table.iter() // Iterate over all buckets containing an entry
            .filter(|v| match v { Bucket::Entry(_n) => true, _ => false }) {
            if let Bucket::Entry(d) = k {
                write!(output_str, "{}: {}, ", d.0, d.1)?;
            }
        }

        let len = output_str.len();
        if len > 1 {
            output_str = String::from(&output_str[..len - 2]);
        }
        output_str.push_str("}");

        write!(f, "{}", output_str)
    }
}

lib.rs

mod dictionary;

use dictionary::Dictionary;

/* 
 * Creates the dictionary
 * {
 * 1: 6,
 * 2: 7,
 * 3: 8,
 * 4: 9,
 * 5: 0
 * }
 */
#[allow(dead_code)]
fn create_dict() -> Dictionary<u8, u8> {
    let tuples: Vec<(u8, u8)> = vec![(1, 6), (2, 7), (3, 8),
                             (4, 9), (5, 0)];
    Dictionary::from_tuples(tuples)
}

#[allow(dead_code)]
fn has_same_elements<T: PartialEq>(vec1: &Vec<T>, vec2: &Vec<T>) -> bool {
    for i in vec1 {
        if vec2.contains(i) {
            continue;
        }
        return false;
    }
    true
}

#[cfg(test)]
mod tests{
    use super::*;

    #[test]
    fn make_dict() {
        let _d: Dictionary<u8, u8> = Dictionary::new();
        
        assert_eq!(_d.capacity(), 8);
    }

    #[test]
    fn create_sized() {
        let _d: Dictionary<u8, u8> = Dictionary::with_capacity(16); 
        assert_eq!(_d.capacity(), 16);
    }

    #[test]
    #[should_panic]
    fn zero_sized_dict() {
        let _d: Dictionary<u8, u8> = Dictionary::with_capacity(0);
    }

    #[test]
    fn create_from_vecs() {
        let vec1: Vec<usize> = vec![1, 2, 3, 4, 5];
        let vec2: Vec<usize> = vec![6, 7, 8, 9, 0];
        let _d: Dictionary<usize, usize> = Dictionary::from_vecs(vec1, vec2);
       
        assert_eq!(_d.size(), 5); 
    }

    #[test]
    fn create_from_tuples() {
        let tuples: Vec<(u8, u8)> = vec![(1, 2), (3, 4)];
        let _d: Dictionary<u8, u8> = Dictionary::from_tuples(tuples);

        assert_eq!(_d.get(&1).unwrap(), 2);
    }

    #[test]
    #[should_panic]
    fn zero_sized_tuple_dict() {
        let tuples: Vec<(u8, u8)> = Vec::new();
        let _d: Dictionary<u8, u8> = Dictionary::from_tuples(tuples);
    }
    
    #[test]
    #[should_panic]
    fn paniced_from_vecs() {
        let vec1: Vec<usize> = vec![1, 2, 3, 4];
        let vec2: Vec<usize> = vec![5, 6, 7];
        let _d = Dictionary::from_vecs(vec1, vec2);
    }

    #[test]
    #[should_panic]
    fn zero_sized_vecs() {
        let vec1: Vec<u8> = Vec::new();
        let vec2: Vec<u8> = Vec::new();
        let _d = Dictionary::from_vecs(vec1, vec2);
    }

    #[test]
    fn lookup() {
        let _d = create_dict();

        assert_eq!(_d.get(&1).unwrap(), 6);
    }

    #[test]
    fn insert() {
        let mut _d: Dictionary<u8, u8> = Dictionary::new();
        _d.insert(1, 2);

        assert_eq!(_d.get(&1).unwrap(), 2);
    }

    #[test]
    fn size() {
        let _d = create_dict();
        assert_eq!(_d.size(), 5);
    }

    #[test]
    fn resize() {
        let mut _d: Dictionary<u8, u8> = Dictionary::with_capacity(4);
        assert_eq!(_d.capacity(), 4);
        for i in 0..4{
            _d.insert(i, i);
        }

        assert_eq!(_d.capacity(), 8);
    }

    #[test]
    fn contains() {
        let mut _d = create_dict();
        
        assert!(_d.contains(&1));
    }

    #[test]
    fn remove() {
        let mut _d = create_dict();
        let _r = _d.remove(&1);
        
        assert!((!_d.contains(&1)) &&
        _r.is_some() &&
        _r.unwrap() == (1, 6) &&
        _d.size() == 4);
    }
    
    #[test]
    fn down_size() {
        let mut _d = create_dict();
        
        _d.remove(&1);
        _d.remove(&2);

        assert_eq!(_d.capacity(), 5);
    }

    #[test]
    fn remove_panic() { 
        let mut _d: Dictionary<u8, u8> = Dictionary::new();
        _d.remove(&1);
    }

    #[test]
    fn keys() {
        let _d = create_dict();
        let expected_keys: Vec<u8> = vec![1, 2, 3, 4, 5];
        let keys = _d.keys().into_iter().map(|x| *x).collect(); 
        assert!(has_same_elements(&keys, &expected_keys));
    }
    
    #[test]
    fn values() {
        let _d = create_dict();
        let expected_values: Vec<u8> = vec![6, 7, 8, 9, 0];
        let values = _d.values().into_iter().map(|x| *x).collect();
        assert!(has_same_elements(&values, &expected_values));
    }

    #[test]
    fn items() {
        let tuples: Vec<(u8, u8)> = vec![(1, 6), (2, 7), (3, 8), (4, 9), (5, 0)];
        let _t = tuples.clone();
        let _d: Dictionary<u8, u8> = Dictionary::from_tuples(_t);
        let expected_items = _d.items().into_iter().map(|x| (*x.0, *x.1)).collect();
        assert!(has_same_elements(&expected_items, &tuples));
    }
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Just asking: is there some specific reason that prevents you from sticking to the standard guidelines? \$\endgroup\$
    – L. F.
    Aug 10 '20 at 3:55
  • \$\begingroup\$ Use Rustdoc documentation instead of /* ... */ comments to document your functions. It will allow you to generate nice HTML documentation. \$\endgroup\$
    – Jesper
    Sep 18 '20 at 22:00
4
\$\begingroup\$
#[derive(Copy, Clone)]
enum Bucket<K: Clone, V: Clone> {
    Entry((K, V, usize, usize)),
    Empty,
    Tombstone
}

The general recommendation is not to put type constraints on your structs/enums but only on your impls. This enum works fine K and V aren't clone, so you don't need restrictions.

pub struct Dictionary<K: Clone + Hash, V: Clone> {
    capacity: usize,
    size: usize,
    table: Vec<Bucket<K, V>>
}

capacity is just table.len() You don't really need your own copy of the vec length, just use the one on Vec.

fn lookup(&self, key: &K) -> Option<(K, V, usize)> { 

Throughout your api you return Clones of your keys and values. This generally decreases the usefulness of your implementation because it is only useful for things with cheap clones. Generally, such an item returns borrows not object to overcome this.

    let mut index = (key_hash % self.capacity) as usize;

You unnecessarily cast to usize a lot. As long as you stick to usize you shouldn't be needing to cast at all.

        let current: Bucket<K, V> = self.table.get(index).unwrap().clone();

If you are just going to .unwrap() how about using self.table[index] instead?

pub fn from_vecs(mut key_vec: Vec<K>, mut value_vec: Vec<V>) -> Dictionary<K, V> {

Typically such methods would be defined to a generatic Iterator or IntoIter rather than being restricted to Vec.

pub fn from_tuples(tuples: Vec<(K, V)>) -> Dictionary<K, V> {

Rust has a standard interface: std::iter::FromIterator which would typically want to implement in this case.

pub fn get(&self, key: &K) -> Result<V, String> {

Typically, looking up a missing a key wouldn't be considered an error and would return Option rather than Error. As it stands creating an error with a String will be somewhat ineffecient because it'll allocate memory for the string.

pub fn keys(&self) -> Vec<&K> {

Such functions are typically implemented as Iterators not Vecs.

impl<K, V> fmt::Display for Dictionary<K, V>

This should probably be implementing std::fmt::Debug instead

    let mut output_str = String::new();
    output_str.push_str("{");

Firstly, its not helpful to build your String and write it into the formatter, just write directly to the formatter. Secondly, Formatter has a number of methods to help write debug style format like this. In particular, checkout the debug_map() method.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for the advice! \$\endgroup\$ Aug 12 '20 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.