什么是鲜为人知但有用的数据结构?

周围有一些确实有用的数据结构,但大多数程序员都不知道。他们是哪一个?

每个人都知道链表,二叉树和哈希,但是例如跳过列表Bloom 过滤器呢 。我想了解更多不是很常见的数据结构,但是值得一读,因为它们依赖于出色的构想并丰富了程序员的工具箱。

PS:我对诸如跳舞链接之类的技术也很感兴趣,这些技术巧妙地利用了通用数据结构的属性。

编辑 :请尝试包含指向更详细描述数据结构的页面的链接 。另外,尝试添加几个关于数据结构为何如此酷的词(如JonasKölker 所指出的)。另外,尝试为每个答案提供一种数据结构 。这将使更好的数据结构仅凭其投票就可以浮动到顶部。

答案

尝试树(也称为前缀树或临界位树 )已经存在 40 多年了,但仍然相对未知。在 “ TRASH - 动态 LC-trie 和哈希数据结构 ” 中介绍了尝试的一种非常酷的用法,它结合了 trie 和哈希函数。

布隆过滤器m位的位数组,最初都设置为 0。

要添加项目,请通过k 个哈希函数运行该项目,该函数将为您提供数组中的k 个索引,然后将其设置为 1。

要检查某项是否在集合中,请计算k 个索引并检查它们是否都设置为 1。

当然,这给出了一些假阳性的可能性(根据 Wikipedia,大约为 0.61 ^(m / n),其中 n 是插入项的数量)。假阴性是不可能的。

删除项目是不可能的,但是您可以实现计数布隆过滤器 (由整数数组和增量 / 减量表示)。

Rope :这是一个允许便宜的前缀,子字符串,中间插入和追加的字符串。我实际上只用过一次,但是没有其他结构可以满足要求。常规的字符串和数组前置对于我们需要做的事情来说太昂贵了,而反转一切都不是问题。

跳过列表非常简洁。

维基百科
跳过列表是一种概率数据结构,它基于多个并行的,已排序的链表,其效率可与二进制搜索树相比(大多数操作的顺序日志为平均时间)。

它们可以用作平衡树的替代方法(使用概率平衡而不是严格执行平衡)。它们比一棵红黑树更容易实现并且速度更快。我认为他们应该成为每个优秀程序员的工具。

如果您想深入了解跳过列表,请访问 MIT 的算法入门讲座视频链接

另外, 是一个 Java 小程序,以可视方式演示了跳过列表。

空间索引 ,尤其是R 树KD 树 ,可以有效地存储空间数据。它们适用于地理地图坐标数据和 VLSI 放置和路线算法,有时还可以用于最近邻居搜索。

位阵列紧凑地存储各个位,并允许快速位操作。

拉链 - 数据结构的派生词,将其修改为具有自然的 “光标” 概念(当前位置)。这些功能非常有用,因为它们可以确保索引不会超出范围 - 例如在xmonad 窗口管理器中使用,以跟踪哪个窗口聚焦了。

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

这里有一些:

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

  • 八叉树(如上所述)。他们很酷的原因有三点:

    • 它们很小:您只需像在任何二叉树中一样需要左右指针(无需存储节点颜色或大小信息)
    • 它们(相对)非常容易实现
    • 它们为整个 “测量标准”(登录 n 查找时间是每个人都知道的)提供了最佳的摊销复杂性。看到 http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
  • 堆排序的搜索树:您在树中存储了一堆(密钥,优先级)对,这样一来,对于密钥而言,这是一棵搜索树;对于优先级而言,这就是一堆堆排序。可以显示出这样一棵树具有独特的形状(并且并不总是完全包装在左上方)。具有随机优先级,它为您提供了预期的 O(log n)搜索时间 IIRC。

  • 一个利基市场是具有 O(1)邻居查询的无向平面图的邻接表。这不是数据结构,而是组织现有数据结构的特定方式。操作方法如下:每个平面图都有一个度数最多为 6 的节点。选择一个这样的节点,将其邻居放置在其邻居列表中,将其从图中删除,然后递归直到图为空。给定一对(u,v)后,在 v 的邻居列表中查找 u,并在 u 的邻居列表中查找 v。两者的大小最大为 6,因此这是 O(1)。

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

我认为标准数据结构的无锁替代方案(即无锁队列,堆栈和列表)被忽略了很多。
随着并发成为更高的优先级,并且与使用 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

迈克 · 阿克顿Mike Acton )的博客(通常是挑衅性的)上有一些关于无锁设计和方法的优秀文章。

对于需要将一堆项目划分为不同的集合和查询成员身份的情况,我认为Disjoint Set非常漂亮。联合和查找操作的良好实施会导致摊销成本实际上是恒定的(如果我正确地回忆起我的数据结构类,则为 Ackermnan 函数的逆函数)。

斐波那契堆

在许多已知的最快算法中(渐近地)将它们用于许多与图相关的问题,例如最短路径问题。 Dijkstra 的算法使用标准二进制堆以 O(E log V)的时间运行;使用斐波那契堆将其改进为 O(E + V log V),这对于密集图是极大的加速。但是,不幸的是,它们具有较高的恒定因子,通常使它们在实践中不切实际。