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

[DinoStray]

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

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

[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 值的