如何在C++中高效使用unordered_map
C++提供了std::unordered_set和std::unordered_map,分别用作哈希集和哈希映射。它们在常数平均时间内执行插入/删除/访问操作。
- 然而,最坏情况的复杂度为O(n 2 )。
- 原因是unordered_map通过输入值取模质数来存储键值对,然后将其存储在哈希表中。
- 当输入的数据很大且输入值是这个质数的倍数时,会发生很多冲突,可能导致O(n 2 )的复杂度。
- 根据编译器不同,质数可能是107897或126271。
示例1: 如果我们插入上述两个质数的倍数并计算执行时间。其中一个质数的执行时间比另一个长得多。
// C++ program to determine worst case
// time complexity of an unordered_map
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
int N = 55000;
int prime1 = 107897;
int prime2 = 126271;
void insert(int prime)
{
// Starting the clock
auto start
= high_resolution_clock::now();
unordered_map<int, int> umap;
// Inserting multiples of prime
// number as key in the map
for (int i = 1; i <= N; i++)
umap[i * prime] = i;
// Stopping the clock
auto stop
= high_resolution_clock::now();
// Typecasting the time to
// milliseconds
auto duration
= duration_cast<milliseconds>(
stop - start);
// Time in seconds
cout << "for " << prime << " : "
<< duration.count() / 1000.0
<< " seconds "
<< endl;
}
// Driver code
int main()
{
// Function call for prime 1
insert(prime1);
// Function call for prime 2
insert(prime2);
}
输出:
for 107897 : 2.261 seconds
for 126271 : 0.024 seconds
显然,其中一个质数的时间复杂度是O(n 2 )。
标准内置的哈希函数与此类似,应用于unordered_map:
struct hash {
size_t operator()(uint64_t x)
const { return x; }
};
上述函数可能会产生许多冲突。插入在HashMap中的键不均匀分布,并且在插入大量质数倍数后,进一步插入会导致哈希函数将所有先前的键重新分配到新的槽中,从而使其变慢。因此,我们的想法是要随机化哈希函数。
我们的想法是使用一种方法,使我们哈希映射中的键均匀分布。这将防止发生冲突。为此,我们使用斐波那契数列。与斐波那契数列相关的黄金比例(Phi = 1.618)具有一个性质,即它可以将任何范围平均分成若干段,而不需要回到起始位置。
我们可以创建自己的简单哈希函数。下面是哈希函数:
struct modified_hash {
static uint64_t splitmix64(uint64_t x)
{
// 0x9e3779b97f4a7c15,
// 0xbf58476d1ce4e5b9,
// 0x94d049bb133111eb 是一些数字,
// 它们是通过将高次二分之一的Phi
// (1.6180 ..)进行除法获得的。
// 通过这种方式,将
// x的值进行修改,
// 以均匀地分配
// 在哈希表中的键。
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
int operator()(uint64_t x) const
{
static const uint64_t random
= steady_clock::now()
.time_since_epoch()
.count();
// 上面的代码使用高精度时钟
// 生成随机数
return splitmix64(
// 返回最终哈希值
x + random);
}
};
基本上,上面的哈希函数生成随机哈希值以存储键。欲了解更多信息,请参考这篇文章Fibonacci哈希。
示例2: 使用上面的哈希函数,程序运行得非常快。
// C++程序,用于确定无序_map
// 使用修改后的哈希函数的最坏情况下的时间复杂度
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
struct modified_hash {
static uint64_t splitmix64(uint64_t x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30))
* 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27))
* 0x94d049bb133111eb;
return x ^ (x >> 31);
}
int operator()(uint64_t x) const
{
static const uint64_t random
= steady_clock::now()
.time_since_epoch()
.count();
return splitmix64(x + random);
}
};
int N = 55000;
int prime1 = 107897;
int prime2 = 126271;
// 在 hashMap 中插入函数
void insert(int prime)
{
auto start = high_resolution_clock::now();
// unordered_map初始化中的第三个参数
// 确保map使用哈希函数
unordered_map<int, int, modified_hash>
umap;
// 将质数的倍数插入到 map 中作为键
for (int i = 1; i <= N; i++)
umap[i * prime] = i;
auto stop
= high_resolution_clock::now();
auto duration
= duration_cast<milliseconds>(
stop - start);
cout << "for " << prime << " : "
<< duration.count() / 1000.0
<< " seconds "
<< endl;
}
// 主函数int main()
{
// prime1 的函数调用
insert(prime1);
// prime2 的函数调用
insert(prime2);
}
输出:
for 107897 : 0.025 seconds
for 126271 : 0.024 seconds
预先分配空间
默认情况下,unordered_map的容量是16,并为此创建了哈希表。 但是,每次达到阈值时,unordered_map的容量会增加一倍,并根据新的哈希表重新为所有值进行哈希处理。
因此,我们可以使用.reserve()方法预先根据我们的输入大小保留容量。
umap.reserve(1024);
1024可以根据输入大小替换为任何int值。 这可以防止重新哈希和动态分配,从而使程序更有效。
设置max_load_factor
unordered_map 的 max_load_factor 确定了碰撞的概率。默认值为1。
将其设置为较低的值,如0.25,可以大大减少碰撞的概率。
umap.max_load_factor(0.25);
示例: 使用上述两种方法可以使 umap 更快:
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
int N = 55000;
int prime1 = 107897;
int prime2 = 126271;
void insert(int prime)
{
// 启动时钟
auto start
= high_resolution_clock::now();
unordered_map<int, int> umap;
umap.reserve(1024); // 提前保留空间
umap.max_load_factor(0.25); // 减小 max_load_factor
// 将 prime 数的倍数插入到 map 中
for (int i = 1; i <= N; i++)
umap[i * prime] = i;
// 停止时钟
auto stop
= high_resolution_clock::now();
// 将时间强制转换成毫秒
auto duration
= duration_cast<milliseconds>(
stop - start);
// 时间(秒数)
cout << "for " << prime << " : "
<< duration.count() / 1000.0
<< " 秒 "
<< endl;
}
// 主函数
int main()
{
// prime1 的函数调用
insert(prime1);
// prime2 的函数调用
insert(prime2);
}
输出:
for 107897 : 0.029 秒
for 126271 : 0.026 秒