100種高級數據結構 (速查表)

一、基礎結構的擴展與組合 (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)
* 介紹：一種用于表示布爾函數的壓縮圖結構。
* 應用場景：形式化驗證、硬件電路設計、模型檢測。