思考与感悟

学习算法是编程思维的修炼

有同学问：“为什么要学习算法？学习算法有用吗？具体工作中又不怎么会用到。”

智慧老师回答：“常见的算法是编程思维的修炼，用到用不到的都应该好好学习算法。”而面试时考算法，主要是查看一个人的思维能力（虽然入职后都是螺丝钉）。

联想学习

智慧老师说很多知识其实不用学，用“猜”的就能猜出个大概来，如果是你，你会怎么去设计？如果猜错也不要紧，再去看书，再去学习，这样就能加深对知识的印象和理解，所以他学习知识还是很轻松的。

我对智慧老师这段话的理解：还是要主动地获取知识，站在更高的角度去看问题（以师者、或者作者的角度），去思考。与被动地学习（看书、被灌输）相比，知识留存率要高。

学而不思则罔，思而不学则殆。

TIPS

• 百万级并发，应该是中国互联网的顶级并发了。一定要理解并发的概念（同时处理请求的数目）。

• 数据库不推荐用 docker，可以使用公有云提供的数据库服务。

数据结构与算法 - 2020/7/23 - 周四

数据结构

• 数组

• 必须要在内存中一块连续的空间

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

• 随机快速读写，根据小标访问，时间复杂度 O(1)

• 链表

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

• 所以链表总的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。

• 想要在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是 O(N).

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

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

• Hash(哈希) 表

• 既快速访问数据，又快速增删数据

• Hash 表 Key 冲突

• 队列

• 先进先出的数据结构，可以用数组实现，也可以用链表实现。

• 阻塞等待的线程被放入队列。

• 典型应用场景：生产者消费者

• 用队列搜索好友中关系最近的有钱人

• 用队列搜索最短路径

• 栈

• 后进先出的数据结构，可以用数组实现，也可以用链表实现。

• 线程栈

• 树

• 二叉排序树

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

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

• 左、右子树也分别为二叉排序树。

• 平衡二叉排序树

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

• 左右子树仍然为平衡二叉树

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

• 删除时，需要维护从被删节点到根节点这条路径上所有节点的平衡性，时间复杂度 O(logN)

• 非平衡二叉排序树

• 
  

• 红黑（排序）树

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

• 根节点是黑色的。

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

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

• 红黑树 VS 平衡二叉树

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

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

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

• 跳表

• 跳着查找链表中的元素

• 需要额外的空间复杂度 O(n)

• 图

• 有向图

• 入度，出度

• 一笔画

• 戈尼斯堡七桥问题

• 无向图

算法

算法的时间复杂度

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

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

• O(1), O(log(n)), O(n^a) 多项式复杂度

• O(a^n) 和 O(n!) 非多项式复杂度

算法的空间复杂度

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

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

NP 问题

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

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

NP ?= P

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

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

常用的算法

• 穷举算法

• 递归算法

• 快速排序

• 选择基线条件，让左边的小于它，右边的大于它，然后层层递归。

• 时间复杂度：n * log(n)

• 贪心算法

• 背包问题：小偷背了一个 4 磅的背包去商城偷东西，将哪些商品放入背包才能收益最大化。

• 改进贪心算法 - 迪杰斯特拉算法（最快路径）

• 找出“最便宜”的节点，即可在最短时间内到达的节点。

• 更新该节点的邻居的开销，检查是否有前往他们的更短路径，如果有，就更新其开销。

• 重复这个过程，知道对图中的每个节点都这样做了。

• 计算最终路径。

迪杰斯特拉算法的核心是找到起点到每个节点的最快路径。

• 动态规划算法解决背包问题

• 通过找到合适的角度，将所求解的目标值在某（几）个维度上展开，将一个大问题拆解为若干小问题，小问题的最优解，寻找大问题的最优解

• 每个动态规划算法都从一个网格开始，背包问题的网格如下

• 遗传算法解决背包问题

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

• 基因编码与染色体

• 物品基因编码

• 适应函数与控制参数

• 选择算法

• 轮盘赌选择

• 随机竞争选择

• 均匀排序

• 交叉遗传

• 遗传算法得到的不是最优解

网络与数据库 - 2020/7/25 - 周六

网络通信协议

Web 请求的一次网络通信历程

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

• OSI 七层模型

• 应用层

• 表示层

• 会话层

• 传输层

• 网络层

• 数据链路层

• 物理层

• TCP/IP 四层模型

• 应用层

• 传输层

• 网络互联层

• 网络访问(链路)层

网络数据包格式

物理层

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

数据链路层

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

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

数据链路层负载均衡

网络层

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

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

IP 负载均衡

传输层(TCP 协议)

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

TCP 协议是一种面向连接的、可靠的、基于字节流的传输层协议。TCP 作为一个比较基础的通讯协议，又很多重要的机制保证了 TCP 协议的可靠性和强壮性：

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

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

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

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

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

丢失包的重传

TCP/IP 三次握手与四次挥手

应用层 HTTP 协议

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

HTTP 请求的 7 种方法

• Get: 只读请求

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

• Post: 提交请求

• Put: 上传请求

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

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

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

HTTP 响应的 5 种状态

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

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

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

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

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

HTTP 协议版本

• HTTP/1.0

• 频繁创建、关闭 TCP 连接

• HTTP/1.1

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

• HTTP/2

• 客户端发送多个请求和服务端给出多个响应的顺序不受限制，这样既避免了“队头堵塞”，又能更快获取响应。

非阻塞网络 I/O

BIO Blocking I/O 阻塞 I/O

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

服务器-客户端 -> 多线程服务器-客户端 -> 线程池服务器(减少了 new 线程的开销)

服务器会有 n+1 个 socket, n 为 accept socket(Socket socket = serverSocket.accept())，1 为服务器监听 socket.

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

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

非阻塞网络 I/O 不像传统的 socket, 在 accept, read, write 时会被阻塞。

阻塞与非阻塞都是针对应用程序来看的。

Java NIO(New I/O)

Selector, Buffer, SelectableChannel, SelectionKey

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

无活动连接时，Selector.select 方法被阻塞

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

PrepareStatement 预编译

可以防止 SQL 注入攻击

数据库架构

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

连接器

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

语法分析器

语义分析与优化器

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

执行计划

B 树与 B+ 树

聚簇索引

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

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

非聚簇索引

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

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

添加必要的索引优化 SQL 查询性能

谨慎使用索引

不要盲目添加索引，尤其在生产环境中

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

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

• 删除不用的索引，避免不必要的增删开销

• 使用更小的数据类型创建索引

数据库事务

事务特性 ACID

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

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

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

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

数据库事务日志