20220814笔记

• 谈谈了解的设计模式

• 设计模式在开发中的应用

• 时间与空间复杂度

• 常见的数据结构

• 链表的数据结构的特点

• 栈数据结构特点

• 队列数据结构特点

• 散列表数据结构特点

• 说一说什么是跳表?Redis为什么用跳表实现有序集合?

• 二叉树数据结构特点

• 图数据结构特点

• 堆数据结构特点

• 大顶堆和小顶堆的区别

谈谈了解的设计模式

设计模式大致可以分成创建型模式、结构型模式和行为型模式。

• 创建型模式是对对象创建过程中的各种问题和解决方案的总结，其中包括：工厂模式、单例模式、构造器模式、原型模式。
• 结构型模式是针对软件设计结构的总结，关注于类对象继承组合方式的实践经验。常见的结构型模式有桥接模式、适配器模式、装饰者模式、代理模式、组合模式、外观模式、享元模式等。
• 行为型模式是从类或对象之间交互、职责划分等角度总结的模式。比较常见的行为型模式有策略模式、解释器模式、命令模式、观察者模式迭代器模式、模板模式、访问者模式、

设计模式在开发中的应用

1. 单例模式：例如配置类的对象只能存在一个。
2. 工厂模式：例如使用BeanFactory工厂创建对象，不用自己去new对象。
3. 代理模式：例如Spring底层的AOP就是通过代理模式实现的。
4. 适配器模式：例如SpringMVC中的HandlerInterceptorAdapt就是适配器模式。
5. 建造者模式：例如Mybatis中的SqlSessionFactoryBuilder就是建造者模式，遵循单一原则，只做一件事。

时间与空间复杂度

• 时间复杂度：算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))
• 空间复杂度：空间复杂度是对算法运行过程中临时占用空间大小的度量，一个算法所需的存储空间用 f (n) 表 示，可得出 S(n) = O(f(n)) ，其中 n 为问题的规模， S(n) 表示空间复杂度。通常用 S(n) 来定义。

常见的数据结构

数组、链表、队列、堆、栈、树、散列表、图。

链表的数据结构的特点

链表使用不连续内存空间，空间的利用率高。

链表插入删除效率高，查询效率慢。

链表占用空间大小不固定，可以扩展。

栈数据结构特点

栈是一种操作首先的线性表，只允许从一端插入删除数据，有先进后出的特点。

栈的插入和删除只能在一个位置上进行，栈只有进栈、出栈两个操作，进栈相当于插入，出栈相当于删除。

从底层看，栈就是CPU寄存器里面的一个指针指向的一片区域。

队列数据结构特点

队列也是一种操作受限的数据结构，只能做队尾进行插入，队首删除，具有先进先出的特点。双端队列不受这种限制，两端都能进行插入和删除。

散列表数据结构特点

哈希表的查找效率主要取决于构造哈希表的哈希函数和处理冲突的方法。

在各种查找方法中，平均查找长度和节点个数n无关的查找方法就是哈希表查找法。

哈希函数取值时候平均是评价哈希函数好坏的标准。

哈希存储方法只能存储数据元素的值，不能存储数据元素之间的关系。

说一说什么是跳表?Redis为什么用跳表实现有序集合?

Redis的有序集合是通过调表实现的，同时还用到了散列表，它支持的核心操作有：插入一个数据、删除一个数据、查找一个数据、按区间查找数据、迭代输出有序序列。

按照区间来查找数据，这个操作红黑树的效率没有跳表高，其他几个操作红黑树都可以完成，时间复杂度也都一样。按照去就按查找，跳表可以在做到O（logn）的时间复杂度定位区间的起点，然后再原始链表中的顺序往后遍历即可，非常的高效。

跳表通过空间换时间，通过构建多级索引来提高擦汗寻的效率，实现基于链表的二分查找，体哦啊表就是一个动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是O（logn）。

跳表的空间复杂度是O（n），通过改变索引构建策略。

二叉树数据结构特点

每个节点最多有两颗子树，所以二叉树中不可能存在长度大于2的节点。注意不是只有两棵子树，而是最多有两棵子树。没有子树或一颗子树也是可以的。

左子树与右子树的顺序不能颠倒。即使只有一颗子树也要区分他是左子树还是右子树。

图数据结构特点

无向图：每个节点都没有方向，边上可能有权重。

有向图：每个节点都是有方向的。

有向无环图：可以用来描述任务之间的关系。

堆数据结构特点

将根节点为最大值的堆称之为大顶堆，根节点值最小的堆称之为小顶堆。

常见的堆有二叉堆、斐波拉且堆。

大顶堆的时间复杂度：

• 查找最大值:O(1)。
• 删除最大值：O（logn）
• 添加值：O（1）或者O（logn）

大顶堆和小顶堆的区别

大顶堆：根节点（堆顶）的关键字是堆里所有节点最大的。大顶堆要求根节点的关键字即大于等于左子树的关键字值，又大于等于右子树的关键字值。

大顶堆：根节点（堆顶）的关键字是堆里所有节点最小的。小顶堆要求根节点的关键字即小于等于左子树的关键字值，又小于等于右子树的关键字值。

本文使用 文章同步助手 同步