当前位置：首页 > news >正文

100种高级数据结构 (速查表)

news 2025/9/4 5:32:24

一、基础结构的扩展与组合 (Advanced Linear Structures)

这些结构在数组、链表、队列、栈等基础结构上增加了特定功能或约束。

双端队列 (Deque - Double-Ended Queue)
- 介绍：允许在队列的前后两端都进行插入和删除操作的线性结构。
- 应用场景：工作窃取算法（如Java的Fork/Join框架）、滑动窗口问题、撤销历史记录（前后都可以操作）。
循环缓冲区/环形缓冲区 (Circular Buffer / Ring Buffer)
- 介绍：固定大小的数组，头尾相连，通过移动指针来实现高效的插入和删除，避免数据搬移。
- 应用场景：生产者-消费者问题、音频/视频数据处理、高速数据流缓存、性能关键的队列实现。
位图 (Bitmap / Bitset)
- 介绍：用比特位（bit）来存储数据（通常是布尔值）的紧凑数组，每个元素只占1bit。
- 应用场景：快速排序、海量数据去重、布隆过滤器的基础、数据库索引。
并行数组 (Parallel Arrays)
- 介绍：使用多个相同长度的数组，通过相同索引来关联不同属性，是一种数据组织方式而非单一结构。
- 应用场景：在注重缓存性能和对齐的数值计算、游戏开发（ECS架构）中常见。
间隙缓冲区 (Gap Buffer)
- 介绍：在数组中维护一个“间隙”，插入操作通过移动间隙来实现，在间隙处插入效率高。
- 应用场景：文本编辑器（如Emacs）的核心数据结构，适用于光标附近的频繁插入删除。
链式散列表 (Chained Hash Table)
- 介绍：数组+链表的组合，解决哈希冲突的主要方法之一。
- 应用场景：各种编程语言字典/对象的基础实现（如Python dict早期版本）、高速缓存。
开放寻址散列表 (Open-Addressed Hash Table)
- 介绍：所有元素都存放在数组本身中，通过探测解决冲突（线性探测、二次探测、双重哈希）。
- 应用场景：对缓存更友好，常用于需要极高性能且数据量可预估的场景。
跳跃表 (Skip List)
- 介绍：一种多层的有序链表，通过增加索引层来实现近似二分查找的效率。
- 应用场景：Redis的有序集合（Sorted Set）、LevelDB的MemTable，替代平衡树的一种简单高效方案。
布隆过滤器 (Bloom Filter)
- 介绍：一种概率型数据结构，用于快速判断一个元素绝对不在集合中或可能在其中。非常节省空间。
- 应用场景：缓存穿透防护、爬虫URL去重、分布式系统（如Cassandra）判断数据是否存在。
布谷鸟过滤器 (Cuckoo Filter)
- 介绍：布隆过滤器的改进版，支持删除操作，具有更高的查询性能和空间效率。
- 应用场景：需要支持删除的大规模集合成员判定场景。

二、树形结构 (Tree Structures)

树是层次化数据存储和高效搜索的基石。

A. 二叉搜索树 (BST) 及其变种

自平衡二叉搜索树 (AVL Tree)
- 介绍：通过旋转操作严格保持左右子树高度差不超过1，查询效率极高。
- 应用场景：适用于查询多、增删少的场景，如数据库索引的内存部分。
红黑树 (Red-Black Tree)
- 介绍：通过着色和旋转规则来保持大致平衡，增删改查的综合性能很好。
- 应用场景：std::map in C++, TreeMap in Java, epoll的内核实现，广泛用于需要高效有序性的场景。
伸展树 (Splay Tree)
- 介绍：通过“伸展”操作将最近访问的节点移动到根节点，利用“局部性原理”。
- 应用场景：缓存、垃圾回收算法。
替罪羊树 (Scapegoat Tree)
- 介绍：通过判断平衡因子，在插入时回溯找到“替罪羊”子树并进行重构以实现平衡。
- 应用场景：函数式编程中的有序数据结构。

B. 多路搜索树 (B-Tree家族) - 磁盘友好的巨人

B树 (B-Tree)
- 介绍：多路平衡搜索树，一个节点可以有多个键和多个子节点，显著减少磁盘I/O次数。
- 应用场景：数据库索引（如MySQL的InnoDB引擎）、文件系统（如NTFS, HFS+, Ext4）。
B+树 (B+ Tree)
- 介绍：B树的变种，所有数据都存储在叶子节点，且叶子节点形成有序链表。
- 应用场景：关系型数据库索引的标准实现，范围查询效率极高。
B树 (B Tree)
- 介绍：B+树的变种，通过非根节点和非叶子节点的键满时进行分裂优化，提高空间利用率。
- 应用场景：某些文件系统和数据库。
2-3树 / 2-3-4树
- 介绍：B树的特例（阶数较低），是理解B树和红黑树的重要基础。
- 应用场景：主要用于教学，某些内存中的有序数据结构实现。

C. 空间划分树 (Spatial Partitioning Trees)

四叉树 (Quadtree) (2D)
- 介绍：将2D空间递归地划分为四个象限。
- 应用场景：图像处理（压缩、稀疏存储）、碰撞检测、地图点搜索。
八叉树 (Octree) (3D)
- 介绍：四叉树在3D空间的扩展，划分为八个卦限。
- 应用场景：3D图形学（碰撞检测、视锥裁剪）、医学成像、粒子模拟。
k-d树 (k-dimensional Tree)
- 介绍：每个节点都对k维空间中的一个维度进行划分的二叉搜索树。
- 应用场景：最近邻搜索、范围搜索、多维键值检索。
R树 (R-Tree)
- 介绍：用于存储空间数据的多路平衡树，节点代表空间中的最小边界矩形（MBR）。
- 应用场景：地理信息系统（GIS），如地图查询“查找附近的所有餐馆”，数据库的空间扩展（PostGIS）。
R*树, R+树
- 介绍：R树的变种，通过不同的插入、分裂策略来优化重叠和性能。
- 应用场景：对R树性能要求更高的复杂空间查询。

D. 堆与优先队列 (Heaps & Priority Queues)

二项堆 (Binomial Heap)
- 介绍：由一组二项树组成的森林，支持高效合并。
- 应用场景：图算法（如Dijkstra）中优先队列的实现之一。
斐波那契堆 (Fibonacci Heap)
- 介绍：理论上的最优堆结构，摊还代价非常低，特别是对于decrease-key操作。
- 应用场景：理论价值高，实际因常数因子大而较少使用，但在某些图算法（如最小生成树）中有理论意义。
配对堆 (Pairing Heap)
- 介绍：一种简单高效的堆，实践性能往往很好。
- 应用场景：实际应用中常见的优先队列实现。
左倾堆 (Leftist Heap)
- 介绍：一种用于快速合并的堆结构。
- 应用场景：函数式编程、需要频繁合并堆的场景。

E. 树形结构的其他变种

字典树 (Trie / Prefix Tree)
- 介绍：专门用于处理字符串的树，节点的位置代表键（字符串的前缀）。
- 应用场景：输入法提示、搜索框自动补全、IP路由表最长前缀匹配。
后缀树 (Suffix Tree)
- 介绍：包含一个字符串所有后缀的压缩字典树，是字符串处理的强大工具。
- 应用场景：生物信息学（DNA序列匹配）、文本编辑器中的快速搜索、数据压缩。
线段树 (Segment Tree) / 区间树 (Interval Tree)
- 介绍：用于存储区间或线段，高效查询符合条件的区间。
- 应用场景：范围查询（最大值、最小值、求和）、计算机图形学、日历调度。
芬威克树/二叉索引树 (Fenwick Tree / Binary Indexed Tree)
- 介绍：一种巧妙设计用于计算前缀和的高效数据结构，代码简洁。
- 应用场景：频繁计算数组前缀和、动态数组区间求和（比线段树更简单高效）。
笛卡尔树 (Cartesian Tree)
- 介绍：由一组数据构建的二叉树，满足堆性质和二叉搜索树性质。
- 应用场景：解决范围最小查询（RMQ）问题、构建后缀树。
决策树 (Decision Tree)
- 介绍：机器学习中的模型，用于分类和回归，结构上是树形。
- 应用场景：数据挖掘、模式识别。
语法分析树 (Parse Tree) / 抽象语法树 (AST)
- 介绍：编译器中表示程序语法结构的树。
- 应用场景：编译器、解释器、代码静态分析。
默克尔树 (Merkle Tree) / 哈希树 (Hash Tree)
- 介绍：每个叶子节点的值都是数据块的哈希值，每个非叶子节点的值是它的子节点值的哈希值。
- 应用场景：区块链（比特币、以太坊）、分布式系统（Git, IPFS）的数据一致性和完整性验证。
VP树 (Vantage-Point Tree)
- 介绍：一种度量树，用于在度量空间中进行最近邻搜索。
- 应用场景：图像检索、音频匹配。

三、图结构 (Graph Structures)

图用于表示实体间的复杂关系。

邻接矩阵 (Adjacency Matrix)
- 介绍：使用二维数组表示图中顶点之间的边。
- 应用场景：稠密图、需要快速判断任意两点间是否存在边。
邻接表 (Adjacency List)
- 介绍：为每个顶点维护一个链表，存储与其相邻的顶点。
- 应用场景：存储稀疏图的主流方法，节省空间。
邻接多重表/边表 (Incidence List/Edge List)
- 介绍：显式地存储所有边的列表，或存储每个顶点连接到的边。
- 应用场景：需要频繁遍历所有边的图算法。
十字链表 (Orthogonal List)
- 介绍：针对有向图优化的邻接多重表，可以同时高效获取顶点的入边和出边。
- 应用场景：有向图的存储。
拓扑排序 (Topological Sort)
- 介绍：对有向无环图（DAG）的顶点进行线性排序，使得对任何边 (u, v)，u都排在v前面。
- 应用场景：任务调度、依赖解析（如Makefile, 软件包管理）、课程安排。

四、用于特定算法和领域的数据结构

并查集/不相交集合 (Union-Find / Disjoint-Set Union - DSU)
- 介绍：管理元素分组，支持高效的合并和查询操作。
- 应用场景：Kruskal最小生成树算法、连通分量计算、动态连通性问题。
循环冗余检查 (CRC) 表
- 介绍：预计算的查表法，用于快速计算CRC校验码。
- 应用场景：网络数据传输、存储设备的错误检测。
双缓冲 (Double Buffering)
- 介绍：使用两个缓冲区，一个用于后台计算，一个用于前台显示，然后交换。
- 应用场景：计算机图形学、游戏渲染，防止屏幕撕裂。
环形缓冲区的各种变种
- 介绍：如MPSC（多生产者单消费者）、SPMC（单生产者多消费者）等并发环形队列。
- 应用场景：高并发编程、无锁数据结构。
Zipper
- 介绍：函数式编程中的一种数据结构，用于在不可变数据中高效地“遍历和聚焦”。
- 应用场景：函数式语言中的树或列表的遍历和修改。
绳索 (Rope)
- 介绍：由多个字符串片段构建的二叉树，用于高效处理超长字符串的插入、删除和连接。
- 应用场景：文本编辑器（如Apache Xerces, TextMate 2）处理大型文档。
计数最小略图 (Count-Min Sketch)
- 介绍：一种概率数据结构，用于估算数据流的频率。
- 应用场景：大数据流分析、估算热门项目、网络流量监控。
分层计时轮 (Hierarchical Timing Wheel)
- 介绍：用于管理大量定时器的高效数据结构。
- 应用场景：网络框架（如Netty, Kafka）、操作系统内核中的定时器实现。
最大-最小堆 (Min-Max Heap)
- 介绍：同时支持高效获取最大和最小元素的堆。
- 应用场景：双端优先队列。
可合并堆 (Melable Heap)
- 介绍：支持高效合并操作的堆的统称（如斐波那契堆、二项堆、配对堆）。
- 应用场景：需要合并优先队列的算法。
范围树 (Range Tree)
- 介绍：用于多维范围查询的树，每个节点关联一个子树。
- 应用场景：多维数据库查询、计算几何。
BK树 (Burkhard-Keller Tree)
- 介绍：用于在度量空间中搜索相似项目的树结构。
- 应用场景：拼写检查、模糊搜索、DNA序列匹配。
图编码 (Graph Encoding)
- 介绍：如邻接矩阵的各种压缩表示（CSR, CSC），用于存储超大规模图。
- 应用场景：科学计算、社交网络分析。
日志结构合并树 (LSM-Tree - Log-Structured Merge-Tree)
- 介绍：核心思想是将随机写转换为顺序写，通过内存表和多个SSTable文件层次合并。
- 应用场景：现代NoSQL数据库的基石（LevelDB, RocksDB, Cassandra, HBase）。
布谷鸟哈希表 (Cuckoo Hashing)
- 介绍：使用两个哈希函数和两个表，冲突时“踢走”原有元素，直到找到空位或达到最大次数。
- 应用场景：提供最坏情况下的常数查询时间，用于高性能哈希表实现。
可扩展哈希 (Extendible Hashing)
- 介绍：一种动态哈希技术，通过目录和页面的分裂来适应数据增长。
- 应用场景：数据库文件组织、某些文件系统。
线性哈希 (Linear Hashing)
- 介绍：另一种动态哈希技术，无需目录，通过逐步分裂桶来实现扩展。
- 应用场景：数据库文件组织。
一致性哈希 (Consistent Hashing)
- 介绍：一种特殊的哈希技术，在节点增减时，只需重新映射一小部分数据。
- 应用场景：分布式缓存/存储系统的核心算法（如Memcached, Amazon Dynamo, Riak）。
跳表的各种变种
- 介绍：如概率跳表、锁定跳表等。
- 应用场景：并发环境下的有序数据结构。
** van Emde Boas 树**
- 介绍：一种用于整数密钥的特殊集合数据结构，支持所有操作在O(log log U)时间内完成（U是域大小）。
- 应用场景：算法竞赛、对性能要求极高的特殊领域。
Fusion Tree
- 介绍：一种理论上可以在O(log_w n)时间内完成查询的树（w是机器字长），利用了CPU的并行指令。
- 应用场景：理论计算机科学，处理极大整数集合。
** Judy Arrays**
- 介绍：一种非常节省内存的关联数组，使用压缩的256路树。
- 应用场景：内存极度受限的系统。

五、并发与并行数据结构 (Concurrent & Parallel Structures)

并发链表 (Concurrent Linked List)
- 介绍：使用锁或无锁编程技术实现线程安全的链表。
- 应用场景：多线程编程中的共享资源池。
并发哈希表 (Concurrent Hash Map)
- 介绍：线程安全的哈希表，如Java的ConcurrentHashMap，使用分段锁或CAS操作。
- 应用场景：高并发环境下的缓存、计数。
并发跳表 (Concurrent Skip List)
- 介绍：如Java的ConcurrentSkipListMap，使用无锁技术实现的有序并发字典。
- 应用场景：需要高并发有序访问的场景。
无锁队列 (Lock-Free Queue)
- 介绍：基于CAS操作实现的队列，完全避免锁，提供更好的扩展性。
- 应用场景：高性能生产者-消费者场景，如线程池任务队列。
无锁栈 (Lock-Free Stack)
- 介绍：基于CAS操作实现的栈。
- 应用场景：内存分配、回溯算法的并行化。
RCU (Read-Copy-Update)
- 介绍：一种同步机制，读者无锁，写者复制更新后替换指针，适用于读多写少。
- 应用场景：Linux内核数据结构（如路由表）、数据库。

六、持久化与函数式数据结构 (Persistent & Functional Structures)

持久化数据结构 (Persistent Data Structures)
- 介绍：保留所有历史版本的数据结构，修改操作会创建新版本而非改变旧版本。
- 应用场景：函数式编程、事务系统、时间旅行调试、文本编辑器的撤销/重做。
不可变数据结构 (Immutable Data Structures)
- 介绍：创建后不能被修改的数据结构，任何修改都会产生一个新的副本（通常共享部分结构）。
- 应用场景：函数式编程（Clojure, Haskell）、React状态管理、简化并发编程。
持久化链表 (Persistent List)
- 介绍：最简单的持久化结构，通过共享尾部来实现。
- 应用场景：函数式语言的基础（如Lisp的cons cell）。
持久化二叉搜索树 (Persistent BST)
- 介绍：通过路径复制来实现持久化。
- 应用场景：需要版本历史的有序字典。
持久化数组 (Persistent Vector)
- 介绍：使用高度平衡的树（如32路树）实现，支持高效随机访问和持久化。
- 应用场景：Clojure的核心数据结构之一。
持久化哈希映射 (Persistent Hash Map)
- 介绍：使用哈希数组映射尝试树（HAMT）实现。
- 应用场景：Clojure, Scala的不可变Map实现。

七、概率与近似数据结构 (Probabilistic & Approximate Structures)

HyperLogLog (HLL)
- 介绍：用于估算海量数据集中基数（唯一元素个数）的概率数据结构，极其节省空间。
- 应用场景：网站UV统计、数据库查询优化中的基数估算。
Count-Min Sketch (再次强调)
- 应用场景：频率估算。
Bloom Filter (再次强调)
- 应用场景：存在性检测。
t-Digest
- 介绍：用于计算流式数据近似分位数（如中位数、百分位数）的数据结构。
- 应用场景：监控系统（如Prometheus）、性能分析。
Top-K Sketch / Heavy Hitters
- 介绍：如Space-Saving算法，用于找出数据流中出现最频繁的K个元素。
- 应用场景：网络流量分析、热门话题挖掘。

八、硬件相关与优化结构 (Hardware-Aware & Optimized Structures)

B树针对CPU缓存线的优化
- 介绍：调整节点大小使其完全匹配CPU缓存线（如64字节），减少缓存失效。
- 应用场景：高性能数据库（LMDB）。
CSR/CSC矩阵存储格式
- 介绍：压缩稀疏行/列格式，用于高效存储和计算稀疏矩阵。
- 应用场景：科学计算、机器学习、图算法。
结构体数组 (Array of Structs - AoS)
- 介绍：将对象的属性打包在一个结构体中，然后用数组存储多个结构体。
- 应用场景：面向对象编程的常见方式。
数组结构体 (Struct of Arrays - SoA)
- 介绍：将所有对象的同一个属性存储在单独的数组中。
- 应用场景：数据导向设计（DOD），对SIMD指令和缓存预取友好，常用于游戏引擎、数值计算。
缓存敏感型B树 (Cache-Sensitive B-Tree - CSB+)
- 介绍：B树的变种，优化缓存性能。
- 应用场景：主存数据库。
位级并行数据结构
- 介绍：利用CPU的字长特性，一次操作处理多个比特位。
- 应用场景：位图算法、基因序列分析。

九、抽象数据类型 (ADT) 及其多种实现

以下是一些重要的抽象数据类型，它们可以由上述多种数据结构实现。

优先队列 (Priority Queue) ADT
- 实现：二叉堆、斐波那契堆、配对堆、平衡BST。
- 应用场景：任务调度、Dijkstra算法、Huffman编码。
符号表/字典/映射 (Map/Dictionary) ADT
- 实现：哈希表、红黑树、跳跃表、B树、BST。
- 应用场景：无处不在。
集合 (Set) ADT
- 实现：基于Map实现，或使用布隆过滤器（近似）。
- 应用场景：去重、集合运算。
多重集合 (Multiset/Bag) ADT
- 介绍：允许重复元素的集合。
- 实现：Map<T, Integer>、计数布隆过滤器。
- 应用场景：计数统计。
图 (Graph) ADT
- 实现：邻接矩阵、邻接表、边表。
- 应用场景：建模关系网络。
栈 (Stack) ADT
- 实现：数组、链表。
- 应用场景：函数调用、表达式求值、回溯。
队列 (Queue) ADT
- 实现：数组、链表、环形缓冲区。
- 应用场景：BFS、消息队列、缓冲。
双端队列 (Deque) ADT
- 实现：双向链表、动态数组、环形缓冲区。
- 应用场景：如前所述。
并查集 (Union-Find) ADT
- 实现：父指针树（带路径压缩和按秩合并）。
- 应用场景：如前所述。

十、更多特定领域与新兴结构

波利亚计数桶 (Pólya’s Counting Bucket)
- 介绍：用于组合数学计数的数据结构。
- 应用场景：数学、算法分析。
单调队列 (Monotonic Queue)
- 介绍：队列中的元素保持单调性（递增或递减）。
- 应用场景：滑动窗口最大值/最小值问题。
单调栈 (Monotonic Stack)
- 介绍：栈中的元素保持单调性。
- 应用场景：下一个更大元素（Next Greater Element）问题、柱状图最大矩形。
差分数组 (Difference Array)
- 介绍：用于快速对数组的某个区间进行增量操作。
- 应用场景：区间更新、批量操作。
二进制决策图 (BDD - Binary Decision Diagram)
* 介绍：一种用于表示布尔函数的压缩图结构。
* 应用场景：形式化验证、硬件电路设计、模型检测。