作者：赵烨
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
轻松学算法——互联网算法面试宝典试读：
前言
互联网越来越热门了，相信每个人都或多或少地在体验如今的互联网带给我们的各种便利。借助之前非常火热的电商，我们可以足不出户地购买衣服和日常用品；现在，就算是一个超级宅的人，也可以不出门便可完成订餐、在线交水电费、通过各种到家服务进行保洁和按摩、通过应用将在超市买的东西轻松配送到家，等等。在线办公在一些行业中也开始流行，视频会议更是可以轻松地实现异地交流。之前我们还需要见面签约，现在越来越多地在进行在线签约。
不得不感谢互联网带给我们的各种便利，但这背后是由很多产品、运营和技术人员的努力在支撑的。
我最初所在的公司属于传统行业，但也是一家服务与互联网公司。相信任何行业的技术员工都想进入互联网公司，这其中的好处有太多：技术的挑战、大用户量、大数据、高并发，这些都是我们所渴望的。
经常听到身边有很多人在抱怨算法不好学、学会了记不住、记住了不知道怎么用等，所以我决定写本书，结合自己的经验讲解一些算法的实际应用及适用场景，希望通过本书帮助更多的朋友进入互联网公司。
其实很多人怯场时无非担心的是自己的算法太差、技术太烂、别人会瞧不起，等等。本书可以帮助读者解决一些基础、常见的算法问题，当然，在技术上仍需自己努力，若再有一点运气，则一定可以找到理想的公司。不要害怕，很多时候就算没有面试成功，也应该总结一下，等过段时间后便能感悟到自己的成长。
算法有很多，而且不停地有新的算法出现。本书将介绍其中一些比较基础且常用的算法，当然，会先简单介绍几个基础的数据结构作为学习算法的铺垫；之后会介绍一些在工作中可能用到的算法；最后会介绍一些新兴的算法，以拓展读者的思路。
我会尽量以轻松、愉快的方式介绍每一个算法，由浅入深地介绍如何在工作中使这些算法变成我们的代码，让我们在开发应用时更高效。第1章数组、集合和散列表
我们将在本章中学习最基础、最简单的数据结构及其延伸。
数组，作为数据结构中最基础的一个存储方式，是我们学习一切数据结构、算法的基石。大部分数据结构都可以用数组来实现。本章会介绍数组的概念、存储结构、特点及适用场景。
集合这个结构其实并不存在于我们在学校学习的数据结构知识中，而是在一些高级语言中出现的，算是升级版的数组。本章会介绍集合的特点、实现及它的适用场景。
散列表，又叫哈希表（Hash Table），其实在很多高级语言里是在数组的基础上实现的，当然散列表也有其他实现形式。本章会详细介绍散列表的基本概念、实现方式，并结合实现方式介绍其对应的存储结构、特点及适用场景。1.1要用就要提前想好的数据结构——数组
要用就要提前想好？为什么？这其实是由数组的一个特点决定的，那就是对于数组这个数据结构，在用它之前必须提前想好它的长度；有了长度，才能知道该为这个存储结构开辟多少空间；而在决定了长度之后，不管我们最后往里面填充的数据够不够长，没有用到的空间也就都浪费了；如果我们想往这个数组中放入的数据超过了提前设定好的长度，那么是不可行的，因为空间只有这么大。1.1.1 什么是数组
数组（Array），就是把有限个数据类型一样的元素按顺序放在一起，用一个变量命名，然后通过编号可以按顺序访问指定位置的元素的一个有序集合。
其实简单来说，就是为了方便而把这些元素放在一起。我们通过编号去获取每个元素，这个编号叫作下标或者索引（Index），一般的语言是从0开始的。
我们常说的数组一般指一维数组，当然还有多维数组，虽然多维数组并不常用。
多维的实现其实是数组的某些元素本身也是一个数组，这里以一个标准的二维数组为例进行介绍。其实，二维数组相当于每个元素的长度都一样的一个一维数组（也就是我们常说的数组）。可以想象一下矩阵（若不了解矩阵，则请阅读1.1.2节中标准二维数组的存储结构示例），其实它和数学中的矩阵类似。
在很多弱语言中，并不要求每个元素的长度都一样，可以某些元素是数组（长度可以不一样），某些元素不是数组，甚至每个元素的数据类型都不同。这里讲的二维数组指的是标准的二维数组。
注：弱类型语言也叫作弱类型定义语言，简称弱语言。弱语言一般对语言的标准没有特别的要求。比如在JavaScript中用var声明变量，不会指定该变量是哪种类型。如果想更多地了解弱语言，则请参考JavaScript，该语言主要用于前端开发。强语言对编写规则比较有要求，所以不容易出现问题，很多开发工具都会帮助检查其基本规则。1.1.2 数组的存储结构
在了解了什么是数组之后，我们来看下数组的存储结构。
1.数组的存储结构
首先我们来看下一维数组的存储结构，如图1-1所示。图1-1 数组的存储结构
其实，我们先要确定一个值，也就是数组的长度；然后，系统会根据我们声明的数据类型开辟一些空间（当然，每种数据类型需要开辟的空间也不一样）。这时，这些空间就归这个变量所有了。一般在编程语言的实现中，这些空间会默认对我们声明的数据类型赋值，比如整型值是0，布尔值是false，等等。
所以有以下几种情况。（1）只声明了指定长度的空间，没有初始化值（以整型为例，所有值都会默认为0，如图1-2所示）。图1-2 在未初始化值时会默认初始化为0（2）声明了指定长度的空间，初始化了部分值（以整型为例，未初始化的值都会默认为0，如图1-3所示）。图1-3 只初始化了前三个值，其余值自动初始化为0（3）声明了指定长度的空间，初始化了全部的值，如图1-4所示。图1-4 初始化了全部的值
2.数组在编程语言中的初始化及操作
在多数语言中，数组的声明都是非常简单的，一般有下面几种声明方式（以Java语言、整型为例，其他语言、数据类型差异不大）。
数组指定位置的元素的值，是通过下标获取的，下标在大部分语言中是从0开始的。
为数组赋值，和获取元素的值类似，可以直接赋值。
数组常用的另一种方式是按顺序访问每一个值，一般通过编程语言中的循环语句实现（比如for循环）。
上面展示了循环打印数组的值的代码，其中num.length可以获取数组的长度。细心的同学可以发现这个length后面没有括号，是的，这个length是数组的内置属性（以Java为例，有些语言会同时提供两种或更多的获取数组长度的方式）。
下面我们看下二维数组的存储结构，如图1-5所示。图1-5 二维数组的存储结构
二维数组的初始化方式实际上和一维数组没有太大的区别，只不过我们需要提前确定第1维和第2维的长度。
在图1-5中，第1维的长度为3，每维的元素又是一个长度为6的数组。
3.多维数组在编程语言中的初始化及操作
由于多维数组与一维数组的初始化及访问区别不大，下面集中进行列举。
二维数组的访问方式其实和一维数组和多维数组的访问方式没什么区别，我们只需要理解为数组的元素也是个数组。1.1.3 数组的特点
因为本身存储的方式，数组有如下特点。
1.定长
数组的长度是固定的，这是数组最重要的一个特点。
只要我们在声明时确定了数组的长度，在赋值时就算没有给数组的所有元素赋值，未赋值的元素也是有初始默认值的；而如果我们在赋值时发现数组的长度不够用，这时也没有什么好办法，因为数组的长度无法改变。要是想继续存放数据，就只能重新声明一个数组了。
2.按顺序访问
我们在访问一个数组中的某个元素时，必须从第1个元素开始按顺序访问，直到访问到指定位置的元素。
这里想说明一点，虽然我们在开发时可以直接通过下标访问指定位置的元素，但是实际上计算机在处理时也是按顺序访问的。1.1.4 数组的适用场景
数组其实是一个非常简单的数据结构，用起来也比较简单。但是，数组是所有数据结构的基础，我们必须掌握好数组，才能更好地学习其他数据结构和算法。
数组适合在什么时候用，其实根据数组的特点我们就可以想到，由于数组的长度一般是固定的，所以在不会出现变化的业务上比较适合使用数组。
注：本书所举例的适用场景只是可以并且多数会这样做，并不是说这种使用方式是最优的或者可不替代的。实际上有些团队可能会有一些更好的实现方式。
1.技能快捷键
不知道大家对RPG（ARPG）等类似的游戏了解多少，在这类游戏中会有一排快捷键技能格，比如F1～F9这样9个快捷键技能格，我们每个人可以把自己惯用的技能拖动到这些技能格上，这样就可以直接通过技能快捷键操控技能了。一般在这种设计中，一个游戏的快捷键格子会有固定的个数。于是，我们在程序里就可以通过数组来存储每个人的技能快捷键对应的技能（当然，肯定会通过一定的映射存到数据库之类的磁盘上）。
2.优酷8+1
先声明，我没有参与制作优酷8+1，这里只是举例。优酷8+1是什么？打开优酷首页，会看到最上面的1个大图、8个小图，这就是优酷8+1了。
这里我们可以声明一个长度为9的数组，里面的每个元素是一个对象（对象是高级语言中的一个名词，包含了一系列的变量和方法），这些对象至少应该包含图片地址（用于展示图片）和URL地址（用于在单击后跳转）。
到这里，我们应该已经很清晰地认识到了数组的劣势，那就是在用之前必须提前确定数组的长度，而后不管我们的技能是否需要增加快捷键位，或者优酷首页从8+1变成了11+1，都会导致对程序进行一定的改动。这时我们就该认识一下数组的升级版——集合了。1.2升级版数组——集合
数组的致命缺点就是长度固定，如果我们一开始不确定长度，该怎么办呢？这时就需要集合了，其实集合也是基于数组实现的。在许多高级语言中，集合是对数组的一个拓展，我们在向里面放数据时，想放多少就可以放多少，不用在意集合到底能放多少（当然得内存够用才行）。1.2.1 什么是集合
集合的概念有些宽泛。本节讲的集合主要是可变长度的列表（也叫作动态数组）。
下面这些都是集合。
◎ 列表：一般是有序的集合，特点就是有顺序，比如链表、队列、栈等，我们会在第2章学习这些集合。
◎ 集：一般是无序的集合，特点就是没有顺序并且数据不能重复，多数语言是使用散列表实现的，支持对集进行添加、删除、查找包含等操作。
◎ 多重集：一般是无序的集合，特点是没有顺序，但是数据可以有重复的值，支持对集进行添加、删除、查找包含、查找一个元素在集中的个数等操作。多重集一般可以通过排序转换为列表。
◎ 关联数组：其实多数语言是使用散列表实现的，就是可以通过键（Key）获取到值（Value）。同样是没有顺序的。
◎ 树、图：同样是集合，我们会在后面进行详细了解。1.2.2 集合的实现
本节说的集合在数据结构书中本来是不会有的，但我还是决定介绍一下，这不管是对我们拓展思路还是了解更多的内容，都是有帮助的。
这里以Java中的ArrayList为例，它是一个数组的列表，其实就是数组的拓展，或者说是可变长度的数组。
上面一直提到，这个ArrayList是基于数组实现的，这如何理解呢？其实就是在ArrayList里有个属性，这个属性是一个数组。另外，还会有个属性记录我们放了多少数据，这样我们再向其中放数据时，就会知道该向这个内部数组的哪个位置放数据了，但是这个数组也会有长度限制，若超过了这个限制该怎么办呢？当超过这个限制时，其内部会创建一个具有更长的长度的数组，然后把旧数组的数据复制到新数组里面，这样就可以继续往里面放数据了。
在外部，我们感觉不到这个ArrayList是有长度限制的，它在自己内部都处理好了。
下面我们通过图1-6来形象地理解一下这个流程吧。图1-6 ArrayList插入数据的流程注：在面向对象的编程语言中一般把成员变量称为属性。
下面我们先来简单地用代码实现这个变长数组。在第10章中，我们会进一步实现ArrayList这个集合。
这里以整型为例简单实现了变长数组。
可以看到，其中有两个属性：一个是array，就是内部数组；另一个是size，用来存当前变长数组的长度。当调用add向变长数组中放值时，要确认内部数组是否足够放这个值，若不够，就生成一个长度是原数组长度的两倍的新数组，并且复制旧数组的数据到新数组里，再放值。
这里新建数组并复制旧数组的数据，是通过Java内部的一个工具类实现的，底层调用的是本地方法（native），效率很高。
上面的代码展示了如何调用变长数组来执行添加、修改、获取值、获取总长度操作。在调用过程中，我们完全不用在意其内部是怎么实现的，只需往里面添加值、获取值就好了。
很多编程语言的实现，要比这个实现复杂得多，因为除了这些简单的操作，还需要一些更复杂的操作，另外要考虑很多其他问题，比如这个数组的增幅怎样设置比较合理等（上面的代码是每次直接增加为两倍。当然，这部分实现对于每种语言，甚至每种语言的每个版本都不一定一样）。1.2.3 集合的特点
集合的特点，也和它的实现有关，那就是变长。变长是相对而言的，内部还是通过数组实现的，只是在不够长时根据一定的策略生成一个更长的数组，把旧数组中的数据复制到新数组里使用。
所以在正常情况下会有两个系统开销：一个是数组总是比我们实际使用的长度长，所以存在空间浪费；另一个是当数组不够长时，需要新建一个更长的数组，同时把旧数组的数据复制到新数组中，这个操作会比较消耗系统的性能。1.2.4 集合的适用场景
集合的适用场景很多。现在基本上所有的批量查询及获得一定条件的数据列表，都使用变长数组。比如查询某游戏中一个玩家包裹里的所有物品，若不清楚物品的数量，则会用变长数组去存储返回的结果。
博客的文章列表、评论列表等，只要涉及列表，就会有集合的身影。
是不是有了变长数组就够了？当然不够，在后面的算法学习中，我们会了解到数组的查询效率是很低的，所以要使用一些更复杂的其他数据结构，来帮助我们完成更高效的算法实现。1.2.5 数组与变长数组的性能
虽然集合这个变长数组比普通数组高级一些，但它本质上是基于数组实现的，所以与数组的性能差不多。
对数组的操作，并不像我们看到的那么直观，计算机需要根据我们具体操作的位置，从头到尾一个一个地寻找到指定的位置，所以在数组中增加元素、修改元素、获取元素等操作的时间复杂度都为O（n）。
变长数组也有性能损耗的问题，在插入元素时若发现其中的固定数组长度不够，则需要新建更长的数组，还得复制元素，这都会造成性能损耗。
注：在算法中，每种算法的性能指标一般有两个，即时间复杂度和空间复杂度。在设计算法的过程中，时间复杂度和空间复杂度往往是互相影响的，所以一般会在其中根据实际应用场景寻找一个最优的实现。
◎ 时间复杂度：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数，常用大O符号描述，不包括这个函数的低阶项和首项系数，它实际上描述了算法执行的时间。
◎ 空间复杂度：是对一个算法在运行过程中临时占用存储空间大小的量度。1.3数组的其他应用——散列表
我们在前面提到集合其实是有很多种的，散列表也算是集合的一种。为什么需要散列表呢？实际上顺序存储的结构类型需要一个一个地按顺序访问元素，当这个总量很大且我们所要访问的元素比较靠后时，性能就会很低。
散列表是一种空间换时间的存储结构，是在算法中提升效率的一种比较常用的方式，但是所需空间太大也会让人头疼，所以通常需要在二者之间权衡。我们会在之后的具体算法章节中得到更多的领悟。1.3.1 什么是散列表
让我们想一下，若在手机通信录中查找一个人，那我们应该不会从第1个人一直找下去，因为这样实在是太慢了。我们其实是这样做的：首先看这个人的名字的首字母是什么，比如姓张，那么我们一定会滑到最后，因为“Z”姓的名字都在最后。
还有在查字典时，要查找一个单词，肯定不会从头翻到尾，而是首先通过这个单词的首字母，找到对应的那一页；再找第2个字母、第3个字母……这样可以快速跳到那个单词所在的页。
其实这里就用到了散列表的思想。
散列表，又叫哈希表（Hash Table），是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。也就是说，把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。
通常，我们把这个关键字称为Key，把对应的记录称为Value，所以也可以说是通过Key访问一个映射表来得到Value的地址。而这个映射表，也叫作散列函数或者哈希函数，存放记录的数组叫作散列表。
其中有个特殊情况，就是通过不同的Key，可能访问到同一个地址，这种现象叫作碰撞（Collision）。而通过某个Key一定会得到唯一的Value地址。
目前，这个哈希函数比较常用的实现方法比较多，通常需要考虑几个因素：关键字的长度、哈希表的大小、关键字的分布情况、记录的查找频率，等等。
下面简单介绍几种哈希函数。
1.直接寻址法
取关键字或关键字的某个线性函数值为散列地址。
2.数字分析法
通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。
3.平方取中法
当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。
4.取随机数法
使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。
5.除留取余法
取关键字被某个不大于散列表的表长n的数m除后所得的余数p为散列地址。这种方式也可以在用过其他方法后再使用。该函数对m的选择很重要，一般取素数或者直接用n。
1.3.2对散列表函数产生冲突的解决办法
散列表为什么会产生冲突呢？前面提到过，有时不同的Key通过哈希函数可能会得到相同的地址，这在我们操作时可能会对数据造成覆盖、丢失。之所以产生冲突是由于哈希函数有时对不同的Key计算之后获得了相同的地址。
冲突的处理方式也有很多，下面介绍几种。
1.开放地址法（也叫开放寻址法）
实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。
2.再哈希法
在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。
3.链地址法
链地址法其实就是对Key通过哈希之后落在同一个地址上的值，做一个链表。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的，我们会在后面着重学习这种方式。
4.建立一个公共溢出区
这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。1.3.3 散列表的存储结构
一个好的散列表设计，除了需要选择一个性能较好的哈希函数，否则冲突是无法避免的，所以通常还需要有一个好的冲突处理方式。这里我们选择除留取余法作为哈希函数，选择链地址法作为冲突处理方式。
具体存储结构如图1-7所示。图1-7 散列表的存储结构
在大多数时候，我们通过数组定义散列表，如图1-7所示，这时我们声明的数组长度是8，也就是说散列表的长度为8。
这里以Key的类型为整型数字为例，用Key对长度8取余，必定会得到很大的冲突，这时每个地址并不放真正的值，而是记录一个链表的起始地址。当然，在实际情况下我们不会让这个哈希表这么短，这里只是举个简单的例子。
通过这种方式，我们可以快速地找到Key所对应的Value在哪个地址上，如果在这个地址上链表比较长，则也需要一个个地去检索。
在通常情况下，新增元素时如果遇到了冲突，那么链表会有两种方式去插入元素。
◎ 一种方式是直接把新元素的下一个元素指向原来链表的第1个元素，然后把刚刚对应上的那个地址链表头的下一个元素指向新建的元素。这种方式的好处是在插入元素时会比较快，因为不需要遍历链表，而是直接改变头部的指向关系。
◎ 另一种方式是使链表元素有序，这种方式的劣势就是在每次插入元素时需要遍历链表，在中间打开链表、插入元素。
注：这里涉及了一些链表知识，读者可以简单地将其理解为一条链子，每个元素都会有一个指向下一个元素地址的指针。也可以将其理解为数组，是有序的、挨着的，具体会在下面的链表章节中进行讲解。
有的读者会问，这里是以整数为例的，万一这个Key需要是一个字符串类型呢？其实在很多编程语言的实现中，都会存在将一个类型转换为整型的方法，比如Java中的每个对象都有个hashCode方法，通过获取字符串的这个方法，可以将一个字符串轻松地转换为整型。当然，这种方法还可能返回负数，这也是可以直接使用绝对值解决的。1.3.4 散列表的特点
散列表有两种用法：一种是Key的值与Value的值一样，一般我们称这种情况的结构为Set（集合）；而如果Key和Value所对应的内容不一样时，那么我们称这种情况为Map，也就是人们俗称的键值对集合。
根据散列表的存储结构，我们可以得出散列表的以下特点。
1.访问速度很快
由于散列表有散列函数，可以将指定的Key都映射到一个地址上，所以在访问一个Key（键）对应的Value（值）时，根本不需要一个一个地进行查找，可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时，速度都很快。
2.需要额外的空间
首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题（有关扩容的内容，会在1.3.6节进行讲解）。
另外，如果有冲突的话，则也是需要额外的空间去存储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。
这个特点有个很常用的词可以表达，叫作“空间换时间”，在大多数时候，对于算法的实现，为了能够有更好的性能，往往会考虑牺牲些空间，让算法能够更快些。
3.无序
散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素，散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快，但是对于有序访问却没有办法应对。
4.可能会产生碰撞
没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决方案不一定一样。1.3.5 散列表的适用场景
根据散列表的特点可以想到，散列表比较适合无序、需要快速访问的情况。
1.缓存
通常我们开发程序时，对一些常用的信息会做缓存，用的就是散列表，比如我们要缓存用户的信息，一般用户的信息都会有唯一标识的字段，比如ID。这时做缓存，可以把ID作为Key，而Value用来存储用户的详细信息，这里的Value通常是一个对象（高级语言中的术语，前面提到过），包含用户的一些关键字段，比如名字、年龄等。
在我们每次需要获取一个用户的信息时，就不用与数据库这类的本地磁盘存储交互了（其实在大多数时候，数据库可能与我们的服务不在一台机器上，还会有相应的网络性能损耗），可以直接从内存中得到结果。这样不仅能够快速获取数据，也能够减轻数据库的压力。
有时我们要查询一些数据，这些数据与其他数据是有关联的，如果我们进行数据库的关联查询，那么效率会非常低，这时可以分为两部分进行查询：将被关联的部分放入散列表中，只需要遍历一遍；对于另一部分数据，则通过程序手动关联，速度会很快，并且由于我们是通过散列表的Key、Value的对应关系对应数据的，所以性能也会比较好。
我之前所在的一家公司曾要做一个大查询，查询和数据组装的时间达到了40秒，当然，数据量本身也比较大。但是，40秒实在让人无法忍受，于是我优化了这段代码，发现可以通过散列表处理来减少很多重复的查询，最终做到了4秒左右的查询耗时，速度快了很多。
2.快速查找
这里说的查找，不是排序，而是在集合中找出是否存在指定的元素。
这样的场景很多，比如我们要在指定的用户列表中查找是否存在指定的用户，这时就可以使用散列表了。在这个场景下使用的散列表其实是在上面提到的Set类型，实际上不需要Value这个值。
还有一个场景，我们一般对网站的操作会有个IP地址黑名单，我们认为某些IP有大量的非法操作，于是封锁了这些IP对我们网站的访问。这个IP是如何存储的呢？就是用的散列表。当一个访问行为发送过来时，我们会获取其IP，判断其是否存在于黑名单中，如果存在，则禁止其访问。这种情况也是使用的Set。
当然，对于上面说的两个例子，用列表也是可以实现的，但是访问速度会受到很大的影响，尤其是列表越来越长时，查找速度会很慢。散列表则不会。1.3.6 散列表的性能分析
散列表的访问，如果没有碰撞，那么我们完全可以认为对元素的访问是O（1）的时间复杂度，因为对于任何元素的访问，都可以通过散列函数直接得到元素的值所在的地址。
但是实际上不可能没有碰撞，所以我们不得不对碰撞进行一定的处理。
我们常用链表方式进行解决（当然，也有一些语言使用开放寻址方式解决，Java使用链表解决），由于可能会产生碰撞，而碰撞之后的访问需要遍历链表，所以时间复杂度将变为O（L），其中L为链表的长度。当然，在大多数时候不一定会碰撞，而很多Key也不一定刚好都碰撞到一个地址上，所以性能还是很不错的。
上面提到了一个情况，那就是有可能分配的地址即散列表的元素大部分被使用了，这时再向散列表中添加元素，就很容易产生碰撞了，甚至散列表分配的地址越在后面使用，越容易被占用。这时该怎么办呢？解决办法很简单，就是上面提到的——扩容。
比如之前在存储结构一节举例的，散列表长度只有8，很容易被占满，一般不会等到真的占满了才去扩容，而是会提前扩容。这里设计一个叫作扩充因子的术语（也叫作载荷因子，意思是达到这个值时，其性能就不好了），是一个小数，在使用散列表的过程中，不会等到把所有地址都用完了才去扩容，而是会在占用地址达到散列表长度乘以扩容因子的这个值时去扩容，一般的扩容会在原有的长度基础上乘以2作为新的长度。
这里可以直接告诉大家，在Java中，扩容因子默认为0.75（很多语言都是0.75，这算是个经验数值吧），以之前的存储结构一节的总长度是8为例，当占用长度达到6时，就会扩容，而扩容后的长度会变为16。
当然，扩容有很多工作要做，除了简单地增加原本的散列表长度，还需要把之前那些由于碰撞而存放在一个地址的链表上的元素重新进行哈希运算，有可能之前存在碰撞的元素，现在不会碰撞了（比如图1-7中值为1和9的数，由于现在总长度为16了，所以它们通过除留取余法，不会指到同一个地址了）。
下面展示如何用代码实现一个简单的散列表，这里用数组代替散列表元素（在真实的高级语言实现中，大多数元素都是一个特别的数组，每个元素对应一个地址），每个数组元素作为一个地址。
首先需要一个元素类，这个类用于存储Key及Value，实际上就是链表上的每一个元素。实现起来非常简单。
下面是散列表的实现代码。
下面是对我们自己实现的散列表的一个小小的测试。1.4小结
数组，作为数据结构与算法中非常基础、常用的一个结构，是我们必须掌握的内容。在本章中，我们通过学习数组及其实现，并学习集合、散列表这两个稍微高级点的数据结构，对数组的应用有了更深入的了解。通过对比这三种结构，我们更加清楚它们之间的区别和适用场景了。
在本章的每一节中都有示例代码，读者应该在学习的过程中跟着敲一遍代码，在了解了其中的原理之后自己再练习一遍，最后与书核对一下看是否有遗漏。当然，本章的代码并不是特别完善的，只是举例写了一部分功能，在真正的编程语言中的实现会更复杂。
如果希望有更好的提升，则可以尝试把本章中散列表的冲突处理方式改为开放地址方式，我想聪明的读者一定可以轻松搞定。第2章栈、队列、链表
本章将会带大家学习数据结构中非常有意思的几个数据结构——栈、队列和链表，这三个结构都是用于顺序存储数据的，但是由于它们的存储方式不同，并且各有特点，所以在本章中一起讲解并比较。如果把我们在第1章中学习的数组比作数据结构中幼儿园级别的内容，那么这三个数据结构相当于小学级别的内容了。
这三种数据结构也是我们在面试时经常被问到的知识点，大家要认真学习。本章会向大家讲解这三个数据结构的概念、存储结构、特点及适用场景，另外会介绍一些面试中可能会遇到的问题，读者可以将其作为参考来拓展自己的思路。2.1汉诺塔游戏——栈
应该有一部分人在小时听说过汉诺塔这个游戏。我记得在小时曾非常流行买电子词典来学习英语，基本上每个人都有一本电子词典。在电子词典中也预设了几个益智的小游戏，其中一个就是汉诺塔。2.1.1 什么是汉诺塔
汉诺塔是印度的一个古老的益智玩具，其基本设置如图2-1所示。图2-1 汉诺塔游戏的基本设置
这个游戏的目标是，把A上的所有圆盘重新按顺序堆到C上，但是有两个规则，一是小圆盘不能放置在大圆盘下面，二是每次只能移动一个圆盘。
怎么才能完成这个游戏？大家可以先思考一下。
我们先来举个简单的例子：假如只有三个圆盘，那么怎么玩呢？为了描述方便，我们按照从小到大的顺序将圆盘分别编号为1、2、3号。
最初，三个圆盘都在A柱子上，开始后每次只能移动一个圆盘，那么将1号圆盘放到B上，还是C上？如果将1号圆盘放到B上，那么根据小圆盘不能处于大圆盘之下的规则，2号圆盘只能放到C上；当把1号圆盘放回到2号圆盘上时，1、2号圆盘都在C上，之后再要移动的3号圆盘只能放到B上了。这时你可能会想：如果游戏的目标是把圆盘移动到B上该多好啊，那么此刻就快完成了。但游戏的目标是将所有圆盘按顺序移动到C上。当然，现在圆盘比较少，肯定能完成目标，只是移动的次数有些多。我们反过来思考一下，一开始把1号圆盘移动到C上，这样移动的步数是最少的。
通过这个动手操作的过程，我们反过来思考一下，怎么移动才能让最大的圆盘到最后刚好放到C上？
假设圆盘总数为N，那么我们需要先把上面N-1个圆盘从A移动到B上，然后第N个圆盘才能移动到C上，之后再把B上N-1个圆盘移动到C上，又该怎么移动？此时必须先把最小的N-2个圆盘从B上全部移动到A上，第N-1个圆盘才能移动到C上，同理可依次完成剩下圆盘的移动，直至最终完成游戏。
大家可以先想想怎么去解决，其实现代码会在2.6节具体介绍。2.1.2 什么是栈
栈是一个有着特殊规则的数据结构。我们在前面了解了汉诺塔游戏，这里有一个明确的规则，即每次只能移动顶端的一个圆盘。
栈也有这个特点。我们可以将栈视为汉诺塔中的一个柱子，我们往这个柱子上放置圆盘，先放下去的一定是最后才能拿出来的，而最后放下去的一定是最先拿出来的。这也是栈的最重要一个特点——后进先出（LIFO，Last In First Out），也可以说是先进后出（FILO，First In Last Out），我们无论如何只能从一端去操作元素。
栈又叫作堆栈（Stack），这里说明一下不要将它和堆混淆。实际上堆和栈是两个不同的概念，栈是一种只能在一端进行插入和删除的线性数据结构。
一般来说，栈主要有两个操作：一个是进栈（PUSH），又叫作入栈、压栈；另一个是出栈（POP），或者叫作退栈。
其实栈是一种比较简单的数据结构，但是由于其特性，又衍生了不少的相关算法。2.1.3 栈的存储结构
栈一般使用一段连续的空间进行存储，通常预先分配一个长度，可以简单地使用数组去实现，具体的存储结构如图2-2所示。图2-2 栈的存储结构
通过图2-2可以清晰地看到，只有一个方向可以对栈内的元素进行操作，而栈中最下面的一个元素成为栈底，一般是数组的第0个元素，而栈顶是栈内最后放入的元素。
一般而言，定义一个栈需要有一个初始的大小，这就是栈的初始容量。当需要放入的元素大于这个容量时，就需要进行扩容。栈扩容的实现类似于在第1章中介绍的集合。
栈出入元素的操作如下。例如我们初始化一个长度为10的数组，并向其中放入元素，根据栈的定义，只能从数组的一端放入元素，我们设定这一端为数组中较大下标的方向。我们放入第1个元素，由于栈内没有元素，于是第1个元素就落到了数组的第0个下标的位置上；接着放入第2个元素，第2个元素该放入下标为1的位置上；以此类推，当放入了5个元素时，第5个入栈的元素应该在数组的第4个下标的位置上。现在我们要进行出栈操作，出栈只能从一端操作，我们之前设定只能从数组下标较大的方向操作，因此需要确定数组中下标最大的一个方向中存在栈元素的位置下标是多少。我们一般会在栈中做个计数器来记录这个值。现在栈中有5个元素，所以将数组中的第5个位置也就是下标为4的元素出栈。此时数组中只剩下4个元素了。
下面是栈的实现代码，这里以整型元素为例，在Java类的高级语言中，数据类型可以换成对象。
试读结束[说明：试读内容隐藏了图片]