Rust语言实现哈希表：开放地址法详解（从零开始掌握Rust数据结构）

为什么选择 Rust 实现？

Rust 以其内存安全、零成本抽象和并发无畏著称。通过手动实现 Rust数据结构，你可以更深入地理解所有权（ownership）、生命周期（lifetimes）以及泛型等核心概念。

实现步骤详解

我们将使用线性探测（Linear Probing）作为开放地址法的探测策略。以下是完整实现：

1. 定义哈希表结构

#[derive(Clone, Debug)]pub enum Entry<K, V> {    Empty,    Deleted,    Occupied(K, V),}pub struct OpenAddressingHashTable<K, V> {    buckets: Vec<Entry<K, V>>,    size: usize,    capacity: usize,}

我们定义了三种状态：Empty（从未使用）、Deleted（曾被使用但已删除）、Occupied（当前存储键值对）。这有助于正确处理删除操作。

2. 实现构造函数与辅助方法

use std::hash::{Hash, Hasher};use std::collections::hash_map::DefaultHasher;impl<K: Clone + Eq + Hash, V: Clone> OpenAddressingHashTable<K, V> {    pub fn new(capacity: usize) -> Self {        let mut buckets = Vec::with_capacity(capacity);        for _ in 0..capacity {            buckets.push(Entry::Empty);        }        OpenAddressingHashTable {            buckets,            size: 0,            capacity,        }    }    fn hash(&self, key: &K) -> usize {        let mut hasher = DefaultHasher::new();        key.hash(&mut hasher);        (hasher.finish() as usize) % self.capacity    }}

3. 插入（Insert）方法

pub fn insert(&mut self, key: K, value: V) {    if self.size >= self.capacity / 2 {        // 简单扩容策略：负载因子超过0.5时扩容        self.resize();    }    let mut index = self.hash(&key);    loop {        match &self.buckets[index] {            Entry::Empty | Entry::Deleted => {                self.buckets[index] = Entry::Occupied(key, value);                self.size += 1;                return;            }            Entry::Occupied(k, _) if k == &key => {                // 覆盖已有键                self.buckets[index] = Entry::Occupied(key, value);                return;            }            _ => {                // 线性探测：下一个位置                index = (index + 1) % self.capacity;            }        }    }}

4. 查找（Get）与删除（Remove）方法

pub fn get(&self, key: &K) -> Option<&V> {    let mut index = self.hash(key);    loop {        match &self.buckets[index] {            Entry::Empty => return None,            Entry::Occupied(k, v) if k == key => return Some(v),            _ => index = (index + 1) % self.capacity,        }    }}pub fn remove(&mut self, key: &K) -> bool {    let mut index = self.hash(key);    loop {        match &self.buckets[index] {            Entry::Empty => return false,            Entry::Occupied(k, _) if k == key => {                self.buckets[index] = Entry::Deleted;                self.size -= 1;                return true;            }            _ => index = (index + 1) % self.capacity,        }    }}

5. 扩容（Resize）方法

fn resize(&mut self) {    let old_buckets = std::mem::replace(        &mut self.buckets,        vec![Entry::Empty; self.capacity * 2],    );    let old_capacity = self.capacity;    self.capacity *= 2;    self.size = 0;    for entry in old_buckets {        if let Entry::Occupied(k, v) = entry {            self.insert(k, v);        }    }}

测试我们的哈希表

fn main() {    let mut table = OpenAddressingHashTable::new(8);    table.insert("apple", 5);    table.insert("banana", 3);    table.insert("cherry", 7);    println!("apple: {:?}", table.get(&"apple")); // Some(5)    println!("grape: {:?}", table.get(&"grape")); // None    table.remove(&"banana");    println!("banana after removal: {:?}", table.get(&"banana")); // None}

总结

通过本教程，你已经掌握了如何在 Rust 中使用 开放地址法 实现一个基础的哈希表。这不仅加深了你对 Rust数据结构 的理解，也为后续学习更复杂的系统编程打下坚实基础。

记住，实际项目中通常使用标准库的 HashMap，但手动实现能让你更清楚其内部机制。希望这篇 Rust编程教程 对你有所帮助！

关键词回顾：Rust哈希表、开放地址法、Rust数据结构、Rust编程教程。