2. 数据结构基础
2.1 什么是数组
2.1.1 概念
数组对应的英文是array， 是有限个相同类型的变量所组成的有序集合， 数组中的每一个变量被称为元素。 数组是最为简单、 最为常用的数据结构。
数组在内存中顺序存储（连续内存）
2.1.2 数组的基本操作
- 读取
由于数组在内存中顺序存储， 所以只要给出一个数组下标， 就可以读取到对应的数组元素。 输入的下标必须在数组的长度范
围之内， 否则会出现数组越界 - 更新
利用数组下标， 就可以把新值赋给该元素
插入
- 尾部插入：直接把插入的元素放在数组尾部的空闲位置即可。
- 中间插入：会涉及到元素的移动。
- 超范围插入：在插入时数组越界进行扩容。
- 删除
删除元素也会涉及元素的移动。
2.1.3 数组的优势和劣势
- 优势：数组拥有非常高效的随机访问能力，只要给出下标就能迅速获取数据。
- 劣势：数组的元素都存放在连续的内存中，插入和删除涉及大量的元素移动，影响效率。
- 总结：数组适合读操作多，写操作少的场景。
2.2 什么是链表
2.2.1 概念
- 链表（linked list） 是一种在物理上非连续、 非顺序的数据结构， 由若干节点（node）所组成。
- 单向链表的每一个节点又包含两部分， 一部分是存放数据的变量data， 另一部分是指向下一个节点的指针next。
- 双向链表比单向链表稍微复杂一些， 它的每一个节点除了拥有data和next指针， 还拥有指向前置节点的prev指针。
2.2.2 链表的基本操作
- 查找节点：从头节点开始向后一个一个节点逐一查找
- 更新节点：更新=查找+替换。替换直接把旧数据替换成新数据即可。
插入节点：
- 尾部插入：最后一个节点的next指针指向新插入的节点
- 头部插入：把新节点的next指针指向原先的头节点 ，把新节点变为链表的头节点 。
- 中间插入：新节点的next指针， 指向插入位置的节点 。插入位置前置节点的next指针， 指向新节点。
删除元素：
- 尾部删除：把倒数第2个节点的next指针指向空即可。
- 头部删除：把链表的头节点设为原先头节点的next指针即可。
- 中间删除：把要删除节点的前置节点的next指针， 指向要删除元素的下一个节点即可。
2.2.3 数组VS链表
数据结构没有绝对的好坏，数组和链表各有千秋。
- 从表格可以看出，数组的优势在于能够快速定位元素，对于读操作多，写操作少的业务场景，数组更合适。
- 链表的优势在于能够灵活的进行插入和删除，适合需要频繁插入和删除元素的业务场景。
2.3 栈和队列
2.3.1 物理结构和逻辑结构
逻辑结构是抽象的概念， 它依赖于物理结构而存在。
栈和队列就属于逻辑结构，他们的物理实现可以使链表也可以是数组。
2.3.2 什么是栈
栈（stack） 是一种线性数据结构。栈中的元素只能先入后出（First In Last Out， 简称FILO）。最早进入的元素存放的位置
叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶（top） 。
栈这种数据结构既可以用数组来实现， 也可以用链表来实现。
栈的数组实现如下。
栈的链表实现如下。
2.3.3 栈的基本操作
- 入栈
入栈操作（push） 就是把新元素放入栈中， 只允许从栈顶一侧放入元素， 新元素的位置将会成为新的栈顶。
- 出栈
出栈操作（pop） 就是把元素从栈中弹出， 只有栈顶元素才允许出栈， 出栈元素的前一个元素将会成为新的栈顶。
2.3.4 什么是队列
队列（queue） 是一种线性数据结构，不同于栈的先入后出， 队列中的元素只能先入先出（First In First Out， 简称FIFO） 。 队列的出口端叫作队头（front） ， 队列的入口端叫作队尾（rear） 。
与栈类似， 队列这种数据结构既可以用数组来实现， 也可以用链表来实现。
队列的数组实现如下。
队列的链表实现如下。
2.3.5 队列的基本操作
对于链表实现方式， 队列的入队、 出队操作和栈是大同小异的。 但对于数组实现方式来说， 队列的入队和出队操作有了一些有趣的变化。
- 入队
入队（enqueue） 就是把新元素放入队列中， 只允许在队尾的位置放入元素， 新元素的下一个位置将会成为新的队尾。
- 出队
出队操作（dequeue） 就是把元素移出队列， 只允许在队头一侧移出元素， 出队元素的后一个元素将会成为新的队头。
- 数组队列
在数组不做扩容的前提下， 如何让新元素入队并确定新的队尾位置呢？ 我们可以利用已出队元素留下的空间， 让队尾指针重新指回数组的首位。
一直到（ 队尾下标+1） %数组长度 = 队头下标时， 代表此队列真的已经满了。 需要注意的是， 队尾指针指向的位置永远空出1位， 所以队列最大容量比数组长度小1。
2.3.6 栈和队列的应用
- 栈的应用：
栈的输出顺序和输入顺序相反， 所以栈通常用于对“历史”的回溯， 也就是逆流而上追溯“历史”。
例如实现递归的逻辑， 就可以用栈来代替， 因为栈可以回溯方法的调用链。
- 队列的应用：
队列的输出顺序和输入顺序相同， 所以队列通常用于对“历史”的回放， 也就是按照“历史”顺序， 把“历史”重演一遍。
例如在多线程中， 争夺公平锁的等待队列， 就是按照访问顺序来决定线程在队列中的次序的。
再如网络爬虫实现网站抓取时， 也是把待抓取的网站URL存入队列中， 再按照存入队列的顺序来依次抓取和解析的。
- 双端队列：
双端队列这种数据结构， 可以说综合了栈和队列的优点， 对双端队列来说， 从队头一端可以入队或出队， 从队尾一端也可以入队或出队。
- 优先队列：
还有一种队列， 它遵循的不是先入先出， 而是谁的优先级最高， 谁先出队。
这种队列叫做优先队列
优先队列已经不属于线性数据结构的范畴了， 它是基于二叉堆来实现的。
2.4 散列表
2.4.1 散列表
散列表也叫作哈希表（hash table） ， 这种数据结构提供了键（ Key） 和值（ Value）的映射关系。 只要给出一个Key， 就可以高效查找到它所匹配的Value， 时间复杂度接近于O(1)。
2.4.2 哈希函数
散列表本质上是一个数组，通过hash函数将key值映射到数组下标上。
在java以及大多数语言中，每个对象都有属于自己的hashcode，这个hashcode是区分不同对象的重要标识。无论对象自身的类型是什么，他们的hashcode都是一个整型变量。
通过这个整型变量转化成数组下标就不难实现了。最简单的转化方式如下：按照数组长度进行取模运算。
index = HashCode (Key) % Array.length
实际上， JDK（Java Development Kit， Java语言的软件开发工具包） 中的哈希函数并没有直接采用取模运算， 而是利用了位运算的方式来优化性能。 不过在这里可以姑且简单理解成取模操作。
key=001121时，
index = HashCode ("001121") % Array.length = 1420036703 % 8 = 7
而当key=this时，
index = HashCode ("this") % Array.length = 3559070 % 8 = 62.4.3 散列表的读写操作
写操作（put）:
- 通过hash函数计算出数组下标
- 如果数组下标位置没有数据，则存入数据。
如果下标位置已经存在数据，即产生hash冲突
- 开放地址法：线性探测、再平方、伪随机
- 链地址法：
读操作（get）:
- 通过hash函数计算key的index地址
- 找到数组对应的元素位置，然后根据key的equals判断获取到对应的value。
扩容（resize）:
对于JDK中的散列表实现类HashMap来说， 影响其扩容的因素有两个。
- Capacity， 即HashMap的当前长度
- LoadFactor， 即HashMap的负载因子， 默认值为0.75f
当HashMap的长度大于等于Capacity*LoadFactor触发扩容
- 扩容， 创建一个新的Entry空数组， 长度是原数组的2倍
- 重新Hash， 遍历原Entry数组， 把所有的Entry重新Hash到新数组中。
2.5 小结
- 什么是数组：
数组是由有限个相同类型的变量所组成的有序集合， 它的物理存储方式是顺序存储，访问方式是随机访问。 利用下标查找数组元素的时间复杂度是O(1)， 中间插入、 删除数组元素的时间复杂度是O(n)。
- 什么是链表：
链表是一种链式数据结构， 由若干节点组成， 每个节点包含指向下一节点的指针。 链表的物理存储方式是随机存储， 访问方式是顺序访问。 查找链表节点的时间复杂度是O(n)， 中间插入、 删除节点的时间复杂度是O(1)。
- 什么是栈：
栈是一种线性逻辑结构， 可以用数组实现， 也可以用链表实现。 栈包含入栈和出栈操作， 遵循先入后出的原则（FILO） 。
- 什么是队列：
队列也是一种线性逻辑结构， 可以用数组实现， 也可以用链表实现。 队列包含入队和出队操作， 遵循先入先出的原则（FIFO） 。
- 什么是散列表：
散列表也叫哈希表， 是存储Key-Value映射的集合。 对于某一个Key， 散列表可以在接近O(1)的时间内进行读写操作。 散列表通过哈希函数实现Key和数组下标的转换， 通过开放寻址法和链表法来解决哈希冲突。
