为什么 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

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

谢谢大家~

[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