当前位置：极客教程 > C++语言 > C++ 问答 > 如何在C++中高效使用unordered_map

如何在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);
}
C++

输出：

for 107897 : 2.261 seconds 
for 126271 : 0.024 seconds
C++

显然，其中一个质数的时间复杂度是O(n 2 )。

标准内置的哈希函数与此类似，应用于unordered_map：

struct hash {
    size_t operator()(uint64_t x)
        const { return x; }
};
C++

上述函数可能会产生许多冲突。插入在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);
    }
};
C++

基本上，上面的哈希函数生成随机哈希值以存储键。欲了解更多信息，请参考这篇文章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);
}
C++

输出：

for 107897 : 0.025 seconds 
for 126271 : 0.024 seconds
C++

预先分配空间

默认情况下，unordered_map的容量是16，并为此创建了哈希表。 但是，每次达到阈值时，unordered_map的容量会增加一倍，并根据新的哈希表重新为所有值进行哈希处理。

因此，我们可以使用.reserve()方法预先根据我们的输入大小保留容量。

umap.reserve(1024);
C++

1024可以根据输入大小替换为任何int值。 这可以防止重新哈希和动态分配，从而使程序更有效。

设置max_load_factor

unordered_map 的 max_load_factor 确定了碰撞的概率。默认值为1。

将其设置为较低的值，如0.25，可以大大减少碰撞的概率。

umap.max_load_factor(0.25);
C++

示例： 使用上述两种方法可以使 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);
}
C++

输出：

for 107897 : 0.029 秒
for 126271 : 0.026 秒
C++

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

C++ 精品教程

登录

找回密码？

注册