1.数据结构与算法

数据结构与算法是为了解决让代码如何运行的更快，如何更省存储空间的问题。在数据结构与算法中通过时间、空间复杂度两个维度来衡量代码是否运行的更快，更省存储空间。用大 O 表示复杂度。

• 时间复杂度

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

O(2^n)表示对 n 数据处理需要进行 2^n 次计算。

• 空间复杂度

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

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

NP 问题

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

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

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

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

1.1 常用数据结构

• 数组

创建数组必须要内存中一块连续的空间，且必须存放相同的数据类型。

特点：随机快速读写，根据数组的下标访问数据（直接根据内存地址偏移方式获取），读的时间复杂度为 O(1)，如果不是在数组末尾添加，删除数据，就会有移动数据操作。

• 链表

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

特点：查找数据，只能遍历链表，查找时间复制度 O(n).与数组相比读性能低，添加，删除操作不需要移动其他元素。

• hash 表

既然快速读数据，也能快速删数据。

• 栈

在线性表（数组和链表）基础上添加了“先进后出”的操作限制。

• 队列

在线性表（数组和链表）基础上添加了“先进先出”的操作限制。

应用场景：搜索好友关系最近的有钱人、搜索最近路径。

• 树

常见的有不平衡二叉树，平衡二叉树，红黑树等。

平衡二叉树 VS 红黑树

a.红黑树最多需要 3 次旋转就会重新达到红黑平衡，时间复杂度 O(1).

b.大量删除时，红黑树效率更高。

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

• 跳表

1.2 常用算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划

• 遗传算法

2.网络通信协议

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

2.2 网络数据包格式

2.3TCP 协议（传输层）

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

TCP 关闭连接 4 次挥手

2.4http 协议

http 请求 7 种方法

http 响应 5 种状态

http 协议版本

3.非阻塞网络 I/O

I/O 的阻塞与非阻塞都上针对一个线程而言的。

• BIO(Blocking I/O 阻塞 I/O)

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

• 非阻塞 I/O(Non-Blocking I/O)

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

非阻塞 read 操作：

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

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

非阻塞 write 操作：

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

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

• Java NIO(New I/O)

NIO 与传统 I/O 之间第一个最大的区别是，IO 是面向流的，NIO 是面向缓冲区的。

四个主要对象：Selector,Buffer,Channel,SelectionKey。

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

select(poll)管理下的 read 过程

epoll 管理下的 read 过程

4.数据库原理

4.1 数据库架构

mysql 数据库架构图（引用林晓斌的图）

• 连接器

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

• 语法分析器

通过分析 SQL 生成语法树，并校验 SQL 语法问题。

• 语义分析与优化器

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

• 执行计划

4.2 索引

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

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

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

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

在 MYSQL 中当某个查询并发量非常大，可以通过建立复合索引来进行优化，直接通过复合索引获取需要查询的结果，减少回表的操作。

使用索引的注意点：

4.3 数据库事务