test rust

hashmap.rs

#[derive(Debug, Clone, PartialEq)]
pub struct HashMap<T> {
    size: usize,
    slot: Vec<usize>,
    data: Vec<T>,
}

impl<T: Clone + PartialEq + Default> HashMap<T> {
    // 创建
    pub fn new(size: usize) -> Self {
        // 初始化 slot 和 data
        let mut slot = Vec::with_capacity(size);
        let mut data = Vec::with_capacity(size);
        for _i in 0..size {
            slot.push(0);
            data.push(Default::default());
        }
        HashMap { size, slot, data }
    }

    pub fn hash(&self, key: usize) -> usize {
        key % self.size
    }

    pub fn rehash(&self, pos: usize) -> usize {
        (pos + 1) % self.size
    }

    // 添加新的键值对,如果键存在，那么新值替换旧值
    pub fn insert(&mut self, key: usize, val: T) {
        if 0 == key {
            panic!("错误： key 必须大于 0");
        }
        let pos = self.hash(key);
        if self.slot[pos] == 0 {
            // 槽没有数据直接插入
            self.slot[pos] = key;
            self.data[pos] = val;
        } else {
            // 插入槽有数据再找下一个科兴的位置
            let mut next = self.rehash(pos);
            while self.slot[next] != 0 && key != self.slot[next] {
                next = self.rehash(next);
                if next == pos {
                    // 槽满了旧退出
                    println!("错误： 空间已满，退出插入");
                    return;
                }
            }

            // 在找到的槽中插入数据
            if self.slot[next] == 0 {
                self.slot[next] = key;
                self.data[next] = val;
            } else {
                // self.slot[next] == key
                self.data[next] = val;
            }
        }
    }

    // 删除 key 返回对应的 v
    pub fn remove(&mut self, key: usize) -> Option<T> {
        if 0 == key {
            panic!("错误： key 必须大于 0");
        }

        let pos = self.hash(key);
        if 0 == self.slot[pos] {
            None
        } else if key == self.slot[pos] {
            self.slot[pos] = 0;
            let data = Some(self.data[pos].clone());
            self.data[pos] = Default::default();
            data
        } else {
            let mut data: Option<T> = None;

            let mut stop = false;
            let mut found = false;
            let mut curr = pos;

            while 0 != self.slot[curr] && !found && !stop {
                if key == self.slot[curr] {
                    // 找到 删除
                    found = true;
                    self.slot[curr] = 0;
                    data = Some(self.data[curr].clone());
                    self.data[curr] = Default::default();
                } else {
                    // 在找
                    curr = self.rehash(curr);
                    if curr == pos {
                        stop = true;
                    }
                }
            }

            data
        }
    }

    // 返回 key 对应的值
    pub fn get(&self, key: usize) -> Option<&T> {
        let pos = self.hash(key);
        let mut data: Option<&T> = None;

        let mut stop = false;
        let mut found = false;
        let mut curr = pos;

        while 0 != self.slot[curr] && !found && !stop {
            if key == self.slot[curr] {
                // 找到 删除
                found = true;
                data = self.data.get(curr);
            } else {
                // 在找
                curr = self.rehash(curr);
                if curr == pos {
                    stop = true;
                }
            }
        }

        data
    }

    // 返回
    pub fn contains(&self, key: usize) -> bool {
        if 0 == key {
            panic!("错误： key 必须大于 0");
        }

        self.slot.contains(&key)
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    pub fn len(&self) -> usize {
        let mut length = 0;
        for d in self.slot.iter() {
            if d != &0 {
                // 插槽不为0 表示有数据
                length += 1;
            }
        }

        length
    }
}

#[test]
fn test_hashmap() {
    let mut hmap = HashMap::new(11);
    hmap.insert(10, "cat");
    hmap.insert(1, "dog");
    hmap.insert(2, "tiger");

    assert_eq!(hmap.get(1), Some(&"dog"));
    assert_eq!(hmap.remove(1), Some("dog"));
    assert_eq!(hmap.len(), 2);
}