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