StackOverflow：鲜为人知但有用的数据结构

周围有一些数据结构非常有用，但大多数程序员都不知道。他们是哪几个？

每个人都知道链表、二叉树和散列，但是例如跳过列表和Bloom过滤器呢？我想知道更多不那么常见但值得了解的数据结构，因为它们依赖于伟大的想法，并丰富了程序员的工具箱。

PS：我对舞蹈链接这样的技术也很感兴趣，这些技术巧妙地利用了公共数据结构的属性。

编辑：请尝试包含更详细描述数据结构的页面的链接。此外，尝试添加几个词来说明为什么数据结构很酷(正如Jonas Kölker已经指出的那样)。此外，请尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅基于它们的投票而浮动到顶部。

尝试，也称为前缀树或临界位树，已经存在了40多年，但仍然相对鲜为人知。"；trash-A dynamic LC-trie和散列数据结构"；中描述了一种非常酷的尝试用法，它将trie与散列函数相结合。

突发尝试也是一个有趣的变体，您只使用字符串的前缀作为节点，否则将字符串列表存储在节点中。 -托尔斯滕·马雷克(Torsten Marek)。

根据我的经验，考虑到指针通常比字符更长，尝试的代价高得令人痛苦，这是一件令人遗憾的事情。它们只适用于某些数据集。 -约翰·乔(Joe)。

因为如果没有人提到jQuery，那么任何问题，无论是什么主题，都是完整的……。John Resig，jQuery的创建者，有一个有趣的数据结构系列文章，其中他研究了各种TRIE实现，其中包括：ejohn.org/blog/revised-javascript-dictionary-search -奥斯卡·奥斯特加德(Oskar Austegard)

要添加一个项目，您可以通过k个散列函数运行它，这些散列函数将给您数组中的k个索引，然后将其设置为1。

要检查项目是否在集合中，请计算k个指数，并检查它们是否都设置为1。

当然，这也给出了一些误报的可能性(根据维基百科的数据，大约是0.61^(m/n)，其中n是插入的项目数)。假-阴性是不可能的。

移除一个项目是不可能的，但是您可以实现计数Bloom Filter，用整数数组和增量/减量来表示。

您忘了提到它们在字典中的用法：)您可以将一个完整的字典压缩到大约512k的Bloom过滤器中，就像没有值的哈希表一样 --克里斯·S(Chris S)。

Google在Bigtable的实现中引用了Bloom Filters的使用。 --布莱恩·詹福卡罗(Brian Gianforcaro)。

@FreshCode它实际上允许您以较低的成本测试集合中是否缺少元素，因为您可能会得到假阳性，但绝不会得到假阴性 -汤姆·萨维奇(Tom Savage)。

@FreshCode正如@Tom Savage所说，它在检查底片时更有用。例如，您可以将其用作快速且较小的拼写检查器(就内存使用量而言)。将所有单词添加到其中，然后尝试查找用户输入的单词。如果你得到的是否定的，那就意味着拼错了。然后，您可以运行一些更昂贵的检查来查找最接近的匹配项并提供更正。 --Lacop(空洞无章)

@abhin4v：当大多数请求可能返回答案"；no"；(如这里的情况)时，通常会使用Bloom过滤器，这意味着可以使用较慢的精确测试来检查少数"；是"；答案。这仍然大大缩短了平均查询响应时间。我不知道Chrome的安全浏览功能是否能做到这一点，但那只是我的猜测。 -dj_Random_hacker。

绳索：它是一种允许廉价的前缀、子串、中间插入和附加的字符串。我真的只用过一次，但没有其他结构可以满足我的需要。常规的字符串和数组前缀对于我们需要做的事情来说太昂贵了，而且颠倒一切都是不可能的。

我想过把这样的东西用在我自己身上。很高兴知道它已经在其他地方实施了。 -Kibbee。

在不知道它叫什么的情况下，我最近为JAVA写了一些非常类似的东西-性能一直很出色：code.google.com/p/mikeralib/source/browse/trunk/Mikera/src/…。-米凯拉(Sigmikera)。

维基百科跳过列表是一种概率数据结构，基于多个并行的排序链表，其效率可与二叉搜索树相媲美(对于大多数操作，排序日志n平均时间)。

它们可以用作平衡树的替代方案(使用概率平衡，而不是严格执行平衡)。它们很容易实现，而且比红黑树更快。我认为它们应该出现在每个优秀的程序员工具箱中。

如果你想深入了解跳表，这里有一个链接，链接到麻省理工学院关于它们的算法入门讲座的视频。

+1 Qt使用跳过列表而不是RB树作为其排序的映射&；集。是的，它们很漂亮(至少是在命令式语言中)。 -迈克尔·埃克斯特兰德(Michael Ekstrand)

当我需要一个好的数据结构，并且我不能保证数据的顺序，并且我想要一个比其他平衡数据结构更简单的实现时，跳跃列表可能是我最喜欢使用的数据结构。真是一件好事。 -西里诺。

有趣的附注：如果您向您的跳跃列表中添加了足够的级别，您基本上会得到一个B树。 -里亚德·卡拉(Riyad Kalla)。

空间索引，特别是R-树和KD-树，能够高效地存储空间数据。它们适用于地理地图坐标数据和VLSI位置和路线算法，有时还适用于最近邻搜索。

空间索引对于涉及长程力(如重力)的N体模拟也很有用。 -作者贾斯汀·皮尔(Justin Peel)。

拉链(Zippers)-数据结构的派生，将结构修改为具有光标的自然概念-当前位置。这些非常有用，因为它们保证索引不会越界--例如，在xmonad窗口管理器中用来跟踪哪个窗口被聚焦。

令人惊讶的是，您可以通过将微积分中的技术应用于原始数据结构的类型来派生它们！

这只在函数式编程中有用(在命令式语言中，您只需保留一个指针或索引)。另外，我还是不明白拉链到底是怎么工作的。 --斯特凡·莫诺夫(Stefan Monov)。

@Stefan，重点是你现在不需要保留单独的索引或指针。 -唐·斯图尔特(Don Stewart)

后缀尝试。适用于几乎所有类型的字符串搜索(http://en.wikipedia.org/wiki/Suffix_trie#Functionality).。另请参阅后缀数组；它们不如后缀树快，但要小得多。

它们很小：您只需要左指针和右指针，就像在任何二叉树中一样(不需要存储节点颜色或大小信息)。

它们为一系列度量标准(每个人都知道log n查找时间)提供了最佳的摊销复杂性。请参阅http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems。

按堆排序的搜索树：您在树中存储一串(键，优先级)对，这样它就是相对于键的搜索树，并且按照优先级按堆排序。人们可以证明，这样的树有一个独特的形状(而且它并不总是被完全打包在一起，向左)。对于随机优先级，它给出了预期的O(Logn)搜索时间IIRC。

一个小生境是具有O(1)个邻接查询的无向平面图的邻接表。与其说这是一种数据结构，不如说是组织现有数据结构的一种特殊方式。你可以这样做：每个平面图都有一个度不超过6的节点。选择一个这样的节点，把它的邻居放在它的邻居列表中，把它从图中删除，然后递归，直到图为空。当给定一对(u，v)时，在v'；的邻居列表中查找u，在u'；的邻居列表中查找v。这两个函数的大小都不超过6，所以这是O(1)。

根据上述算法，如果u和v是邻居，则v的列表中不会同时包含u和v。如果需要，只需将每个节点缺少的邻居添加到该节点的邻居列表中，但要存储您需要查找多少邻居列表才能快速查找。

堆排序搜索树称为树。其中一个技巧是更改节点的优先级，将其推到树的底部，这样更容易删除。 --纸马。

堆排序搜索树称为树。--在我听说的定义中，IIRC，树是具有随机优先级的堆排序搜索树。您可以根据应用程序选择其他优先级... --乔纳斯·科尔克(Jonas Kölker)

后缀trie几乎但不完全与更酷的后缀树相同，后者的边缘有字符串，而不是单个字母，并且可以在线性时间内构建(！)。此外，尽管后缀数组的速度渐近较慢，但实际上对于许多任务而言，后缀数组通常比后缀树快得多，因为后缀数组的大小更小，指针间接性更少。喜欢O(1)平面图查找BTW！ -dj_Random_hacker。

@j_Random_Hacker：后缀数组不会渐近变慢。下面是构建线性后缀数组的大约50行代码：cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf -爱德华·KMETT(Edward KMETT)。

@Edward Kmett：事实上，我读过那篇论文，它在后缀数组构造方面取得了相当大的突破。(虽然我们已经知道通过后缀树进行线性时间构造是可能的，但这是第一个不可否认的实用算法。)。但是，除非还构建了LCA表，否则在后缀数组上，构造外的一些操作仍然会逐渐变慢。这也可以在O(N)中实现，但是这样做会失去纯后缀数组的大小和局部性优势。 -dj_Random_hacker。

我认为标准数据结构的无锁替代方案(即无锁队列、堆栈和列表)被忽视了。随着并发性成为更高的优先级，它们变得越来越相关，并且比使用Mutex或锁来处理并发读/写要好得多。

在当今多核、高度并行、可扩展性上瘾的世界里，无锁替代方案非常重要：-) -西里诺。

我认为当您需要将一堆项目划分为不同的集合并查询成员身份时，不相交集合非常有用。UNION和FIND操作的良好实现会产生有效恒定的摊销成本(如果我没有记错数据结构类，则与Ackermnan的函数相反)。

这也被称为联合查找数据结构。当我在算法课上第一次了解到这种聪明的数据结构时，我感到非常敬畏…… --BlueRaja-Danny Pflughoeft。

我为我的地下城发电机使用了一套不相交的装置，以确保所有房间都可以通过通道到达：) -更高的黄金比率

它们被用在一些已知的最快算法中(渐近地)来解决许多与图相关的问题，例如最短路径问题。Dijkstra'；的算法使用标准的二进制堆运行在O(E Log V)时间内；使用斐波纳契堆将其改进为O(E+V log V)，这对于密集图来说是一个巨大的加速。然而，不幸的是，它们有一个很高的恒定因素，经常使它们在实践中不切实际。

如你所说的高恒定因素，据一位不得不这样做的朋友说，很难很好地实施。虽然不是很酷，但也许还是值得了解一下。 -3p4bl0。

这里的这些人使它们与其他堆类型相比更具竞争力：cphstl.dk/Presentation/SEA2010/SEA-10.pdf有一种称为配对堆的相关数据结构，它更容易实现，并且提供了相当好的实际性能。然而，理论分析是部分开放的。 --约翰·曼努埃尔。

根据我使用斐波纳契堆的经验，我发现内存分配的昂贵操作使其效率低于由数组作为后端的简单二进制堆。 -JUTTACY。

任何有3D渲染经验的人都应该熟悉BSP树。一般来说，这是一种方法，通过构造一个3D场景，以便在知道相机坐标和方位的情况下进行渲染。

二元空间划分(BSP)是一种用超平面递归地将空间细分为凸集的方法。该细分通过称为BSP树的树数据结构产生场景的表示。

换句话说，它是一种将形状复杂的多边形分解为凸集或完全由无反射角度(小于180°的角度)组成的较小多边形的方法。有关空间分区的更一般说明，请参见空间分区。

这种方法最初是在3D计算机图形学中提出的，目的是提高渲染效率。一些其他应用包括在CAD中对形状执行几何操作(构造性实体几何)，在机器人和3D计算机游戏中进行碰撞检测，以及涉及处理复杂空间场景的其他计算机应用。

虽然这很有趣，但这不是算法导论的一种吗，这里是一个贪婪算法的例子类型的话题吗？ -牧羊人。

看一下指状树，特别是如果您是前面提到的纯函数数据结构的粉丝的话。它们是持久序列的函数表示，支持在分期恒定时间内访问末端，并且在较小片段的大小中以时间对数连接和拆分。

我们的功能性2-3指树是Okasaki(1998)介绍的一种称为隐式递归减速的通用设计方法的一个实例。我们已经注意到，这些树是他的隐式双队列结构的扩展，用2-3个节点替换对，以提供有效的级联和拆分所需的灵活性。

指状树可以用么半群参数化，使用不同的么半群将导致树的不同行为。这使指状树可以模拟其他数据结构。

看一下这个重复的答案，它非常值得一读！ --弗朗索瓦·G(Francois G)。

此外，令人作呕的是，不知何故设法获得了专利(至少在用于视频时是这样)。IP.com/Patent/USRE36801 -大卫·艾森(David Eison)。

基于阅读链接，我认为数据结构本身并不是专利，而是一些基于它的发明。我同意这绝对是一个很少使用的数据结构。 --地心引力。

在许多情况下(P2P程序、数字签名)使用，当您只有部分文件可用时，您想要验证整个文件的哈希。

我想知道为什么它们很酷是很有用的。通常，为什么要问的问题是最重要的。)。

我的答案是，他们给您提供具有{1..n}个键的O(Log Log N)个字典，与正在使用的键的数量无关。就像重复减半得到O(Logn)一样，重复sqrting得到O(Logn)，这就是在VEB树中发生的事情。

从理论上讲，它们是不错的。然而，在实践中，要从他们身上获得有竞争力的表现是相当困难的。据我所知，这篇论文让它们可以很好地工作到32位密钥(citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.7403))，但这种方法不会扩展到超过34-35位左右，而且还没有实现。 --约翰·曼努埃尔。

它们很酷的另一个原因是，它们是许多缓存无关算法的关键构建块。 -爱德华·KMETT(Edward KMETT)。

哈希表的一个有趣变体称为布谷鸟散列。它使用多个散列函数而不是只使用1个散列函数来处理散列冲突。冲突的解决方法是从主散列指定的位置删除旧对象，并将其移动到备用散列函数指定的位置。布谷鸟散列允许更有效地使用内存空间，因为您只需使用3个散列函数就可以将负载率提高到91%，并且仍然具有良好的访问时间。

最小-最大堆是实现双端优先级队列的堆的变体。它通过简单地更改heap属性来实现这一点：如果偶(奇)级上的每个元素都小于(大于)所有子级和子级，则称树是最小-最大排序的。级别从1开始编号。

我喜欢缓存不经意的数据结构。其基本思想是在递归较小的块中布局树，以便许多不同大小的缓存将利用适合它们的块。这导致高效地使用从RAM中的L1缓存到从磁盘读取的大块数据的所有内容的缓存，而无需知道任何缓存层的具体大小。

该链接的有趣抄写："；关键是van Emde Boas布局，以1977年由Peter van Emde Boas"构思的van Emde Boas树数据结构命名； -谢尔盖·塞吉奥尔

左倾的红黑相间的树。Robert Sedgewick在2008年发布的一个显著简化的红黑树实现(大约需要实现一半的代码行)。如果您曾经在理解红黑树的实现时遇到过困难，请阅读这个变体。

多线程工作均衡分配的无锁数据结构C/C++中工作窃取队列的实现。

尽管它们的名称很长，但它们提供了渐近最优的堆操作，即使在函数设置中也是如此。

请注意，UNION需要O(1)而不是O(Logn)时间，这与数据结构教科书中通常介绍的更知名的堆不同，比如左倾堆。与斐波那契堆不同的是，这些渐近是最坏的情况，而不是摊销，即使持续使用！

它们是在布罗达尔提出具有相同渐近性的命令堆之后，由布罗达尔和冈崎共同推导出来的。

KD-Trees是实时光线跟踪中使用的(其中包括)空间数据结构，其缺点是需要对与不同空间相交的三角形进行裁剪。一般来说，BVH&39；的速度更快，因为它们更轻。

MX-CIF四叉树通过将规则四叉树与四叉树边缘的二叉树相结合来存储边界框而不是任意点集。

HAMT，由于涉及的常量，访问时间通常超过O(1)个散列映射的分层散列映射。

倒排索引，在搜索引擎界非常有名，因为它用于快速检索与不同搜索词相关联的文档。

其中的大部分(如果不是全部)都记录在NIST算法和数据结构字典中。

球树是对公制空间中的点进行索引的数据结构。这里有一篇关于建造它们的文章。它们通常用于查找到某一点的最近邻居或加速k-Means。

这些树也通常被称为“有利位置树”或“VP树”。En.wikipedia.org/wiki/vp-tree -爱德华·KMETT(Edward KMETT)。

不是真正的数据结构；更多的是一种优化动态分配数组的方式，但是Emacs中使用的间隙缓冲区是一种很酷的方式。

对于任何感兴趣的人，这也正是支持Swing文本组件的文档(例如，PlainDocument)模型的实现方式；在1.2之前，我认为文档模型是直数组，这导致大型文档的插入性能非常糟糕；一旦它们转移到Gap Buffers，一切又都正常了。 -里亚德·卡拉(Riyad Kalla)。

芬威克树。它是一种数据结构，用来计算向量中两个给定子索引i和j之间的所有元素的总和。平凡的解决方案是，从一开始就预先计算总和，不允许更新项目(你必须做O(N)次工作才能跟上)。

Fenwick树允许您在O(Logn)内更新和查询，并且它的工作方式非常酷和简单。芬威克的原创论文对此进行了很好的解释，可以在这里免费获得：

它的父亲，RQM树也是。

.