面试题：Rust HashMap扩容对性能的影响及优化

扩容对程序性能的影响

时间性能
- 插入性能下降：扩容时，HashMap需要重新计算所有键的哈希值，并将原有的键值对重新分配到新的更大的哈希表中。这一过程涉及大量的计算和数据移动操作，使得插入操作的时间复杂度在扩容期间会显著增加，从通常的接近O(1)变为接近O(n)，其中n是HashMap中键值对的数量。
- 查找性能波动：在扩容完成之前，由于数据的重新分布，查找操作可能需要在新旧哈希表之间进行，导致查找时间变长。扩容完成后，查找性能会随着哈希表的负载因子降低而有所提升，但在扩容过程中查找性能会有明显波动。
空间性能
- 额外空间开销：扩容时，新的哈希表会预先分配更大的空间，在数据迁移完成之前，新旧哈希表同时占用内存，导致程序的内存使用量在短时间内显著增加。这可能会对系统的内存资源造成压力，尤其是在频繁扩容的情况下。

减少扩容性能损耗的代码设计方法

预分配足够空间
- 在创建HashMap时，可以通过with_capacity方法预先分配足够的容量，以减少扩容的次数。例如：
```
use std::collections::HashMap;
let mut map = HashMap::with_capacity(1000);
for i in 0..1000 {
    map.insert(i, i.to_string());
}
```
- 这样在插入1000个元素时，就不需要进行扩容操作，从而提高性能。

调整负载因子

Rust的HashMap默认负载因子是0.75，可以通过HashMap::with_capacity_and_hasher方法并自定义BuildHasher来调整负载因子。例如，增大负载因子可以减少扩容的频率，但同时可能会增加哈希冲突的概率，影响查找性能。

use std::collections::{HashMap, BuildHasherDefault};
use std::hash::BuildHasher;
struct MyBuildHasher {
    // 可以在这里定义自定义哈希构建器的参数
}
impl BuildHasher for MyBuildHasher {
    type Hasher = std::collections::hash_map::DefaultHasher;
    fn build_hasher(&self) -> Self::Hasher {
        std::collections::hash_map::DefaultHasher::new()
    }
}
let mut map = HashMap::with_capacity_and_hasher(100, BuildHasherDefault::<MyBuildHasher>::default());

在这个自定义BuildHasher的基础上，可以进一步调整负载因子相关的逻辑来平衡扩容频率和哈希冲突。

批量操作
- 避免频繁的单个插入操作，而是采用批量插入的方式。例如使用extend方法：
```
use std::collections::HashMap;
let mut map = HashMap::new();
let data: Vec<(i32, &str)> = vec![(1, "a"), (2, "b")];
map.extend(data);
```
- 批量操作可以减少扩容的触发次数，因为批量插入时HashMap可以更好地预测所需的容量，从而一次性进行扩容（如果需要的话），而不是在每次插入时都可能触发扩容。

星途面试题库

面试题：Rust HashMap扩容对性能的影响及优化

知识考点

面试题答案

扩容对程序性能的影响

减少扩容性能损耗的代码设计方法