C++ 高性能容器：ankerl::unordered_dense::map
介绍
ankerl::unordered_dense::map 是一个 高性能哈希表容器，来自开源库 unordered_dense，由 Martin Ankerl 开发。
它的作用和标准库中的 std::unordered_map 类似，用于存储键值对，但有以下优点：
| 特性 | 说明 |
|---|---|
| 🚀 更快 | 性能通常比 std::unordered_map 更好，特别是在查找、插入、大量数据时 |
| 📦 内存紧凑 | 内存布局更紧凑，缓存友好，避免了节点式内存开销 |
| 🔁 开放寻址 (Open Addressing) | 使用了 Robin Hood Hashing，避免链表结构，提升性能一致性 |
| 🧠 数据局部性更好 | 有利于 CPU 缓存利用，提升实际运行速度 |
| 🛠️ 无依赖 | 是一个头文件库，直接包含即可使用，不需要链接其他库 |
和std::unordered_map的区别
| 项目 | std::unordered_map | ankerl::unordered_dense::map |
|---|---|---|
| 结构 | 链表式哈希桶 | 扁平数组 + Robin Hood |
| 查找性能 | 中等，可能退化 | 极快且稳定 |
| 内存使用 | 较高（每个节点有额外指针） | 更低 |
| 迭代顺序 | 不确定 | 稳定迭代（插入顺序） |
| 线程安全 | 无 | 无 |
| C++标准 | C++11 以上 | C++17 以上（推荐） |
测试目标
- 插入 N 个随机整数作为键，值为序号
- 随机查找 N 次，记录时间消耗
- 对比两个容器的性能差异
#include <iostream>
#include <unordered_map>
#include <ankerl/unordered_dense.h>
#include <chrono>
#include <vector>
#include <random>constexpr size_t N = 1'000'000;std::vector<int> generate_random_keys(size_t n) {std::vector<int> keys(n);std::mt19937 rng(12345);std::uniform_int_distribution<int> dist(1, n * 10);for (size_t i = 0; i < n; ++i) {keys[i] = dist(rng);}return keys;
}template<typename Map>
void benchmark(const std::string& name, const std::vector<int>& keys) {Map map;auto t1 = std::chrono::high_resolution_clock::now();for (size_t i = 0; i < keys.size(); ++i) {map[keys[i]] = static_cast<int>(i);}auto t2 = std::chrono::high_resolution_clock::now();std::cout << name << " insert time: "<< std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count()<< " ms\n";size_t found = 0;auto t3 = std::chrono::high_resolution_clock::now();for (size_t i = 0; i < keys.size(); ++i) {if (map.find(keys[i]) != map.end()) {++found;}}auto t4 = std::chrono::high_resolution_clock::now();std::cout << name << " lookup time: "<< std::chrono::duration_cast<std::chrono::milliseconds>(t4 - t3).count()<< " ms (found: " << found << ")\n\n";
}int main() {auto keys = generate_random_keys(N);benchmark<std::unordered_map<int, int>>("std::unordered_map", keys);benchmark<ankerl::unordered_dense::map<int, int>>("ankerl::unordered_dense::map", keys);return 0;
}
总结
| 操作 | std::unordered_map | ankerl::unordered_dense::map | 差距 |
|---|---|---|---|
| 插入 100 万个键 | 慢 | 快 | ✅ |
| 查找 100 万个键 | 慢 | 快 | ✅ |
| 内存占用 | 高 | 低 | ✅ |
| 代码兼容性 | 标准 | 非标准 | ⚠️ |
为什么两者会有这样的差距
1、底层实现结构不同
| 特性 | std::unordered_map | ankerl::unordered_dense::map |
|---|---|---|
| 哈希碰撞处理 | 分离链接（chaining） 每个桶是链表或红黑树 | 开放寻址（open addressing） Robin Hood Hashing |
| 存储结构 | 哈希桶数组 + 动态链表节点 | 扁平数组，紧凑布局 |
| 内存分布 | 离散（每个节点分配在堆上） | 连续（所有元素集中在数组中） |
2、CPU 缓存友好性
现代 CPU 在访问内存时，最重要的就是 cache locality（缓存局部性）。
- std::unordered_map 节点式结构，数据跳跃，cache miss 多。
- ankerl::unordered_dense::map 紧凑数组结构，cache hit 高，速度自然快。
3、内存分配频率
- std::unordered_map 插入每个元素时都需要 独立分配节点内存，开销大。
- ankerl::unordered_dense::map 一次性分配数组空间，插入快得多。
4、哈希冲突处理方式不同
-
std::unordered_map 用链表或红黑树存储冲突项 → 查找时间不稳定（最差的情况是退化成单链表）
-
ankerl::unordered_dense::map 用 Robin Hood Hashing：
-
冲突时较老元素会被“抢占”回前面
-
查找路径更平均 → 查找速度更稳定
-
5、内存占用对比
-
std::unordered_map 每个节点有额外结构：指针、allocator header 等
-
ankerl::unordered_dense::map 只需两个数组（key-value + metadata）
参考链接
https://zhuanlan.zhihu.com/p/1891902733864375991