写点什么

基础知识(二)

用户头像
eazonshaw
关注
发布于: 2020 年 07 月 29 日
基础知识(二)

数据结构与算法

时间复杂度与空间复杂度

时间复杂度:算法执行语句的次数

空间复杂度:算法在执行过程中临时占用存储空间大小的量度

NP 问题

P 问题:能在多项式时间复杂度内解决的问题

NP 问题:能在多项式时间复杂度内验证答案正确与否的问题

NP ?= P



例子:数独

常见数据结构

数组

数组必须要内存中一块连续的空间

链表

链表可以使用零散的内存空间存储数据

数组与链表对比

  • 链表中增删数据要比数组性能好;

  • 可以利用数组链表结合,实现快速查找和快速增删

哈希表

  • 既能快速访问数据,又能快速增删数据;

  • 日常开发中最常用的数据结构

哈希冲突:由于 key 经过哈希函数的结果是一致的,因此指向的地址相同,导致冲突

在线性表(数组和链表)的基础上加了操作限制:后添加的数据,在删除时必须先删除,即“后进先出”。

注意:理解线程调用栈。

队列

一种操作受限的线性表;先进先出

应用场景:生产者消费者;阻塞等待的线程被放入队列。

二叉排序树:左子树所有结点的值均小于或等于它的根结点的值;右子树上所有结点的值均大于或等于它的根节点的值。左、右子树也分别为二叉排序树。

不平衡的二叉排序树会退化成链表。

平衡二叉排序树:从任何一个节点出发,左右子树深度之差的绝对值不超过1.左右子树为平衡二叉树。

红黑树

  • 每个节点只有两种颜色:红色和黑色

  • 根节点是黑色的

  • 每个叶子节点(NIL)都是黑色的空节点

  • 从根节点到叶子节点,不会出现两个连续的红色节点

  • 从任何一个节点出发,到叶子节点,这条路径上都有相同数目的黑色节点

红黑树 VS 平衡二叉树

  • 红黑树最多只需3次旋转就会重新达成红黑平衡,时间复杂度O(1)。

  • 在大量增删的情况下,红黑树较好。

  • 红黑树的平衡性不如平衡二叉树,查找效率较低。

跳表

常用算法

归类

  • 穷举算法

  • 递归算法

  • 贪心算法

  • 动态规划

递归算法

快排

贪心算法

改进的贪心算法:迪杰斯特拉算法(最快路径)

  1. 找出“最便宜”的节点,即可在最短时间内到达的节点

  2. 更新该节点的邻居的开销,检查是否有前往它们的最短路径,如果有,就更新其开销

  3. 重复这个过程,直到对图中

网络通信协议

引入

web 请求的一次网络通信历程?



模型

OSI 七层模型和 TCP/IP 四层模型。



TCP/ID 四层协议结构。



网络数据包格式



物理层

  • 负责数据的物理传输

  • 如何让不同的设备(光纤、电缆、无线)能够理解、处理相同的二进制数据,是物理层要解决的问题

链路层

  • 将数据进行封装后给物理层进行传输

  • 最大传输单元:定义帧的大小;帧中包含发送者和接受者的MAC地址(网卡的设备标识符,唯一)

网络层(IP 协议)

在传输给链路层的数据包中,加上IP地址,交换机通过IP地址进行路由转发,到达目标服务器

传输层(TCP 协议)

TCP协议:一种面向连接的、可靠的、基于字节流的传输层协议。

TCP 协议的三次握手与四次挥手:

三次握手:

  1. APP->服务器:发送SYN=1 SEQ=X报文,表示建立连接,X为随机数。

  2. 服务器->APP:应答SYN=1 ACK=X+1 SEQ=Y报文,表示同意建立连接。

  3. APP:检查ACK正确性,发送ACK=Y+1 SEQ=Z报文,表示确认连接;服务器:检查ACK正确性,表示确认连接。



四次挥手

  1. 客户端->服务器:发送FIN,请求关闭数据传输

  2. 服务器->客户端:发送ACK=FIN+SEQ

  3. 服务器->客户端:发送FIN,表示客户端应用程序关闭

  4. 客户端->服务器:发送ACK=FIN+SEQ



应用层(HTTP 协议)

互联网应用在全球范围为用户提供服务,将全球的应用和全球的用户联系在一起,需要一个统一的应用层协议,即 HTTP 协议。

非阻塞网络 I/O

非阻塞I/O:I/O操作立即返回,发起线程不会阻塞等待

数据库架构原理及性能优化

数据库架构

连接器 - 语法分析器 - 语义分析与优化器 - 执行引擎

连接器

  • 为每个链接请求分配专用的内存空间,用于会话上下文管理

  • 建立连接成本较高,通常会初始化数据库连接在连接池中,当处理外部请求执行 SQL 操作时不需花费时间建立连接。

语法分析器

语法分析器只能检查出语句的大概错误位置。

语义分析与优化器

将各种复杂的嵌套 SQL 进行语义等价转化,得到有限几种关系代数计算结构,并利用索引等信息进一步进行优化。

执行计划

通过 explain 分析 sql 语句:

  • key:索引类型,NULL 无索引

  • rows:需要处理的行数

  • prossible_key:潜在可以利用的索引

PrepareStatement

String sql = "update User set name = ? where id = 1";
PreparedStatement ps = connection.prepareStatement(sql);
ps.setString(1,"xiaoyz");
ps.executeUpdate();

为什么PrepareStatement更好?

PrepareStatement会预先提交带占位符的SQL到数据库进行预处理,提前生成执行计划,当给定占位符参数,真正执行SQL的时候,执行引擎可以直接执行,效率更高。同时,PrepareStatement可以防止SQL注入攻击。

索引

B 树和 B+ 树



聚簇索引与非聚簇索引

  • 聚簇索引(主键索引):数据库记录和索引存储在一起

  • 非聚簇索引(普通索引):叶子节点存储的不是数据库记录,而是聚簇索引,即主键。

索引的使用

  • 添加合适的索引提高性能

  • 合理使用索引(不能盲目使用索引)

思考

  • 善于思考,猜想比学一堆堆的知识更重要

用户头像

eazonshaw

关注

还未添加个人签名 2019.04.10 加入

还未添加个人简介

评论

发布
暂无评论
基础知识(二)