Rust 中 HashMap 的容量（Rust 实践）

Question

我目前正在进行“Rust by Practice”练习。在“Collection Types > HashMap”部分有一个示例：

use std::collections::HashMap;
fn main() {
    let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
    map.insert(1, 2);
    map.insert(3, 4);
    // Indeed ,the capacity of HashMap is not 100, so we can't compare the equality here.
    assert!(map.capacity() >= 100);
    
    println!("Capacity #1: {}", map.capacity());

    // Shrinks the capacity of the map with a lower limit. It will drop
    // down no lower than the supplied limit while maintaining the internal rules
    // and possibly leaving some space in accordance with the resize policy.

    map.shrink_to(50);
    assert!(map.capacity() >= 50);
    
    println!("Capacity #2: {}", map.capacity());

    // Shrinks the capacity of the map as much as possible. It will drop
    // down as much as possible while maintaining the internal rules
    // and possibly leaving some space in accordance with the resize policy.
    map.shrink_to_fit();
    assert!(map.capacity() >= 2);
    
    println!("Capacity #3: {}", map.capacity());
    
    println!("Success!");
}

运行上面的程序我得到以下输出：

Capacity #1: 112
Capacity #2: 56
Capacity #3: 3
Success!

我的问题如下：

我们将一个容量为 100 个（元素）的空 HashMap 分配给变量map。然后我们将两个元素插入到所述 HashMap 中。所以整个HashMap的长度为2个元素。所以我们有 98 个地方可以插入更多元素，对吧？那么为什么Rust编译器在这里将容量扩展到112呢？

另外，当我们将 HashMap 的容量缩小到 50 时，实际容量似乎是 53，尽管里面仍然只有 2 个元素。

第三个输出也是如此。有人可以向我解释一下这里发生了什么吗？

Answer 1

我们为变量map分配一个容量为100（元素）的空HashMap。然后我们将两个元素插入到所述 HashMap 中。所以整个HashMap的长度为2个元素。所以我们有 98 个地方可以插入更多元素，对吧？那么为什么Rust编译器在这里将容量扩展到112呢？

如果你检查分配后的容量，你会发现它已经是112了，这不是插入导致的扩展。

但关于为什么会这样的答案实际上是在代码中找到的，并没有真正记录下来。

首先，hashmap不能 % 满：为了限制冲突（以及随之而来的性能下降），它必须保留“闲置空间”，其数量取决于哈希图的实现（特别是其冲突）分辨率算法）。“可用”散列图（减去闲置空间）与“总”散列图大小的比率称为“负载因子”，例如，如果散列图的负载因子为 75%，则在调整大小（扩展）之前，它最多会满 75% ）。

在 Rust 的 hashmap 中，负载率相当高，接近 90%（具体来说是 7/8，即 87.5%）。如果将此应用于您的请求 (100 / 0.875)，您将得到 114.29，这...不是我们得到的。PlusHashMap::capacity在返回之前会应用负载系数，因此如果内部容量为 115 ¹，则应返回 100。

第二位是，由于计算机和位图的原因，hashbrown 将从负载因子获得的“内部”容量四舍五入到最接近的 2 的 2 次幂^，因此当您为 100 个项目请求足够的空间时，它首先应用负载因子115，然后四舍五入为 128。

当您请求时，capacity()它会将负载系数应用于实际内部容量，128 / 8 * 7 = 112，而鲍勃是您的叔叔。

50 的情况相同，除以负载系数为 57，四舍五入为 64，乘以负载系数 = 56。

2 的本质上是相同的，尽管它实际上是特殊情况：4 以下的内部容量向上舍入为 4 (capacity() = 3)，4 以上但低于 8 的内部容量向上舍入为 8 (capacity() = 7) 。

您可以在 中找到确切的代码capacity_to_buckets。

1：数组中不能有小数单元格，因此容量必须向上舍入

2：如果“真实”容量是2的幂，则hashmap只能存储2的幂，最多为64（对于2 ⁶⁴），因此适合单个字节，否则需要8个字节，它还使用位图来存储哪些条目已满/空，这样位图的大小始终与实际容量匹配