数据结构常见考察知识点:链表、栈、队列、散列表(哈希表)、二叉树、二叉搜索树(BST)、字典树、红黑树、跳表、霍夫曼树、有序字典、KMP字符串匹配等

目录

哈希表

如何解决哈希冲突

  • 开放定址法(再散列法)

当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:Hi=(H(key)+di)%m (i=1,2,…,n)

  • 链地址法;哈希表的第i个单元中保存单链表的头指针

开放定址法,需要开辟连续的内存空间,以进行再散列函数的计算

AVL树

BST(binary search/sort tree):二叉查找/搜索/排序树 ,满足 左节点 <= 根 <= 右节点;

AVL树:平衡的BST树,即平衡二叉树

平衡二叉树的目的:为了减少二叉查找树层次,提高查找速度

平衡二叉树的常用实现方法:AVL树、红黑树、替罪羊树、Treap、伸展树等

AVL树的特征:

  • 空树 或左右两个子树的高度差(平衡因子)的绝对值不超过1,
  • 并且左右两个子树都是一棵平衡二叉树
  • 同时,平衡二叉树必定是二叉搜索树,反之则不一定

旋转

所谓的左旋和右旋都是以子树为原点的:如b是a的子树,那么旋转就围绕b来进行。

  • 如果b是a的左子树,那么就围绕b将a向右旋转,看着就像是a直接掉下来了,掉成了b的右子树。
  • 如果b是a的右子树,那么就围绕b将a向左旋转,看着就像是a直接掉下来了,掉成了b的左子树。

插入算法

插入节点的4种情况:

插入算法

插入方式 描述 旋转方式
LL 在a的左子树根节点的左子树上插入节点而破坏平衡 右旋转
RR 在a的右子树根节点的右子树上插入节点而破坏平衡 左旋转
LR 在a的左子树根节点的右子树上插入节点而破坏平衡 先左旋后右旋
RL 在a的右子树根节点的左子树上插入节点而破坏平衡 先右旋后左旋

删除算法

删除算法

红黑树

红黑树是一种自平衡的二叉搜索树,为了解决极端情况(树非常倾斜,不够平衡)下二叉搜索树的搜索效率问题

红黑树的特征

  • 节点分为黑色和红色
  • 根节点是黑色
  • Null节点是黑色(Null叶子节点)
  • 如果一个节点是红的,他的子节点一定是黑的
  • 节点到该节点子孙节点的路径上拥有相同数目的黑节点

应用场景

  • 有序集合:编程语言的STL库中的一些容器,比如Java的TreeMap, C++的map,set,Javascript ES6中的map等
  • linux进程调度:用红黑树减小选择下一个可运行进程,以及插入一个进程的开销
  • 一致性hash算法:查找下一个虚节点位置

插入算法

  1. 红黑树的插入节点总是设为红节点
  2. 插入节点
  3. 通过”旋转和重新着色”等一系列来修正该树,使之重新成为一棵红黑树。

删除算法

  1. 将红黑树当作一颗二叉查找树,将该节点从二叉查找树中删除;
  2. 通过”旋转和重新着色”等一系列来修正该树,使之重新成为一棵红黑树。

跳表

跳表:一种链表加多级索引的结构

本质:跳表是一种支持二分查找的有序链表

跳表的结构

跳表

查找某个数据的时候需要的时间复杂度为O(n)

redis中的有序集合是用跳表实现的,为什么不用红黑树

分析下Redis的有序集合支持的操作:

  1. 插入元素: 都是O(logN)
  2. 删除元素: 都是O(logN)
  3. 查找元素: 都是O(logN)
  4. 有序输出所有元素: 跳表效率更高O(N),红黑树O(NlogN)
  5. 查找区间内所有元素
    • 在跳表中,要查找区间的元素,我们只要定位到两个区间端点在最低层级的位置,然后按顺序遍历元素就可以了,非常高效。
    • 红黑树只能定位到端点后,再从首位置开始每次都要查找后继节点,相对来说是比较耗时的。

综合比较:

  • 在做范围查找的时候,平衡树比skiplist操作要复杂
  • 平衡树的插入和删除操作可能引发子树的调整,逻辑复杂,而skiplist的插入和删除只需要修改相邻节点的指针,操作简单又快速
  • 从内存占用上来说,skiplist更节省内存,指针平均数量少。一般来说,平衡树每个节点包含2个指针(分别指向左右子树),而skiplist每个节点包含的指针数目平均为1/(1-p),具体取决于参数p的大小。如果像Redis里的实现一样,取p=1/4,那么平均每个节点包含1.33个指针,比平衡树更有优势。
  • 从算法实现难度上来比较,skiplist比平衡树要简单得多

redis中的有序集合是用跳表实现的,为什么不用B+树

  • B+树适合磁盘IO,redis是内存数据库,logN的时间复杂度可以接受
  • B+树的节点中数据空间是连续的,对于开辟内存来说,要求较高
  • 从算法实现难度上来比较,跳表实现更简单

B-树

多路查找树

定义:B-树是一类树,包括B-树、B+树、B*树等,是一棵自平衡的搜索树,它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。B-树是专门为外部存储器设计的,如磁盘,它对于读取和写入大块数据有良好的性能,所以一般被用在文件系统及数据库中。

定义只需要知道B-树允许每个节点有更多的子节点即可。子节点数量一般在上千,具体数量依赖外部存储器的特性。

用来搜索的平衡二叉树有很多,如AVL树、红黑树等,查询IO次数较多,从设计上无法“迎合”磁盘,只适用于内存操作。

B-树:减少磁盘 IO 次数

应用场景

常用于数据库操作系统的文件系统

B-树特征

一个m阶的B-树具有如下几个特征:

  1. 根结点至少有两个子女
  2. 每个中间节点都至少包含ceil(m / 2)个孩子,最多有m个孩子
  3. 每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m
  4. 所有的叶子结点都位于同一层
  5. 每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划

B-树与普通二叉搜索树的区别

  • 高度形态 > 平衡二叉树窄高,B-树扁平

  • 分支数量 > 平衡二叉树,只有二叉 > m阶的B-树 有 [ceil(m / 2),m]叉

  • 插入删除操作 > 平衡二叉树,后若不满足平衡条件则进行旋转操作 > B-树中,插入删除后不满足条件则进行分裂及合并操作;元素自底向上插入。

  • 场景 > 平衡二叉树适IO次数多,适用于内存操作 > B-树 IO次数少,对于磁盘,连续空间寻址效率高,适用于磁盘查找

B-树的查找算法

同一节点上,地址空间连续,单调递增,使用二分查找算法

B+树

B+树是B-树的变种,区别在于:

  • 在B+树中,key 的副本存储在内部节点,真正的 key 和 data 存储在叶子节点上
  • n 个 key 值的节点指针域为 n 而不是 n+1;
  • 只有叶子节点才会有数据,非叶结点仅具有索引作用
  • 为了增加区间访问性,有的B+树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。

B+树比起B-树

  1. 查询时间复杂度: B+树内节点不存储数据,所有data存储在叶节点导致固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)。
  2. 区间查找: B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等;B-树区间查找需要查询多个节点,并且进行组合,效率更低
  3. 由于内节点无 data 域,每个节点能索引的范围更大更精确B+树更适合外部存储

为什么MongoDB索引选择B-树

  • MongoDB 是文档型的数据库,是一种 nosql,它使用类 Json 格式保存数据,属于聚合型数据库。 > 键值数据库也属于聚合型数据库,比如 redis

相对于 Mysql 关系型数据库,MongoDB 这类 nosql 适用于数据模型简单,性能要求高的场合

尽可能少的磁盘 IO 是提高性能的有效手段。MongoDB 是聚合型数据库,而 B-树恰好 key 和 data 域聚合在一起,找到了key就不需要继续索引data了,相比B+树,B-树对聚合型数据库更优。

LRU算法

LRU(The Least Recently Used,最近最久未使用算法)是一种常见的缓存算法,在很多分布式缓存系统(如Redis, Memcached)中都有广泛使用。

LRU算法的思想是:如果一个数据在最近一段时间没有被访问到,那么可以认为在将来它被访问的可能性也很小。因此,当空间满时,最久没有访问的数据最先被置换(淘汰)。

LRU算法的描述:设计一种缓存结构,该结构在构造时确定大小,假设大小为 K,并有两个功能:

  • set(key,value):将记录(key,value)插入该结构。当缓存满时,将最久未使用的数据置换掉。
  • get(key):返回key对应的value值。

实现:最朴素的思想就是用数组+时间戳的方式,不过这样做效率较低。因此,我们可以用双向链表(LinkedList)+哈希表(HashMap)实现(链表用来表示位置,哈希表用来存储和查找),在Java里有对应的数据结构LinkedHashMap。

LinkedHashMap

利用Java的LinkedHashMap用非常简单的代码来实现基于LRU算法的Cache功能

import java.util.LinkedHashMap;
import java.util.Map;
/**
 * 简单用LinkedHashMap来实现的LRU算法的缓存
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int cacheSize;
    public LRUCache(int cacheSize) {
        super(16, (float) 0.75, true);
        this.cacheSize = cacheSize;
    }
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
}

LFU算法

LFU(Least Frequently Used,最近最不经常使用算法)也是一种常见的缓存算法。

顾名思义,LFU算法的思想是:如果一个数据在最近一段时间很少被访问到,那么可以认为在将来它被访问的可能性也很小。因此,当空间满时,最小频率访问的数据最先被淘汰。

LFU 算法的描述:

设计一种缓存结构,该结构在构造时确定大小,假设大小为 K,并有两个功能:

  • set(key,value):将记录(key,value)插入该结构。当缓存满时,将访问频率最低的数据置换掉。
  • get(key):返回key对应的value值。

算法实现策略:考虑到 LFU 会淘汰访问频率最小的数据,我们需要一种合适的方法按大小顺序维护数据访问的频率。LFU 算法本质上可以看做是一个 top K 问题(K = 1),即选出频率最小的元素,因此我们很容易想到可以用二项堆来选择频率最小的元素,这样的实现比较高效。最终实现策略为小顶堆+哈希表