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

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

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

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

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

当前回答

展开的链接列表是链接列表的变体，它在每个节点中存储多个元素。它可以显著提高缓存性能，同时减少与存储列表元数据（如引用）相关的内存开销。它与B树有关。

record node {
    node next       // reference to next node in list
    int numElements // number of elements in this node, up to maxElements
    array elements  // an array of numElements elements, with space allocated for maxElements elements
}

2011-01-15 12:12:08

其他回答

Kd-Trees是实时光线跟踪中使用的空间数据结构，它的缺点是需要裁剪与不同空间交叉的三角形。一般来说，BVH更快，因为它们更轻。MX-CIF四叉树，通过将规则四叉树与四叉树边缘的二叉树组合，存储边界框而不是任意点集。HAMT，由于所涉及的常数，访问时间通常超过O（1）个哈希图的分层哈希图。反向索引，在搜索引擎界非常有名，因为它用于快速检索与不同搜索词相关的文档。

大多数（如果不是全部）记录在NIST算法和数据结构词典中

2009-02-01 13:29:08

尝试，也称为前缀树或临界位树，已经存在了40多年，但仍然相对未知。在“TRASH-一个动态LC trie和哈希数据结构”中描述了一个非常酷的trys用法，它将trie与哈希函数结合在一起。

2009-02-01 11:24:12

远离所有这些图形结构，我只喜欢简单的环形缓冲区。

如果实施得当，您可以在保持性能的同时，甚至可以提高性能，从而大大减少内存占用。

2009-05-13 14:36:49

Gerth Stølting Brodal和Chris Okasaki的自助倾斜二项式堆：

尽管它们的名字很长，但即使在函数设置中，它们也提供了渐近最优的堆操作。

O（1）尺寸，接头，插入件，最小值O（log n）删除最小值

注意，union需要O（1）而不是O（log n）时间，这与数据结构教科书中通常包含的更为知名的堆（如左派堆）不同。与斐波那契堆不同，这些渐近线是最坏的情况，而不是摊销，即使持续使用！

Haskell中有多种实现。