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

Nov 20, 2019

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



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

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

2019-11-20 李智慧来自北京

《后端技术面试 38 讲》

课程介绍



讲述：李智慧

时长12:55大小11.83M



大概十年前，我在阿里巴巴工作的时候，曾经和另一个面试官一起进行一场技术面试，面试过程中我问了一个问题：Hash 表的时间复杂度为什么是 O(1)？候选人没有回答上来。面试结束后我和另一个面试官有了分歧，我觉得这个问题没有回答上来是不可接受的。而他则觉得，这个问题有一点难度，回答不上来不说明什么。
因为有了这次争执，后来这个问题成了我面试时的必考题。此后十年间，我用这个问题面试了大约上千人，这些面试经历让我更加坚定了一个想法：这个问题就是候选人技术水平的一个分水岭，是证明一个技术人员是否具有必备专业技能和技术悟性的一个门槛。这个槛过不去是不可接受的。
为什么呢？我很难相信，如果基本的数据结构没有掌握好，如何能开发好一个稍微复杂一点的程序？
要了解 Hash 表，需要先从数组说起。
数组数组是最常用的数据结构，创建数组必须要内存中一块连续的空间，并且数组中必须存放相同的数据类型。比如我们创建一个长度为 10，数据类型为整型的数组，在内存中的地址是从 1000 开始，那么它在内存中的存储格式如下。
由于每个整型数据占据 4 个字节的内存空间，因此整个数组的内存空间地址是 1000～1039，根据这个，我们就可以轻易算出数组中每个数据的内存下标地址。利用这个特性，我们只要知道了数组下标，也就是数据在数组中的位置，比如下标 2，就可以计算得到这个数据在内存中的位置 1008，从而对这个位置的数据 241 进行快速读写访问，时间复杂度为 O(1)。
随机快速读写是数组的一个重要特性，但是要随机访问数据，必须知道数据在数组中的下标。如果我们只是知道数据的值，想要在数组中找到这个值，那么就只能遍历整个数组，时间复杂度为 O(N)。
链表不同于数组必须要连续的内存空间，链表可以使用零散的内存空间存储数据。不过，因为链表在内存中的数据不是连续的，所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。如下图，链表的每个元素包含两部分，一部分是数据，一部分是指向下一个元素的地址指针。最后一个元素指向 null，表示链表到此为止。
因为链表是不连续存储的，要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是 O(N)。
但是正因为链表是不连续存储的，所以在链表中插入或者删除一个数据是非常容易的，只要找到要插入（删除）的位置，修改链表指针就可以了。如图，想在 b 和 c 之间插入一个元素 x，只需要将 b 指向 c 的指针修改为指向 x，然后将 x 的指针指向 c 就可以了。
相比在链表中轻易插入、删除一个元素这种简单的操作，如果我们要想在数组中插入、删除一个数据，就会改变数组连续内存空间的大小，需要重新分配内存空间，这样要复杂得多。
Hash 表前面说过，对数组中的数据进行快速访问必须要通过数组的下标，时间复杂度为 O(1)。如果只知道数据或者数据中的部分内容，想在数组中找到这个数据，还是需要遍历数组，时间复杂度为 O(N)。
事实上，知道部分数据查找完整数据的需求在软件开发中会经常用到，比如知道了商品 ID，想要查找完整的商品信息；知道了词条名称，想要查找百科词条中的详细信息等。
这类场景就需要用到 Hash 表这种数据结构。Hash 表中数据以 Key、Value 的方式存储，上面例子中，商品 ID 和词条名称就是 Key，商品信息和词条详细信息就是 Value。存储的时候将 Key、Value 写入 Hash 表，读取的时候，只需要提供 Key，就可以快速查找到 Value。
Hash 表的物理存储其实是一个数组，如果我们能够根据 Key 计算出数组下标，那么就可以快速在数组中查找到需要的 Key 和 Value。许多编程语言支持获得任意对象的 HashCode，比如 Java 语言中 HashCode 方法包含在根对象 Object 中，其返回值是一个 Int。我们可以利用这个 Int 类型的 HashCode 计算数组下标。最简单的方法就是余数法，使用 Hash 表的数组长度对 HashCode 求余， 余数即为 Hash 表数组的下标，使用这个下标就可以直接访问得到 Hash 表中存储的 Key、Value。
上图这个例子中，Key 是字符串 abc，Value 是字符串 hello。我们先计算 Key 的哈希值，得到 101 这样一个整型值。然后用 101 对 8 取模，这个 8 是哈希表数组的长度。101 对 8 取模余 5，这个 5 就是数组的下标，这样就可以把 (“abc”,“hello”) 这样一个 Key、Value 值存储在下标为 5 的数组记录中。
当我们要读取数据的时候，只要给定 Key abc，还是用这样一个算法过程，先求取它的 HashCode 101，然后再对 8 取模，因为数组的长度不变，对 8 取模以后依然是余 5，那么我们到数组下标中去找 5 的这个位置，就可以找到前面存储进去的 abc 对应的 Value 值。
但是如果不同的 Key 计算出来的数组下标相同怎么办？HashCode101 对 8 取模余数是 5，HashCode109 对 8 取模余数还是 5，也就是说，不同的 Key 有可能计算得到相同的数组下标，这就是所谓的 Hash 冲突，解决 Hash 冲突常用的方法是链表法。
事实上，(“abc”,“hello”) 这样的 Key、Value 数据并不会直接存储在 Hash 表的数组中，因为数组要求存储固定数据类型，主要目的是每个数组元素中要存放固定长度的数据。所以，数组中存储的是 Key、Value 数据元素的地址指针。一旦发生 Hash 冲突，只需要将相同下标，不同 Key 的数据元素添加到这个链表就可以了。查找的时候再遍历这个链表，匹配正确的 Key。
如下图：
因为有 Hash 冲突的存在，所以“Hash 表的时间复杂度为什么是 O(1)？”这句话并不严谨，极端情况下，如果所有 Key 的数组下标都冲突，那么 Hash 表就退化为一条链表，查询的时间复杂度是 O(N)。但是作为一个面试题，“Hash 表的时间复杂度为什么是 O(1)”是没有问题的。
栈数组和链表都被称为线性表，因为里面的数据是按照线性组织存放的，每个数据元素的前面只能有一个（前驱）数据元素，后面也只能有一个（后继）数据元素，所以称为线性表。但是对数组和链表的操作可以是随机的，可以对其上任何元素进行操作，如果对操作方式加以限制，就形成了新的数据结构。
栈就是在线性表的基础上加了这样的操作限制条件：后面添加的数据，在删除的时候必须先删除，即通常所说的“后进先出”。我们可以把栈可以想象成一个大桶，往桶里面放食物，一层一层放进去，如果要吃的时候，必须从最上面一层吃，吃了几层后，再往里放食物，还是从当前的最上面一层放起。
栈在线性表的基础上增加了操作限制，具体实现的时候，因为栈不需要随机访问、也不需要在中间添加、删除数据，所以可以用数组实现，也可以用链表实现。那么在顺序表的基础上增加操作限制有什么好处呢？
我们上篇提到的程序运行过程中，方法的调用需要用栈来管理每个方法的工作区，这样，不管方法如何嵌套调用，栈顶元素始终是当前正在执行的方法的工作区。这样，事情就简单了。而简单，正是我们做软件开发应该努力追求的一个目标。
队列队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。
在软件运行期，经常会遇到资源不足的情况：提交任务请求线程池执行，但是线程已经用完了，任务需要放入队列，先进先出排队执行；线程在运行中需要访问数据库，数据库连接有限，已经用完了，线程进入阻塞队列，当有数据库连接释放的时候，从阻塞队列头部唤醒一个线程，出队列获得连接访问数据库。
我在上面讲堆栈的时候，举了一个大桶放食物的例子，事实上，如果用这种方式存放食物，有可能最底下食物永远都吃不到，最后过期了。
现实中也是如此，超市在货架上摆放食品的时候，其实是按照队列摆放的，而不是堆栈摆放的。工作人员在上架新食品的时候，总是把新食品摆在后面，使食品成为一个队列，以便让以前上架的食品被尽快卖出。
树数组、链表、栈、队列都是线性表，也就是每个数据元素都只有一个前驱，一个后继。而树则是非线性表，树是这样的。
软件开发中，也有很多地方用到树，比如我们要开发一个 OA 系统，部门的组织结构就是一棵树；我们编写的程序在编译的时候，第一步就是将程序代码生成抽象语法树。传统上树的遍历使用递归的方式，而我个人更喜欢用设计模式中的组合模式进行树的遍历，具体我将会在设计模式部分详细讨论。
小结这是一篇关于数据结构的专栏文章，面试中问数据结构是一个非常有意思的话题，很多拥有绚丽简历和多年工作经验的候选人在数据结构的问题上翻了船，这些人有时候会解释说，这些知识都是大学时学过的，工作这些年用不着，记不太清楚了。
事实上，我很难相信，如果这些基本数据结构没有掌握好，如何能开发好一个稍微复杂一点的程序。但欣慰的是，在这些年的面试过程中，我发现候选者中能够正确回答基本数据结构问题的比例越来越高了，我也越来越坚定用数据结构问题当做是否跨过专业工程师门槛的试金石。作为一个专业软件工程师，不管有多少年经验，说不清楚基础数据结构的工作原理是不能接受的。
思考题链表结构虽然简单，但是各种组合变换操作却可以很复杂。关于链表的操作也是面试官最喜欢问的数据结构问题之一，我在面试过程中喜欢问的一个链表问题是：
有两个单向链表，这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
关于这道题，你的答案是什么呢？
欢迎你在评论区写下你的思考，我会和你一起交流，也欢迎把这篇文章分享给你朋友或者同事，一起交流一下。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

赞 15

提建议

01丨程序运行原理：程序是如何运行又是如何崩溃的？

03丨Java虚拟机原理：JVM为什么被称为机器（machine）？

 写留言

精选留言(65)

_funyoo_
2019-11-20
说说我的思考：方法1：在遍历链表1，看该结点是否在2中存在，若存在，即为合并。遍历的方法：①两个for嵌套 ②根据1建立hash表，遍历2时在1中查找方法2：计算两个链表的长度，谁长谁先“往前走”，待长链表未查看长度等于短链表是，两两元素比较，遍历完未出现相同时，则没有合并方法3：直接比较两个链表的最后一个元素，相等即合并
展开
作者回复: √ 方法2 👍
共 31 条评论
76
Geek_9c3134
2019-11-28
老师你这问题我问了别人发现只回答到了数组下标没有人讲到内存还说我的问题太简单了
作者回复: 那就继续问下去~~ Hash表数组长度不足怎么办？多线程并发修改Hash表怎么办？如何保证线程安全？JDK的ConcurrentHashMap是如何解决的？如何使Hash表中的数据分布更加均匀，减少Hash聚集？余数Hash算法应用于分布式缓存路由的时候有什么问题？如何解决？一致性Hash算法原理是什么？用你熟悉的编程语言20分钟写一个一致性Hash算法实现。
共 7 条评论
55
Bug? Feature!
2019-11-20
思路特别清晰，但是都是点到为止呀，感觉差点啥，哈哈，可能后面的文章会具体介绍，更加详细。
19
　扬帆丶启航　
2019-11-20
计算两个链表的长度，用长的链表减去短的链表，计算出差值，长的链表先向后移动差值的个数，然后两个链表再同时移动，判断一下个节点的地址是否相同。
共 4 条评论
18
breezeQian
2019-11-20
步骤一：将长度短的链表的元素构造成哈希表，key是指针，value是节点值。步骤二：遍历较长链表找出合并的节点
作者回复: √
共 3 条评论
13
Geek_ac779f
2019-11-27
老师，为什么有些数据结构的内存空间不要求是连续的？都是连续的内存空间不好吗。既然连续和不连续的内存空间都可以实现这些数据结构，使用不连续的内存空间实现有什么好处呢，利用率更高吗。为什么利用率更高呢，不都是以字节为基本单位吗
作者回复: 程序运行过程中，内存不断被申请、释放，内存的空闲空间呈碎片化，本身就是不连续的。
共 2 条评论
6
乘坐Tornado的线程魔...
2019-11-20
思考题：第一步：分别遍历针对两个链表A、B（先不考虑长度差）。第二步：如果A链表先走到了末尾那么把A链表的指针指向B链表的第一个节点，继续遍历B链表；B链表的原始指针继续做遍历不变，走到末尾后，将B链表的指针指向A链表的第一个节点，继续遍历A链表。第三步：两个链表继续做遍历，如果分别指向的节点数值（地址）相同，那么这两个链表就是合并链表，这个节点就为合并的第一个节点。思想：通过指针的变换指向，很好滴解决的长度差的问题。消除两个链表的长度差带来的影响，
展开
共 1 条评论
6
晶晶
2019-11-20
是我听过的课程里面觉得最让我思路清晰的课程~所以先打卡沙发一下☺
作者回复: 🌹
共 2 条评论
7
Anne
2020-04-21
暴力法：双重循环，针对链表1的每个元素，对链表2的每个元素进行遍历，比较是否相等，第一个相等的元素就是相交点使用栈：将两个链表的元素分别放入2个栈中，分别弹出栈顶元素，进行比较，如果栈顶元素相同则相交，相交之后第一个不相同元素的前一个元素就是相交点判断两个链表的长度：如果长度不同，比如一个是n，一个m，较长的链表先走n-m步，然后两个链表一起遍历，相同的元素即为交点。如果长度相同，一起遍历。
展开
3
escray
2020-09-20
看到题目，我也回答不上来，为什么 Hash 表的访问时间复杂度是 O(1)，后来看了专栏才知道（想起来），Hash 表的底层实现其实是数组。然后老师在留言里面提到的 Hash 表高阶问题，更是问的我一头大汗。即使是简单的数据结构，也能问出来好问题。课后思考题，单向链表合并，其实是 LeetCode 的 160 题，Intersection of Two Linked Lists。官方给出了三个解题思路： 1. Brute Force 暴力解法，双重循环遍历两个链表，时间复杂度 O(mn)，空间复杂度 O(1) 2. Hash Table 哈希表，将一个链表转为 Hash 表，然后遍历另一个链表，时间复杂度 O(m+n)，空间复杂度 O(m) 或 O(n) 3. Two Pointers 双指针，同时遍历两个链表，遍历到一条链表终点之后，续到另一条链表头部，比较两个指针，如果相等，则为交点因为这一篇以 Hash 表为题，所以第二个解法比较容易想到。 public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // boundary check if (headA == null || headB == null) { return null; } ListNode pA = headA; ListNode pB = headB; // if a & b have different len, // then we will stop the loop after second iteration while (pA != pB) { // for the end of first iteration, // we just reset the pointer to the head of another linkedlist pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; } }
展开
2
王杰
2020-04-22
其实这个问题可以归纳为两链表是否具有相同的元素地址。具体：两层for循环，查找相同的指针地址
共 1 条评论
2
Better me
2019-11-30
老师，文中这段话“想在 b 和 c 之间插入一个元素 x，只需要将 b 指向 c 的指针修改为指向 x，然后将 x 的指针指向 c 就可以了”感觉反过来说更合理一些，如果按以上顺序代码实现会出现指针丢失内存泄漏的情况吧。
作者回复: 是的，你描述的算法过程更合理。文中只是想表达这个插入节点，修改指针的逻辑，文中描述不作为算法过程。
共 2 条评论
2
郭刚
2019-11-20
类似Oracle中的hash join的算法
作者回复: √
共 2 条评论
2
碧雪天虹
2020-07-13
把两个链表都入栈, 然后从栈顶开始同时出栈, 如果某一轮出栈两个元素不同, 那么前一轮的就是x元素
1
小狼
2020-04-11
“但是正因为链表是不连续存储的，所以在链表中插入或者删除一个数据是非常容易的，只要找到要插入（删除）的位置，修改链表指针就可以了” 这句话的归因“但是正因为链表是不连续存储的”不严谨，插入或者删除一个数据非常容易并不是因为链表是不连续存储的，而是因为本质上链表指针的设计，有了这些指针，即便链表的存储是连续的，也丝毫不影响插入或者删除一个数据的快捷性，也即链表中插入或删除数据方便跟链表的存储分配是否连续没有因果关系
展开
1
小伟
2020-02-02
之前只给了伪代码，感觉不过瘾，同时也验证自己的思路是否正确，就实现了下，请老师和同学拍砖。 https://github.com/ToddSAP/Geektime/blob/master/src/backendinterview38/course2/LinkedListMergedTest.java
1
恺撒之剑
2019-11-26
课程中的数组示意图，长度为10的整数数组，地址从1000开始，下标为9的数组对应的起始地址应该为1036，而不是1039
作者回复: 已改正，谢谢~
1
小烽
2019-11-22
我的思考去下：能想到的就是遍历，结合前面几位的方法，做个比较。假设长度分别为m和n，m大。方法一：先去遍历m 链表到m-n,然后同时遍历两个链表，比较大小，时间复杂度是O(m) 方法二：取一条链表的值放入hash 表，另一个链表进行遍历，在没有hash 冲突的情况下，时间复杂度应该是O(m+n) 方法三：从链表末端开始比较，时间复杂度应该也是O(m+n) 不知道理解的对不对。
展开
共 1 条评论
1
小太白52度
2019-11-20
1.将两个单链表顺序颠倒，即由尾指向头； 2.将两个新链表由头开始一一比较，直到两个元素不想等； 3.若第一元素即不等，则两个链表不合并，否则最后一个相等元素即为合并处的元素。
共 1 条评论
1
Geek_60eace
2019-11-20
获取2个列表的所有指针，进行交集运算，抛出第一个指针就是开始合并的地方
1

