面试题：Rust中HashMap扩容策略的基本原理

Question

简述Rust中HashMap在什么情况下会发生扩容，以及扩容过程中的大致操作步骤。

Answer 1

扩容情况

当HashMap的负载因子（load factor）超过一定阈值时会发生扩容。Rust中HashMap默认的负载因子阈值是0.75，即当哈希表中元素的数量（len）与容量（capacity）的比例达到或超过0.75时，就会触发扩容。

扩容步骤

1. 计算新容量：扩容时，HashMap会分配一个新的、更大的容量。新容量通常是原容量的两倍。
2. 分配新内存：根据新容量，在堆上分配一块新的内存空间，用于存储新的哈希表数据。
3. 重新哈希和迁移：将旧哈希表中的所有键值对重新计算哈希值，并根据新的哈希值将它们插入到新的哈希表中。这个过程称为“重哈希（rehashing）”。在插入过程中，由于新的哈希表大小改变，键值对可能会被放置到与旧表不同的位置。
4. 释放旧内存：当所有键值对都迁移到新的哈希表后，旧的哈希表内存将被释放。