面试题：自定义Rust HashMap扩容策略的实现

定义新的数据结构：
- 首先定义一个新的结构体来承载自定义的哈希表，例如：
```
struct CustomHashMap<K, V> {
    capacity: usize,
    size: usize,
    buckets: Vec<Option<(K, V)>>,
}
```
- capacity 表示当前哈希表的容量，size 表示当前哈希表中键值对的数量，buckets 是一个存放键值对的向量，其中每个元素是一个 Option<(K, V)>，None 表示该桶为空。

实现构造函数：

为 CustomHashMap 实现一个构造函数，用于初始化哈希表。

impl<K, V> CustomHashMap<K, V> {
    fn new() -> Self {
        CustomHashMap {
            capacity: 8, // 初始容量设为8
            size: 0,
            buckets: vec![None; 8],
        }
    }
}

实现插入方法：

在插入新的键值对时，需要检查负载因子并决定是否扩容。

impl<K, V> CustomHashMap<K, V> {
    fn insert(&mut self, key: K, value: V)
    where
        K: std::hash::Hash + Eq,
    {
        if (self.size as f64) / (self.capacity as f64) >= 0.6 {
            self.resize();
        }
        let hash = key.hash(&mut std::collections::hash_map::DefaultHasher::new());
        let index = hash as usize % self.capacity;
        let mut index = index;
        loop {
            match self.buckets[index] {
                None => {
                    self.buckets[index] = Some((key, value));
                    self.size += 1;
                    break;
                }
                Some((ref k, _)) if k == &key => {
                    self.buckets[index] = Some((key, value));
                    break;
                }
                _ => {
                    index = (index + 1) % self.capacity;
                }
            }
        }
    }
}

实现扩容方法：

当负载因子达到0.6时，调用该方法进行扩容。扩容后的容量是原容量的1.5倍。

impl<K, V> CustomHashMap<K, V> {
    fn resize(&mut self) {
        let new_capacity = (self.capacity as f64 * 1.5) as usize;
        let mut new_buckets = vec![None; new_capacity];
        for entry in self.buckets.drain(..) {
            if let Some((key, value)) = entry {
                let hash = key.hash(&mut std::collections::hash_map::DefaultHasher::new());
                let index = hash as usize % new_capacity;
                let mut index = index;
                loop {
                    match new_buckets[index] {
                        None => {
                            new_buckets[index] = Some((key, value));
                            break;
                        }
                        _ => {
                            index = (index + 1) % new_capacity;
                        }
                    }
                }
            }
        }
        self.capacity = new_capacity;
        self.buckets = new_buckets;
    }
}

实现获取方法（可选）：

如果需要从哈希表中获取值，可以实现 get 方法。

impl<K, V> CustomHashMap<K, V> {
    fn get(&self, key: &K) -> Option<&V>
    where
        K: std::hash::Hash + Eq,
    {
        let hash = key.hash(&mut std::collections::hash_map::DefaultHasher::new());
        let index = hash as usize % self.capacity;
        let mut index = index;
        loop {
            match self.buckets[index] {
                None => return None,
                Some((ref k, ref v)) if k == key => return Some(v),
                _ => {
                    index = (index + 1) % self.capacity;
                }
            }
        }
    }
}

这样就实现了一个具有自定义扩容策略的哈希表，负载因子达到0.6时扩容，扩容后的容量是原容量的1.5倍。在实际应用中，还可以根据需要进一步优化和完善，比如实现更多的哈希表操作方法。

星途面试题库

面试题：自定义Rust HashMap扩容策略的实现

知识考点

面试题答案