26 LC
来自经典的抄多算法册: 从数据结构篇开启 → 刷题篇
数据结构
List (线性表)
A. 数组
B. 链表
C. 环形数组
RingBuffer / 滑动窗口
环形数组的核心应用就在双端队列这, 它相比普通数组的最大优势就是:
- 头和尾都能 O(1) 增/删
- 自带循环, 滚动更新/覆盖的场景无需担心扩容 (环的应用)
而且相当于结合了双指针 + 数组的运用. 动手实现参考 lc/src/test/java/TestList.java
Map
A. 哈希表核心原理
如果主看 Java 的话, 可能以为拉链法是主流, 实际上它并不是, 因为使用 map 且大量删除的场景很少, 而 map 追求的高并发/性能很常见
- 开放地址 (横向扩展)
- 优点: 最大的好处之一是高效简洁, CPU Cache 友好, cache line miss 极大降低 (链表则很不友好)
- 数组操作, 不需要增删 Node, 不需要跨 Cache, 不需要额外的对象头/指针 (空间并不会多)
- 适合追求**”高性能 + 读多写少”**的场景 (Redis/Python/Go 默认实现策略都基于此)
- 拉链法 (纵向扩展)
B. 链式哈希表（LinkedHashMap）
C. 数组哈希表（ArrayHashMap）
Refer: