这是一个创建于 1060 天前的主题，其中的信息可能已经有所发展或是发生改变。
各位大佬，请问一下 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
11 条回复 • 2022-01-11 00:50:37 +08:00
 |
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 1
@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 |
Select Language