如何在C++中高效使用unordered_map

如何在C++中高效使用unordered_map

C++提供了std::unordered_set和std::unordered_map,分别用作哈希集和哈希映射。它们在常数平均时间内执行插入/删除/访问操作。

  1. 然而,最坏情况的复杂度为O(n 2 )。
  2. 原因是unordered_map通过输入值取模质数来存储键值对,然后将其存储在哈希表中。
  3. 当输入的数据很大且输入值是这个质数的倍数时,会发生很多冲突,可能导致O(n 2 )的复杂度。
  4. 根据编译器不同,质数可能是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 秒

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程