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

为什么 C++自带的哈希表竟然有点慢?

  •  
  •   dorafmon · 2021-01-18 07:39:10 +08:00 · 3233 次点击
    这是一个创建于 489 天前的主题,其中的信息可能已经有所发展或是发生改变。

    大家好,我是一名 C++码农,因为在平时工作 /面试的过程中经常会遇到一些关于 C++的细节,而这些知识点大多散在各种书 /博客 /github repo 里,所以我想把这些只是总结成每个 10mins 左右的视频,分享给大家,也是我自己对自己知识图谱的一个总结。我在录这个视频的时候面对的对象人群是 junior C++ developer,想好好准备 C++知识面试,或者是想学习一些跟 C++有关的能应用在工作中的 best practice 。因为我自己在国外,所以有些时候有些中英混杂,实在不好意思。

    下面是第三个视频,讲的是关于 C++中自带的哈希表,为什么它有那么一丢丢慢~

    希望大家喜欢我的视频,也希望大家指出我视频中的错误~

    b 站: https://www.bilibili.com/video/BV1ah411y7Ni

    youtube: https://youtu.be/nx5g5bwtUuA

    还烦请大家给我一键三连,订阅我的频道,开启小铃铛~

    谢谢大家~

    第 1 条附言  ·  2021-01-18 08:12:34 +08:00
    没时间看视频的可以看我的底稿文案: https://github.com/bobfang1992/vlog/tree/master/c%2B%2B3-maps
    30 条回复    2021-01-18 22:00:01 +08:00
    elfive
        1
    elfive  
       2021-01-18 07:43:38 +08:00 via iPhone   ❤️ 3
    标题党
    dorafmon
        2
    dorafmon  
    OP
       2021-01-18 07:47:59 +08:00
    @elfive 我改了,我本来想幽默一把的
    dorafmon
        3
    dorafmon  
    OP
       2021-01-18 07:50:53 +08:00
    没时间看视频的可以看我的底稿文案: https://github.com/bobfang1992/vlog/tree/master/c%2B%2B3-maps
    nnqijiu
        4
    nnqijiu  
       2021-01-18 08:43:08 +08:00
    推广帖
    AkideLiu
        5
    AkideLiu  
       2021-01-18 08:48:33 +08:00
    他慢他是 std
    dorafmon
        6
    dorafmon  
    OP
       2021-01-18 08:51:18 +08:00
    @nnqijiu 嗯嗯 我之前的视频标题都是“给新手 C++程序员的 tips”这回本来想幽默一把,但是感觉好像起了反作用,但是我还是想分享这个知识的,不好意思让你觉得是推广贴了,你可以选择不看视频,底稿文案我也付在下面了。
    dorafmon
        7
    dorafmon  
    OP
       2021-01-18 08:52:14 +08:00
    @AkideLiu 对,也没什么特别好的选择,就算慢也要用,所以有的时候就认了。
    b00tyhunt3r
        8
    b00tyhunt3r  
       2021-01-18 09:35:34 +08:00
    对我来说视频形式反而比文章更易于吸收,中文圈技术短视频 up 主太少了
    滋瓷一个
    Monad
        9
    Monad  
       2021-01-18 09:39:14 +08:00 via iPhone
    其实感觉讲的还不错 就是标题😅
    Monad
        10
    Monad  
       2021-01-18 09:40:11 +08:00 via iPhone
    @Monad 我感觉直接写 absi 对比 std 实现都会有更多人点进来😅
    52coder
        11
    52coder  
       2021-01-18 09:43:20 +08:00
    资瓷,讲的不错,声音可以搞得稍微大点,视频和文件一起放出来,萝卜青菜各有所爱,已关注
    XIVN1987
        12
    XIVN1987  
       2021-01-18 09:43:35 +08:00
    意思是 std::map 比 google 的 map 实现慢 10 倍??

    那可真是够慢啊,,怪不得经常有人说 java 比 C++快,,看来也不是没可能啊
    BrettD
        13
    BrettD  
       2021-01-18 09:54:05 +08:00 via iPad
    @XIVN1987 这和 Java 比 C++快有啥关系……
    YouLMAO
        14
    YouLMAO  
       2021-01-18 09:57:53 +08:00 via Android   ❤️ 2
    std::map 是红黑树,哈希你妹妹
    fps23dot9999
        15
    fps23dot9999  
       2021-01-18 10:01:51 +08:00
    都打开-o2 优化试试
    XIVN1987
        16
    XIVN1987  
       2021-01-18 10:03:48 +08:00
    @BrettD

    写程序肯定要用标准库啊,,标准库里的代码速度慢,,那最终程序就跑的慢啊
    dinghao188
        17
    dinghao188  
       2021-01-18 10:16:18 +08:00
    @YouLMAO unordered_map 是哈希表
    anzu
        18
    anzu  
       2021-01-18 10:21:51 +08:00
    在 closed hashing 的情况下,怎么知道查找一个元素时需要再 probing ?
    sariya
        19
    sariya  
       2021-01-18 10:32:13 +08:00 via Android
    stl 暴露实现细节那块没看懂,原文直译是“所有可见行为取决于某人”?
    fengjianxinghun
        20
    fengjianxinghun  
       2021-01-18 10:35:06 +08:00
    @XIVN1987 标准库里有 std::unordered_map,那才是 hash 表,std::map 是红黑树。
    jones2000
        21
    jones2000  
       2021-01-18 10:39:36 +08:00
    看源码不就知道了嘛
    arvinsilm
        22
    arvinsilm  
       2021-01-18 11:22:34 +08:00   ❤️ 1
    - 推广贴请发到推广节点
    - 但是推广节点没人看没效果
    - 你有注意到热榜经常出现一些推广贴吗?
    - 为什么呢,因为他们会抽奖
    - 推广有成本,不要用污染论坛环境的方式做推广
    BrettD
        23
    BrettD  
       2021-01-18 13:01:36 +08:00 via iPhone
    @XIVN1987 比较语言速度会专门比较某个特定的库特性的速度吗? C++和 Java 比速度比的不是原生代码和 JVM 的速度吗?
    siyemiaokube
        24
    siyemiaokube  
       2021-01-18 13:17:09 +08:00 via iPhone
    感谢分享

    不过,感觉 up 有一点点没抓到重点……

    稍微补充一点点:
    平衡树维护了邻域信息,并且是稳定算法。相对地,hash table 的复杂度同时依赖于内存空间的占用以及数据量,当两者同数量级时,hash table 的速度会退化为 n^2 。我印象中(不太确定) java 的 map 设定了一个阈值,在小数据使用 hash table,数据量增大到一定程度时会使用平衡树。

    不同的重 hash 方法可以理解为,给出了 hash table 从 O(1)到 O(n^2)的退化程度的曲线(同样也依赖于概率分布)。
    siyemiaokube
        25
    siyemiaokube  
       2021-01-18 13:35:16 +08:00 via iPhone
    如果是我的话,可能会这样组织 hash table 的讲授:

    1:hash table 提供的 adt
    2:与平衡树的比较
    3:极端情况与复杂度
    4:重 hash 方式,什么是好的重 hash
    5:画一个 hash 函数关于内存-数据量的碰撞次数的曲线
    6:工程上的常用实现
    DarkCat123
        26
    DarkCat123  
       2021-01-18 14:01:51 +08:00   ❤️ 1
    @Livid 在程序员节点推广。
    Leviathann
        27
    Leviathann  
       2021-01-18 18:35:54 +08:00 via iPhone
    @siyemiaokube java 没那么复杂 就是链表记录冲突,冲突多余 8 就把链表转红黑树
    java 的实现应该是最直接的实现之一了。。
    Livid
        28
    Livid  
    MOD
       2021-01-18 20:08:44 +08:00
    @DarkCat123 谢谢举报。这个主题已经从 /go/programmer 移动到 /go/promotions

    @dorafmon 请阅读 V2EX 的节点使用指南:

    https://www.v2ex.com/help/node

    如果持续违反规则,你的账号将会被禁用。
    dorafmon
        29
    dorafmon  
    OP
       2021-01-18 20:35:19 +08:00
    @Livid 为什么我的这个算推广而这个贴子不算? https://www.v2ex.com/t/745736#reply22 而且我之前几次分享视频都不算推广。。。我想明白站方对推广的定义。我看很多人 po 自己的博客,或者视频来分享知识,我现在也在分享我的知识为什么我的就算推广?
    dorafmon
        30
    dorafmon  
    OP
       2021-01-18 22:00:01 +08:00
    @DarkCat123 @Livid 为啥我的算推广这个就不算推广? https://www.v2ex.com/t/745751#reply2
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2774 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 14:48 · PVG 22:48 · LAX 07:48 · JFK 10:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.