数据结构不迷茫 _数据结构

前言

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 个结点。