比如, hash 和 红黑树 哪个更合适.
如果用 hash, 有没有推荐的 hash 算法?
PS: 这个问题我尽量不关联编程语言提问. 实际上我这边是 C++20, 涉及到 std::map, std::unordered_map
This topic created in 1873 days ago, the information mentioned may be changed or developed.
Supplement 1 Apr 19, 2021
针对 uint64, 我一直觉得肯定有什么最优的解决方案, 只是我没听过, 不知道
Supplement 2 Apr 19, 2021
另外我的 key 有个特点, 是一直自增+1 的
Supplement 3 Apr 19, 2021
我的业务场景, 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); }
};
```
Supplement 4 Apr 19, 2021
其中 HashBucketCount 是 1 百万
然后调用 std::unordered_map::rehash(HashBucketCount) 做初始化
然后调用 std::unordered_map::rehash(HashBucketCount) 做初始化
Supplement 5 Apr 19, 2021
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, 控制桶的数量
Supplement 6 Apr 19, 2021
理解错了, max_load_factor 只会增加桶的数量, 不会缩减
Supplement 7 Apr 19, 2021
```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 Apr 19, 2021 红黑树不是挺好的，那么经典。比 hash 好，hash 函数有冲突，红黑树是自平衡，没有潜在问题。 |
 | 2 minami Apr 19, 2021  2 一般推荐用 xxhash 或 murmurhash （ 2 或 3 版本），前者比较好，但后者实现简单 |
 | 3 geelaw Apr 19, 2021 via iPhone 字典树也可以考虑一下。 |
| 4 geelaw Apr 19, 2021 via iPhone 如果 key 是连续范围且该范围内稠密，考虑用 vector 。 |
| 6 3dwelcome Apr 19, 2021 1 |
| 7 3dwelcome Apr 19, 2021 google 搜“Integer Hash Function", 这才是针对整形 key 的散列函数。 |
| 8 3dwelcome Apr 19, 2021 "第 2 条附言 55 分钟前 另外我的 key 有个特点, 是一直自增+1 的" 这种特点可以用二分法查找，自己管理一个集合，未必需要依赖于 C++20，只要保持数据始终内存数序排列就可以。 |
 | 9 ysc3839 Apr 19, 2021 via Android @3dwelcome 这些 hash 函数都是可用于任意二进制数据的，没记错的话 MSVC 的 STL 就是直接用 FNV Hash 去处理整数 key 的。 |
 | 10 DinoStray OP @3dwelcome 我有个问题, 我看标准库的 hash, 对 int 的处理是直接返回 值, 那么如果我的 uint64 key 一直自增下去, 不是会存在桶一直增加, 内存不够用的情况么? unordered_map 会对桶做收缩么 |
| 11 minami Apr 19, 2021 @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; } }; |
| 13 DinoStray OP @minami 辛苦您看下, 基于我的业务场景, 我这样重定义 hash 有问题么? 因为我的 key 只是简单自增, 不关联任何业务逻辑. 我只是基于避免桶数量过多, 内存溢出, 所以取余了一下, 限制桶数量 |
 | 14 iceheart Apr 19, 2021 via Android 多频繁？每秒千万次以内查询建议直接 std::map |
| 15 3dwelcome Apr 19, 2021 |
| 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