1 数据结构与算法

1.1 数据结构

数组存储在连续的内存空间，查找时间复杂度为O(1)。链表可以使用零散的内存空间，每个数据元素都必须指向下一个数据元素的内存地址，查找复杂度为O(n)。链表的新增和删除时间复杂都都是O(1)，要比数组性能好，数组的新增和删除都是O(n)。



数组和链表结合，可实现快速查找和快速删除。Java中HashMap的数据结构就是数组+链表来实现的，查找时间复杂度是O(1)。哈希表中存储的是指针，这个指针指向链表的表头，当出现hash冲突时，新的数据会插入到链表中。



跳表在原有的有序链表上面增加了多级索引，通过索引实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除性能。



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



栈就是在线性表的基础上加了操作限制：后面添加的数据，在删除时必先删除，即后进先出。



void f(){
    int x = g(1);
    x++;	// g函数返回，当前堆栈顶部为f函数栈帧，在当前栈帧继续执行f函数的代码
}
int g(int x){
    return x + 1;
}



队列也是一种操作受限的线性表，栈是后进先出，而队列则是先进先出。



典型应用场景：生产者消费者；阻塞等待的线程被放入队列队尾。



用队列搜索好友最有钱的人



算法描述：

（1）首先将“你”入队尾，将有钱人设置为“你”

（2）将队首元素出队，并判断出队元素是否比有钱人更有钱，如果是则设置有钱人为当前元素。

（3）将与出队元素的所有朋友先后入队列。

（4）如果队列为空，则返回当前有钱人；否则继续执行。

（5）重复（2）-（4）

二叉树（Binary Search Tree）是数据结构中一种重要的数据结构，二叉树每个结点至多只有2棵子树，子树有左右之分，次序不能颠倒。二叉树的第i层最多有2^(i-1)个结点。



二叉排序树（Binary Sort Tree）中，左子树所有结点值小于或者等于它的根节点的值，右子树的所有结点值均大于或者等于它的根节点的值。左右子树也分别为二叉排序树。时间复杂度O(logn)。而不平衡的二叉排序树，时间复杂度可能为O(n)；



平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），其左右子树高度差的绝对值不能超过1，并且左右两个子树都是一颗平衡二叉树。平衡二叉树的常用算法又红黑树、AVL树等。



平衡二叉树插入时，最多只需要两次旋转就会重新恢复平衡。删除时，需要维护从删除结点到根节点这条路径上所有结点的平衡性。



红黑树，每个结点只有两种颜色：红色和黑色。根节点是黑色的。每个叶子结点（NIL）都是黑色的空结点。从根节点到叶子结点，不会出现两个连续的红色结点。从任何一个结点出发，到叶子结点，这条路上的都有相同数目的黑色结点。



红黑树VS平衡二叉树



• 红黑树只需要3次旋转就会到达红黑平衡，时间复杂度O(1)

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

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



Java中TreeMap就是使用红黑树实现的。

1.2 算法

1.2.1 时间/空间复杂度



衡量一个算法好坏的两个指标：时间复杂度和空间复杂度。

时间复杂度并不是计算程序具体执行的时间，而是算法执行语句的次数。O(2^n)表示对n数据处理需要进行2^n次方计算。O(1)，O(log(n))，O(n^a)为多项式时间复杂度。O(a^n)和O(n!)为非多项式时间复杂度。

空间复杂度时一个算法在运行过程中临时占用存储空间的大小的度量。O(n)表示需要临时存储n个数据。



1.2.2 NP问题



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



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



NP ？= P，能在多项式时间复杂度内验证的问题，是不是能在多项式时间复杂度内解决的问题？



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



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

1.2.3 算法策略



穷举算法的思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一进行验证，直到全部情况验证完毕。



递归算法，对于求解规模为N的问题，设法将它分解成规模较小的问题，然后由这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大的问题的解。比如快速排序



贪心算法，是指在对问题求解时，总是做出在当前看来是最好的选择。做出的选择在整体上可能不是最优解。比如背包问题。



动态规划，通常用于求解具有某种最优性质的问题。通常使用一个表来记录所有求解的子问题答案，不管该子问题以后是否被用到，只要它被计算过，将将其结果存入表中，最终从这个结果表中选择一个最优解。



遗传算法（Genetic Algorithm, GA），是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

2 网络通信协议

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





2.2 网络数据包格式



2.3 各个分层的任务



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



链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位铜鼓哦物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。



链路层会定义帧的大小，这个大小也被称为最大传输单元。像HTTP要在传输的数据上添加一个HTTP头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一个重要信息就是发送者和接收者的MAC地址。MAC地址是网卡的设备标识符，是唯一的，数据帧通过这个信息确保数据送达到正确的目标机器。



网络层IP协议使得互联网应用根据IP地址就能访问到目标服务器，请求离开App后，到达运营商的交换机，交换机会根据这个IP地址进行路由转发，可能中间会经过很多个转发结点，最后数据到达目标服务器。



网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络层的IP数据包必须要小于最大传输单元才能进行网络传输，这个数据包也有一个IP头，主要包括的就是发送者和接收者的IP地址。



传输层，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协议的七种方法



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

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

Post：提交请求。

Put：上传请求。

Delete：删除URL标识的资源

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

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



HTTP协议响应的五种状态



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

2xx消息：请求已成功被服务器接收、理解、并接收

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

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

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



3 非阻塞网络I/O

3.1 阻塞I/O



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



服务器-客户端



先启动的是服务器，监听一个端口，客户端通过这个端口连接服务器。



当服务器启动后，第一个客户端跟它建立连接的时候，服务器有两个socket。一个socket叫做服务器socket，这个socket需要先new出来，然后监听端口。另一个socket是客户端与它连接以后建立起来的socket。Socket总数目是客户端连接数+1。

3.2 非阻塞I/O

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

非阻塞read操作：

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

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

非阻塞write操作：

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

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



4 数据库架构原理

4.1 PrepareStatement预编译



// 未使用预编译
statement.executeUpdate("UPDATE Users SET status=2 WHERE userID=223");
// 使用预编译
PreparedStatement updateUser = con.prepareStatement("UPDATE Users SET status=? WHERE userID=223");
updateUser.setInt(1, 2);
updateUser.executeUpdate();

PrepareStatement会预先提交带占位符的SQL到数据库进行预处理，提前生成执行计划，当给定占位符参数，真正执行SQL的时候，执行引擎可以直接执行，效率更好一点。

而且PrepareStatement会防止SQL注入攻击。

• select * from users where username = 'Frank';

• Frank';drop table users;--

• select * from users where username = 'Frank';drop table users;--'

• select * from users where username=?

4.2 数据库组件



架构分成连接器、语法分析器、语义分析与优化器和执行引擎，是为了组件复用。



数据库连接器会为每个连接请求分配一块专用的内存空间用于会话上下文管理。建立连接堆数据库而言相对比较重，需要花费一定的时间，因此应用程序启动的时候，通常会初始化建立一些数据库连接放在连接池里，这样当处理外部请求执行SQL操作的时候，就不需要花费时间建立连接了。



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



索引类型分为聚簇索引和非聚簇索引



聚簇索引：聚簇索引的数据库记录和索引存储在一起。

MySQL数据库的主键就是聚簇索引，主键ID和所在的记录行存储在一个B+树中。



非聚簇索引在叶子结点记录的就不是数据行记录，而是聚簇索引，也就是主键。

通过非聚簇索引找到主键索引，再通过主键索引找到行记录的过程也被称作回表。



在几百万行的数据库中查找一条记录，如果没有索引，就需要全表扫描，检索所有的行记录，才能找到需要的记录。所以需要添加必要的索引以优化SQL查询性能。

但也不能盲目添加索引，尤其是在生产环境。因为：

• 添加索引的alter操作会消耗较长的时间（分钟级）

• Alter操作期间，所有数据库的增删改操作全部阻塞，对应用而言，因为连接不能释放，事实上查询也被阻塞。

其次删除不用的索引，避免不必要的增删开销。使用更小的数据类型创建索引。

4.3 数据库事务

事务特性ACID

• 原子性（Atomicity）：要么全部完成，要么全部取消。如果事务崩溃，状态回到事务之前（事务回滚）。

• 隔离性（Isolation）：如果2个事务T1和T2同时运行，事务T1和T2最终结果是相同的，不管T1和T2谁先结束，隔离性主要依靠锁实现。

• 持久性（Durability）：一旦事务提交，不管发生什么（崩溃或者出错），数据要保存在数据库中。

• 一致性（Consistency）：只有合法的数据（依照关系约束和函数约束）才能写入数据库。

数据库事务日志

进行事务操作时，事务日志文件会记录更新前的数据记录，然乎再更新数据库中的记录，如果全部记录都更新成功，那么事务正常结束，如果过程中某条记录更新失败，那么整个事务全部回滚，已经更新的记录根据事务日志中记录的数据进行恢复，这样全部数据都恢复到事务提交前的状态，仍然保持数据一致性。

• LSN：一个按时间顺序分配的唯一事务记录日志序列号。

• TransID：产生操作的事务ID。

• PageID：被修改的数据再磁盘上的位置。

• PrevLSN：同一个事务产生的上一条日志记录的指针。

• UNDO：取消本次操作的方法，按照此方法回滚。

• REDO：重复本次操作的方法。