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

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

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

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


当前回答

工作窃取队列

无锁数据结构,用于在多个线程之间平均分配工作C/C++中工作窃取队列的实现?

其他回答

Van Emde Boas树

我想知道它们为什么很酷会很有用。一般来说,“为什么”这个问题是最重要的;)

我的答案是,他们给你O(log-logn)字典,其中包含{1..n}个键,而与使用的键的数量无关。就像重复减半得到O(log n)一样,重复平方得到O(log-log n),这就是vEB树中发生的情况。

XOR链表使用两个XOR'd指针来减少双链表的存储需求。有点晦涩但整洁!

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

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

角落缝合的数据结构。根据总结:

拐角缝合是一种用于表示矩形二维对象。看起来特别适合VLSI交互式编辑系统布局。数据结构有两个重要特征:第一,空白明确表示;第二,矩形区域被缝合在他们的角落像一个拼缝被子。此组织快速算法的结果(线性时间或更好),创建、删除、拉伸和压实。算法如下以简化模型VLSI电路和存储器结构要求如下讨论。测量结果表明拐角缝合要求大约三倍尽可能简单的存储空间代表。

哈希表的一个有趣的变体叫做布谷鸟哈希。为了处理哈希冲突,它使用多个哈希函数而不是1。通过从主哈希指定的位置删除旧对象,并将其移动到备用哈希函数指定的位置,可以解决冲突。Cuckoo Hashing允许更有效地使用内存空间,因为您只需要3个哈希函数就可以将负载因子提高91%,而且访问时间也很长。