什么是较less的已知但有用的数据结构？
有一些数据结构是非常有用的，但大多数程序员都不知道。 他们是哪一个？
每个人都知道链表，二叉树和散列，但跳过列表和布隆filter例如。 我想知道更多不太常见的数据结构，但值得了解，因为它们依赖于伟大的想法并丰富了程序员的工具箱。
PS：我也喜欢跳舞链接这样的技巧，这些技巧巧妙地使用了一个通用数据结构的属性。
编辑 ：请尝试包括更详细的描述数据结构的页面的链接 。 另外，为了说明为什么数据结构很酷，尝试添加几个字（正如JonasKölker指出的那样）。 另外，尝试为每个答案提供一个数据结构 。 这将允许更好的数据结构根据他们的选票浮动到顶部。
尝试 ，也被称为前缀树或暴击位树 ，已经存在了40多年，但还是比较陌生。 “ TRASH – dynamicLC-trie和哈希数据结构 ”中描述了一个非常酷的尝试，它将一个trie与一个哈希函数结合在一起。
布隆filter ： m位的位数组，最初全部设置为0。
要添加一个项目，你可以通过k散列函数来运行它，它会给你数组中的k个索引，然后你设置为1。
要检查一个项目是否在集合中，计算k个索引并检查它们是否都设置为1。
当然，这给出了一些错误肯定的概率（根据维基百科，它大约是0.61 ^（m / n），其中n是插入项目的数量）。 假阴性是不可能的。
删除一个项目是不可能的，但你可以实现计数布隆filter ，由整数和增量/减量表示。
绳 ：这是一个string，允许便宜的prepends，子string，中间插入和附加。 我真的只用过一次，但没有其他的结构是足够的。 对于我们需要做的事情来说，常规的string和数组的前置代码太昂贵了，而颠倒过来是不可能的。
跳过列表非常整齐。
维基百科
跳过列表是基于多个并行sorting链接列表的概率数据结构，其效率可与二叉search树（大多数操作的平均时间顺序logging）相比较。
它们可以作为平衡树木的替代品（使用平衡性而不是严格的平衡）。 它们很容易实施，而且比红黑树更快。 我认为他们应该是每个好的程序员的工具。
如果您想深入介绍跳过列表，可以链接到麻省理工学院“algorithm入门”讲义。
此外， 这里是一个Java小程序可视化展示跳过列表。
空间索引 ，特别是R树和KD树 ，有效地存储空间数据。 它们适用于地理地图坐标数据和VLSI布局布线algorithm，有时也用于最近邻search。
位arrays紧凑地存储各个位，并允许快速位操作。
拉链 – 数据结构的衍生物，修改结构以具有“游标”的自然概念 – 当前位置。 这些function是非常有用的，因为它们可以保证指示不会超出限制 – 例如在xmonad窗口pipe理器中，可以跟踪哪个窗口已经关注。
令人惊讶的是，您可以通过将微积分技术应用于原始数据结构的types来派生它们！
这里有几个：
-
后缀尝试。 几乎适用于所有types的stringsearch（ http://en.wikipedia.org/wiki/Suffix_trie#Functionality ）。 另见后缀数组; 它们并不像后缀树那么快，但却小了很多。
-
张开树木（如上所述）。 他们很酷的原因有三个：
- 它们很小：您只需要像在任何二叉树中一样使用左和右指针（不需要存储节点颜色或大小信息）
- 它们（相对）很容易实现
- 它们为大量的“测量标准”提供了最佳的分期复杂性（日志查询时间是每个人都知道的）。 请参阅http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
-
堆sortingsearch树：您将一堆（键，prio）对存储在一棵树中，这样它就是一个关于键的search树，并且相对于优先级来说是堆sorting的。 人们可以certificate这样一棵树具有独特的形状（它并不总是全部包装在一起）。 随机优先级，它给你预期O（log n）的search时间，IIRC。
-
一个小生境是邻接列表的无向平面图与O（1）邻居查询。 这不是一个数据结构，而是组织现有数据结构的一种特殊方式。 这是你怎么做的：每个平面图都有一个节点，最多有6个节点。select这样一个节点，把它的邻居放到它的邻居列表中，从图中移除它，然后recursion到图表为空。 当给定一对（u，v）时，在v的邻居列表中查找u，在u的邻居列表中查找v。 两者的大小最多为6，所以这是O（1）。
通过上面的algorithm，如果u和v是邻居，你不会在列表中列出v和列表中的列表。 如果你需要这个，只需要将每个节点的缺失邻居添加到该节点的邻居列表中，但是需要存储多less邻居列表才能快速查找。
我认为标准数据结构（如无锁队列，堆栈和列表）的无锁select被忽略。
它们越来越相关，因为并发性成为更高的优先级，并且比使用Mutex或锁来处理并行读/写更令人钦佩。
这里有一些链接
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
迈克·阿克顿 （经常挑衅）博客上有一些关于无锁devise和方法的优秀文章
我认为不相交集是非常漂亮的案件，当你需要将一堆项目分成不同的集合和查询成员资格。 联盟和查找操作的良好实施会导致实际上不变的成本分摊（如果我正确地记得我的数据结构类，则是Ackermnan函数的反函数）。
斐波那契堆
它们被用于一些最快的已知algorithm（渐近地），用于很多与graphics相关的问题，例如最短path问题。 Dijkstraalgorithm运行在标准二进制堆的O（E log V）时间内; 使用斐波那契堆提高到O（E + V log V），这是密集图的巨大加速。 不幸的是，他们有一个很高的恒定因素，经常使他们在实践中不切实际。
任何有3D渲染经验的人都应该熟悉BSP树 。 一般来说，通过构造一个3D场景来进行渲染是可以pipe理的，以便了解相机的坐标和方位。
二进制空间分割（BSP）是一种用超平面recursion地将空间细分为凸集的方法。 这个细分通过被称为BSP树的树数据结构产生场景的表示。
换句话说，这是一种将复杂形状的多边形分解为凸集或者完全由非reflectionangular（小于180°的angular）组成的更小的多边形的方法。 有关空间分区的更一般的描述，请参阅空间分区。
最初，这种方法是在3D计算机graphics中提出的，以提高渲染效率。 其他一些应用包括用CAD中的形状（build设性立体几何），机器人和3D计算机游戏中的碰撞检测以及涉及处理复杂空间场景的其他计算机应用来执行几何操作。
霍夫曼树 – 用于压缩。
看看Finger Trees ，特别是如果你是前面提到的纯粹function性数据结构的粉丝。 它们是持久化序列的function表示，支持以分期固定的时间访问末端，在时间上连接和分割对数大小的小块。
按照原文 ：
我们的function性2-3指树是由Okasaki（1998）提出的一种通用devise技术的实例，称为隐式recursion减速 。 我们已经注意到，这些树是他的隐式双层结构的扩展，用2-3个节点来替代对，以提供高效连接和分裂所需的灵活性。
手指树可以用monoid参数化，并且使用不同的monoid会导致树的不同行为。 这可以让Finger Trees模拟其他数据结构。
循环或环形缓冲区 – 用于stream式传输等等。
我很惊讶没有人提到梅克尔树（即哈希树 ）。
在许多情况下（P2P程序，数字签名），当您只有部分文件可用时，您要validation整个文件的散列。
Van Emde-Boas树
我想知道为什么他们很酷很有用。 一般来说，“为什么”是最重要的问题;）
我的答案是，他们给你带有{1..n}个键的O（log log n）个字典，而不pipe有多less个键在使用中。 就像重复减半给你O（log n），重复的sqrting给你O（log log n），这是在vEB树中发生的。
如何张开树木 ？
另外，Chris Okasaki的纯粹的function数据结构也浮现在脑海。
哈希表的一个有趣的变体称为布谷鸟哈希 。 它使用多个散列函数而不是1个来处理散列冲突。 通过从主散列指定的位置移除旧对象并将其移动到由交替散列函数指定的位置来解决冲突。 杜鹃散列技术可以更有效地利用内存空间，因为只需3个散列函数即可将载入因子提高到91％，并且仍然具有良好的访问时间。
min-max堆是实现双端优先级队列的堆的变体。 它通过对堆属性的简单改变来实现：如果偶数（奇数）级别上的每个元素比所有儿童和大孩子less（大于），则称该树为最小 – 最大有序。 级别从1开始编号。
http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg
我喜欢Cache不重要的数据结构 。 基本思想是以recursion较小的块来布局树，以便许多不同大小的caching将利用方便地适合它们的块。 这导致从RAM中的L1caching到从磁盘读取的大块数据的高速caching的有效使用，而不需要知道任何这些caching层的大小的细节。
左倾斜的红黑树 。 Robert Sedgewick在2008年发表了一个显着简化的红黑树实现（实现代码行的一半）。 如果你在实施红黑树时遇到困难，请阅读这个变种。
与Andersson树非常相似（如果不相同）。
工作窃取队列
在multithreading间平均分配工作的无锁数据结构在C / C ++中实现工作窃取队列？
由GerthStøltingBrodal和Chris Okasaki提出的自助式歪斜二项式堆 ：
尽pipe名字很长，但即使在函数设置中，它们也能提供渐近最佳的堆操作。
-
O(1)大小， 联合 ，插入，最小 -
O(log n)deleteMin
请注意，与数据结构教科书（如左边的堆）中通常涵盖的更为人熟知的堆不同，联合需要O(1)而不是O(log n)时间。 与斐波那契堆不同，那些渐近是最坏的情况，而不是分期付款，即使持续使用！
Haskell中有多个 实现 。
他们是由Brodal和Okasaki共同衍生出来的，Brodal提出了一个与渐近相同的命令堆 。
- 在实时光线追踪中使用的Kd-Trees （空间数据结构）（其中包括），缺点是需要剪切交叉相交于不同空间的三angular形。 一般BVH的速度更快，因为它们更轻量。
- MX-CIF四叉树 ，通过在四边形边上结合常规四叉树和二叉树，存储边界框而不是任意点集。
- HAMT ，层次哈希映射的访问时间通常超过O（1）散列映射由于涉及的常量。
- 倒排索引在search引擎的圈子里非常有名，因为它用于快速检索与不同search条件相关的文档。
大部分（如果不是全部的话）都logging在NIST algorithm和数据结构字典中
球树。 只因为他们让人咯咯笑。
球树是一个数据结构，用于索引度量空间中的点。 这里有一篇关于构build它们的文章。 它们通常用于寻找最近的邻居或加速K均值。
不是一个真正的数据结构; 更多的是优化dynamic分配数组的方法，但Emacs中使用的间隙缓冲区有点酷。
Fenwick树。 这是一个数据结构，以保持在一个向量中的所有元素的总和，在两个给定的子索引i和j之间。 这个简单的解决scheme，预先计算开始以来的总和不允许更新一个项目（你必须做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树。
范埃姆博阿斯树 。 我甚至有一个C ++ 实现它，最多2 ^ 20个整数。
嵌套集很适合在关系数据库中表示树并在其上运行查询。 例如，ActiveRecord（Ruby on Rails默认的ORM）带有一个非常简单的嵌套设置插件 ，这使得树木工作变得微不足道。
这是相当域特定的，但半边数据结构是相当整洁。 它提供了一种迭代多边形网格（面和边）的方法，这在计算机graphics和计算几何中非常有用。
;){kind=link}