周围有一些数据结构非常有用，但大多数程序员都不知道。他们是哪些？
每个人都知道链表、二叉树和散列，但是例如跳过列表和布隆过滤器呢？我想知道更多不那么常见但值得了解的数据结构，因为它们依赖于伟大的想法并丰富了程序员的工具箱。
PS：我也对像跳舞链接这样巧妙地利用通用数据结构的属性的技术感兴趣。
编辑：请尝试包含指向更详细描述数据结构的页面的链接。另外，尝试添加一些关于为什么数据结构很酷的词（正如Jonas Kölker已经指出的那样）。此外，尝试为每个 answer 提供一个数据结构。这将允许更好的数据结构仅根据他们的投票浮动到顶部。
尝试，也称为前缀树或暴击位树，已经存在了 40 多年，但仍然相对不为人知。“ TRASH - A dynamic LC-trie and hash data structure ”中描述了一个非常酷的 Trie 用法，它结合了 trie 和哈希函数。
布隆过滤器：m位的位数组，最初全部设置为 0。
要添加一个项目，您可以通过k个哈希函数运行它，这些函数将为您提供数组中的k个索引，然后您将其设置为 1。
要检查一个项目是否在集合中，请计算k个索引并检查它们是否都设置为 1。
当然，这给出了一些误报的可能性（根据维基百科，它大约是 0.61^(m/n)，其中 n 是插入项目的数量）。假阴性是不可能的。
删除一个项目是不可能的，但您可以实现计数布隆过滤器，由整数数组和增量/减量表示。
Rope：这是一个允许廉价前置、子串、中间插入和附加的字符串。我真的只用过一次，但没有其他结构就足够了。常规的字符串和数组前置对于我们需要做的事情来说太昂贵了，而且扭转一切都是不可能的。
拉链- 修改结构以具有“光标”的自然概念的数据结构的衍生物 - 当前位置。这些非常有用，因为它们保证索引不会越界——例如在xmonad 窗口管理器中用于跟踪哪个窗口已聚焦。
令人惊讶的是，您可以通过将微积分技术应用于原始数据结构的类型来推导出它们！
这里有几个：
后缀尝试。适用于几乎所有类型的字符串搜索（http://en.wikipedia.org/wiki/Suffix_trie#Functionality）。另见后缀数组；它们不如后缀树快，但要小得多。
张开树（如上所述）。他们很酷的原因有三个：
堆排序的搜索树：您将一堆（键，优先级）对存储在树中，这样它是关于键的搜索树，并且相对于优先级是堆排序的。可以证明这样一棵树有一个独特的形状（而且它并不总是完全挤在左边）。使用随机优先级，它可以为您提供预期的 O(log n) 搜索时间 IIRC。
一个利基是具有 O(1) 邻居查询的无向平面图的邻接表。这与其说是一种数据结构，不如说是一种组织现有数据结构的特定方式。这样做的方法如下：每个平面图都有一个度数最多为 6 的节点。选择这样一个节点，将其邻居放入其邻居列表中，将其从图中删除，然后递归直到图为空。当给定一对 (u, v) 时，在 v 的邻居列表中查找 u，并在 u 的邻居列表中查找 v。两者的大小最多为 6，所以这是 O(1)。
通过上面的算法，如果 u 和 v 是邻居，你不会在 v 的列表中同时拥有 u 和在 u 的列表中的 v。如果您需要这个，只需将每个节点的缺失邻居添加到该节点的邻居列表中，但存储您需要查看多少邻居列表以进行快速查找。
我认为标准数据结构（即无锁队列、堆栈和列表）的无锁替代方案被忽视了。
它们变得越来越重要，因为并发性变得更高优先级，并且比使用互斥锁或锁来处理并发读/写更令人钦佩。
这里有一些链接
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [PDF链接]
http://www.boyet.com/Articles/LockfreeStack.html
Mike Acton 的（通常是挑衅性的）博客有一些关于无锁设计和方法的优秀文章
我认为Disjoint Set非常适合需要将一堆项目划分为不同的集合和查询成员资格的情况。Union 和 Find 操作的良好实现导致摊销成本实际上是恒定的（如果我正确回忆我的数据结构类，则与 Ackermnan 的函数相反）。
它们被用于一些已知最快的算法（渐近），用于解决许多与图相关的问题，例如最短路径问题。Dijkstra 算法使用标准二进制堆在 O(E log V) 时间内运行；使用斐波那契堆将其提高到 O(E + V log V)，这对于密集图来说是一个巨大的加速。但不幸的是，它们具有很高的常数因子，在实践中常常使它们不切实际。
任何有 3D 渲染经验的人都应该熟悉BSP 树。通常，这是通过构建 3D 场景以便在知道相机坐标和方位的情况下进行渲染的方法。
二元空间分割（BSP）是一种通过超平面递归地将空间细分为凸集的方法。这种细分通过称为 BSP 树的树数据结构产生场景的表示。
换句话说，它是将复杂形状的多边形分解为凸集或完全由非反射角（小于 180° 的角度）组成的较小多边形的方法。有关空间分区的更一般描述，请参阅空间分区。
最初，这种方法是在 3D 计算机图形学中提出的，以提高渲染效率。其他一些应用包括在 CAD 中使用形状（构造立体几何）执行几何操作、机器人和 3D 计算机游戏中的碰撞检测，以及涉及处理复杂空间场景的其他计算机应用。
霍夫曼树- 用于压缩。
看看Finger Trees，特别是如果您是前面提到的纯函数数据结构的粉丝。它们是持久序列的功能表示，支持在摊销的常数时间内访问末端，以及在较小部分的大小上按时间对数连接和拆分。
根据原始文章：
我们的功能 2-3 指树是 Okasaki (1998) 引入的通用设计技术的一个实例，称为隐式递归减速。我们已经注意到，这些树是他的隐式双端队列结构的扩展，用 2-3 个节点替换对，以提供有效连接和拆分所需的灵活性。
手指树可以用monoid参数化，使用不同的 monoid 会导致树的不同行为。这让手指树可以模拟其他数据结构。
圆形或环形缓冲区- 用于流式传输等。
我很惊讶没有人提到默克尔树（即哈希树）。
在许多情况下使用（P2P 程序、数字签名），当您只有部分文件可供您使用时，您想要验证整个文件的哈希值。
<zvrba> Van Emde-Boas 树
我认为了解它们为什么很酷会很有用。一般来说，“为什么”这个问题是最重要的；）
我的回答是，他们给你 O(log log n) 个带有 {1..n} 键的字典，与正在使用的键的数量无关。就像重复减半给你 O(log n) 一样，重复 sqrting 给你 O(log log n)，这就是 vEB 树中发生的情况。
哈希表的一个有趣变体称为Cuckoo Hashing。它使用多个散列函数而不是仅使用 1 个来处理散列冲突。通过从主散列指定的位置删除旧对象并将其移动到备用散列函数指定的位置来解决冲突。Cuckoo Hashing 允许更有效地使用内存空间，因为您可以仅使用 3 个哈希函数将负载因子提高到 91%，并且仍然具有良好的访问时间。
最小-最大堆是实现双端优先级队列的堆的变体。它通过对堆属性的简单更改来实现这一点：如果偶数（奇数）级别上的每个元素都小于（大于）所有子节点和孙子节点，则称树是最小最大排序的。级别从 1 开始编号。
http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg
我喜欢Cache Oblivious 数据结构。基本思想是在递归较小的块中布置树，以便许多不同大小的缓存将利用方便放入它们的块。这导致在从 RAM 中的 L1 缓存到从磁盘读取的大块数据的所有内容中有效地使用缓存，而无需知道任何这些缓存层大小的细节。
左倾红黑树。Robert Sedgewick 于 2008 年发布的一个显着简化的红黑树实现（大约需要实现的代码行数的一半）。如果您在思考红黑树的实现时遇到过麻烦，请阅读此变体。
与安德森树非常相似（如果不相同）。
工作窃取队列
用于在多个线程之间平均分配工作的无锁数据结构 在 C/C++ 中实现工作窃取队列？
Gerth Stølting Brodal 和 Chris Okasaki 的自举倾斜二项式堆：
尽管它们的名字很长，但它们提供了渐近优化的堆操作，即使在函数设置中也是如此。
O(1)大小，联合，插入，最小O(log n)删除最小值请注意，与数据结构教科书中通常介绍的更知名的堆（例如左派堆O(1)）不同，联合需要而不是时间。与Fibonacci heaps不同，这些渐近线是最坏的情况，而不是摊销，即使持续使用！O(log n)
它们是 Brodal 和 Okasaki 在 Brodal 提出具有相同渐近线的命令堆之后共同推导出的。
大多数（如果不是全部）都记录在 NIST算法和数据结构词典中
球树。只是因为他们让人们咯咯笑。
球树是一种对度量空间中的点进行索引的数据结构。 这是一篇关于构建它们的文章。 它们通常用于寻找一个点的最近邻居或加速 k-means。
不是真正的数据结构；更多的是一种优化动态分配数组的方法，但是 Emacs 中使用的间隙缓冲区有点酷。
芬威克树。它是一种数据结构，用于在两个给定的子索引 i 和 j 之间对向量中所有元素的总和进行计数。简单的解决方案，从一开始就预先计算总和，不允许更新项目（您必须做 O(n) 工作才能跟上）。
Fenwick Trees 允许您在 O(log n) 中更新和查询，它的工作原理非常酷且简单。Fenwick 的原始论文中对此进行了很好的解释，可在此处免费获得：
http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf
它的父亲，RQM 树也很酷：它允许你保存向量的两个索引之间的最小元素的信息，它也适用于 O(log n) 更新和查询。我喜欢先教授 RQM，然后再教授 Fenwick Tree。
Van Emde-Boas 树。我什至有它的 C++实现，最多 2^20 个整数。
它是特定领域的，但半边数据结构非常整洁。它提供了一种迭代多边形网格（面和边）的方法，这在计算机图形学和计算几何中非常有用。
替罪羊树。 普通二叉树的一个典型问题是它们变得不平衡（例如，当键以升序插入时。）
平衡二叉树（AKA AVL 树）在每次插入后都会浪费大量时间进行平衡。
红黑树保持平衡，但每个节点都需要额外的存储空间。
替罪羊树像红黑树一样保持平衡，但不需要任何额外的存储空间。他们通过在每次插入后分析树并进行细微调整来做到这一点。请参阅http://en.wikipedia.org/wiki/Scapegoat_tree。
展开的链表是链表的一种变体，它在每个节点中存储多个元素。它可以显着提高缓存性能，同时减少与存储列表元数据（如引用）相关的内存开销。它与B树有关。
record node {
node next // reference to next node in list
int numElements // number of elements in this node, up to maxElements
array elements // an array of numElements elements, with space allocated for maxElements elements
}
Hinze 和 Paterson的2-3 Finger Trees是一种出色的函数式数据结构瑞士军刀，具有出色的渐近性，适用于各种操作。虽然很复杂，但它们比 Persistent 列表的命令式结构要简单得多，通过在它们之前的 Kaplan 和 Tarjan 的递归减速进行连接。
它们作为可连接双端队列工作，可以O(1)访问任一端、O(log min(n,m))追加，并提供O(log min(n,length - n))索引，可以直接访问序列任何部分的单端前缀和。
Haskell、Coq、F#、Scala、Java、C、Clojure、C#和其他语言都有实现。
您可以使用它们来实现优先级搜索队列、区间映射、具有快速头部访问的绳索、映射、集合、可连接序列或几乎任何您可以将其表述为在快速可连接/可索引序列上收集单曲面结果的结构。
我还有一些幻灯片描述了它们的派生和使用。
XOR Linked List使用两个 XOR'd 指针来减少双向链表的存储要求。有点晦涩但很整洁！
配对堆是一种堆数据结构，实现比较简单，实际摊销性能优良。
我真的很喜欢间隔树。它们允许您获取一堆间隔（即开始/结束时间或其他时间）并查询哪些间隔包含给定时间，或者在给定时间段内哪些间隔是“活动的”。查询可以在 O(log n) 中完成，预处理是 O(n log n)。
飞溅表很棒。它们就像一个普通的哈希表，除了它们保证恒定时间查找并且可以处理 90% 的利用率而不会损失性能。它们是Cuckoo Hash的概括（也是一个很好的数据结构）。它们看起来确实是专利，但与大多数纯软件专利一样，我不会太担心。
二元决策图是我最喜欢的数据结构之一，或者实际上是归约二元决策图（ROBDD）。
例如，这类结构可用于：
请注意，许多问题可以表示为布尔表达式。例如，数独的解决方案可以表示为布尔表达式。并且为该布尔表达式构建 BDD 将立即产生解决方案。
区域四叉树
（引自维基百科）
区域四叉树通过将区域分解为四个相等的象限、子象限等来表示二维空间的划分，每个叶节点包含对应于特定子区域的数据。树中的每个节点要么恰好有四个孩子，要么没有孩子（叶节点）。
像这样的四叉树非常适合存储空间数据，例如纬度和经度或其他类型的坐标。
这是迄今为止我在大学时最喜欢的数据结构。给这个人编码并看到它工作非常酷。如果您正在寻找一个需要深思熟虑并且有点偏僻的项目，我强烈推荐它。无论如何，它比您通常在数据结构类中分配的标准 BST 衍生物有趣得多！
事实上，作为奖励，我在这里找到了课堂项目（来自弗吉尼亚理工大学）的讲座笔记（pdf 警告）。
我喜欢 treaps - 因为简单而有效的想法是在二叉搜索树上叠加具有随机优先级的堆结构以平衡它。
DAWG是一种特殊的 Trie，其中相似的子树被压缩为单亲。我扩展了修改后的 DAWG，并提出了一个漂亮的数据结构，称为 ASSDAWG（Anagram Search Sorted DAWG）。其工作方式是每当将字符串插入 DAWG 时，首先对其进行桶排序，然后再插入，并且叶节点保存一个额外的数字，指示如果我们从根到达该叶节点，哪些排列是有效的。这有两个很好的优点：
Fast Compact tries:
Judy arrays: Very fast and memory efficient ordered sparse dynamic arrays for bits, integers and strings. Judy arrays are faster and more memory efficient than any binary-search-tree.
HAT-trie: A Cache-conscious Trie-based Data Structure for Strings
我有时使用反转列表来存储范围，它们通常用于在正则表达式中存储字符类。参见例如http://www.ibm.com/developerworks/linux/library/l-cpinv.html
另一个不错的用例是加权随机决策。假设您有一个符号列表和相关概率，并且您想根据这些概率随机选择它们
a => 0.1 b => 0.5 c => 0.4
然后你对所有概率进行运行总和：
(0.1, 0.6, 1.0)
这是你的反转列表。您生成一个介于 0 和 1 之间的随机数，并在列表中找到下一个更高条目的索引。你可以通过二分搜索来做到这一点，因为它是排序的。获得索引后，您可以在原始列表中查找符号。
如果您有n符号，则每个随机选择的符号都有 O(n) 准备时间，然后是 O(log(n)) 访问时间 - 与权重分布无关。
倒排列表的一种变体使用负数来表示范围的端点，这样可以很容易地计算在某个点有多少范围重叠。有关示例，请参见http://www.perlmonks.org/index.pl?node_id=841368 。
Arne Andersson 树是红黑树的一种更简单的替代方案，其中只有正确的链接可以是红色的。这极大地简化了维护，同时保持了与红黑树相当的性能。原始论文为插入和删除提供了一个漂亮而简短的实现。
看看 Donald Knuth 提出的横向堆。
http://stanford-online.stanford.edu/seminars/knuth/071203-knuth-300.asx
BK-Trees 或 Burkhard-Keller Trees是一种基于树的数据结构，可用于快速查找字符串的近似匹配项。
Fenwick 树（或二叉索引树）是工具包的一个有价值的补充。如果您有一个计数器数组，并且需要在查询累积计数时不断更新它们（如在 PPM 压缩中），则 Fenwick 树将在 O(log n) 时间内完成所有操作，并且不需要额外的空间。另请参阅此topcoder 教程以获得很好的介绍。
Zobrist Hashing是一种散列函数，通常用于表示棋盘位置（如在国际象棋中），但肯定还有其他用途。关于它的一件好事是可以随着董事会的更新而逐步更新。
伸展树很酷。它们以一种将最常查询的元素移近根的方式重新排序。
您可以使用最小堆在恒定时间内找到最小元素，或者使用最大堆来找到最大元素。但是如果你想同时做这两个操作呢？您可以使用Min-Max在恒定时间内完成这两项操作。它通过使用最小最大排序来工作：在连续树级别之间的最小和最大堆比较之间交替。
远离所有这些图形结构，我只喜欢简单的Ring-Buffer。
如果实施得当，您可以大大减少内存占用，同时保持性能，有时甚至提高性能。
根据 Bloom Filter 的提及，可删除的 Bloom Filters (DlBF) 在某些方面优于基本的计数变体。见http://arxiv.org/abs/1005.0352
它是一种以更昂贵的插入为代价的高效搜索 B 树。
优先级双端队列比必须维护 2 个具有不同排序的独立优先级队列便宜。 http://www.alexandria.ucsb.edu/middleware/javadoc/edu/ucsb/adl/middleware/PriorityDeque.html http://cphstl.dk/Report/Priority-deque/cphstl-report-2001-14.pdf
跳过列表实际上非常棒： http ://en.wikipedia.org/wiki/Skip_list
使用 2 个堆栈实现的队列非常节省空间（与使用至少有 1 个额外指针/引用开销的链表相反）。
当队列很大时，这对我来说效果很好。如果我在一个指针上保存 8 个字节，这意味着有一百万个条目的队列可以节省大约 8MB 的 RAM。
我认为 Paolo Ferragina 和 Giovanni Manzini 的FM-index真的很酷。尤其是在生物信息学方面。它本质上是一个压缩的全文索引，它结合了后缀数组和参考文本的 burrows-wheeler 变换。可以在不解压整个索引的情况下搜索索引。
增量列表/增量队列在 cron 或事件模拟器等程序中用于计算下一个事件应该何时触发。 http://everything2.com/title/delta+list http://www.cs.iastate.edu/~cs554/lec_notes/delta_clock.pdf
正确的字符串数据结构。几乎每个程序员都满足于一种语言对结构的任何原生支持，这通常是低效的（特别是对于构建字符串，你需要一个单独的类或其他东西）。
最糟糕的情况是将字符串视为 C 中的字符数组，并依赖 NULL 字节来保证安全。
Burrows–Wheeler 变换（块排序压缩）
其压缩的基本算法。假设您要压缩文本文件上的行。你会说，如果你对这些行进行排序，你就会丢失信息。但 BWT 的工作原理是这样的——它通过对输入进行排序来大量减少熵，保持整数索引以恢复原始顺序。
PATRICIA - 检索以字母数字编码的信息的实用算法，DRMorrison (1968)。
PATRICIA 树与 Trie 相关。Tries 的问题在于，当键集稀疏时，即当实际键形成潜在键集的一小部分时，通常情况下，Trie 中的许多（大多数）内部节点只有一位子孙。这导致 Trie 具有很高的空间复杂度。
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/
一个角缝的数据结构。从总结：
角拼接是一种表示矩形二维对象的技术。它似乎特别适合用于 VLSI 布局的交互式编辑系统。该数据结构有两个重要特点：一是显式表示空白空间；其次，矩形区域的角落像拼布被子一样缝合在一起。这种组织导致搜索、创建、删除、拉伸和压缩的快速算法（线性时间或更好）。该算法是在一个简化的VLSI电路模型下提出的，并讨论了该结构的存储要求。测量表明，角拼接需要的存储空间大约是最简单的表示的三倍。
不相交集森林允许快速的成员查询和联合操作，并且最著名的是在 Kruskal 算法中用于最小生成树。
真正酷的是，这两个操作都摊销了与Ackermann Function的倒数成正比的运行时间，使其成为“最快的”非常量时间数据结构。
斗式旅
它们在 Apache 中被广泛使用。基本上它们是一个链表，在一个环中循环。我不确定它们是否在 Apache 和 Apache 模块之外使用，但它们作为一种很酷但鲜为人知的数据结构符合要求。桶是一些任意数据的容器，桶旅是桶的集合。这个想法是您希望能够在结构中的任何位置修改和插入数据。
假设您有一个存储桶旅，其中包含一个 html 文档，每个存储桶一个字符。您想要将所有<and>符号转换为<and>实体。桶旅允许您在遇到<或>符号时在旅中插入一些额外的桶，以适应实体所需的额外字符。因为铲斗大队是一个环形，你可以向后或向前插入。这比使用简单的缓冲区更容易（在 C 中）。
下面是一些关于斗式旅的参考：
我个人觉得稀疏矩阵数据结构非常有趣。 http://www.netlib.org/linalg/html_templates/node90.html
著名的 BLAS 库使用这些。当您处理包含 100,000 行和列的线性系统时，使用它们变得至关重要。其中一些也类似于计算机图形学中常见的紧凑网格（基本上就像一个桶排序的网格）。 http://www.cs.kuleuven.be/~ares/publications/LD08CFRGRT/LD08CFRGRT.pdf
同样就计算机图形学而言，MAC 网格有些有趣，但这只是因为它们很聪明。 http://www.seas.upenn.edu/~cis665/projects/Liquation_665_Report.pdf
二项式堆有很多有趣的属性，其中最有用的是合并。
我认为循环排序是一种非常简洁的排序算法。
这是一种用于最小化写入总数的排序算法。当您处理闪存的寿命与写入量成正比的闪存时，这特别有用。这是Wikipedia 文章，但我建议转到第一个链接。（漂亮的视觉效果！）
环境跟踪递归结构。
编译器使用递归但不像树的结构。内部范围有一个指向封闭范围的指针，因此嵌套是由内向外的。验证变量是否在范围内是从内部范围到封闭范围的递归调用。
public class Env
{
HashMap<String, Object> map;
Env outer;
Env()
{
outer = null;
map = new HashMap();
}
Env(Env o)
{
outer = o;
map = new HashMap();
}
void put(String key, Object value)
{
map.put(key, value);
}
Object get(String key)
{
if (map.containsKey(key))
{
return map.get(key);
}
if (outer != null)
{
return outer.get(key);
}
return null;
}
Env push()
{
return new Env(this);
}
Env pop()
{
return outer;
}
}
我不确定这个结构是否有名字。我称之为由内而外的清单。
我以前在WPL Trees上运气不错。最小化分支的加权路径长度的树变体。权重由节点访问决定，使经常访问的节点迁移到更靠近根的位置。不知道它们与伸展树相比如何，因为我从未使用过它们。
其他人已经提出了 Burkhard-Keller-Trees，但我想我可能会再次提及它们以插入我自己的实现。:)
http://well-adjusted.de/mspace.py/index.html
周围有更快的实现（请参阅 ActiveState 的 Python 配方或其他语言的实现），但我认为/希望我的代码有助于理解这些数据结构。
顺便说一句，BK 和 VP 树的用途远不止搜索相似的字符串。只要您有一个满足几个条件（正性、对称性、三角不等式）的距离函数，您就可以对任意对象进行相似性搜索。
对计算几何算法很有用。
那里有一个聪明的数据结构，它使用数组来保存元素的数据，但是数组在链接列表/数组中链接在一起。
这样做的好处是元素的迭代非常快（比纯链表方法快），并且在内存中移动带有元素的数组和/或（取消）分配的成本最低。（因为这个数据结构对于模拟的东西很有用）。
我从这里知道：
http://software.intel.com/en-us/blogs/2010/03/26/linked-list-verses-array/
“......并且一个额外的数组被分配并链接到粒子数组的单元列表中。这在某些方面类似于 TBB 如何实现其并发容器。”（它是关于链接列表与数组的性能)
自适应细分网格的精美简单方法。拆分和合并操作只是几行代码。
当我读到一些与 RMQ 和 LCA 相关的算法时，我偶然发现了另一种数据结构笛卡尔树。在笛卡尔树中，两个节点之间的最低共同祖先是它们之间的最小节点。将 RMQ 问题转换为 LCA 很有用。
这些是我能想到的。维基百科上还有更多关于数据结构的内容