让我们从上一篇文章结束的地方继续。我们要实现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变量让我们知道那里什么都没有,但我们仍然需要继续探索。
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,
}
}
}
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
})
}
......
}
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!()
}
......
}
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);
}
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的实现。