常见数据结构小结

2020-11-04 | 阅读：次

前言

HashMap是怎么实现的？为什么JDK8之后要换成红黑树？Mysql的索引为什么要用B+树？

这些问题在面试中是经常被问到的。今天抽空把这些数据结构进行总结。其实每种数据结构都是为了满足某种场景的需求，都是有着某种内在的联系的，今天我们将尝试进行梳理和总结。此外，在我们对这些数据结构进行研究的时候，主要关注于其评价指标，包括查找，删除，插入的时间复杂度。

这里解释下，我只是对其进行了梳理和总结，里面的配图是在网上找的，会在后面注明来源。

数组和链表

数组和链表是我们最先接触到的数据结构，我们先来分析下

	数组	链表
查找	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

注：我们一般设置一个哨兵节点，这样在处理头结点的删除和插入的时候不至于进行特殊处理。

上面的链表说的是单链表，除此之外，我们还需要了解双向链表和循环链表。

栈和队列

这里需要注意，栈和队列本质上是用数组/链表来实现的，不过二者是操作受限的线性表，其在特定的场景下可以发挥特有的作用。

跳表

跳表是什么？我们为什么需要跳表呢？

我们知道，二分查找的时间复杂度为lgn，性能是很好的，但是其只能局限在数组中，链表是不能使用二分查找的。那么有没有办法在链表中实现二分查找的特性呢？

如果数据是有序的，还是需要O(n)的时间复杂度。

那怎么提高查找效率呢？每两个结点提取一个结点到上一级。

类推：

所以，当链表的长度 n 比较大时，在构建索引之后，查找效率的提升就会非常明显。直观上，我们可以看到查找的效率提高了提高，下面让我们来具体分析提高的效率。

假设链表的长度为n，那么第一级索引的节点个数为n/2，第二级为n/4,那么第k级索引的节点个数为n/(2^k)。我们知道，最高的索引有2个节点，则k=lgn-1。在我们查询数据的时候，如果每一层需要查找m个节点，则在跳表中查询一个数据的时间复杂度就是 O(m*logn)。

且m=3，则时间复杂度为O(lgn)。

原因如下：假设我们要查找的数据是 x，在第 k 级索引中，我们遍历到 y 结点之后，发现 x 大于 y，小于后面的结点 z，所以我们通过 y 的 down 指针，从第 k 级索引下降到第 k-1 级索引。在第 k-1 级索引中，y 和 z 之间只有 3 个结点(包含 y 和 z)，所以，我们在 K-1 级索引中最多只需要遍历 3 个结点，依次类推，每一级索引都最多只需要遍历 3 个结点。

我们可以看到，通过建立索引，我们实现了快速查找，代价了浪费了空间，空间复杂度为O(n)。其实在实际的软件开发中，链表中存储的是比较大的对象，但是索引中存储的是id，所以相比较之下是可以忽略的。

下面我们来分析插入和删除的时间复杂度，先给结论，也是O(lgn)。

我们还需要注意的是要及时更新索引,红黑树是通过左右旋来保持稳定的，而跳表是通过随机函数来保存平衡性的。

hashmap

我们知道，数组可以在O(1)的时间复杂度内完成查询，但是需要O(n)的时间复杂度完成插入和删除，而链表正好相反，那么我们是否可以综合利用数组和链表的优势，这就是hashmap。

二叉查找树

前面我们看到，hashmap是十分高效的，但是其问题也是比较明显的。

Hashmap中的数据是无序存储的，若要输出有序数据，则需要先进行排序，而二叉查找树直接中序遍历即可；
Hashmap扩容耗时多；
Hashmap在hash冲突的时候耗时多；
Hashmap的构造复杂，需要考虑散列函数的设计、冲突解决办法、扩容、缩容等问题，而二叉查找树只需要考虑平衡性问题；

所以综合以上的考量，在某些场景下，我们需要二叉查找树，其查找的时间复杂度为O(logn)。

平衡二叉树和红黑树

前面我们学到二叉查找树在某些情况下可能会失衡，即退化为链表，时间复杂度降低为O(n),所以我们需要对二叉查找树进行平衡。

最先被使用的是AVL平衡二叉查找树，其首先符合二叉查找树的概念，然后左右子树的高度差不超过1。这样就可以很好的保证查找的时间复杂度了。但是其缺点也是很明显的，需要不断的对整棵树进行调整。

这个时候我们就引入了红黑树：左右子树的高度差不超过1倍。红黑树的高度，是2logn。其查找，插入，删除的时间复杂度都是O(logn)。

堆

我们再来看另外一种特殊的二叉树：堆。

我们知道堆是一种完全二叉树，往往采用数据里存储。堆在很多地方都有应用，比如

优先级队列:用在赫夫曼编码、图的最短路径、最小生成树算法
TOPK问题
求动态数据中的中位数

此外，堆在排序算法中的表现也是很好的，时间复杂度是O(logn),空间复杂度为O(1)，从这个角度来讲，是要比快排和归并排序都要优秀的，但是工程中更常见的排序算法依然是快排的，那这是为什么呢？主要从2个角度来考虑：

堆排序数据访问的方式没有快速排序友好。CPU的空间局部性原理。快排中，数据是顺序访问的，而堆中是跳着访问的。
同样的数据，堆排序的交换次数多余快排。

B树和B+树

这里要从mysql讲起，使用mysql来查询数据，我们比较关注的两个点是等值查询和范围查询，如：

select * from user where id=1234;
select * from user where id > 1234 and id < 2345

我们前面学到的数据结构中：

散列表：等值查询时间复杂度为O(1)，但可能存在hash冲突的问题，且范围查询不支持；
二分查找树：可能失衡
平衡二叉树（AVL，红黑树）：范围查询仍然不方便，且树的高度为logn；
跳表：插入、查找、删除数据的时间复杂度都为logn,同时支持区间查询，但是logn的时间复杂度仍然过高。且B+树提出于1972年，跳表提出于1989年，所以B+树才是爸爸。

综上，我们必须要降低树的高度，所以肯定是多叉树。

B树：

B+树

我们来对比下B树和B+树：

	B	B+
存储结构	每个节点存数据	叶子节点存数据，非叶子节点存储索引。所以可以存放更多的数据
查找性能	不稳定	稳定，必须查找到叶子节点
范围查询	不支持	支持

所以，mysql的索引选择了B+树。那么B+树是怎么演化来的呢？

如果我们对二分查找树进行改造，树中的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。

如果我们要为上亿的数据建立索引，比如，我们给一亿个数据构建二叉查找树索引，那索引中会包含大约 1 亿个节点，每个节点假设占用 16 个字节，那就需要大约 1GB 的内存空间。给一张表建立索引，我们需要 1GB 的内存空间。如果我们要给 10 张表建立索引，那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢?

答案是把索引存放到硬盘中，但是如此一来，需要从硬盘中读取数据，速度是无法忍受的，因为树高是需要IO的次数，所以要降低树高。答案是多叉树。

那多叉树的m到底是多少比较好呢？不管是内存中的数据，还是磁盘中的数据，操作系统都是按页(一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看)来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作。