Rust中HashMap的容量(Rust by Practice)

nr9pn0ug  于 2023-04-30  发布在  其他
关注(0)|答案(1)|浏览(213)

我现在正在进行“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个元素。
第三个输出也是如此。有人能给我解释一下这是怎么回事吗?

lsmepo6l

lsmepo6l1#

我们分配一个容量为100(元素)的空HashMap给变量map。然后我们将两个元素插入到HashMap中。因此,整个HashMap的长度为2个元素。所以我们有98个地方可以插入更多的元素,对吗?那么为什么Rust编译器在这里将容量扩展到112?
如果你检查分配后的容量,你会发现它已经是112了,不是插入导致了扩展。
但是为什么它的答案实际上是在代码中找到的,它没有真正的文档。
首先,hashmap不能100%满,它必须保留“松弛空间”,其数量取决于hashmap的实现,这被称为“加载因子”。在Rust的hashmap中,负载因子相当高,接近90%(具体来说是7/8,或者87。5%)。如果你将此应用于你的请求,你会得到114。28,这…不是我们得到的加上HashMap::capacity在返回之前应用了加载因子,所以如果内部容量是115,它应该返回100。
第二点是,由于计算机和位图的原因,hashbrown将从加载因子获得的“内部”容量四舍五入到最接近的2的幂,因此当您请求足够的空间容纳100个项目时,首先应用加载因子获得115,然后将其四舍五入到128。
当你要求capacity()时,它会将负载因子应用到真实的内部容量,128 / 8 * 7 = 112,bob就是你的叔叔。
同样的楼层,50除以荷载系数等于57,取整到64,乘以荷载系数= 56。
2基本上是一样的,尽管它实际上是特殊情况:小于4的内部容量向上舍入为4(capacity()= 3),大于4但小于8的内部容量向上舍入为8(capacity()= 7)。
您可以在capacity_to_buckets中找到确切的代码。

相关问题