周围有一些数据结构非常有用,但大多数程序员都不知道 . 他们是哪一个?
每个人都知道链接列表,二进制树和哈希,但是例如Skip lists和Bloom filters . 我想知道更多不常见的数据结构,但值得了解,因为它们依赖于伟大的想法并丰富了程序员的工具箱 .
PS:我也对像Dancing links这样的技术感兴趣,这些技术巧妙地使用了通用数据结构的属性 .
EDIT :请尝试更详细地包含指向描述数据结构的页面的链接 . 另外,尝试添加几个关于数据结构为什么很酷的词(如Jonas Kölker已指出) . 另外,尝试提供 one data-structure per answer . 这将允许更好的数据结构根据他们的投票单独浮动到顶部 .
30 回答
Circular or ring buffer - 用于流式传输等 .
我很惊讶没有人提到Merkle树(即Hash Trees) .
在许多情况下(P2P程序,数字签名)使用,当您只有部分文件可用时,您要验证整个文件的哈希值 .
我认为知道为什么它们很酷很有用 . 一般来说,问题"why"是最重要的问题;)
我的答案是他们给你带有{1..n}键的O(log log n)字典,与使用的密钥数量无关 . 就像重复的减半给你O(log n)一样,重复的sqrting给你O(log log n),这就是vEB树中发生的事情 .
splay trees怎么样?
此外,克里斯冈崎的purely functional data structures浮现在脑海中 .
Bloom filter:m位的位数组,最初都设置为0 .
要添加一个项目,您可以通过k哈希函数运行它,该函数将为您提供数组中的k个索引,然后将其设置为1 .
要检查项目是否在集合中,请计算k个索引并检查它们是否都设置为1 .
当然,这给出了一些假阳性的概率(根据维基百科它约为0.61 ^(m / n),其中n是插入项目的数量) . 假阴性是不可能的 .
删除项目是不可能的,但您可以实现计数布隆过滤器,由整数数组和递增/递减表示 .
Tries,也称为前缀树或crit-bit trees,已经存在了40多年,但仍然相对不为人知 . “TRASH - A dynamic LC-trie and hash data structure”中描述了一种非常酷的try尝试,它将trie与散列函数结合起来 .
Rope:它真的只使用过一次,但没有其他结构就足够了 . 常规字符串和数组前置对于我们需要做的事情来说太昂贵了,并且逆转翻转是不可能的 .
Skip lists非常整洁 .
它们可以用作 balancer 树的替代品(使用probalistic balancer 而不是严格执行 balancer ) . 它们易于实施,并且比红黑树更快 . 我认为他们应该在每个优秀的程序员工具箱中 .
如果你想深入介绍跳过列表,请参阅麻省理工学院的算法导论课程 .
此外,here是一个Java applet,可以直观地演示Skip Lists .
Spatial Indices,特别是R-trees和KD-trees,有效地存储空间数据 . 它们适用于地理 Map 坐标数据和VLSI布局布线算法,有时也适用于最近邻搜索 .
Bit Arrays紧凑地存储单个位并允许快速位操作 .
Zippers - 数据结构的衍生物,修改结构以具有'cursor'的自然概念 - 当前位置 . 这些非常有用,因为它们可以保证指标不会受到限制 - 例如,使用,例如在xmonad window manager中跟踪哪个窗口已经聚焦 .
令人惊讶的是,您可以通过applying techniques from calculus将它们派生为原始数据结构的类型!
以下是一些:
后缀尝试 . 几乎适用于所有类型的字符串搜索(http://en.wikipedia.org/wiki/Suffix_trie#Functionality) . 另见后缀数组;它们不如后缀树那么快,但是要小得多 .
Splay树(如上所述) . 他们很酷的原因有三个:
它们很小:你只需要像在任何二叉树中那样使用左右指针(不需要存储节点颜色或大小信息)
它们(相对)非常容易实现
它们为整个主机"measurement criteria"提供了最佳的摊销复杂性(log n查找时间是每个人都知道的) . 见http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
堆有序的搜索树:在树中存储一堆(key,prio)对,这样它就是一个关于键的搜索树,并且根据优先级进行堆排序 . 可以证明这样的树具有独特的形状(并且它并不总是完全包装在左上方) . 通过随机优先级,它可以为您提供预期的O(log n)搜索时间IIRC .
利基是具有O(1)个邻居查询的无向平面图的邻接列表 . 这不是一种数据结构,而是组织现有数据结构的特定方式 . 以下是您的操作方法:每个平面图都有一个度数最多的节点6.选择这样一个节点,将其邻居放在其邻居列表中,将其从图中删除,然后递归直到图表为空 . 当给出一对(u,v)时,在v的邻居列表中查找u,在u的邻居列表中查找v . 两者的大小最多为6,因此这是O(1) .
通过上面的算法,如果u和v是邻居,你将不会同时拥有v列表中的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's(经常是挑逗性的)博客有一些关于无锁设计和方法的优秀文章
我认为Disjoint Set非常适合需要将一堆项目分成不同的集合和查询成员资格的情况 . Union和Find操作的良好实现导致有效的常量摊销成本(如果我正确地回忆起我的数据结构类,则与Ackermnan函数相反) .
Fibonacci heaps
它们被用于一些最快的已知算法(渐近)中,用于许多与图形相关的问题,例如最短路径问题 . Dijkstra算法在标准二进制堆的O(E log V)时间内运行;使用Fibonacci堆可以将其提高到O(E V log V),这对于密集图来说是一个巨大的加速 . 不幸的是,它们具有很高的常数因子,通常使它们在实践中不切实际 .
任何具有3D渲染经验的人都应该熟悉BSP trees . 通常,这是通过将3D场景结构化为可管理以便知道相机坐标和方位的方法 .
Huffman trees - 用于压缩 .
看看Finger Trees,特别是如果你是previously mentioned纯功能数据结构的粉丝 . 它们是持久性序列的功能表示,支持以摊销的恒定时间访问末端,并且在较小的片段的大小中以时间对数进行连接和分割 .
根据the original article:
手指树可以使用monoid进行参数化,并且使用不同的幺半群将导致树的不同行为 . 这使得Finger Trees可以模拟其他数据结构 .
哈希表的一个有趣变体叫做Cuckoo Hashing . 它使用多个哈希函数而不是1来处理哈希冲突 . 通过从主哈希指定的位置删除旧对象并将其移动到备用哈希函数指定的位置来解决冲突 . Cuckoo Hashing允许更有效地使用内存空间,因为只需3个哈希函数就可以将加载因子提高到91%,并且仍然具有良好的访问时间 .
min-max heap是heap的变体,它实现了双端优先级队列 . 它通过对堆属性的简单更改来实现这一点:如果偶数(奇数)级别上的每个元素都小于(大于)所有子级和大级子级,则称树为最小 - 最大级别 . 级别已编号从1开始 .
http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg
我喜欢Cache Oblivious datastructures . 基本思想是以递归较小的块布置树,以便许多不同大小的缓存将利用方便地适合它们的块 . 这样可以有效地使用缓存,从RAM中的L1缓存到从磁盘读取的大块数据,而无需了解任何这些缓存层的大小细节 .
Left Leaning Red-Black Trees . Robert Sedgewick于2008年发布了一个非常简化的红黑树实现(大约一半的代码行实现) . 如果您在实施红黑树时遇到麻烦,请阅读此变体 .
与安德森树非常相似(如果不相同) .
工作窃取队列
用于在多个线程之间分配工作的无锁数据结构Implementation of a work stealing queue in C/C++?
Bootstrapped skew-binomial heaps由GerthStøltingBroodal和Chris Okasaki撰写:
尽管名称很长,但它们提供了渐近最优的堆操作,即使在函数设置中也是如此 .
O(1)
size, union ,insert,minimumO(log n)
deleteMin请注意,与数据结构教科书中通常涵盖的更为人熟知的堆(例如leftist heaps)不同,union需要
O(1)
而不是O(log n)
. 与Fibonacci heaps不同,这些渐近是最坏情况,而不是摊销,即使持续使用!Haskell中有multiple implementations .
在布罗达尔提出具有相同渐近线的imperative heap之后,他们是由布罗达尔和冈崎共同衍生出来的 .
Kd-Trees,在实时光线追踪中使用的空间数据结构(以及其他)具有以下缺点:需要剪切与不同空间交叉的三角形 . 通常BVH更快,因为它们更轻便 .
MX-CIF Quadtrees,通过在四边形边缘组合常规四叉树和二叉树来存储边界框而不是任意点集 .
HAMT,由于涉及的常量,访问时间通常超过O(1)哈希映射的分层哈希映射 .
Inverted Index,在搜索引擎圈中非常有名,因为它用于快速检索与不同搜索词相关联的文档 .
大多数(如果不是全部)这些都记录在NIST上Dictionary of Algorithms and Data Structures
球树 . 只是因为他们让人们傻笑 .
球树是一种索引度量空间中的点的数据结构 . Here's an article on building them.它们通常用于寻找一个点的最近邻居或加速k均值 .
不是真正的数据结构;更多的是优化动态分配数组的方法,但Emacs中使用的gap buffers很酷 .
芬威克树 . 它是一个数据结构,用于在两个给定的子索引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树 .
Van Emde-Boas trees . 我甚至有一个C implementation,最多2 ^ 20个整数 .
Nested sets很适合在关系数据库中表示树并在它们上运行查询 . 例如,ActiveRecord(Ruby on Rails的默认ORM)带有一个非常简单的nested set plugin,这使得使用树很简单 .
它非常适合特定领域,但是half-edge data structure非常整洁 . 它提供了一种迭代多边形网格(面和边)的方法,这在计算机图形和计算几何中非常有用 .