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

[dorafmon]

大家好，我是一名 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

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

谢谢大家~

没时间看视频的可以看我的底稿文案： https://github.com/bobfang1992/vlog/tree/master/c%2B%2B3-maps

[elfive]

标题党

[dorafmon]

@elfive 我改了，我本来想幽默一把的

[dorafmon]

没时间看视频的可以看我的底稿文案： https://github.com/bobfang1992/vlog/tree/master/c%2B%2B3-maps

[nnqijiu]

推广帖

[AkideLiu]

他慢他是 std

[dorafmon]

@nnqijiu 嗯嗯 我之前的视频标题都是“给新手 C++程序员的 tips”这回本来想幽默一把，但是感觉好像起了反作用，但是我还是想分享这个知识的，不好意思让你觉得是推广贴了，你可以选择不看视频，底稿文案我也付在下面了。

[dorafmon]

@AkideLiu 对，也没什么特别好的选择，就算慢也要用，所以有的时候就认了。

[b00tyhunt3r]

对我来说视频形式反而比文章更易于吸收，中文圈技术短视频 up 主太少了
滋瓷一个

[Monad]

其实感觉讲的还不错 就是标题😅

[Monad]

@Monad 我感觉直接写 absi 对比 std 实现都会有更多人点进来😅

[52coder]

资瓷，讲的不错，声音可以搞得稍微大点，视频和文件一起放出来，萝卜青菜各有所爱，已关注

[XIVN1987]

意思是 std::map 比 google 的 map 实现慢 10 倍？？

那可真是够慢啊，，怪不得经常有人说 java 比 C++快，，看来也不是没可能啊

[BrettD]

@XIVN1987 这和 Java 比 C++快有啥关系……

[YouLMAO]

std::map 是红黑树，哈希你妹妹

[fps23dot9999]

都打开-o2 优化试试

[XIVN1987]

@BrettD

写程序肯定要用标准库啊，，标准库里的代码速度慢，，那最终程序就跑的慢啊

[dinghao188]

@YouLMAO unordered_map 是哈希表

[anzu]

在 closed hashing 的情况下，怎么知道查找一个元素时需要再 probing ?

[sariya]

stl 暴露实现细节那块没看懂，原文直译是“所有可见行为取决于某人”？

[fengjianxinghun]

@XIVN1987 标准库里有 std::unordered_map，那才是 hash 表，std::map 是红黑树。

[jones2000]

看源码不就知道了嘛

[arvinsilm]

- 推广贴请发到推广节点
- 但是推广节点没人看没效果
- 你有注意到热榜经常出现一些推广贴吗？
- 为什么呢，因为他们会抽奖
- 推广有成本，不要用污染论坛环境的方式做推广

[BrettD]

@XIVN1987 比较语言速度会专门比较某个特定的库特性的速度吗？ C++和 Java 比速度比的不是原生代码和 JVM 的速度吗？

[siyemiaokube]

感谢分享

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

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

不同的重 hash 方法可以理解为，给出了 hash table 从 O(1)到 O(n^2)的退化程度的曲线（同样也依赖于概率分布）。

[siyemiaokube]

如果是我的话，可能会这样组织 hash table 的讲授：

1:hash table 提供的 adt
2:与平衡树的比较
3:极端情况与复杂度
4:重 hash 方式，什么是好的重 hash
5:画一个 hash 函数关于内存-数据量的碰撞次数的曲线
6:工程上的常用实现

[DarkCat123]

@Livid 在程序员节点推广。

[Leviathann]

@siyemiaokube java 没那么复杂 就是链表记录冲突，冲突多余 8 就把链表转红黑树
java 的实现应该是最直接的实现之一了。。

[Livid]

@DarkCat123 谢谢举报。这个主题已经从 /go/programmer 移动到 /go/promotions

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

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

如果持续违反规则，你的账号将会被禁用。

[dorafmon]

@Livid 为什么我的这个算推广而这个贴子不算？ https://www.v2ex.com/t/745736#reply22 而且我之前几次分享视频都不算推广。。。我想明白站方对推广的定义。我看很多人 po 自己的博客，或者视频来分享知识，我现在也在分享我的知识为什么我的就算推广？

[dorafmon]

@DarkCat123 @Livid 为啥我的算推广这个就不算推广？ https://www.v2ex.com/t/745751#reply2