极客笔记C++ STL 中的 unordered_map rehash
在 C++ 中，STL（标准模板库）提供了许多数据结构的实现，其中 unordered_map 是一个常用的哈希表实现。当我们需要在 unordered_map 中添加新的元素时，需要为键（key）和值（value）分配哈希桶（hash bucket）。哈希桶的大小会影响哈希表的性能，而 unordered_map 中实现的哈希桶大小是可以自动调整的。本篇文章将介绍 unordered_map 中的 rehash 函数，它可以用来手动调整哈希表大小。
unordered_map 哈希算法
在深入 rehash 函数之前，我们需要先了解 unordered_map 内部是如何实现哈希算法的。在 unordered_map 中，对于每个元素的键值，都会通过哈希函数得到一个哈希值。C++ STL 提供了一些默认哈希函数，例如 std::hash，可以对大部分常见类型进行哈希。哈希函数的输出是一个无符号整数（unsigned int），并且哈希函数应当尽可能地使键的哈希值均匀地分布在哈希表中。
接着，unordered_map 会根据哈希值对哈希表的大小进行取模运算，得到一个在 0 到哈希表大小之间的下标，用来存储该元素的键值。如果在该下标位置已经存储了元素，就会发生哈希冲突（hash collision）。在哈希冲突的情况下，unordered_map 会采用链式法（chaining）来存储冲突的元素。
使用 unordered_map
在使用 unordered_map 之前，需要先包含头文件 <unordered_map>：
#include <unordered_map>
下面是一个例子，我们将 unordered_map 映射字符串键值到整型值：
#include <unordered_map>
#include <string>
#include <iostream>
int main() {
std::unordered_map<std::string, int> map;
map["one"] = 1;
map["two"] = 2;
map["three"] = 3;
std::cout << map["one"] << std::endl; // 输出 1
std::cout << map["four"] << std::endl; // 输出默认值 0
return 0;
}
上述示例中，我们首先创建了一个空的 unordered_map 对象 map，然后通过运算符重载（operator overloading）将键和值插入到了 map 中。在第 6 行和第 7 行中，我们分别输出了键为 “one” 和 “four” 的值。由于 “one” 存在于 map 中，因此输出 1；而 “four” 不存在于 map 中，因此输出默认值 0。
unordered_map 的桶大小
在使用 unordered_map 时，我们并不需要直接指定哈希表的大小。unordered_map 会自动调整桶（bucket）的大小，以便平衡元素数量和桶的数量。当我们试图将新元素插入 unordered_map 时，如果它的桶已经满了，就会发生 rehash 操作，重新分配更大的桶。这个过程是自动进行的，无需我们关心。但是，如果我们需要手动调整 unordered_map 的桶大小，就可以使用 unordered_map 的 rehash 函数。
unordered_map 的 rehash 函数
unordered_map 的 rehash 函数可以用来手动调整哈希表的桶大小。在 rehash 函数被调用时，unordered_map 会生成一个比原来桶数量更大的素数，然后将哈希表重新映射到新的桶中。因此，调用 rehash 函数会使 unordered_map 的桶数量增加。
unordered_map 的 rehash 函数的使用方式如下：
void rehash( size_typebucket_count );
其中，size_type 是一个无符号整数类型，用于指定新的桶数量。如果显式指定了新的桶数量，rehash 函数将会重新调整桶的数量，使其至少是 size_type 的值，并且大于当前 unordered_map 的元素数量。如果未指定新的桶数量，rehash 函数会将桶数量扩展为当前 unordered_map 元素数量的两倍以上的最小素数。
下面是一个示例，展示了如何使用 rehash 函数来重置 unordered_map 的桶数量：
#include <unordered_map>
#include <string>
#include <iostream>
int main() {
std::unordered_map<std::string, int> map;
map["one"] = 1;
map["two"] = 2;
map["three"] = 3;
std::cout << "bucket count before rehash: " << map.bucket_count() << std::endl;
map.rehash(10);
std::cout << "bucket count after rehash: " << map.bucket_count() << std::endl;
return 0;
}
在上述示例中，我们首先创建了一个包含三个元素的 unordered_map 对象 map。在第 6 行和第 7 行中，我们分别输出了 unordered_map 桶数量的值，结果是 8。在第 8 行中，我们显式调用了 rehash 函数，并将桶数量设置为 10。在第 9 行中，我们再次输出 unordered_map 桶数量的值，结果是 17。说明在调用 rehash 函数后，unordered_map 的桶数量已经增加到了 17。
在实际的应用中，我们可以通过手动调用 rehash 函数先为 unordered_map 分配足够的桶，以便提高哈希表的性能。
unordered_map rehash 的注意事项
在使用 unordered_map 的 rehash 函数时，需要注意以下几点：
- rehash 函数可能会造成 unordered_map 的迭代器失效。如果我们在重新哈希后仍需要继续迭代 unordered_map，则需要重新获取 unordered_map 的迭代器。
-
手动指定桶数量时，应该尽量选择一个合适的值。过小的桶数量会导致哈希冲突概率增加，从而降低 unordered_map 的性能；过大的桶数量会带来额外的空间浪费。通常，桶数量选择 2 的整数幂比选择任意数字要好。
-
rehash 函数可以被多次调用，但频繁调用可能会影响性能。
结论
本文介绍了 C++ STL 中 unordered_map 的 rehash 函数。unordered_map 使用哈希表实现，当桶已满时自动进行 rehash 操作。手动调用 rehash 函数可以手动调整 unordered_map 的桶数量，以满足特定的应用需求。尽管 rehash 函数提供了更灵活的方式解决哈希表的空间管理问题，但我们仍然需要注意 rehash 函数可能带来的迭代器失效以及适当选择桶数量等问题。