程序如何运行
- 编写代码，形成文本格式文件
- 通过编译器编译成操作系统可执行代码
- 存储在磁盘上，静态的可执行代码和文本格式代码称为程序
- 把程序从磁盘等外部设备，加载到内存中，并由操作系统调度 CPU 去执行，称为 进程（代码、内存堆空间、栈空间）
堆：创建数组、对象，会从堆中申请一块空间，并把内存地址记录到栈
栈：记录函数内部局部变量、堆空间分配的内存地址等，先进后出
- 函数调用时，会在栈中创建 栈帧（stack frame），正在执行的函数栈帧在栈顶，栈帧中存储函数的局部变量、输入参数等内容
- 函数与函数之间的栈帧是隔离的，因此定义相同变量不会混乱
java运行：
- java 源码通过 javac 编译器编译为JVM使用的
.class字节码文件 - JVM 加载验证字节码
- 解释器解释字节码，JIT 将字节码编译为本地机器码
- CPU 执行机器指令
进程生命周期
- 就绪：获得所有资源，没获得 CPU，未运行
- 运行：进程在 CPU上运行
- 阻塞/睡眠：等待例如 IO 事件、锁时暂停运行，CPU 分配也无法运行的状态
- 进程通过 CPU 分片方式轮流执行
- 进程切换上下文开销较大，所以更多是通过多线程执行，例如用户请求
- 线程通过进程创建，线程和进程也是三种状态
Java Web 架构
请求执行：
- Tomcat 启动多线程
- 每个请求分配一个线程，调用请求URL的 Controller/Servlet，完成请求处理
系统运行变慢和崩溃
线程安全问题
- 多线程访问同个资源进行修改，结果应当具备多个线程修改结果，例如对一个资源 + 1，结果应当为 +n，但可能出现多个线程访问同个资源时，没有获得每个线程修改后的结果，而是原始值，导致最终只 + 1，这就是 线程安全 问题
- 多个线程共享资源的代码称为 临界区
- 通过 加锁解决线程安全问题
- 加锁会导致其他线程无法访问共享资源，形成 阻塞，最终导致系统速度变慢，假如被阻塞的线程越多，占用消耗资源超过系统承受资源极限，就会导致系统崩溃
RDBMS 关系型数据库：web 服务器用的多
解决
- 分布式架构：通过部署服务器集群，并发处理请求，解决高并发响应变慢
- 限流：在请求入口通过限流，减少并发请求数
- 业务降级：减少线程资源消耗
锁如何保证自己是线程安全的：锁通过 CPU 提供的原子指令（如 CAS（Compare And Swap）） 和缓存一致性机制，保证多个线程竞争锁时只有一个线程能成功获取，从而实现锁自身的线程安全。
- 原子指令（Atomic Instruction）：CPU 提供的不可分割的操作，保证多个线程并发执行时，不会出现操作交叉干扰。
- CAS（Compare And Swap，比较并交换）：一种原子操作，先比较内存中的当前值与预期值是否相等，相等则更新为新值，否则更新失败，用于实现无锁并发和锁状态竞争。
- 缓存一致性（Cache Coherence）：通过 MESI 等协议，协调多个 CPU 核心的缓存数据，确保同一内存位置的修改能够在各核心之间保持一致，避免使用过期的缓存数
- MESI 协议（Modified、Exclusive、Shared、Invalid）：一种 CPU 缓存一致性协议，通过已修改（M）、独占（E）、共享（S）、无效（I）四种缓存行状态，协调多个 CPU 核心对同一内存数据的读写，保证缓存数据的一致性。
数据结构
| 数据结构 | 随机访问 | 查找 | 插入/删除 |
|---|---|---|---|
| 数组 | O(1) | O(n) | O(n) |
| 单链表 | O(n) | O(n) | O(1)* |
| HashMap | 不适用 | 平均 O(1) | 平均 O(1) |
| 栈 | 不适用 | 通常 O(n) | 栈顶 O(1) |
| 队列 | 不适用 | 通常 O(n) | 队首/队尾 O(1)** |
-
数组：占用连续空间，存放相同数据类型，根据类型每个数据占用固定的字节地址空间
- 占用空间固定，因此可以通过下标查找到数据，随机读写时间复杂度为 O（1），按值查找为O(n)
- 插入删除，末尾为 O（1），中间为 O（n）
- Java 使用 ArrayList 动态数组自动扩容
-
链表：无需连续空间，每个数据包含指向下个节点的指针
- 只能遍历链表查找数据，复杂度 O(n)
- 插入删除只需断开旧节点指针，新节点指向后方指针，复杂度o(1)
- 查找2个链表是否合并：遍历链表1，记录hashmap映射，遍历链表2，查找hashmap中是否有相同节点，有则为开始合并的节点
-
哈希表（HashMap）：key-value，物理存储是数组格式，通过 hashcode 计算出数据所在的物理地址
java 的hashcode 通常存储在根对象的
hashcode()方法下，例如key是 a，则为a.hashcode()，再通过 hashcode 计算出数据在hashmap 下的索引位置哈希冲突：2 个不同的key得到相同的索引下标，解决方法通常是链表法，数组中存储的是 key，value数据元素的地址指针，如果出现冲突，就把数据加到该链表中，再遍历链表得到正确答案，退化链表会导致性能下降。
哈希表时间复杂度为何为 O（1）：基于哈希算法计算索引，若所有数据都存在哈希冲突，指向同个索引，那么最后就会退化成链表，此时不再是O（1）
栈：线性表基础上加操作限制，例如用于函数调用栈，顶部永远是当前执行方法工作区
队列：也是受限线性表，可以用于阻塞等待，例如数据库连接释放后去队列头部阻塞线程访问数据库
树：用于数据组织或优化访问速度，可用于例如组织架构，通常都是树形的
