02丨数据结构原理：Hash表的时间复杂度为什么是O(1)？

李智慧



该思维导图由 AI 生成，仅供参考

大概十年前，我在阿里巴巴工作的时候，曾经和另一个面试官一起进行一场技术面试，面试过程中我问了一个问题：Hash 表的时间复杂度为什么是 O(1)？候选人没有回答上来。面试结束后我和另一个面试官有了分歧，我觉得这个问题没有回答上来是不可接受的。而他则觉得，这个问题有一点难度，回答不上来不说明什么。
因为有了这次争执，后来这个问题成了我面试时的必考题。此后十年间，我用这个问题面试了大约上千人，这些面试经历让我更加坚定了一个想法：这个问题就是候选人技术水平的一个分水岭，是证明一个技术人员是否具有必备专业技能和技术悟性的一个门槛。这个槛过不去是不可接受的。
为什么呢？我很难相信，如果基本的数据结构没有掌握好，如何能开发好一个稍微复杂一点的程序？
要了解 Hash 表，需要先从数组说起。
数组数组是最常用的数据结构，创建数组必须要内存中一块连续的空间，并且数组中必须存放相同的数据类型。比如我们创建一个长度为 10，数据类型为整型的数组，在内存中的地址是从 1000 开始，那么它在内存中的存储格式如下。
由于每个整型数据占据 4 个字节的内存空间，因此整个数组的内存空间地址是 1000～1039，根据这个，我们就可以轻易算出数组中每个数据的内存下标地址。利用这个特性，我们只要知道了数组下标，也就是数据在数组中的位置，比如下标 2，就可以计算得到这个数据在内存中的位置 1008，从而对这个位置的数据 241 进行快速读写访问，时间复杂度为 O(1)。

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

本文深入浅出地解释了Hash表的原理和实现，以及其他数据结构如数组、链表、栈和队列的特点和应用。文章首先介绍了数组和链表的存储方式及时间复杂度，然后深入讲解了Hash表的工作原理，通过计算Key的哈希值得到数组下标，实现了快速查找。同时，文章也提到了Hash冲突可能导致时间复杂度退化为O(N)，但通过链表法可解决此问题。此外，文章还介绍了栈和队列的操作限制及应用场景。总之，本文通过对各种数据结构的解释，深入浅出地解答了Hash表时间复杂度为O(1)的原因，对读者快速了解Hash表的原理和实现具有重要参考价值。文章还提到了树的应用场景和遍历方式，以及对面试中数据结构问题的重视。文章以思考题的形式引发读者思考，增加了互动性。整体而言，本文内容丰富，涵盖了多种数据结构的知识，适合对数据结构感兴趣的读者阅读。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《后端技术面试 38 讲》，新⼈⾸单¥59

立即购买

登录后留言

全部留言(67)

最新
精选

_funyoo_
说说我的思考：方法1：在遍历链表1，看该结点是否在2中存在，若存在，即为合并。遍历的方法：①两个for嵌套 ②根据1建立hash表，遍历2时在1中查找方法2：计算两个链表的长度，谁长谁先“往前走”，待长链表未查看长度等于短链表是，两两元素比较，遍历完未出现相同时，则没有合并方法3：直接比较两个链表的最后一个元素，相等即合并
作者回复: √ 方法2 👍
2019-11-20
31
78
Geek_9c3134
老师你这问题我问了别人发现只回答到了数组下标没有人讲到内存还说我的问题太简单了
作者回复: 那就继续问下去~~ Hash表数组长度不足怎么办？多线程并发修改Hash表怎么办？如何保证线程安全？JDK的ConcurrentHashMap是如何解决的？如何使Hash表中的数据分布更加均匀，减少Hash聚集？余数Hash算法应用于分布式缓存路由的时候有什么问题？如何解决？一致性Hash算法原理是什么？用你熟悉的编程语言20分钟写一个一致性Hash算法实现。
2019-11-28
7
56
breezeQian
步骤一：将长度短的链表的元素构造成哈希表，key是指针，value是节点值。步骤二：遍历较长链表找出合并的节点
作者回复: √
2019-11-20
3
13
晶晶
是我听过的课程里面觉得最让我思路清晰的课程~所以先打卡沙发一下☺
作者回复: 🌹
2019-11-20
2
8
Geek_ac779f
老师，为什么有些数据结构的内存空间不要求是连续的？都是连续的内存空间不好吗。既然连续和不连续的内存空间都可以实现这些数据结构，使用不连续的内存空间实现有什么好处呢，利用率更高吗。为什么利用率更高呢，不都是以字节为基本单位吗
作者回复: 程序运行过程中，内存不断被申请、释放，内存的空闲空间呈碎片化，本身就是不连续的。
2019-11-27
2
6
Better me
老师，文中这段话“想在 b 和 c 之间插入一个元素 x，只需要将 b 指向 c 的指针修改为指向 x，然后将 x 的指针指向 c 就可以了”感觉反过来说更合理一些，如果按以上顺序代码实现会出现指针丢失内存泄漏的情况吧。
作者回复: 是的，你描述的算法过程更合理。文中只是想表达这个插入节点，修改指针的逻辑，文中描述不作为算法过程。
2019-11-30
2
2
郭刚
类似Oracle中的hash join的算法
作者回复: √
2019-11-20
2
2
恺撒之剑
课程中的数组示意图，长度为10的整数数组，地址从1000开始，下标为9的数组对应的起始地址应该为1036，而不是1039
作者回复: 已改正，谢谢~
2019-11-26

1
远心
实现了同时遍历两个单向链表的方法，欢迎拍砖：https://github.com/Huan-Rong/geektime-backend-technology-basics/blob/master/sources/2-the-time-complexity-of-hash-table/src/main/java/site/blbc/MergeDetect.java
作者回复: 思路很赞👍 你这里利用了LinkedList的特性，按照题意，应该无法直接得到两个链表的长度。
2019-11-20
2
1
幸福来敲门
由于每个整型数据占据 4 个字节的内存空间，因此整个数组的内存空间地址是 0x1000～0x1039，根据这个，我们就可以轻易算出数组中每个数据的内存下标地址。利用这个特性，我们只要知道了数组下标，也就是数据在数组中的位置，比如下标 2，就可以计算得到这个数据在内存中的位置 0x1008。请问这个内存16进制地址是怎么得出来的？ 0x1000～0x1039
作者回复: 谢谢指正，应该用十进制
2019-11-20
3
1

收起评论