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

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

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

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


当前回答

Zobrist Hashing是一个哈希函数,通常用于表示棋盘位置(如国际象棋),但肯定还有其他用途。它的一个优点是它可以随着电路板的更新而逐步更新。

其他回答

斐波那契堆

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

Bloom过滤器:m位的位数组,最初全部设置为0。

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

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

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

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

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

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

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

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

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