（二）常见数据结构及其优缺点

1、数组

数组

优点：查询快,通过索引直接查找
缺点：在中间部位增删复杂；大小固定；只能存储一种类型的数据
使用场景：频繁查询，很少增加和删除的情况

数组通过下标查询的时间复杂度为O(1)，增删需要移动后面的数据，时间复杂度为O(n)
参考：https://www.cnblogs.com/ysocean/p/7894448.html

2、链表

单向链表

双端链表

双向链表

优点：插入快，删除快，只需要修改元素指针就行了
缺点：查找慢，需要从第一个元素一个个节点查
使用场景：少查询，需要频繁插入或删除的情况

链表查询的时间复杂度为O(n)，增删的时间复杂度为O(1)
参考：https://www.cnblogs.com/ysocean/p/7928988.html

3、栈

栈

优点：提供后进先出（LIFO）的存取方式，添加速度快
缺点：只能在一头操作，存取其他项很慢
使用场景：①实现递归 ②字符串逆序 ③符号是否匹配等

栈可由数组或者单向链表实现，是一种ADT（抽象数据类型），入栈和出栈的时间复杂度都是O(1)
参考：https://www.cnblogs.com/ysocean/p/7911910.html

4、队列

队列

优点：提供先进先出的存取方式，添加速度快
缺点：只能在一头添加一头获取，存取其他项都很慢
使用场景：多线程阻塞队列管理非常有用

队列也可以有数组和双端链表实现，也是一种ADT，出队和入队的时间复杂度是O(1)
优先级队列的插入操作需要 O(n)的时间，而删除操作则需要O(1) 的时间
参考：https://www.cnblogs.com/ysocean/p/7921930.html

5、哈希表

image

$\color{red}{哈希表（HashTable，也叫散列表），是根据键（Key）直接访问在内存存储位置的数据结构。}$
其实现原理是：通过哈希函数（也叫散列函数）将元素的键映射为数组下标（转化后的值叫做哈希值或散列值），然后在对应下标位置存储记录值。当我们按照键查询元素时，就是用同样的哈希函数，将键转化数组下标，从对应的数组下标的位置取数据。

常见哈希函数：
①直接定址法：即 f(key) = a*key + b，f表示哈希函数，a、b是常量，key是键值
②数字分析法：即对数字做左移、右移、反转等操作获取散列值
③除数留余法：即 f(key) = key % p，p 表示容器数量，这种方式通常用在将数据存放到指定容器中，如何决定哪个数据放到哪个容器，比如分表后插入数据如何处理（此时p表示拆分后数据表的数量），分布式Redis如何存放数据（此时p表示几台Redis服务器）
④随机数法：即 f(key) = random(key)，比如负载均衡的random机制

设计再好的哈希函数也无法避免哈希冲突，原因是哈希值是非负整数，总量是有限的，但是现实世界中要处理的键值是无限的，将无限的数据映射到有限的集合，肯定避免不了冲突。事实上，如果不考虑哈希冲突，哈希表的查找效率是非常高的，时间复杂度是 O(1)，比二分查找效率还要高，但是因为无法避免哈希冲突，所以哈希表查找的时间复杂度取决于哈希冲突。

解决哈希冲突常用方法：
①开放寻址法：该方法又可以细分为三种 —— 线性探测、二次探测、随机探测。线性探测表示出现散列冲突之后，就去寻找下一个空的散列地址；线性寻址步长是1，二次探测步长是线性寻址步长的2次方，其它逻辑一样；同理，随机探测每次步长随机。不管哪种探测方法，散列表中空闲位置不多的时候，散列冲突的概率就会提高，为了保证操作效率，我们会尽可能保证散列表中有一定比例的空闲槽位，我们用装载因子来表示空位的多少， $\color{red}{装载因子=填入元素/散列表长度}$ ，装载因子越大，表明空闲位置越少，冲突越多，散列表性能降低。（当哈希表变得比较满时，我们每插入一个新的数据，都要频繁的探测插入位置，因为可能很多位置都被前面插入的数据所占用了，这称为聚集。数组填的越满，聚集越可能发生。二次探测会发生二次聚集。）
②再哈希法：发生散列冲突后，换一个散列函数计算散列值。 $\color{red}{这种方法不易产生聚集，但增加了计}$ $\color{red}{算时间。}$
③链地址法：这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。 $\color{red}{链地址法适用于经}$ $\color{red}{常进行插入和删除的情况。 }$ 找到初始单元需要O(1)的时间级别，而搜索链表的时间与M成正比，M为链表包含的平均项数，即O(M)的时间级别。
④建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

优点：如果关键字已知则存取速度极快，插入快
缺点：删除慢，如果不知道关键字则存取很慢，对存储空间使用不充分
应用场景：哈希表适用于那种查找性能要求高，数据元素之间无逻辑关系要求的情况。
Hash表在海量数据处理中有着广泛应用。

哈希算法的应用
1、场景一：安全加密
日常用户密码加密通常使用的都是 md5、sha等哈希函数，因为不可逆，而且微小的区别加密之后的结果差距很大，所以安全性更好。
2、场景二：唯一标识
比如 URL 字段或者图片字段要求不能重复，这个时候就可以通过对相应字段值做 md5 处理，将数据统一为 32 位长度从数据库索引构建和查询角度效果更好，此外，还可以对文件之类的二进制数据做 md5 处理，作为唯一标识，这样判定重复文件的时候更快捷。
3、场景三：数据校验
比如从网上下载的很多文件（尤其是P2P站点资源），都会包含一个 MD5 值，用于校验下载数据的完整性，避免数据在中途被劫持篡改。
4、场景五：散列函数
前面已经提到，PHP 中的 md5、sha1、hash 等函数都是基于哈希算法计算散列值
5、场景五：负载均衡
对于同一个客户端上的请求，尤其是已登录用户的请求，需要将其会话请求都路由到同一台机器，以保证数据的一致性，这可以借助哈希算法来实现，通过用户 ID 尾号对总机器数取模（取多少位可以根据机器数定），将结果值作为机器编号。
6、场景六：分布式缓存
分布式缓存和其他机器或数据库的分布式不一样，因为每台机器存放的缓存数据不一致，每当缓存机器扩容时，需要对缓存存放机器进行重新索引（或者部分重新索引），这里应用到的也是哈希算法的思想。
参考：https://www.cnblogs.com/mzhaox/p/11295360.html
https://www.cnblogs.com/mzhaox/p/11295279.html
https://www.cnblogs.com/ricklz/p/9006424.html

6、二叉树

二叉树

前面我们介绍数组的数据结构，我们知道对于有序数组，查找很快，并介绍可以通过二分法查找，但是想要在有序数组中插入一个数据项，就必须先找到插入数据项的位置，然后将所有插入位置后面的数据项全部向后移动一位，来给新数据腾出空间，平均来讲要移动N/2次，这是很费时的。同理，删除数据也是。

然后我们介绍了另外一种数据结构——链表，链表的插入和删除很快，我们只需要改变一些引用值就行了，但是查找数据却很慢了，因为不管我们查找什么数据，都需要从链表的第一个数据项开始，遍历到找到所需数据项为止，这个查找也是平均需要比较N/2次。

那么我们就希望一种数据结构能同时具备数组查找快的优点以及链表插入和删除快的优点，于是树诞生了。树是一种抽象数据类型（ADT）

$\color{red}{深度}$ ：节点的深度为从根到该节点的唯一路径长，根的深度为0；
$\color{red}{高度}$ ：节点的高度为从该节点到一片树叶的最长路径长，所有树叶的高度为0；

二叉树：树的每个节点最多只能有两个子节点
如果我们给二叉树加一个额外的条件，就可以得到一种被称作 $\color{red}{二叉搜索树}$ 的特殊二叉树。
二叉搜索树要求：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

$\color{red}{树的效率}$ ：查找节点的时间取决于这个节点所在的层数，每一层最多有2^n-1个节点，总共N层共有2ⁿ-1个节点，那么时间复杂度为O(log₂N)。（N表示的是二叉树节点的总数，而不是层数）。增删查的时间复杂度都是O(log₂N)，遍历树有前序遍历、中序遍历、后序遍历

优点：如果是平衡二叉树，那么查找，插入，删除都快
缺点：删除算法复杂
应用场景：常见业务需求像决策树、目录树、索引树、甚至简单的流程树都可以用二叉树来实现。
参考：https://www.cnblogs.com/ysocean/p/8032642.html

7、平衡二叉树（又叫AVL树，区别AVL算法）

$\color{red}{为了防止二叉搜索树退化成链表，产生了平衡二叉树。}$

AVL树

AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值（左子树的高度减去右子树的高度）判断是否平衡并通过旋转（左旋、右旋）来实现平衡，左右子树高度差不超过1。和红黑树相比，AVL树是严格的平衡二叉树，平衡条件必须满足(所有结点的左右子树高度差不超过1)。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保存平衡，而因为旋转非常耗时，由此我们可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况。

平衡二叉树常用算法有红黑树、AVL、Treap、伸展树等。

应用：Windows NI内核中广泛存在

8、红-黑树

$\color{red}{为了防止AVL树频繁插入和删除，产生了红-黑树。}$

红黑树

红黑树是一种含有红黑结点并能自平衡的二叉查找树。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因此，红黑树是一中弱平衡二叉树(由于是弱平衡，可以看到，在相同的节点情况下，AVL树的高度低于红黑树)，相对于要求严格的AVL树来说，它的旋转次数少，插入最多两次旋转，删除最多三次旋转，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树）。

节点要么是红色，要么是黑色
根节点是黑色
每个叶子的节点都是黑色的空节点（NULL）（废话，通常省略）
每个红色节点的两个子节点都是黑色的。
从任意节点到其每个叶子的所有路径都包含相同的黑色节点。（保证红黑树的最长路径不超过最短路径的两倍。）

优点：查找，插入，删除都快，树总是平衡的(局部调整)
缺点：算法复杂
应用场景：红黑树常被用于需求查找效率稳定的场景
①IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查；
②ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器；
③java中TreeMap，jdk1.8的hashmap的实现
④Linux 中内核使用它管理内存区域对象

9、2-3-4树

优点：查找，插入，删除都快，树总是平衡的。类似的树对磁盘存储有用
缺点：算法复杂

10、B树

有一个问题：就在大规模数据存储中，要实现索引查询，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下（为什么会出现这种情况，下面有解释），另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发，自然就想到平衡多路查找树结构。B树（又叫B+tree）就是平衡多路查找树。

例题：一棵已经建立好的B树如下图所示，要求查找关键字为29的文件。

B树

上面的图中比如根结点，其中17表示一个磁盘文件的文件名；小红方块表示这个17文件内容在硬盘中的存储位置；p1表示指向17左子树的指针
指针、关键字以及关键字所代表的文件地址合起来构成了B树的一个结点，这个结点存储在一个磁盘块上
假如每个磁盘块正好可以存放一个B树的结点（正好存放2个文件名）。那么一个B树结点就代表一个盘块，而子树指针就是存放另外一个盘块的地址

搜索过程如下：

从根结点开始，读取根结点信息，根结点有2个关键字：17和35。因为17 < 29 < 35，所以找到指针P2指向的子树，也就是磁盘块3（1次I/0操作）
读取当前结点信息，当前结点有2个关键字：26和30。因为26 < 29 < 30，所以找到指针P2指向的子树，也就是磁盘块8（2次I/0操作）
读取当前结点信息，当前结点有2个关键字：28和29。找到了！（3次I/0操作）

由上面的过程可见，同样的操作，如果使用平衡二叉树，那么需要至少4次 I/O 操作，而且这种优势还会随着结点数的增加而更加明显。另外，因为 B 树结点中的关键字都是排好序的，所以，在结点中的信息被读入内存之后，可以采用二分查找这种快速的查找方式，更进一步减少了读入内存之后的计算时间。由此可见，对于外存数据结构来说，I/O操作的次数是其查找信息中最大的时间消耗，而我们要做的所有努力就是尽量在搜索过程中减少I/O操作的次数。

如何理解“树的高度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下”这句话？

在大规模数据存储方面，大量数据存储在外存磁盘中，而在外存磁盘中读取/写入块（block）中某数据时，首先需要定位到磁盘中的某磁盘块。

磁盘读取数据是以盘块（block）为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘I/O代价主要花费在盘块查找时间T上。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间T。

因此，使用B树使得树的高度更低，从而需要查找的盘块也就更少（即减少磁盘I/O操作的次数），所需的盘块查找时间也就越低，查询效率自然提高。

参考：https://blog.csdn.net/v_july_v/article/details/6530142

11、B+树

$\color{red}{B+-tree ：是应文件系统所需而产生的一种B-tree的变形树。}$

B+树

B+树的特征：

有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引；
所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)；
所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)；

为什么说B+树比B树更适合数据库索引？

1）B+树的磁盘读写代价更低
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了；

2）B+树查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当；

3）B+树便于范围查询（最重要的原因，范围查找是数据库的常态）
B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低；不懂可以看看这篇解读-》范围查找

补充：B树的范围查找用的是中序遍历，而B+树用的是在链表上遍历；

12、堆

大根堆

堆的定义：
①它是完全二叉树
②它通常用数组实现
　假设节点的索引值为index，那么：
　节点的左子节点是 2index+1，
　节点的右子节点是 2index+2，
　节点的父节点是（index-1）/2。
③堆中的每一个节点的关键字都大于（或等于）这个节点的子节点的关键字。

优点：插入，删除快，对最大数据的项存取很快
缺点：对其他数据项存取很慢

13、图

优点：对现实世界建模
缺点：有些算法慢且复杂

参考资料：https://www.cnblogs.com/wyh-study/p/11830197.html
//www.greatytc.com/p/ce8e75baaadb
https://www.cnblogs.com/liaogan-1110/p/11377609.html

最后编辑于：2019.11.22 10:08:31

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 211,348评论 6赞 491
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,122评论 2赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 156,936评论 0赞 347
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,427评论 1赞 283
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,467评论 6赞 385
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,785评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,931评论 3赞 406
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,696评论 0赞 266
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,141评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,483评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,625评论 1赞 340
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,291评论 4赞 329
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,892评论 3赞 312
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,741评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,977评论 1赞 265
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,324评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,492评论 2赞 348