知识点总结

###时间复杂度与空间复杂度

时间复杂度

• 并不是计算程序具体运行的时间，而是算法执行语句的次数。 • O(2^n) 表示对 n 数据处理需要进行 2^n 次计算

• 多项式时间复杂度

• 非多项式时间复杂度

空间复杂度

• 一个算法在运行过程中临时占用存储空间大小的量度。

• O(n) 表示需要临时存储 n 个数据。





NP 问题

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

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

• NP ?= P

• NP-hard 问题：比 NP 问题更难的问题（NP问题的解法可以规约到 NP-hard 问题的解法）

• NP 完全问题：是一个 NP-hard 问题，也是一个 NP 问题。



基本数据结构



数组

• 内存中一组连续的空间

• 数组中必须存放相同的数据类型

• 基于以上两个规则，根据第一个数据的内存地址，就可以计算得出其他数据的内存地址

• 随机快速读写

• 根据下标访问数据，时间复杂度为O(1)



链表

• 可以使用零散的内存空间

• 每个元素都必须包括一个指向下一个数据元素的内存地址的指针

• 想要在链表中查找一个数据，必须变量链表，所以时间复杂度是O(n)

• 增删数据在链表中的效率比数组更好，数组中增删数据，可能会导致其他数据的位置变化，而链表不需要，链表的时间复杂度是O(1)

• 查找数据在数组中的效率比链表更好

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

• 数组链表结合，实现快速查找和快速增删



Hash表

• 能实现快速访问数据，也能快速增删数据，时间复杂度都是O(1)



Hash 冲突

• 当出现多个key计算出同一个HashCode

• 使用链表解决

• Hash碰撞



栈

• 数组和链表都是线性表（每个节点都有唯一的前驱和唯一的后继）

• 在线性表基础上加入限制规则就会出现新的数据结构：栈

• 实现了『后进先出』



队列

• 也是一种受限的线性表

• 实现的是『先进先出』

• 应用场景：消息队列，生产者消费者



树

• 不是线性表

• 二叉排序树

• 左子树上所有节点的值都小于或等于它的根节点的值

• 右子树上所有节点的值都大于或等于它的根节点的值



平衡二叉排序树和不平衡二叉排序树

• 从任何一个节点出发，左右子树深度只差绝对值不超过1

• 平衡二叉排序树时间复杂度是O(logn)， 而不平衡儿茶排序树不是

• 旋转二叉树恢复平衡

• 插入时，最多需要两次旋转就会恢复平衡

• 删除时，需要维护从被删节点到根节点这条路径上所有节点的平衡性

• 为了减少二叉树的平衡性维护，使用红黑树



红黑（排序）树

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

• 根节点是黑色的。

• 每个叶子节点（NIL）都是黑色的空节点。

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

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



红黑树 VS 平衡二叉树

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

• 在大量增删的情况下，红黑树的效率更高。

• 红黑树的平衡性不如平衡二叉树，查找效率要差一些。



常用算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划



网络通信协议



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





网络数据包格式





物理层

物理层负责数据的物理传输，计算机输入输出的只能是 0 1 这样的二进制数据，但是在

真正的通信线路里有光纤、电缆、无线各种设备。光信号和电信号，以及无线电磁信号

在物理上是完全不同的，如何让这些不同的设备能够理解、处理相同的二进制数据，这

就是物理层要解决的问题。



链路层

链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以

帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。

链路层会定义帧的大小，这个大小也被称为最大传输单元。像 HTTP 要在传输的数据上

添加一个 HTTP 头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一

个重要信息就是发送者和接受者的 MAC 地址。MAC 地址是网卡的设备标识符，是唯一

的，数据帧通过这个信息确保数据送达到正确的目标机器。



网络层

网络层 IP 协议使得互联网应用根据 IP 地址就能访问到目标服务器，请求离开 App 后，

到达运营服务商的交换机，交换机会根据这个 IP 地址进行路由转发，可能中间会经过很

多个转发节点，最后数据到达目标服务器。

网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络

层的 IP 数据包必须要小于最大传输单元才能进行网络传输，这个数据包也有一个 IP 头，

主要包括的就是发送者和接受者的 IP 地址。



传输层（TCP协议）

IP 协议不是一个可靠的通信协议，不会建立稳定的通信链路，并不会确保数据一定送达。要保证通

信的稳定可靠，需要传输层协议 TCP。

TCP协议是一种面向连接的、可靠的、基于字节流的传输层协议。TCP作为一个比较基础的通讯协

议，有很多重要的机制保证了TCP协议的可靠性和强壮性：

使用序号，对收到的TCP报文段进行排序和检测重复的数据

无错传输，使用校验和检测报文段的错误

使用确认和计时器来检测和纠正丢包或者延时

流量控制，避免主机分组发送得过快而使接收方来不及完全收下

拥塞控制，发送方根据网络承载情况控制分组的发送量，以获得高性能同时避免拥塞崩溃

丢失包的重传。



TCP 建立连接的3次握手过程

1. App 先发送 SYN=1，Seq=X 的报文，表示请求建立连接，X 是一个随机数；

2. 服务器收到这个报文后，应答 SYN=1，ACK=X+1，Seq=Y 的报文，表示同意建立连接；

3. App 收到这个报文后，检查 ACK 的值为自己发送的 Seq 值 +1，确认建立连接，并发

送 ACK=Y+1 的报文给服务器；服务器收到这个报文后检查 ACK 值为自己发送的 Seq

值 +1，确认建立连接。至此，App 和服务器建立起 TCP 连接，就可以进行数据传输了。





TCP 关闭连接4次挥手

• 客户端向服务器端发送一个 FIN，请求关闭数据传输。

• 当服务器接收到客户端的 FIN 时，向客户端发送一个 ACK，其中 ACK 的值等于FIN + SEQ。

• 然后服务器向客户端发送一个 FIN，告诉客户端应用程序关闭。

• 当客户端收到服务器端的 FIN 是，回复一个 ACK 给服务器端。其中 ACK 的值等于FIN + SEQ。





应用层 HTTP 协议

而互联网应用需要在全球范围为用户提供服务，将全球的应用和全球的用户联系在一起，

需要一个统一的应用层协议，这个协议就是 HTTP 协议。



HTTP 请求的7种方法

• Get：只读请求，请求处理过程不应该产生副作用，即web应用不应该因为 get 请求而发生任何状态改变。

• Head：和 get 方法一样，但是只返回响应头。

• Post：提交请求。

• Put：上传请求。

• Delete：删除 URL 标识的资源。

• Trace：回显服务器收到的请求，用以测试或者诊断。

• Options：请求服务器返回支持的所有 HTTP 请求方法，测试服务器是否正常。





HTTP 响应的5种状态

• 1xx消息——请求已被服务器接收，继续处理

• 2xx成功——请求已成功被服务器接收、理解、并接受

• 3xx重定向——需要后续操作才能完成这一请求

• 4xx请求错误——请求含有词法错误或者无法被执行

• 5xx服务器错误——服务器在处理某个正确请求时发生错误





http协议版本之间的区别

• 1.0协议：每次连接都需要三次握手

• 1.1协议：引入保持连接，允许客户端复用TCP连接，但一个连接不能并发，一个连接只能处理一个请求。在一个页面中如果有多个静态资源，就需要建立多个tcp连接

• 2.0协议：引入http流的概念，允许将不同的http请求并发地复用到同一个TCP连接上，使得浏览器可以高效地复用tcp连接。但当多个http请求复用一个tcp连接时，如果前面的请求/响应还没完成，后面的请求/响应就无法进行，也就是会出现队头堵塞现象。

• 3.0协议：不再使用TCP作为会话的传输层，而是使用QUIC。该协议在传输层将流作为一等公民引入。QUIC是基于UDP的。



非阻塞网络 I/O



单线程的阻塞



accept，read，write三个点都有可能被阻塞，导致后面的请求进来时无法响应





多线程服务器-客户端



主线程只负责accept，每个请求进来，都创建一个socket。

每个socket再创建单独的线程来负责read和write





线程池服务器





BIO Blocking I/O 阻塞 I/O



阻塞 I/O：进行 I/O 操作时，用户线程会一直阻塞，直到读操作或者写操作完成。





非阻塞 I/O（ Non-Blocking I/O ）





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

• 非阻塞 read 操作：

1. Socket 接收缓冲区有数据，读 n 个（不保证数据被读完整，因此有可能需要多次读）。

2. Socket 接收缓冲区没数据，则返回失败（不会等待）。

• 非阻塞write：

1. Socket 发送缓冲区满，返回失败（不会等待）。

2. Socket 发送缓冲区不满，写 n 个数据（不保证一次性全部写入，因此可能需要多次写）。



系统 I/O 复用方式：select，poll，epoll