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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1404 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

2021-01-18 07:43:38 +08:00 via iPhone

标题党

dorafmon

2021-01-18 07:47:59 +08:00

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

dorafmon

2021-01-18 07:50:53 +08:00

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

nnqijiu

2021-01-18 08:43:08 +08:00

推广帖

AkideLiu

2021-01-18 08:48:33 +08:00

他慢他是 std

dorafmon

2021-01-18 08:51:18 +08:00

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

dorafmon

2021-01-18 08:52:14 +08:00

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

b00tyhunt3r

2021-01-18 09:35:34 +08:00

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

Monad

2021-01-18 09:39:14 +08:00 via iPhone

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

Monad

2021-01-18 09:40:11 +08:00 via iPhone

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

52coder

2021-01-18 09:43:20 +08:00

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

XIVN1987

2021-01-18 09:43:35 +08:00

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

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

BrettD

2021-01-18 09:54:05 +08:00 via iPad

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

YouLMAO

2021-01-18 09:57:53 +08:00 via Android

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

fps23dot9999

2021-01-18 10:01:51 +08:00

都打开-o2 优化试试

XIVN1987

2021-01-18 10:03:48 +08:00

@BrettD

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

dinghao188

2021-01-18 10:16:18 +08:00

@YouLMAO unordered_map 是哈希表

anzu

2021-01-18 10:21:51 +08:00

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

sariya

2021-01-18 10:32:13 +08:00 via Android

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

fengjianxinghun

2021-01-18 10:35:06 +08:00

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

jones2000

2021-01-18 10:39:36 +08:00

看源码不就知道了嘛

arvinsilm

2021-01-18 11:22:34 +08:00

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

BrettD

2021-01-18 13:01:36 +08:00 via iPhone

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

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

2021-01-18 13:35:16 +08:00 via iPhone

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

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