周围有一些数据结构非常有用，但大多数程序员都不知道。他们是哪一个？
每个人都知道链表、二叉树和散列，但比如Skip列表和Bloom过滤器。我想知道更多不太常见但值得了解的数据结构，因为它们依赖于伟大的想法，丰富了程序员的工具箱。
PS：我还对舞蹈链接等技术感兴趣，这些技术巧妙地利用了通用数据结构的财产。
编辑：请尝试包含更详细描述数据结构的页面链接。此外，试着补充几句关于数据结构为什么很酷的话（正如乔纳斯·Kölker已经指出的那样）。此外，尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。
当前回答
增强的哈希算法非常有趣。线性哈希很简单，因为它允许一次在哈希表中拆分一个“桶”，而不是重新哈希整个表。这对于分布式缓存特别有用。然而，对于大多数简单的拆分策略，您最终会快速连续地拆分所有存储桶，并且表的负载系数波动非常严重。
我认为螺旋哈希法也很好。与线性哈希一样，一次拆分一个存储桶，存储桶中的记录只有不到一半被放入同一个新存储桶中。它非常干净和快速。然而，如果每个“桶”都由具有类似规格的机器托管，则效率可能很低。为了充分利用硬件，您需要混合使用功能较弱和功能更强的机器。
其他回答
我有时使用反转列表来存储范围，它们通常用于在正则表达式中存储字符类。例如，请参见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例如。
Hinze和Paterson的2-3手指树是一种功能强大的数据结构瑞士军刀，具有很好的渐近线，适用于各种操作。虽然复杂，但它们比之前的Kaplan和Tarjan通过递归减速实现的持久列表的命令式结构简单得多。
它们作为一个可链接的deque，O（1）访问任意一端，O（log-min（n，m））追加，并提供O（log-main（n），length-n））索引，直接访问序列的任何部分上的单形前缀和。
实现存在于Haskell、Coq、F#、Scala、Java、C、Clojure、C#和其他语言中。
您可以使用它们来实现优先级搜索队列、区间映射、具有快速头部访问的绳索、映射、集合、可链接序列或几乎任何结构，您可以将其表述为在快速可链接/可索引序列上收集单形结果。
我还有一些幻灯片描述了它们的派生和使用。
XOR链表使用两个XOR'd指针来减少双链表的存储需求。有点晦涩但整洁！
铲斗大队
它们在Apache中被广泛使用。基本上，它们是一个在环中围绕自身循环的链接列表。我不确定它们是否在Apache和Apache模块之外使用，但它们适合作为一种很酷但鲜为人知的数据结构。桶是一些任意数据的容器，桶大队是桶的集合。其思想是，您希望能够在结构中的任何点修改和插入数据。
假设您有一个bucket旅，其中包含一个html文档，每个bucket包含一个字符。您希望将所有<和>符号转换为<；并且>；实体。当您遇到<或>符号时，bucket旅允许您在旅中插入一些额外的bucket，以适应实体所需的额外字符。因为铲斗大队在一个环中，您可以向后或向前插入。这比使用简单的缓冲区要容易得多（在C语言中）。
关于铲斗大队的一些参考信息如下：
Apache Bucket旅参考
Buckets和Brigades简介
BK树或Burkhard Keller树是一种基于树的数据结构，可用于快速查找字符串的近似匹配项。
