【架构师训练营】第八期笔记

数据结构与算法

数组

• 数组是内存中一块连续的空间

• 数组中的元素必须是相同的数据类型

• 数组可以随机快速读写，根据下表访问数据时间复杂度为 O(1)

链表

• 链表可以用零散的内存空间存储数据

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

• 访问链表元素需要遍历链表，时间复杂度为 O(n)

哈希表

• 通过计算哈希值获取哈希表中的下标，访问数据为数组访问，时间复杂度为 O(1)

• 可能会出现哈希值冲突的情况，此时通过链表的方式来解决 key 冲突问题

栈

• 后进先出的线性表

队列

• 先进先出的线性表

树

二叉排序树

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

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

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

跳表

常用算法：

• 穷举算法

• 递归算法（快速排序）

• 贪心算法（迪杰斯特拉算法）

• 动态规划

网络通信

Web 请求一次网络通信历程

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

数据包格式

系统 IO 复用方式: select, poll, epoll