后端技术面试38讲
李智慧
同程艺龙交通首席架构师,前Intel&阿里架构师,《大型网站技术架构》作者
立即订阅
3682 人已学习
课程目录
已更新 16 讲 / 共 38 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 掌握软件开发技术的第一性原理
免费
软件的基础原理 (8讲)
01丨程序运行原理:程序是如何运行又是如何崩溃的?
02丨数据结构原理:Hash表的时间复杂度为什么是O(1)?
03丨Java虚拟机原理:JVM为什么被称为机器(machine)?
04丨网络编程原理:一个字符的互联网之旅
05丨文件系统原理:如何用1分钟遍历一个100TB的文件?
06丨数据库原理:为什么PrepareStatement性能更好更安全?
07丨编程语言原理:面向对象编程是编程的终极形态吗?
答疑丨Java Web程序的运行时环境到底是怎样的?
软件的设计原理 (6讲)
08丨软件设计的方法论:软件为什么要建模?
09丨软件设计实践:如何使用UML完成一个设计文档?
10 | 软件设计的目的:糟糕的程序员比优秀的程序员差在哪里?
11丨软件设计的开闭原则:如何不修改代码却能实现需求变更?
12 | 软件设计的依赖倒置原则:如何不依赖代码却可以复用它的功能?
13丨软件设计的里氏替换原则:正方形可以继承长方形吗?
不定期加餐 (1讲)
加餐 | 软件设计文档示例模板
后端技术面试38讲
登录|注册

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

李智慧 2019-11-20
大概十年前,我在阿里巴巴工作的时候,曾经和另一个面试官一起进行一场技术面试,面试过程中我问了一个问题:Hash 表的时间复杂度为什么是 O(1)?候选人没有回答上来。面试结束后我和另一个面试官有了分歧,我觉得这个问题没有回答上来是不可接受的。而他则觉得,这个问题有一点难度,回答不上来不说明什么。
因为有了这次争执,后来这个问题成了我面试时的必考题。此后十年间,我用这个问题面试了大约上千人,这些面试经历让我更加坚定了一个想法:这个问题就是候选人技术水平的一个分水岭,是证明一个技术人员是否具有必备专业技能和技术悟性的一个门槛。这个槛过不去是不可接受的。
为什么呢?我很难相信,如果基本的数据结构没有掌握好,如何能开发好一个稍微复杂一点的程序?
要了解 Hash 表,需要先从数组说起。

数组

数组是最常用的数据结构,创建数组必须要内存中一块连续的空间,并且数组中必须存放相同的数据类型。比如我们创建一个长度为 10,数据类型为整型的数组,在内存中的地址是从 1000 开始,那么它在内存中的存储格式如下。
由于每个整型数据占据 4 个字节的内存空间,因此整个数组的内存空间地址是 1000~1039,根据这个,我们就可以轻易算出数组中每个数据的内存下标地址。利用这个特性,我们只要知道了数组下标,也就是数据在数组中的位置,比如下标 2,就可以计算得到这个数据在内存中的位置 1008,从而对这个位置的数据 241 进行快速读写访问,时间复杂度为 O(1)。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《后端技术面试38讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(35)

  • _funyoo_
    说说我的思考:
    方法1:在遍历链表1,看该结点是否在2中存在,若存在,即为合并。
    遍历的方法:①两个for嵌套 ②根据1建立hash表,遍历2时在1中查找

    方法2:计算两个链表的长度,谁长谁先“往前走”,待长链表未查看长度等于短链表是,两两元素比较,遍历完未出现相同时,则没有合并

    方法3:直接比较两个链表的最后一个元素,相等即合并

    作者回复: √
    方法2 👍

    2019-11-20
    7
    27
  • 见哥哥
    思路特别清晰,但是都是点到为止呀,感觉差点啥,哈哈,可能后面的文章会具体介绍,更加详细。
    2019-11-20
    5
  •  扬帆丶启航 
    计算两个链表的长度,用长的链表减去短的链表,计算出差值,长的链表先向后移动差值的个数,然后两个链表再同时移动,判断一下个节点的地址是否相同。
    2019-11-20
    2
    4
  • breezeQian
    步骤一:将长度短的链表的元素构造成哈希表,key是指针,value是节点值。
    步骤二:遍历较长链表找出合并的节点

    作者回复: √

    2019-11-20
    4
  • 乘坐Tornado的线程魔法师
    思考题:第一步:分别遍历针对两个链表A、B(先不考虑长度差)。第二步:如果A链表先走到了末尾那么把A链表的指针指向B链表的第一个节点,继续遍历B链表;B链表的原始指针继续做遍历不变,走到末尾后,将B链表的指针指向A链表的第一个节点,继续遍历A链表。第三步:两个链表继续做遍历,如果分别指向的节点数值(地址)相同,那么这两个链表就是合并链表,这个节点就为合并的第一个节点。

    思想:通过指针的变换指向,很好滴解决的长度差的问题。消除两个链表的长度差带来的影响,
    2019-11-20
    1
    3
  • Geek_9c3134
    老师 你这问题我问了别人 发现只回答到了数组下标 没有人讲到内存 还说我的问题太简单了

    作者回复: 那就继续问下去~~

    Hash表数组长度不足怎么办?

    多线程并发修改Hash表怎么办?如何保证线程安全?JDK的ConcurrentHashMap是如何解决的?

    如何使Hash表中的数据分布更加均匀,减少Hash聚集?

    余数Hash算法应用于分布式缓存路由的时候有什么问题?如何解决?一致性Hash算法原理是什么?

    用你熟悉的编程语言20分钟写一个一致性Hash算法实现。

    2019-11-28
    1
    2
  • 晶晶
    是我听过的课程里面觉得最让我思路清晰的课程~所以先打卡沙发一下☺

    作者回复: 🌹

    2019-11-20
    1
    2
  • 小烽
    我的思考去下:能想到的就是遍历,结合前面几位的方法,做个比较。假设长度分别为m和n,m大。
    方法一:先去遍历m 链表到m-n,然后同时遍历两个链表,比较大小,时间复杂度是O(m)

    方法二:取一条链表的值放入hash 表,另一个链表进行遍历,在没有hash 冲突的情况下,时间复杂度应该是O(m+n)

    方法三:从链表末端开始比较,时间复杂度应该也是O(m+n)

    不知道理解的对不对。
    2019-11-22
    1
  • 小太白52度
    1.将两个单链表顺序颠倒,即由尾指向头;
    2.将两个新链表由头开始一一比较,直到两个元素不想等;
    3.若第一元素即不等,则两个链表不合并,否则最后一个相等元素即为合并处的元素。
    2019-11-20
    1
    1
  • Geek_60eace
    获取2个列表的所有指针,进行交集运算,抛出第一个指针就是开始合并的地方
    2019-11-20
    1
  • 郭刚
    类似Oracle中的hash join的算法

    作者回复: √

    2019-11-20
    1
  • 美美
    hash的意思就是散列,对数据每个元素求hash,hash的结果存储在一维数组中,数据存储在链表中,hash是链表的头。查询时先对数据求hash,定位在数组中的地址,这个时间复杂度为o(1),从链表中查询时间复杂度也是o(1),所以hash表的时间复杂度是o(1)
    2019-12-15
  • 刘东才
    数据结构程序员应该都是知道的,但是在日常编码过程中真的很难遇到需要这些知识的地方
    2019-12-05
  • Paul Shan
    思考题
    我的解法是从两个节点向链表尾部进发,记下走过的节点数目,然后把节点数多的那个先走几步直到两个节点到尾部数目相同,这时比较两个节点是否相等,如果相等程序结束,如果不相等,分别前进一步再比较,直到结尾。
    2019-12-05
  • Better me
    老师,文中这段话“想在 b 和 c 之间插入一个元素 x,只需要将 b 指向 c 的指针修改为指向 x,然后将 x 的指针指向 c 就可以了”感觉反过来说更合理一些,如果按以上顺序代码实现会出现指针丢失内存泄漏的情况吧。

    作者回复: 是的,你描述的算法过程更合理。

    文中只是想表达这个插入节点,修改指针的逻辑,文中描述不作为算法过程。

    2019-11-30
  • Geek_ac779f
    老师,为什么有些数据结构的内存空间不要求是连续的?都是连续的内存空间不好吗。既然连续和不连续的内存空间都可以实现这些数据结构,使用不连续的内存空间实现有什么好处呢,利用率更高吗。为什么利用率更高呢,不都是以字节为基本单位吗

    作者回复: 程序运行过程中,内存不断被申请、释放,内存的空闲空间呈碎片化,本身就是不连续的。

    2019-11-27
    1
  • 熊四
    将两个链表随便一个进行入栈操作,接着每次弹出一个和另外一个链表比较,
    2019-11-27
  • 夜空中最亮的星(华仔)
    我听明白了老师
    2019-11-26
  • 恺撒之剑
    课程中的数组示意图,长度为10的整数数组,地址从1000开始,下标为9的数组对应的起始地址应该为1036,而不是1039

    作者回复: 已改正,谢谢~

    2019-11-26
  • greensky01
    关于hash表复杂度是O(1)这个题,我觉得还是不太妥,不如直接问复杂度是怎样的。因为前者存在误导。
    2019-11-26
收起评论
35
返回
顶部