各位大佬,请问一下 c++ 有什么成熟的库是用 open addressing 方式实现的哈希表实现吗?
我在 cpp conf 上看到 open addressing 会比 chain 的方式 chaining 的方式在利用 cache 会更好一下,但是找了一圈没看到有合适的轮子可以用。
cpp conf 的地址: https://www.youtube.com/watch?v=NH1Tta7purM&list=PLisIt4C4pt0heJZ5sdzI6poWegjGxBTEi&index=1&t=985s
1
Austin2035 2022-01-09 19:48:57 +08:00 1
open addressing 就是开放定地址法吧。
一般来说,Java 中 HashMap(哈希表)是用[数组+红黑树]实现的,Redis 中是[数组+链表]。 可以看一下我的哈希表教程,参考了 Redis 的写法。 https://github.com/LookCos/learn-data-structures/tree/main/2.5%20%E5%93%88%E5%B8%8C%E8%A1%A8 |
2
Austin2035 2022-01-09 19:49:53 +08:00
而且也封装为字典了,可以拿来玩玩。
|
3
liberize 2022-01-09 21:04:36 +08:00 via Android 1
|
4
learningmachine OP @lookcos 谢谢回答,其实我更加希望找到一个关于用 open addressing 实现的库
|
5
learningmachine OP @liberize 谢谢,我去了解一下
|
6
billwsy 2022-01-10 01:32:28 +08:00 via iPhone
absl::flat_hash_set 可以吗?
|
7
GeruzoniAnsasu 2022-01-10 04:10:10 +08:00 3
…………
我去看了半天你附的原视频 首先时间对不上…… 原视频讲 hash map / unordered_map 的部分在「 fast associative containers 」这节( t=1532 ) 然后更重要的点在于,原视频并没有讲开放定址法会更快 仅仅是提了一下「 or you can use something like google's dense hash map 」这个 hash map 是 open addressing 实现,它的优势是不需要链表但 hash 冲突会难以管理。 然后引出了他要表达的关键思路: 尝试一种能混合两种 hash table 优点的新实现。 并且介绍了一下他们自己的 hash table 大概原理是怎样的: 1. 把 hash 和指向元素的指针放在一起 2. (!!)当查找元素发现对应 slot 的 hash 不对时(即在查的 hash 冲突),那么根据空槽探测法(尤指线性法)就会去尝试相邻的下一个槽,而相邻槽已经被读入 cache 了,所以会很快 但是呢 1. 在他的 benchmark 里,10 个样本量也已经比 std::unordered_map 快了一倍,说明主要效率提升其实并不是 open addressing 的效果,而是他的代码本来也更快 2. 他的实现中,提高 cache 命中率与线性探测法是相互绑定的,因此没有提线性探测容易带来的聚集问题 3. 他的实现提升了查找冲突元素的 cache 命中率,但完全牺牲了访问 value 的命中率,因此在理想状态(即不存在冲突)的场景下,他的实现是要比「经典实现」(即 key 和 value 和 hash 都在一起)要慢的,查找时 hash 冲突的几率有多高,你在自己的场景下还得考虑 4. 由于他这个例子优化有效的场景就在发生冲突时,所以基于同样的思路你完全可以在链地址法的实现中进行优化: 给你的冲突链预先分配一定的连续空间,在连续空间中放跟他例子一样的 key+ptr 结构,当冲突时也是一次性读完所有的 key 候选,理论上来说跟他这种实现不会有什么区别 |
8
anonymousar 2022-01-10 09:18:45 +08:00
folly F14FastMap
|
9
111qqz 2022-01-10 20:18:54 +08:00
之前做过调研和实验。 可以看下 ska::flat_hash_map. find 时间是 std::unordered_map 的三分之一,内存也会有所节省。 已经在我们线上服务广泛使用了。 当时有个分析报告可以参考下 https://111qqz.com/2021/08/ska_flat_hash_map_notes/
|
10
learningmachine OP @GeruzoniAnsasu 我去看了下我贴的地址,很抱歉,确实是指错地方了。
首先谢谢你认真的回答,以及对视频中提到的点的解释。 我在看视频的时候也是想到 「相邻槽已经被读入 cache 了」,所以在想会不会快一些,所以想找些轮子做一下 benchmark 看下是不是真的会快一些。 第一点代码实现的角度和第二点线性探查的聚集的问题,如果不提醒确实很容易忽视这些问题都存在。 第四点的 key+ptr 的实现很精彩,我之前也搜索过一些回答,线性探查的实现会限制于数组大小,而 key+ptr 这种方式却不会。 https://stackoverflow.com/questions/2556142/chained-hash-tables-vs-open-addressed-hash-tables 第三点中的经典实现是指 key+value 组成的结构体放在一个 hash 的 bucket 里面吗?如果是这样的话,确实是比视频中的方式,即再访问一次内存要好。 很厉害的回答! |
11
learningmachine OP |