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 相比有多快或多慢。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/L1JaLOHuyMOguR3IHUohBA