基本数据结构

基本数据结构包括栈、队列、链表、有根树。对于这几个,大家应该都很熟悉,前三个就不作讨论,只稍微讲一下有根树。树大致有以下几种:二叉树,堆,B树,字典树。而我们较为熟悉的就是二叉树,同时二叉树也可以推广至n叉树。但是很多情况下,孩子结点个数都是不固定的,如对DOM的描述。所以对于分支无限的有根树来说,更多会采用的是左孩子右兄弟的表示法进行描述,如下图:

对于这种结构,我直接就想到了React Fiber:

Fiber = {
  stateNode, // 当前节点实例
  child, // 子节点,等同于left
  sibling, // 兄弟节点,等同于right
  return, // 父节点
  ...
};
复制代码

不过不知道为啥,之前看过的一些关于Fiber的文章都说这是链表结构,这明明就是分支无限的有根树啊,有木有!

直接寻址表

当关键字的的全域U比较小时,直接寻址是一种简单而有效的技术。举个例子:为了描述某一组数据,如果这些数据的关键字只可能是0-10之间的某个自然数,某次的得到的数据的关键字为2、3、5、8,那么这张表的结构就如下图所示:

其缺点也很明显:如果全域U很大,则需要用很大一张表T来存储,明显是不实际的。而且实际存储的关键字集合K相对U来说可能很小,就使得分配给T的空间会有很大一部分都被浪费,所以就需要用到下面的散列表。

散列表

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

说白了,散列表就是实现字典操作的一种有效的数据结构,是对于数组结构的推广,故其查找性能是十分好的。在一些合理的假设下,在散列表中查找一个元素的平均时间是O(1)。

散列表的大小m一般要比|U|小得多,一个具有关键字k的元素被散列到槽h(k)上,也可以说h(k)是关键字k的散列值。散列函数缩小了数组下标的范围,即减小了数组的大小,使其由|U|减少为m。如下图:

当两个关键字被映射到同一个槽中时,这种情形叫冲突。解决冲突的方法一般有以下两种:链接法和开放寻址法。

链接法解决冲突

链接法就是将散列到同一个槽中的所有元素都放在一个链表中,如下图所示:

简单分析:

散列表的装填因子α=n/m。α越大,填入表中的元素越多,越容易产生冲突;反之则越不容易产生冲突。

假设已有散列表T,存放了n个元素,具有m个槽,那么:

  1. 在最坏情况下,即所有元素都在同一个槽中,散列表其实退化为了链表,查找的时间为O(n)
  2. 在平均情况下,假设散列函数h将所有元素都均匀散列在每一个槽中(这种假设被称为简单均匀散列),即每个槽中的元素为n/m,其查找的所需的时间为O(1 + α)(1指找到槽的时间,α指在链表中查找到目标元素的时间)。如果散列表中的槽数m与散列元素n成正比,即n=O(m),那么α=n/m=O(m)/m=O(1),那么查找所需的时间也只需要O(1 + α)=O(1)

开放寻址法解决冲突

在开放寻址法中,所有的元素都存在在散列表里。也就是说,每个表项或包含动态集合的一个元素,或包含NIL(无值)。开放寻址法的好处在于不用指针,而是计算出要存储的槽序列。由于不用存储指针,就可以用省下来的空间存储更多的槽,潜在地减少了冲突,提高了检索速度。但是在开放寻址法中,散列表可能被填满,以至于无法插入任何新的元素。

为了使用开放寻址法插入一个元素,需要连续地检查散列表,这个过程被称为探查。

假设全局U通过散列函数散列后变成{0,1,...,m-1},即h:U*{0,1,...,m-1} -> {0,1,...,m-1}

对于每一个关键字k,其使用开放寻址法的探查序列<h(k, 0), h(k, 1),...,h(k,m-1)>是<0,1,...,m-1>的某一种排序。如果每个关键字的探查序列等可能为<0,1,...,m-1>的m!种排序的任意一种,这种情况称为均匀散列假设。均匀散列其实就是将前面所说的简单均匀散列的概念加了一般化,推广到了散列函数的结果不只是一个数,而是一个完整的探查序列。

说白了,开放寻址法就是根据探查序列来决定插入元素位置的操作。举个例子:若散列表T具有3个槽,分别为0、1、2,某个元素k的探查序列为<2,0,1>,在插入元素k时,会先检查槽T[2]是否为NIL,如果为空,则将k插入槽T[2]的位置;否则,再去检查槽T[0],执行上诉检查。若检查到槽T[1]时,也不为空,则说明此散列表已满,无法插入。

线性探查

给定一个散列函数h':U -> {0,1,...,m-1},称之为辅助散列函数,线性探查所采用的散列函数为h(k,i)=(h'(k)+i) mod m, i=0,1,...,m-1。

意思就是,对元素k进行插入时,先检查槽T[h'(k)],即辅助散列函数给出的槽位。再探查槽T[h'(k)+1],直至探查到槽T[m-1]。然后又绕到槽T[0],T[1],...T[h'(k)-1]。线性探查方法比较容易实现,但是它存在一次群集的问题。随着连续被占用的槽不断增加,平均查找时间也会不断增加。举个例子:如果散列表T中的槽T[i]、T[i+1]、T[i+2]个元素已经存储了某些关键字,则下一次哈希地址(即通过散列函数得到的地址)为i、i+1、i+2、i+3的关键字都会企图填入槽T[i+3]中,就产生多个关键字争夺同一个槽的现象,将会极大地影响查找效率。

二次探查

二次探查采用如下的散列函数:h(k,i)=(h'(k)+c1i+c2i2) mod m, i=0,1,...,m-1,c1、c2为正的辅助常数。

初始的探查位置为T[h'(k)],后续的探查位置要加上一个偏移量,该偏移已二次的方式依赖于探查序号i。此外,如果两个两个关键字的初始探查位置相同,那么他们的探查序列也是相同的,这样会导致一种轻度的群集,称为二次群集。而且此方法也不能够探查到所有的存储单元。

双重散列

双重散列是用于开放寻址法中的最好的方法之一,因为它所产生的排列具有随机选择排列的许多特性。双重散列具有如下的散列函数:h(k,i)=(h1(k)+i*h2(k)) mod m, i=0,1,...,m-1,h1、h2均为辅助散列函数。

初始的探查位置为T[h'(k)],后续的探查位置是前一个探查加上偏移量h2(k)后模m。此种探查序列以两种不同的方式依赖于关键字k。双重探查要求h2(k)与表的大小m互素(互素,就是互为质数,两个数之间除了1之外没有更多的公约数)。一种简便的方法是:m取2的幂,h2(k)只产生奇数;或者m为素数,h2(k)总是返回比m小的正整数。

举个例子:取m为素数,并取h1(k)=k mod m,h2(k)=1 + (k mod m'),其中m'略小于m(如m-1)。例如,如果k=123456,m=701,m'=700,则有h1(k)=80,h2=257,可知我们的第一个探查位置为80,然后检查每第257个槽,直到找到该关键字,或者遍历了所有的槽。

开放寻址法分析

使用开放寻址表,每个槽中最多只有一个元素,所以n<=m,也就意味着α<=1。对于开放寻址表来说,有三个定理和推论,因为证明起来比较麻烦,所以直接上结果,有兴趣的可以自行了解。

  1. 给定一个装载因子为α=n/m < 1的开放寻址散列表,并假设是均匀散列的,则对于一次不成功的查找,其期望的探查次数至多为1/(1-α)
  2. 假设采用的是均匀散列,平均情况下,向一个装载因子为α的开放寻址散列表中插入一个元素至多需要做1/(1-α)此探查
  3. 假设采用均匀散列,且表中的每个关键字被查找的可能性是相同的,一次成功查找中的探查数至多为1/α*ln(1/(1-α))

总结:散列表越满,即α越大,所需执行探查的查找/插入期望数越小。

完全散列

完全散列即通过一个不含冲突的散列表解决冲突,在最坏情况下也只需O(1)次访问。如下图:

二叉搜索树

二叉搜索树的特点:假设x是二叉搜索树的一个结点,如果y是x左子树中的一个结点,那么y.key<=x.key。如果y是x右子树中的一个结点,那么y.key>=x.key。即相对根节点来说,左子树存放小值,右子树存放大值。那么中序遍历二叉树(左子树->根节点->右子树)就是一个排序的过程。

二叉搜索树的查询/插入/删除的运行时间为O(h),h为树的高度。一棵有n个不同关键字随机构建的二叉搜索树的期望高度为O(logn)。这个不难理解,大学课堂上也讲到过,有兴趣或遗忘的可以自行查阅。

二叉搜索树在多次插入新节点后容易导致不平衡。如下图,原树为4、5、6,在分别插入4、3、2、1后发现这棵树变的极不平衡,已经变成了线性结构。为了解决这种不平衡,就有了下一节所提到的红黑树。

红黑树

红黑树是一棵二叉搜索树,它在每个结点上增加了一个存储位来表示结点的颜色,可以是RED或者BLACK。红黑树是满足以下红黑性质的二叉搜索树:

  1. 每个结点是红色或者黑色
  2. 根结点是黑色
  3. 每个叶节点(NIL)是黑色
  4. 如果一个结点是红色的,则它的两个子结点都是黑色的
  5. 对每个结点,从根结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点

红黑树因为这些特性的限制,确保没有一条路径会比其他路径长出2倍,因而是近似平衡的。

红黑树的查找性能非常好,也是基于其上述特性的原因。使其在最坏情况下的查找时间也能有O(logn)。红黑树的插入和删除操作有可能会打破以上原则,所以需要进行自平衡。关于插入和删除的过程,推荐看下这篇文章。这里贴上其他文章主要是因为我也讲不清=_=,流下了又菜又没有技术的泪水。

当然,学习数据结构不仅仅是要学会其基础知识,更多地是为了扩展数据结构以使其满足我们的需求。例如,在红黑树的基础上可以扩展出顺序统计树、区间树,有兴趣的可以自行了解。更多的,我们是学习数据结构是为了在实际应用用一个合理的模型去描述一个具体的问题,获得一种较效率的解决方案。本章内容内容到此结束,关于图的内容后续再说,因为我也还没看到,下一章预告:高级设计和分析技术。