数据结构与算法
#数据结构 · #总览
底层原理 × 工程实现：不仅讲理论，更追踪各语言（Go/C++/Python/Rust）和系统（Redis/Linux/MySQL）中的真实实现。
本专题系统覆盖数据结构与算法的核心知识，从基础的数组、链表、哈希表，到高级的红黑树、跳表、LSM-Tree，再到分布式场景下的一致性哈希与 Raft 共识。每个主题都结合真实系统中的工程实现来讲解，帮助理解"为什么这样设计"。
基础知识速查
线性结构
| 数据结构 | 特点 | 常见操作复杂度 |
|---|---|---|
| 数组 | 连续内存，随机访问 O(1) | 插入/删除 O(n) |
| Vector | 动态数组，自动扩容 | 末尾插入均摊 O(1) |
| 链表 | 非连续内存，插入删除 O(1) | 查找 O(n) |
| 队列 | FIFO，先进先出 | 入队/出队 O(1) |
| 优先队列 | 按优先级出队 | 插入 O(log n)，取最大 O(1) |
| 双端队列 | 两端均可入队出队 | 两端操作 O(1) |
排序算法
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
算法设计思想
- 分治法、动态规划、贪心算法、回溯法、滑动窗口、双指针
专题深入
数据结构
- 链表、队列与栈 — 单向/双向链表、Slice/Vector、栈、队列、Redis ziplist/listpack
- 环形缓冲区 — 原理与实现、SPSC无锁、Go Channel/kfifo/Disruptor/Kafka中的实现
- 堆与优先队列 — 二叉堆实现、堆排序、TopK问题、斐波那契堆、各系统中的应用
- LRU 与 LFU 缓存淘汰 — 哈希链表实现、Redis近似LRU/LFU、W-TinyLFU对比
- Hash 表与 Map — 哈希函数设计、负载因子、扩容全链路、SwissTable
- O(log n) 查找结构 — 红黑树、AVL/跳表/B/B+/LSM树、多场景对比
- 并查集与线段树 — 路径压缩/按秩合并、线段树(含lazy)、树状数组
- 特殊结构 — Trie/Radix Tree、Bitmap、Bloom Filter/Cuckoo Filter、HyperLogLog、Roaring Bitmap、嵌套集合/物化路径
算法
- 算法基础入门（Hello 算法） — 复杂度分析、基础数据结构、搜索/排序、分治/回溯/DP/贪心
- CLRS《算法导论》补充 — 主定理、摊还分析、斐波那契堆、vEB树、并查集、NP完全性
- 贪心算法 — 正确性证明方法、活动选择/区间调度/Huffman/分数背包/加油站
- 排序与选择算法 — 快排优化、Timsort、pdqsort/Introsort、各语言排序实现
- 二分查找 — 左闭右闭/左闭右开、左右边界、旋转数组、峰值查找、二分答案
- 图算法 — DFS/BFS、拓扑排序、最短路径、最小生成树
- 动态规划 — 核心思想、背包/LCS/LIS/编辑距离、DP分类识别与优化技巧
- 滑动窗口与双指针 — 左右/快慢双指针、滑动窗口框架、经典问题
- 回溯算法 — 三要素框架、子集/组合/排列/N皇后/数独、剪枝技巧
- 字符串匹配算法 — KMP、Boyer-Moore、Rabin-Karp、AC自动机
- 位运算技巧 — Brian Kernighan、lowbit、快速幂、位掩码、状态压缩
- 数学与数论基础 — GCD/LCM、素数筛、快速幂模运算、组合数学（卡特兰数）
- 设计类算法 — 限流（令牌桶/漏桶/滑动窗口）、分布式ID（Snowflake）、短链算法（Base62）、负载均衡（平滑加权轮询）、时间轮/延迟队列、海量Token生命周期管理
- 压缩、散列与加密 — 非加密散列、加密散列、AES/Ed25519、LZ4/Zstd 压缩
- 一致性Hash与Raft — 环形Hash/虚拟节点、Raft 领导者选举/日志复制
登录后即可发表评论 👇