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)。
我们还需要注意的是要及时更新索引,红黑树是通过左右旋来保持稳定的,而跳表是通过随机函数来保存平衡性的。
我们知道,数组可以在O(1)的时间复杂度内完成查询,但是需要O(n)的时间复杂度完成插入和删除,而链表正好相反,那么我们是否可以综合利用数组和链表的优势,这就是hashmap。
前面我们看到,hashmap是十分高效的,但是其问题也是比较明显的。
所以综合以上的考量,在某些场景下,我们需要二叉查找树,其查找的时间复杂度为O(logn)。
前面我们学到二叉查找树在某些情况下可能会失衡,即退化为链表,时间复杂度降低为O(n),所以我们需要对二叉查找树进行平衡。
最先被使用的是AVL平衡二叉查找树,其首先符合二叉查找树的概念,然后左右子树的高度差不超过1。这样就可以很好的保证查找的时间复杂度了。但是其缺点也是很明显的,需要不断的对整棵树进行调整。
这个时候我们就引入了红黑树:左右子树的高度差不超过1倍。红黑树的高度,是2logn。其查找,插入,删除的时间复杂度都是O(logn)。
我们再来看另外一种特殊的二叉树:堆。
我们知道堆是一种完全二叉树,往往采用数据里存储。堆在很多地方都有应用,比如
此外,堆在排序算法中的表现也是很好的,时间复杂度是O(logn),空间复杂度为O(1),从这个角度来讲,是要比快排和归并排序都要优秀的,但是工程中更常见的排序算法依然是快排的,那这是为什么呢?主要从2个角度来考虑:
这里要从mysql讲起,使用mysql来查询数据,我们比较关注的两个点是等值查询和范围查询,如:
select * from user where id=1234;
select * from user where id > 1234 and id < 2345
我们前面学到的数据结构中:
综上,我们必须要降低树的高度,所以肯定是多叉树。
我们来对比下B树和B+树:
B B+ 存储结构 每个节点存数据 叶子节点存数据,非叶子节点存储索引。所以可以存放更多的数据 查找性能 不稳定 稳定,必须查找到叶子节点 范围查询 不支持 支持
所以,mysql的索引选择了B+树。那么B+树是怎么演化来的呢?
如果我们对二分查找树进行改造,树中的节点并不存储数据本身,而是只是作为索引。除此之外,我们把每个叶子节点串在一条链表上,链表中的数据是从小到大有序的。
如果我们要为上亿的数据建立索引,比如,我们给一亿个数据构建二叉查找树索引,那索引中会包含大约 1 亿个节点,每个节 点假设占用 16 个字节,那就需要大约 1GB 的内存空间。给一张表建立索引,我们需要 1GB 的内存空间。如果我们要给 10 张表建立索引,那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢?
答案是把索引存放到硬盘中,但是如此一来,需要从硬盘中读取数据,速度是无法忍受的,因为树高是需要IO的次数,所以要降低树高。答案是多叉树。
那多叉树的m到底是多少比较好呢?不管是内存中的数据,还是磁盘中的数据,操作系统都是按页(一页大小通常是 4KB,这 个值可以通过 getconfig PAGE_SIZE 命令查看)来读取的,一次会读一页的数据。如果要 读取的数据量超过一页的大小,就会触发多次 IO 操作。所以,我们在选择 m 大小的时 后,要尽量让每个节点的大小等于一个页的大小。读取一个节点,只需要一次磁盘 IO 操作。
我们可以看到,任何一种技术都是为了解决在某些场景下,其他的方案存在的某些问题,我们要理清这种内部的关系,这样我们才可以了然于胸。
这篇文章的字数不多,但是希望可以帮助你梳理下常见的数据结构,在学习的时候不至于迷茫。
数据结构与算法之美:https://time.geekbang.org/column/intro/126