V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
learningmachine
V2EX  ›  程序员

c++哈希表的问题

  •  
  •   learningmachine · 2022-01-09 17:20:16 +08:00 · 2495 次点击
    这是一个创建于 1038 天前的主题,其中的信息可能已经有所发展或是发生改变。

    各位大佬,请问一下 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
    Austin2035
        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
    Austin2035
        2
    Austin2035  
       2022-01-09 19:49:53 +08:00
    而且也封装为字典了,可以拿来玩玩。
    liberize
        3
    liberize  
       2022-01-09 21:04:36 +08:00 via Android   ❤️ 1
    learningmachine
        4
    learningmachine  
    OP
       2022-01-09 22:50:28 +08:00
    @lookcos 谢谢回答,其实我更加希望找到一个关于用 open addressing 实现的库
    learningmachine
        5
    learningmachine  
    OP
       2022-01-09 22:50:45 +08:00
    @liberize 谢谢,我去了解一下
    billwsy
        6
    billwsy  
       2022-01-10 01:32:28 +08:00 via iPhone
    absl::flat_hash_set 可以吗?
    GeruzoniAnsasu
        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 候选,理论上来说跟他这种实现不会有什么区别
    anonymousar
        8
    anonymousar  
       2022-01-10 09:18:45 +08:00
    folly F14FastMap
    111qqz
        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/
    learningmachine
        10
    learningmachine  
    OP
       2022-01-11 00:45:48 +08:00   ❤️ 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 里面吗?如果是这样的话,确实是比视频中的方式,即再访问一次内存要好。

    很厉害的回答!
    learningmachine
        11
    learningmachine  
    OP
       2022-01-11 00:50:37 +08:00
    @billwsy @anonymousar 谢谢两位的指路,我去研究研究

    @111qqz 是一位刷了 CSAPP 和 6.828 的大手子,谢谢你的回答,我学习下~
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5462 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 07:03 · PVG 15:03 · LAX 23:03 · JFK 02:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.