Rust挑战 - 动手实现HashMap 2

让我们从上一篇文章结束的地方继续。我们要实现get_mut()方法，这应该与get()方法一样，但编译器不会让我们简单地将不可变变量更新为可变变量。

解决方案是通过迭代器循环遍历entry，而不是老式的索引计数。由于我们需要从给定的索引开始，循环遍历整个数组，以index-1结束，这本身有点棘手，但可以使用Iterator::split_at_mut()方法完成。这样，我们就可以最终实现get_mut()方法了。

代码如下：

impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
    ......

    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut Val>
    where
        Key: Borrow<Q>,
        Q: Eq + Hash,
    {
        if self.len() == 0 {
            return None;
        }
        let idx: usize = self.get_index(key);
        for entry in self.iter_mut_starting_at(idx) {
            match entry {
                Entry::Vacant => {
                    return None;
                }
                Entry::Occupied { key: k, val } if (k as &Key).borrow() == key => {
                    return Some(val);
                }
                _ => {}
            }
        }
        panic!("fatal: unreachable");
    }

    fn iter_mut_starting_at(&mut self, idx: usize) -> impl Iterator<Item = &mut Entry<Key, Val>> {
        let (s1, s2) = self.xs.split_at_mut(idx);
        s2.iter_mut().chain(s1.iter_mut())
    }

    ......
}

现在只剩下两个方法：insert()和remove()。现在是讨论Entry枚举Tombstone变量有什么作用的时候了。

我们的哈希冲突解决方案是从索引开始，探测被占用Entry的链，直到找到匹配的键，或者直到找到一个空的键，这标志着哈希冲突键的结束。

如果我们在链的中间找到匹配的键，并通过将其标记为Vacant来删除它，那么我们将链分成了两部分。下次我们搜索相同的链时，我们将无法搜索链的后半部分，因为我们将到达中间的空Entry。

这就是为什么我们不能简单地删除Entry并将其标记为Vacant。Tombstone变量让我们知道那里什么都没有，但我们仍然需要继续探索。

有了它，我们就可以实现remove()方法——如果我们找到一个具有匹配键的Entry，我们将其标记为Tomtsbone并递减计数器。否则，它是一个no-op。这听起来很简单，但在Rust中实现起来有点棘手。让我们首先实现一个从Entry获取值的辅助方法。

enum Entry<Key, Val> {
    Vacant,
    Tombstone,
    Occupied { key: Key, val: Val },
}

use std::mem::swap;

impl<Key, Val> Entry<Key, Val> {
    fn take(&mut self) -> Option<Val> {
        match self {
            Self::Occupied { key, val } => {
                let mut occupied = Self::Tombstone;
                swap(self, &mut occupied);
                if let Self::Occupied { key, val } = occupied {
                    Some(val)
                } else {
                    panic!("fatal: unreachable");
                }
            }
            _ => None,
        }
    }
}

有了这个，我们就可以实现remove()方法了。

impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
    ......

    pub fn remove<Q>(&mut self, key: &Q) -> Option<Val>
    where
        Key: Borrow<Q>,
        Q: Eq + Hash,
    {
        if self.len() == 0 {
            return None;
        }
        let idx = self.get_index(key);
        let mut result = None;
        for entry in self.iter_mut_starting_at(idx) {
            match entry {
                Entry::Occupied { key: k, .. } if (k as &Key).borrow() == key => {
                    result = entry.take();
                    break;
                }
                Entry::Vacant => {
                    result = None;
                    break;
                }
                _ => {}
            }
        }
        result.map(|val| {
            self.n_occupied -= 1;
            val
        })
    }

    ......
}

现在只剩下最后一个方法：insert()。此方法首先检查负载因子并在必要时调整数组的大小。完成所有这些之后，它将把键、值对插入到表中。让我们创建一个辅助方法insert_helper()来执行插入部分，不需要检查负载因子以调整大小。我们另外分别定义计算负载因子和调整大小的方法。

impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
    ......

    pub fn insert(&mut self, key: Key, val: Val) -> Option<Val> {
        if self.load_factor() >= 0.75 {
            self.resize();
        }

        self.insert_helper(key, val)
    }

    fn load_factor(&self) ->  f64 {
        todo!()
    }

    fn resize(&mut self) {
        todo!()
    }

    fn insert_helper(&mut self, key: Key, val: Val) -> Option<Val> {
        todo!()
    }

    ......
} 

load_factor()方法很简单，但是存在一种极端情况—我们使用空数组初始化哈希表，因此我们需要显式地处理这种情况。至于resize()方法，我们希望将数组的大小增加一倍，除非当前的大小太小。最简单的实现是创建一个哈希表的新实例，简单地插入当前哈希表中的每个元素，最后交换这两个哈希表。

fn load_factor(&self) ->  f64 {
    if self.xs.is_empty() {
        1.0
    } else {
        1.0 - self.n_vacant as f64 / self.xs.len() as f64
    }
}

fn resize(&mut self) {
    let new_size = std::cmp::max(64, self.xs.len() * 2);
    let mut new_table = Self {
        xs: (0..new_size).map(|_| Entry::Vacant).collect(),
        n_occupied: 0,
        n_vacant: new_size,
    };
    for entry in std::mem::take(&mut self.xs) {
        if let Entry::Occupied { key, val } = entry {
            new_table.insert_helper(key, val);
        }
    }

    swap(self, &mut new_table);
}

好了，现在只剩下insert_helper()方法。从概念上讲，这并不太难。我们探测Entry并查找匹配的键。如果找到，则覆盖该值。如果没有，插入到空Entry，不要忘记相应地更新计数器。

impl<Key, Val> Entry<Key, Val> {
    ......

    fn replace(&mut self, mut x: Val) -> Option<Val> {
        match self {
            Self::Occupied { key, val } => {
                swap(&mut x, val);
                Some(x)
            }
            _ => None,
        }
    }
}

impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
    ......
    fn insert_helper(&mut self, key: Key, val: Val) -> Option<Val> {
        let idx = self.get_index(&key);
        let mut result = None;
        for entry in self.iter_mut_starting_at(idx) {
            match entry {
                Entry::Occupied { key: k, .. } if (k as &Key).borrow() == &key => {
                    result = entry.replace(val);
                    break;
                }
                Entry::Vacant => {
                    *entry = Entry::Occupied { key, val };
                    break;
                }
                _ => {}
            }
        }
        if result.is_none() {
            self.n_occupied += 1;
            self.n_vacant -= 1;
        }
        result
    }
    ......
} 

现在我们已经完成了Rust中HashMap的实现。

在下一篇文章中，我将编写一些单元测试和基准测试函数来衡量我们的实现与标准库std::collections::HashMap相比有多快或多慢。

本文由微信公众号coding到灯火阑珊原创，哈喽比特收录。
文章来源：https://mp.weixin.qq.com/s/L1JaLOHuyMOguR3IHUohBA