Rust挑战 - 动手实现HashMap 1
让我们在Rust中实现一个哈希表数据结构，由于哈希表的效率和通用性，它在数据结构中非常重要。通过从头开始实现它，我们可以深入了解所涉及的底层算法和数据结构。同时还还会提高我们的Rust技能。
说到算法，我们将实现线性探测开放寻址哈希表。
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>，但是这个类型T是什么呢？我们叫它Entry，想想Entry应该包含什么。
enum Entry<Key, Val> {
Vacant,
Tombstone,
Occupied { key: Key, val: Val },
}
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()
}
}
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();
}
}
}
}
......
}