总结

1.时间复杂度和空间复杂度

时间复杂度：并不是计算程序具体的运行时间，而是算法执行语句的次数。

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

2.NP 问题

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

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

NP ?= P

NP-hard:比 NP 问题更难的问题

NP 完全问题：是一个 NP-hard 问题,也是一个 NP 问题

3.数组

创建数组需要一个连续的内存空间。数组中必须存放相同的数据类型。随机快速读写是数组的一个重要特性，根据数组下标访问数据，时间复杂度为 O(1)

4.链表

链表可以使用零散的内存空间存储数据。所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针，要想在链表中查找一个数据，只能遍历链表，复杂度为 O(N)

4.Hash 表

hash 表示根据关键码值而直接进行数据访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

hash 表 key 冲突解决：开放寻址、链地址法、再哈希法、建立公共溢出区

5.栈

数组和链表都被称为线性表。

栈是在线性表的基础上加了操作限制条件：后进先出。

6.队列

队列也是一种操作受限的线性表，栈是后进先出，队列是先进先出。阻塞等待的线程被放入队列。

应用场景：生产者消费者

7.树

树是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合

二叉排序树：

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

平衡的二叉排序树：

从任何一个节点出发，左右子树深度之差的绝对值不超过 1，左右子树仍然为平衡二叉树。

红黑排序树：

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

根节点是黑色的

每个叶子节点都是黑色的空节点

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

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

增删节点的时候，红黑树通过染色和旋转，保持红黑树满足定义

红黑树和平衡二叉树

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

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

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

8.跳表

跳表是一种随机化的数据结构，实现原理简单。

9 网络通信协议

OSI 七层模型：

应用层、表示层、会话层、传输层、网络层、数据链路层、物理层

TCP/IP 四层模型：

应用层、传输层、网络层、链路层

网络数据包格式：

物理层：

物理层负责数据的物理传输。计算机输入输出的只能是 0,1 这样的二进制数据，但是在真正的铜线线路里有光纤、电缆、无线各种设备。光信号和电信号，以及无线电磁信号在物理上完全不同，如何让着些不同的设备能够理解、处理相同的二进制数据，是物理层要解决的问题。

链路层：

链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流浪控制。链路层会定义帧的大小，这个大小被称为最大传输单元。

网络层：

网络层 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 次挥手：

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

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

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

4.当客户端收到服务器端的 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 协议版本：

HTTP/1.0，客户端请求到资源后会关闭连接，并发量大的时候会导致频繁创建、关闭 TCP 连接，而 TCP 三次握手、四次挥手会消耗一定的时间。

HTTP/1.1 默认启用长连接模式，即客户端可以使用同一个 TCP 连接顺序发送多个请求，新版本也引入了管道机制，客户端可以不用等上一个请求的响应结果就可以发送下一个请求，但是服务器端也是按照客户端请求的顺序进行响应的，可以理解为半双工模式。

HTTP/2 服务 TCP 连接的方式不同，依然遵循请求-响应模式，但客户端发送多个请求和服务端给出多个响应的顺序不受限制，这样既避免了队头堵塞，又能更快获取响应。

10.非阻塞网络 I/O

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

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

非阻塞 read 操作：socket 接收缓冲区有数据，读 n 个。socket 接收缓冲区没数据，则返回失败。

非阻塞 write：socket 发送缓冲区满，返回失败。socket 发送缓冲区不满，写 n 个数据

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

I/O 多路复用机制，单个线程通过记录跟踪每一个 Socket (I/O 流)的状态来同时管理多个 I/O 流