c++哈希表的问题

[learningmachine]

各位大佬，请问一下 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

[Austin2035]

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

[Austin2035]

而且也封装为字典了，可以拿来玩玩。

[liberize]

https://github.com/sparsehash/sparsehash

[learningmachine]

@lookcos 谢谢回答，其实我更加希望找到一个关于用 open addressing 实现的库

[learningmachine]

@liberize 谢谢，我去了解一下

[billwsy]

absl::flat_hash_set 可以吗？

[GeruzoniAnsasu]

…………

我去看了半天你附的原视频
首先时间对不上…… 原视频讲 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 候选，理论上来说跟他这种实现不会有什么区别

[anonymousar]

folly F14FastMap

[111qqz]

之前做过调研和实验。 可以看下 ska::flat_hash_map. find 时间是 std::unordered_map 的三分之一，内存也会有所节省。 已经在我们线上服务广泛使用了。 当时有个分析报告可以参考下 https://111qqz.com/2021/08/ska_flat_hash_map_notes/

[learningmachine]

@GeruzoniAnsasu 我去看了下我贴的地址，很抱歉，确实是指错地方了。

首先谢谢你认真的回答，以及对视频中提到的点的解释。
我在看视频的时候也是想到 「相邻槽已经被读入 cache 了」，所以在想会不会快一些，所以想找些轮子做一下 benchmark 看下是不是真的会快一些。

第一点代码实现的角度和第二点线性探查的聚集的问题，如果不提醒确实很容易忽视这些问题都存在。
第四点的 key+ptr 的实现很精彩，我之前也搜索过一些回答，线性探查的实现会限制于数组大小，而 key+ptr 这种方式却不会。
https://stackoverflow.com/questions/2556142/chained-hash-tables-vs-open-addressed-hash-tables

第三点中的经典实现是指 key+value 组成的结构体放在一个 hash 的 bucket 里面吗？如果是这样的话，确实是比视频中的方式，即再访问一次内存要好。

很厉害的回答！

[learningmachine]

@billwsy @anonymousar 谢谢两位的指路，我去研究研究

@111qqz 是一位刷了 CSAPP 和 6.828 的大手子，谢谢你的回答，我学习下～