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

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

PS:我还对舞蹈链接等技术感兴趣,这些技术巧妙地利用了通用数据结构的财产。

编辑:请尝试包含更详细描述数据结构的页面链接。此外,试着补充几句关于数据结构为什么很酷的话(正如乔纳斯·Kölker已经指出的那样)。此外,尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。


当前回答

根据Bloom Filter提到的,可删除Bloom Filter(DlBF)在某些方面优于基本计数变体。看见http://arxiv.org/abs/1005.0352

其他回答

一个鲜为人知但相当漂亮的数据结构是Fenwick树(有时也称为二进制索引树或BIT)。它存储累积和并支持O(log(n))运算。虽然累积和听起来不太令人兴奋,但它可以用于解决许多需要排序/log(n)数据结构的问题。

IMO的主要卖点是易于实施。在解决算法问题时非常有用,否则将涉及编码红黑/avl树。

增强的哈希算法非常有趣。线性哈希很简单,因为它允许一次在哈希表中拆分一个“桶”,而不是重新哈希整个表。这对于分布式缓存特别有用。然而,对于大多数简单的拆分策略,您最终会快速连续地拆分所有存储桶,并且表的负载系数波动非常严重。

我认为螺旋哈希法也很好。与线性哈希一样,一次拆分一个存储桶,存储桶中的记录只有不到一半被放入同一个新存储桶中。它非常干净和快速。然而,如果每个“桶”都由具有类似规格的机器托管,则效率可能很低。为了充分利用硬件,您需要混合使用功能较弱和功能更强的机器。

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

二进制空间分区(BSP)是一种递归细分a的方法通过超平面将空间划分为凸集。该细分产生通过方法表示场景树数据结构的BSP树。换句话说,这是一种方法形状复杂的破碎多边形转化为凸集,或更小多边形完全由非反射角(小于180°). 更一般的描述空间分区,请参见空间分区。最初,提出了这种方法在3D计算机图形方面渲染效率。其他一些应用程序包括执行具有形状的几何操作(构造实体几何),机器人和3D中的碰撞检测计算机游戏和其他计算机涉及处理的应用程序复杂的空间场景。

我认为标准数据结构的无锁替代方案,即无锁队列、堆栈和列表被忽略了。随着并发性成为更高的优先级,它们变得越来越重要,并且比使用互斥或锁来处理并发读/写更令人钦佩。

以下是一些链接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)的博客中有一些关于无锁设计和方法的优秀文章

看看唐纳德·克努思(Donald Knuth)展示的侧面堆。

http://stanford-online.stanford.edu/seminars/knuth/071203-knuth-300.asx