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

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

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

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

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

当前回答

Van Emde Boas树。我甚至有一个C++实现，最多支持2^20个整数。

2009-02-01 13:06:37

其他回答

我有时使用反转列表来存储范围，它们通常用于在正则表达式中存储字符类。例如，请参见http://www.ibm.com/developerworks/linux/library/l-cpinv.html

另一个很好的用例是加权随机决策。假设你有一个符号和相关概率的列表，你想根据这些概率随机选择它们

   a => 0.1
   b => 0.5
   c => 0.4

然后，你对所有概率进行一次连续求和：

  (0.1, 0.6, 1.0)

这是你的反转列表。生成一个介于0和1之间的随机数，并查找列表中下一个较高条目的索引。你可以用二进制搜索来实现，因为它是排序的。一旦获得了索引，就可以在原始列表中查找符号。

如果有n个符号，则每个随机选择的符号都有O（n）个准备时间，然后是O（log（n））个访问时间，与权重分布无关。

反转列表的一种变体使用负数来指示范围的端点，这使得计算某一点上有多少范围重叠变得容易。看见http://www.perlmonks.org/index.pl?node_id=841368例如。

2010-07-23 08:03:25

铲斗大队

它们在Apache中被广泛使用。基本上，它们是一个在环中围绕自身循环的链接列表。我不确定它们是否在Apache和Apache模块之外使用，但它们适合作为一种很酷但鲜为人知的数据结构。桶是一些任意数据的容器，桶大队是桶的集合。其思想是，您希望能够在结构中的任何点修改和插入数据。

假设您有一个bucket旅，其中包含一个html文档，每个bucket包含一个字符。您希望将所有<和>符号转换为&lt；并且&gt；实体。当您遇到<或>符号时，bucket旅允许您在旅中插入一些额外的bucket，以适应实体所需的额外字符。因为铲斗大队在一个环中，您可以向后或向前插入。这比使用简单的缓冲区要容易得多（在C语言中）。

关于铲斗大队的一些参考信息如下：

Apache Bucket旅参考

Buckets和Brigades简介

2010-07-22 18:16:52

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

2011-04-17 02:06:38

使用2个堆栈实现的队列非常节省空间（与使用至少有1个额外指针/引用开销的链接列表不同）。

如何使用两个堆栈实现队列？

当排队人数很大时，这对我来说效果很好。如果我在一个指针上节省了8个字节，这意味着拥有百万条目的队列节省了大约8MB的RAM。

2011-03-27 05:35:59

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

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