使用 uint64 作为 map 的 key, 有哪些优化技巧?

[DinoStray]

比如, hash 和 红黑树 哪个更合适.
如果用 hash, 有没有推荐的 hash 算法?

PS: 这个问题我尽量不关联编程语言提问. 实际上我这边是 C++20, 涉及到 std::map, std::unordered_map

针对 uint64, 我一直觉得肯定有什么最优的解决方案, 只是我没听过, 不知道

另外我的 key 有个特点, 是一直自增+1 的

我的业务场景, key 是一直自增 +1, 然后实际 存储数据 大概只有 2 万左右. 然后频繁的会有 插入 删除 查找操作.
避免 hash 桶一直增加下去, 导致内存不够用, 基于我的业务场景, 我自己的 hash:
```C++
struct SessionKeyHash {
std::size_t operator()(const uint64_t &k) const { return (k % HashBucketCount); }
};
```

其中 HashBucketCount 是 1 百万
然后调用 std::unordered_map::rehash(HashBucketCount) 做初始化

The container uses the value of max_load_factor as the threshold that forces an increase in the number of buckets (and thus causing a rehash).
看起来是我多虑了, 我的场景 2 万数据量的情况下, 虽然 key 会一直自增, 但 unordered_map 会一直自动触发 rehash, 控制桶的数量

理解错了, max_load_factor 只会增加桶的数量, 不会缩减

```C++
std::unordered_map<int, int> map;
std::cout << map.bucket_count() << std::endl;
std::cout << map.load_factor() << std::endl;
std::cout << map.max_load_factor() << std::endl;
std::cout << "===========" << std::endl;
for (int i = 0; i < 59481497; ++i) {
map[i] = i;
if (i % 3 == 0) { map.erase(i); }
}
std::cout << map.size() << std::endl;
// 101473717
std::cout << map.bucket_count() << std::endl;
std::cout << map.load_factor() << std::endl;
std::cout << map.max_load_factor() << std::endl;
```

写了个 testcase , 发现 bucket 是可以自动减的, 想弄懂, 还是得研究源码啊

[3dwelcome]

红黑树不是挺好的，那么经典。比 hash 好，hash 函数有冲突，红黑树是自平衡，没有潜在问题。

[minami]

一般推荐用 xxhash 或 murmurhash （ 2 或 3 版本），前者比较好，但后者实现简单

[geelaw]

字典树也可以考虑一下。

[geelaw]

🤧 如果 key 是连续范围且该范围内稠密，考虑用 vector 。

[DinoStray]

@geelaw 因为会频繁的增加删除, 所以长时间运行后是不连续的了

[3dwelcome]

@minami 没有审题啊，楼主 key 是 integer，又不是 string 。你这两个算法都是针对字符串的。

有专门针对 uint64_t 的 hash 函数，你一个都没提到。

[3dwelcome]

google 搜“Integer Hash Function", 这才是针对整形 key 的散列函数。

[3dwelcome]

"第 2 条附言 · 55 分钟前
另外我的 key 有个特点, 是一直自增+1 的"

这种特点可以用二分法查找，自己管理一个集合，未必需要依赖于 C++20，只要保持数据始终内存数序排列就可以。

[ysc3839]

@3dwelcome 这些 hash 函数都是可用于任意二进制数据的，没记错的话 MSVC 的 STL 就是直接用 FNV Hash 去处理整数 key 的。

[DinoStray]

@3dwelcome 我有个问题, 我看标准库的 hash, 对 int 的处理是直接返回 值, 那么如果我的 uint64 key 一直自增下去, 不是会存在桶一直增加, 内存不够用的情况么? unordered_map 会对桶做收缩么

[minami]

@3dwelcome 你是认真的吗，我特地去我以前代码里翻出了针对 uint64_t 的 MurmerHash3
struct MurmerHash3
{
inline std::size_t operator()(const uint64_t &key) const noexcept
{
uint64_t x = (key ^ (key >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
x = x ^ (x >> 31);
return x;
}
};

[minami]

@minami 不好意思，代码里写的 MurmerHash3，实际上查了下是 splitmix64，不知道当年怎么命名的，逃（

[DinoStray]

@minami 辛苦您看下, 基于我的业务场景, 我这样重定义 hash 有问题么? 因为我的 key 只是简单自增, 不关联任何业务逻辑. 我只是基于避免桶数量过多, 内存溢出, 所以取余了一下, 限制桶数量

[iceheart]

多频繁？每秒千万次以内查询建议直接 std::map

[3dwelcome]

@DinoStray "我有个问题, 我看标准库的 hash, 对 int 的处理是直接返回 值, 那么如果我的 uint64 key 一直自增下去, 不是会存在桶一直增加, 内存不够用的情况么?"

刚刚我用 VS2017 调试了一下，和 9 楼的 @ysc3839 同学说的一致，内部对于 uint64_t 都用 FNV-1a hash function 算法处理过一次，不是直接返回的。

既然数列已经打散了，就不用担心 hash 冲突，会内存不够吧。

[DinoStray]

@3dwelcome g++ (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
我这边用这个做实验.
```
std::unordered_map<uint64_t, uint64_t> map{};
std::cout << "1: " << map.hash_function()(1) << std::endl;
std::cout << "50000: " << map.hash_function()(50000) << std::endl;
```
结果是
1
50000

看来 g++ 的实现, 是直接返回 uint64 值的