一、线性结构

1. 定长 & 动态数组

• 细分类型：有序 / 无序数组、稀疏数组、环形数组、SOA 结构数组、SIMD 优化数组。

• 核心算法：

  • 查找：二分查找、插值查找、斐波那契查找、三分查找；

  • 预处理：前缀和（O (1) 区间和查询）、差分（O (1) 区间批量更新）；

  • 技巧：双指针（对撞 / 快慢）、滑动窗口、摩尔投票法、原地哈希、数组分块。

2. 链表

• 细分：单链表、双链表、循环链表、静态链表、块链表、持久化链表。

• 核心算法：链表反转、快慢指针判环 / 找中点、归并排序、删除倒数第 N 节点、拆分重组、惰性删除。

3. 栈

• 细分：顺序栈、链式栈、单调栈、共享栈、表达式栈。

• 核心算法：括号匹配、中缀转后缀、表达式求值、模拟 DFS；单调栈求解下一个更大 / 更小元素、柱状图最大矩形等经典问题。

4. 队列

• 细分：循环队列、双端队列 (Deque)、优先队列、阻塞队列、延时队列、无锁队列。

• 核心算法：BFS 层序遍历、单调队列求解滑动窗口最值、优先队列多路归并、延时队列定时任务调度。

5. 线性表扩展

• 结构：字典（关联数组）、位集合、有序集合、分段字典、稀疏字典。

• 核心操作：集合交并补运算、分段锁并发优化、布隆过滤器前置去重、字典树 + 哈希混合索引。

需要我把其中某一类数据结构的算法展开成更详细的原理与时间复杂度对照表吗？

二、字符串结构

1. 字符串表示

定长字符串、变长字符串、字符串池（常量复用）、rope（大字符串分块拼接）、字符串切片 / 视图（零拷贝引用）、mmap 内存映射大文件。

2. 核心算法

（1）匹配算法

• KMP：预处理 next 数组，主串指针不回溯，单模式匹配线性时间 O (n+m)。

• BM：坏字符 + 好后缀规则，从后往前匹配，大文本下平均性能优于 KMP。

• AC 自动机：多模式匹配标准，一次扫描匹配所有模式串。

• Rabin-Karp：滚动哈希，哈希快速初筛，适合多模式、模糊匹配场景。

• 进阶：Sunday、Shift-Or、Two-Way 等不同侧重的优化算法。

（2）编辑距离与序列比对

• Levenshtein 距离：增删改操作的最小编辑次数，动态规划求解。

• LCS（最长公共子序列）：经典二维动态规划问题。

• 进阶：带权编辑距离、Smith-Waterman 算法（生物信息序列比对）、限长剪枝优化。

（3）排序与压缩

• 字符串排序：基数排序（按字符位线性排序）、字符串快排、SA-IS 线性构建后缀数组。

• 压缩算法：

  • LZ77/LZ78：字典式压缩，现代压缩算法的基础；

  • 哈夫曼编码：熵编码，高频字符短编码，最优前缀码；

  • DEFLATE：LZ77 + 哈夫曼，gzip、PNG 标准；

  • 工业级：LZ4（极速）、ZSTD（高速高压缩比）、Brotli、LZMA。

（4）编码算法

UTF-8/16/32（Unicode 编码）、Base64/32（二进制转可打印字符）、RLE 游程编码、URL 编码、SIMD 加速编解码。

三、树形结构

1. 基础二叉树

• 常见类型：满二叉树、完全二叉树、哈夫曼树（最优前缀编码）、笛卡尔树（堆 + BST 双性质）；

• 区间专用：线段树（区间查询 / 更新，懒标记）、树状数组 (BIT)（单点更新 + 前缀和，实现极简）、主席树（可持久化线段树，历史版本查询）、李超树（线段覆盖最值）；

• 核心算法：前 / 中 / 后序遍历（递归 / 迭代）、层序遍历；线段树区间操作、标记永久化、线段树合并。

2. 二叉查找树 (BST) 及变种

• 基础 BST：左子树 <根 < 右子树，平均 O (log n)，最坏退化为链表。

• 自平衡变种：

  • AVL 树：严格平衡（左右高度差≤1），查询最优，插入删除旋转开销大。

  • 红黑树：近似平衡，通过着色 + 旋转维持性质，插入删除高效，是工业界标准（STL map、Java TreeMap）。

  • 伸展树 (Splay)：访问节点移至根，热点数据访问更快，局部性友好。

  • Treap：树 + 堆，随机优先级维持平衡，分裂 / 合并操作便捷。

• 进阶：可持久化 Treap、替罪羊重构、批量构建。

3. 多路查找树

• B 树：多叉平衡树，节点存数据，降低树高，适配磁盘存储，减少 IO 次数。

• B + 树：仅叶子节点存数据，内部节点仅存索引，叶子通过链表串联，范围查询极优，是数据库、文件系统索引的标准。

• B * 树：优化节点合并策略，提升空间利用率；

• 进阶：2-3 树、2-3-4 树、前缀 B 树、分区 B 树、批量插入优化。

4. 堆结构

• 基础：二叉堆（数组实现，完全二叉树，堆排序、Top-K、优先队列）、左式堆、斜堆；

• 进阶：斐波那契堆（decrease-key O (1)，理论最优）、配对堆（合并高效，实现简单）、二项堆；

• 核心算法：堆化、堆排序、Top-K、延迟删除、多路归并。

5. 字典树体系

• 前缀树 (Trie)：字符串前缀匹配、词频统计，字符路径即字符串。

• 后缀树 / 后缀数组 / 后缀自动机 (SAM)：处理子串、后缀相关问题，SAM 是当前最精简高效的后缀结构。

• AC 自动机：Trie + fail 指针，多模式串匹配，一次扫描匹配所有模式串，用于敏感词过滤、入侵检测。

• 优化：压缩字典树、双数组 Trie、路径压缩。

6. 空间划分树

• k-d 树：k 维空间二分划分，低维数据最近邻搜索高效。

• R 树 / R * 树：空间对象最小外包矩形索引，支持范围查询、空间连接，是 GIS 核心索引。

• 球树 (Ball-Tree)、VP 树：高维空间下比 k-d 树更优的最近邻结构。

7. 日志结构树

• LSM 树：写优化结构，数据先写内存表，满后顺序刷入磁盘 SSTable，后台异步 Compaction 合并；牺牲部分读性能换取极致写吞吐，是 RocksDB、LevelDB、HBase 的核心。

• 核心机制：WAL 预写日志（宕机恢复）、分层 / 大小分级 Compaction、布隆过滤器加速点查。

• 变种：TSM 树（时序数据优化）、WiscKey（键值分离优化）、Fractal Tree。

8. 领域专用树

• 区块链 / 密码学：MPT、稀疏默克尔树、累加器树、默克尔树森林；

• 实时流计算：倾斜树（解决数据倾斜）、窗口计数树（滑动窗口统计）。

四、图形结构

1. 存储方式

• 邻接矩阵：二维数组存储边关系，O (1) 查询边是否存在，适合稠密图，空间复杂度 O (V²)。

• 邻接表：每个节点维护邻接边链表，空间省，适合稀疏图，是最通用的存储方式。

• 十字链表：同时存储入边和出边，优化有向图的双向边遍历。

• 邻接多重表：无向图中每条边仅存储一次，优化边操作的冗余。

• 边集数组：仅存储所有边的列表，适合 Kruskal 等以边为核心的算法。

• CSR/CSC：压缩稀疏行 / 列存储，用数组压缩表示稀疏图，适配矩阵运算与大规模图计算。

• 分片 / 快照存储：分布式图系统的水平拆分，以及时态图的历史版本存储；图数据库（如 Neo4j）采用原生属性图存储优化。

2. 核心算法

（1）遍历与搜索

• DFS：深度优先遍历，基于栈 / 递归回溯，用于环检测、连通分量、拓扑排序，时间 O (V+E)。

• BFS：广度优先遍历，基于队列层序扩展，天然求解无权图最短路径，时间 O (V+E)。

• 迭代加深 DFS：限制搜索深度逐层加深，兼顾 DFS 的低空间与 BFS 的最优解特性。

• 双向 BFS：起点、终点同时向外 BFS，相遇即得到路径，大幅缩减搜索空间。

• A\*：启发式搜索，通过 f(n)=g(n)+h(n) 评估节点，启发函数可采纳时保证最优解，广泛用于路径规划。

• IDA\：迭代加深 + A\，空间复杂度低，适合状态空间极大的寻路场景。

• D Lite*：动态环境增量寻路，环境变化时局部更新路径，适配机器人导航、动态路网。

• Jump Point Search：网格寻路专用，通过跳点规则剪枝冗余节点，在 A * 基础上数倍提升网格寻路效率。

（2）最小生成树（无向连通加权图）

• Kruskal + 并查集：边按权排序后依次加入，用并查集判环，适合稀疏图，时间 O (E log E)。

• Prim + 优先队列：从单点出发，每次选连接已选 / 未选集合的最小边，适合稠密图，时间 O (E log V)。

• Boruvka 算法：每个连通分量独立选择最小出边，天然并行友好，适配分布式超大规模图。

• 进阶支持增量更新、Pregel 框架下的分布式 MST 计算。

（3）拓扑排序（DAG 专属）

• Kahn 算法：基于入度统计，入度为 0 的节点入队输出，同步更新邻接点入度，可同步检测环。

• DFS 逆序法：DFS 后序遍历的逆序即为拓扑序列。

• 进阶支持动态拓扑维护、环定位、多核并行化调度。

（4）最短路径

• Dijkstra + 堆优化：单源非负权最短路，贪心 + 优先队列，工业界最常用，时间 O (E log V)。

• Bellman-Ford / SPFA：处理负权边，可检测负环；SPFA 为队列优化版，平均效率高，最坏 O (VE)。

• Floyd-Warshall：多源最短路，动态规划实现，O (V³)，仅适合小规模图。

• Johnson：重赋权消除负权后多次 Dijkstra，求解带负权无负环的多源最短路。

• 进阶：分层图最短路（带状态约束）、多源最短路、带资源限制的约束最短路径 (CSP)。

（5）连通性与割

• 并查集：无向图动态连通性查询，路径压缩 + 按秩合并后操作近似常数级。

• Tarjan 算法：一次 DFS 求解强连通分量、割点、桥、双连通分量，用于图缩点与容错分析。

• Link-Cut Tree：动态树结构，支持动态连边 / 断边下的路径连通性与信息查询。

• Stoer-Wagner：求解无向图全局最小割，用于网络可靠性分析。

• k – 连通性分析：评估图的容错能力，即至少删除 k 个点 / 边才会断开。

（6）网络流

• Dinic 算法：分层图 + 阻塞流增广，当前工业界最高效的最大流算法之一。

• ISAP：Dinic 的优化版本，无需重复 BFS 分层，常数更小。

• SPFA+EK 费用流：求解最小费用最大流，用最短路寻找最小费用增广路。

• 进阶：上下界网络流、容量缩放优化、分布式大规模网络流。

（7）二分图匹配

• 匈牙利算法：基于增广路求解最大匹配，是二分图匹配的基础算法。

• Hopcroft-Karp：BFS 批量寻找增广路，时间复杂度 O (E√V)，适合大规模二分图。

• KM 算法：求解带权二分图的最大权完美匹配。

• 进阶：最大权闭合子图（转化为最小割）、动态节点在线匹配。

（8）图挖掘与表示学习

• PageRank：基于链接传递的节点重要度迭代计算，用于搜索引擎、社交网络影响力排序。

• Louvain 算法：层次化社区检测，基于模块度优化，是当前最高效的社区发现算法之一。

• 标签传播算法：简单轻量的社区发现，节点向邻居传播标签，收敛快。

• GNN 系列（GCN/GAT/GIN）：图神经网络，基于消息传递机制学习节点 / 图的低维表征，适配图分类、链路预测等任务。

• DeepWalk / Node2Vec：随机游走 + Word2Vec，生成节点嵌入向量，用于下游机器学习。

• Infomap：基于信息流的社区检测，对有向图、加权图效果更优。

五、哈希与索引结构

1. 散列表 (Hash Table)

• 哈希函数：

  • 基础：除留余数法、平方取中法；

  • 工业级高性能：MurmurHash、xxHash、CityHash、FarmHash；

  • 加密级：SHA-256、Blake2，防碰撞、用于校验与安全场景。

• 冲突解决：

  • 链地址法：最通用，冲突节点用链表串联；

  • 开放寻址：线性 / 二次探测，无指针，缓存友好；

  • 布谷鸟哈希：多哈希表位置，高负载因子下仍高效；

  • 跳房子哈希：邻域探测，兼顾缓存局部性与负载率。

• 进阶：一致性哈希（分布式负载均衡，虚拟节点抗倾斜）、可扩展哈希（动态分裂扩容）、布谷鸟过滤器（存在性判断，支持删除）、冷热分层哈希。

2. 跳表 (SkipList)

• 核心思想：在有序链表上叠加多层索引，通过高层跳跃、低层精确定位，实现 O (log n) 的查找、插入、删除。

• 关键特性：概率性平衡（随机决定节点层级），实现比平衡树简单，天然支持区间查询。

• 工程应用：Redis ZSet 核心实现，支持分值排序、跨度统计；进阶有并发跳表（CAS 无锁）、持久化、压缩索引。

3. 倒排索引

• 核心结构：Term 词典 + Posting List（倒排链），记录每个词出现的文档 ID 与位置信息。

• 核心算法：布尔检索（倒排链交并补）、TF-IDF / BM25 相关性评分；

• 优化手段：倒排链差值压缩、跳表加速求交、列式存储优化、增量实时更新与缓存策略。

• 典型场景：全文搜索引擎（Elasticsearch）、关键词检索。

4. 位图结构

• 基础 BitMap：用二进制位表示状态，位运算极快，适合低基数列的快速筛选、去重统计。

• 压缩位图：Roaring Bitmap（高低位分桶，兼顾空间与计算速度）、EWAH Bitmap（字对齐压缩）；

• 进阶优化：SIMD 并行位运算、磁盘持久化、分层位图适配大规模数据。

5. 几何索引结构

• R \ 树*：优化 R 树的节点分裂策略，空间对象范围查询更高效，是 GIS 系统主流索引。

• 四叉树 / 八叉树：二维 / 三维空间递归四 / 八划分，适合点数据的空间检索。

• 希尔伯特 R 树：用空间填充曲线排序数据，优化空间局部性与查询性能。

• 网格索引：地理空间网格化分块，简单高效，适配大规模地理数据。

六、特殊数据结构与算法

1. 并查集 (Disjoint Set Union)

• 核心：路径压缩 + 按秩合并，操作均摊复杂度接近常数，用于集合合并与连通性查询。

• 变种：带权并查集（维护节点到根的权重关系）、可持久化并查集（保留历史版本）、启发式合并、分布式集群连通性实现。

2. 布隆过滤器 (Bloom Filter)

• 核心：多位图 + 多哈希函数，判断元素 “可能存在 / 一定不存在”，无漏判、有误判，空间效率极高。

• 变种：计数布隆过滤器（支持删除）、布谷鸟过滤器（更低误判、支持删除）、分层 / 动态布隆过滤器（支持扩容）、分布式合并操作。

• 典型场景：缓存穿透防护、URL 去重、黑名单前置过滤。

3. 环形缓冲区 (Circular Buffer)

• 核心：固定大小数组 + 头尾循环指针，FIFO 顺序读写，避免数据搬移，空间复用。

• 应用：音视频流缓冲、嵌入式系统、环形日志；进阶支持批量读写、无锁线程安全实现。

4. 多项式与幂级数

• 基础运算：多项式加减乘；

• 核心加速：FFT（快速傅里叶变换）、NTT（数论变换），将多项式乘法从 O (n²) 优化到 O (n log n)；

• 进阶：多项式求逆、开根、插值、模运算（密码学、信号处理场景）。

5. 高级数据结构

（1）平衡树扩展

• 替罪羊树：暴力重构维持平衡，实现简单，适合写少读多场景。

• 珂朵莉树：基于区间赋值的暴力优化，随机数据下区间操作极快。

• Link-Cut Tree：动态树，支持路径信息查询、连边 / 断边，用于动态图与树上问题。

（2）流式数据结构

• 蓄水池抽样：流数据等概率抽样，仅需 O (k) 空间。

• HyperLogLog：极小空间估算集合基数（去重数量），误差可控。

• Count-Min Sketch：多维哈希计数，估算元素频率，结果只高不低。

• Space-Saving / Heavy Hitters：流数据中高效统计高频 Top-K 元素。

（3）机器学习相关

• KD-Tree / Ball-Tree：空间划分树，用于低 / 高维向量的最近邻搜索。

• 乘积量化 (PQ)：高维向量分块压缩，大幅节省向量存储空间。

• 向量索引（FAISS / HNSW / Annoy）：近似最近邻搜索，是向量检索、推荐系统的核心组件。

（4）密码学 / 区块链专用

• 默克尔树：哈希二叉树，仅用根哈希即可校验数据完整性，可快速定位篡改位置。

• 默克尔前缀树 (MPT)：默克尔树 + 前缀树融合，以太坊状态存储核心，支持路径压缩与默克尔证明。

• 稀疏默克尔树：仅存储非默认节点，适配区块链轻客户端；累加器树用于零知识证明的集合成员验证。

（5）系统与流计算

• 控制流图 (CFG)、支配树：编译器代码优化、程序分析的基础结构。

• 内存池、页表、段树：操作系统内存管理的核心数据结构。

• 倾斜树、窗口计数树：流计算中解决数据倾斜、滑动窗口统计的专用结构。

• 时空索引、轨迹索引、GeoHash：时空数据与地理信息的索引结构。

• 稀疏矩阵存储（COO/CSR/CSC）：科学计算中稀疏矩阵的高效存储格式。