C++ STL 中 unordered_map 的 load_factor

什么是 load_factor

load_factor 是指 unordered_map 中当前元素个数与桶数的比值。

一般情况下，load_factor 的默认值是 1，表示元素个数等于桶数。

当 load_factor 大于 1 时，意味着桶中的元素较多，可能会影响查找效率。因此，一般情况下，我们会根据实际情况来调整 load_factor 的值。

unordered_map 的官方文档

下面是 unordered_map 的官方文档中对于 load_factor 的解释。

Load factor is the ratio between the number of elements in the container (its size) and the number of buckets (bucket_count). The load factor influences the probability of collision in the hash table, and thus the probability of a hash function to become inefficient due to an increased number of collisions. By default, unordered_map containers have a load factor of 1.0.

意思是说，“load_factor”是容器中元素数（大小）与桶数（bucket_count）之间的比率。此值影响哈希表中冲突的概率，进而影响哈希函数由于冲突数量的增加而变得低效的概率。默认情况下， unordered_map 容器的 load_factor 值为 1.0。

如何设置 load_factor

在 C++11 中，我们可以使用 unordered_map::max_load_factor(float z) 方法来设置 load_factor。

该方法接受一个浮点数 z 作为参数，表示期望的最大 load_factor。

如下示例代码中，我们将 load_factor 设置为 0.7：

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<int, string> my_map(8);
    my_map.insert({{1, "apple"}, {2, "banana"}, {3, "orange"}, {4, "peach"}, {5, "grape"}, {6, "watermelon"}, {7, "pear"}, {8, "pineapple"}});
    cout << "my_map size: " << my_map.size() << endl;            // 输出 8
    cout << "my_map load_factor: " << my_map.load_factor() << endl;  // 输出 1
    my_map.max_load_factor(0.7);
    cout << "my_map max_load_factor: " << my_map.max_load_factor() << endl;  // 输出 0.7
    my_map.rehash(ceil(my_map.size() / my_map.max_load_factor()));  // 重新分配桶
    cout << "my_map bucket_count: " << my_map.bucket_count() << endl;  // 输出 11
    return 0;
}

在此示例代码中，我们先创建了一个 unordered_map 容器，并向容器中插入了 8 个键值对。输出容器的大小和 load_factor 值后，我们将 load_factor 值设置为 0.7，并输出设置后的最大 load_factor 值。接着，我们使用 ceil() 函数计算出新的 bucket 数量，然后使用 rehash() 方法重新分配桶。最后，我们输出重新分配后的 bucket 数量。