Rust 挑戰 - 動手實現 HashMap 1

讓我們在 Rust 中實現一個哈希表數據結構，由於哈希表的效率和通用性，它在數據結構中非常重要。通過從頭開始實現它，我們可以深入瞭解所涉及的底層算法和數據結構。同時還還會提高我們的 Rust 技能。

說到算法，我們將實現線性探測開放尋址哈希表。

我們將採用自頂向下的方法，從較高級別的抽象開始，然後逐步向下到較低級別的抽象和實現。讓我們從最頂層的抽象開始：API，我們不支持 Rust 標準庫 std::collections::HashMap 的整個 API，只是實現其核心功能。

use std::borrow::Borrow;
use std::hash::Hash;

pub struct HashMap<Key, Val> {
    // todo
}

impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
    pub fn new() -> Self {
        todo!()
    }

    pub fn len(&self) -> usize {
        todo!()
    }

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

    pub fn get<Q>(&self, key: &Q) -> Option<&Val>
    where
        Key: Borrow<Q>,
        Q: Eq + Hash,
    {
        todo!()
    }

    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut Val>
    where
        Key: Borrow<Q>,
        Q: Eq + Hash,
    {
        todo!()
    }

    pub fn remove<Q>(&mut self, key: &Q) -> Option<Val>
    where
        Key: Borrow<Q>,
        Q: Eq + Hash,
    {
        todo!()
    }
}

這些方法具有與標準庫中 HashMap 完全相同的簽名。順便說一下，如果你不熟悉 API 中出現的 Borrow 特性，請參考《Rust 技巧：Borrow Trait》這篇文章。

哈希表基本上是一個項的數組，其索引是鍵的哈希值對數組大小的模。我們自然會對這個數組使用 Vec，但是這個類型 T 是什麼呢？我們叫它 Entry，想想 Entry 應該包含什麼。

我們知道 Entry 可以是空的，也可以是被佔用的。當它被佔用時，它應該同時包含 Key 和 Val。爲了支持 remove() 方法，我們需要第三個狀態：Tombstone。此狀態表示 Entry 曾經被佔用但當前爲空。稍後我們將瞭解爲什麼需要這樣的區分，先看看我們的 Entry 結構體：

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

哈希表結構體需要兩個 usize 字段——一個用於跟蹤已佔用的 Entry，另一個用於跟蹤空 Entry。第一個字段是 len() 方法的返回值，第二個字段讓我們決定何時調整數組的大小。這樣，我們就可以在骨架中添加一些實現細節。代碼修改如下：

pub struct HashMap<Key, Val> {
    xs: Vec<Entry<Key, Val>>,
    n_occupied: usize,
    n_vacant: usize,
}

impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
    pub fn new() -> Self {
        Self {
            xs: Vec::new(),
            n_occupied: 0,
            n_vacant: 0,
        }
    }

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

我們需要一個方法來計算鍵的哈希值，並對數組大小取模來獲得索引。增加如下方法：

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

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

    fn get_index<Q>(&self, key: &Q) -> usize
    where
        Key: Borrow<Q>,
        Q: Eq + Hash,
    {
        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        hasher.finish() as usize % self.xs.len()
    }
}

現在，讓我們實現 get() 方法。我們所需要做的就是遍歷從 index 開始的 entry 並比較鍵，直到找到匹配項，或者直到遇到空 entry。在搜索過程中，我們簡單地忽略並跳過 tombstone 狀態的 entry。

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

    pub fn get<Q>(&self, key: &Q) -> Option<&Val>
    where
        Key: Borrow<Q>,
        Q: Eq + Hash,
    {
        if self.len() == 0 {
            return None;
        }
        let mut idx = self.get_index(key);
        loop {
            match &self.xs[idx] {
                Entry::Vacant => {
                    break None;
                }
                Entry::Occupied { key: k, val } if k.borrow() == key => {
                    break Some(val);
                }
                _ => {
                    idx = (idx + 1) % self.xs.len();
                }
            }
        }
    }

    ......
}

目前看，還不錯。我們可以對 get_mut() 方法做同樣的事情嗎？如果簡單地將不可變變量更新爲可變變量，就會出現一些編譯器錯誤，這個修復需要一些更復雜的修改。爲此，我們將在下一篇文章中繼續，敬請期待！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/7S74tFVkkan5Eyo6hNiDjg

猜你喜歡