这是一个创建于 1314 天前的主题，其中的信息可能已经有所发展或是发生改变。
比如, hash 和 红黑树 哪个更合适.
如果用 hash, 有没有推荐的 hash 算法?
PS: 这个问题我尽量不关联编程语言提问. 实际上我这边是 C++20, 涉及到 std::map, std::unordered_map
第 1 条附言 · 2021-04-19 17:11:25 +08:00
针对 uint64, 我一直觉得肯定有什么最优的解决方案, 只是我没听过, 不知道
第 2 条附言 · 2021-04-19 17:17:39 +08:00
另外我的 key 有个特点, 是一直自增+1 的
第 3 条附言 · 2021-04-19 18:52:57 +08:00
我的业务场景, key 是一直自增 +1, 然后实际 存储数据 大概只有 2 万左右. 然后频繁的会有 插入 删除 查找操作.
避免 hash 桶一直增加下去, 导致内存不够用, 基于我的业务场景, 我自己的 hash:
```C++
struct SessionKeyHash {
std::size_t operator()(const uint64_t &k) const { return (k % HashBucketCount); }
};
```
避免 hash 桶一直增加下去, 导致内存不够用, 基于我的业务场景, 我自己的 hash:
```C++
struct SessionKeyHash {
std::size_t operator()(const uint64_t &k) const { return (k % HashBucketCount); }
};
```
第 4 条附言 · 2021-04-19 18:54:07 +08:00
其中 HashBucketCount 是 1 百万
然后调用 std::unordered_map::rehash(HashBucketCount) 做初始化
然后调用 std::unordered_map::rehash(HashBucketCount) 做初始化
第 5 条附言 · 2021-04-19 19:27:09 +08:00
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, 控制桶的数量
看起来是我多虑了, 我的场景 2 万数据量的情况下, 虽然 key 会一直自增, 但 unordered_map 会一直自动触发 rehash, 控制桶的数量
第 6 条附言 · 2021-04-19 19:41:16 +08:00
理解错了, max_load_factor 只会增加桶的数量, 不会缩减
第 7 条附言 · 2021-04-19 19:50:39 +08:00
```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 是可以自动减的, 想弄懂, 还是得研究源码啊
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 是可以自动减的, 想弄懂, 还是得研究源码啊
 |
1
3dwelcome 2021-04-19 15:53:35 +08:00
红黑树不是挺好的，那么经典。比 hash 好，hash 函数有冲突，红黑树是自平衡，没有潜在问题。
|
 |
2
minami 2021-04-19 16:22:47 +08:00  2
一般推荐用 xxhash 或 murmurhash （ 2 或 3 版本），前者比较好，但后者实现简单
|
 |
3
geelaw 2021-04-19 17:21:04 +08:00 via iPhone
字典树也可以考虑一下。
|
|
4
geelaw 2021-04-19 17:22:03 +08:00 via iPhone
🤧 如果 key 是连续范围且该范围内稠密，考虑用 vector 。
|
|
6
3dwelcome 2021-04-19 18:04:44 +08:00 1
|
|
7
3dwelcome 2021-04-19 18:09:37 +08:00
google 搜“Integer Hash Function", 这才是针对整形 key 的散列函数。
|
|
8
3dwelcome 2021-04-19 18:18:31 +08:00
"第 2 条附言 · 55 分钟前
另外我的 key 有个特点, 是一直自增+1 的" 这种特点可以用二分法查找，自己管理一个集合，未必需要依赖于 C++20，只要保持数据始终内存数序排列就可以。 |
 |
9
ysc3839 2021-04-19 18:40:11 +08:00 via Android
@3dwelcome 这些 hash 函数都是可用于任意二进制数据的，没记错的话 MSVC 的 STL 就是直接用 FNV Hash 去处理整数 key 的。
|
 |
10
DinoStray OP @3dwelcome 我有个问题, 我看标准库的 hash, 对 int 的处理是直接返回 值, 那么如果我的 uint64 key 一直自增下去, 不是会存在桶一直增加, 内存不够用的情况么? unordered_map 会对桶做收缩么
|
|
11
minami 2021-04-19 19:01:44 +08:00
@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; } }; |
|
12
minami 2021-04-19 19:05:51 +08:00
@minami 不好意思，代码里写的 MurmerHash3，实际上查了下是 splitmix64，不知道当年怎么命名的，逃（
|
|
13
DinoStray OP @minami 辛苦您看下, 基于我的业务场景, 我这样重定义 hash 有问题么? 因为我的 key 只是简单自增, 不关联任何业务逻辑. 我只是基于避免桶数量过多, 内存溢出, 所以取余了一下, 限制桶数量
|
 |
14
iceheart 2021-04-19 20:08:57 +08:00 via Android
多频繁？每秒千万次以内查询建议直接 std::map
|
|
15
3dwelcome 2021-04-19 20:39:58 +08:00
|
|
16
DinoStray OP @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 值的 |
Select Language