主题
概念卡片：线性表与哈希表
一句话机制：栈 LIFO、队列 FIFO、链表插入删除快、哈希表 O(1) 查找。哈希表通过散列函数
h(key)把关键字直接映射到存储位置，省去比较；冲突靠开放定址法或拉链法解决。
栈 vs 队列
| 栈 Stack | 队列 Queue | |
|---|---|---|
| 规则 | LIFO（后进先出） | FIFO（先进先出） |
| 操作端 | 只在一端（栈顶）插入/删除 | 前端删、后端插 |
| 基本操作 | push/pop/peek | offer/poll/peek |
链表
- 与数组同级的数据结构，循环遍历效率不高，但插入删除优势明显（不需移动元素）。
- Java 里 ArrayList 是数组实现（非链表），LinkedList 才是链表。
哈希表（散列表）
- 定义：根据关键码值直接访问，
存储位置 = h(key)，一次存取完成查找。 - 优点：查找/插入/删除接近 O(1)，比树快。
- 缺点：基于数组，难扩建，装满后性能骤降。
哈希函数构造方法
| 方法 | 公式/思路 |
|---|---|
| 直接定址法 | H(key)=key 或 a*key+b |
| 除余法 | h(key)=key MOD p（p≤m） |
| 基数转换法 | 关键字按某进制转换 |
| 平方取中法 | 关键字平方后取中间几位（分布均匀） |
| 折叠法 | 分割成几部分叠加（移位叠加/间界叠加） |
哈希冲突及处理
冲突 = 不同关键字算出相同哈希地址。两种处理：
| 方法 | 思路 | 特点 |
|---|---|---|
| 开放定址法 | 冲突时按探查序列找下一个空位（线性/二次/双散列） | 平均查找长度更长 |
| 拉链法 | 同义词放在同一单链表（指针数组存头指针） | 多占指针空间，但比较只发生在同义词间，查找更短 |
- 线性探查：
x+1, x+2, x+3…；二次探查：x+1², x+2², x+3²…（防聚集）。 - 双散列函数法：冲突后探查间隔由第二个哈希函数决定。
关键代码示例（哈希应用场景）
Java 的 HashSet 用 HashMap 的 key 存储元素，靠 hashCode 定位；判断重复调 hashCode + equals。
不变量（必须成立的约束）
- 栈/队列都是操作受限的线性表。
- 哈希表 O(1) 是平均复杂度，冲突严重会退化。
- 拉链法平均查找长度低于开放定址法（只与同义词比较）。
常见误解
- 以为「ArrayList 是链表」→ 是数组（动态数组）。
- 以为「哈希无需比较」→ 冲突发生时仍需在探查序列/链表里比较。
- 以为「开放定址法和拉链法等价」→ 开放定址省空间但查找长，拉链省比较但占指针空间。
关联
- 树：概念卡片：树
- 总览：数据结构与算法技术栈总览