周围有一些数据结构非常有用，但大多数程序员都不知道。他们是哪一个？
每个人都知道链表、二叉树和散列，但比如Skip列表和Bloom过滤器。我想知道更多不太常见但值得了解的数据结构，因为它们依赖于伟大的想法，丰富了程序员的工具箱。
PS：我还对舞蹈链接等技术感兴趣，这些技术巧妙地利用了通用数据结构的财产。
编辑：请尝试包含更详细描述数据结构的页面链接。此外，试着补充几句关于数据结构为什么很酷的话（正如乔纳斯·Kölker已经指出的那样）。此外，尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。
当前回答
我喜欢缓存不可见的数据结构。其基本思想是以递归更小的块来布局树，以便许多不同大小的缓存可以利用适合它们的块。这导致了从RAM中的L1缓存到从磁盘读取的大块数据的所有缓存的高效使用，而无需了解任何缓存层的大小细节。
其他回答
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#和其他语言中。
您可以使用它们来实现优先级搜索队列、区间映射、具有快速头部访问的绳索、映射、集合、可链接序列或几乎任何结构，您可以将其表述为在快速可链接/可索引序列上收集单形结果。
我还有一些幻灯片描述了它们的派生和使用。
环境跟踪递归结构。
编译器使用递归但不像树的结构。内部作用域有一个指向封闭作用域的指针，因此嵌套是由内向外的。验证变量是否在范围内是从内部范围到封闭范围的递归调用。
public class Env
{
HashMap<String, Object> map;
Env outer;
Env()
{
outer = null;
map = new HashMap();
}
Env(Env o)
{
outer = o;
map = new HashMap();
}
void put(String key, Object value)
{
map.put(key, value);
}
Object get(String key)
{
if (map.containsKey(key))
{
return map.get(key);
}
if (outer != null)
{
return outer.get(key);
}
return null;
}
Env push()
{
return new Env(this);
}
Env pop()
{
return outer;
}
}
我不确定这个结构是否有名字。我称之为一份由内而外的清单。
角落缝合的数据结构。根据总结：
拐角缝合是一种用于表示矩形二维对象。看起来特别适合VLSI交互式编辑系统布局。数据结构有两个重要特征：第一，空白明确表示；第二，矩形区域被缝合在他们的角落像一个拼缝被子。此组织快速算法的结果（线性时间或更好），创建、删除、拉伸和压实。算法如下以简化模型VLSI电路和存储器结构要求如下讨论。测量结果表明拐角缝合要求大约三倍尽可能简单的存储空间代表。
持久数据结构
使用2个堆栈实现的队列非常节省空间（与使用至少有1个额外指针/引用开销的链接列表不同）。
如何使用两个堆栈实现队列？
当排队人数很大时，这对我来说效果很好。如果我在一个指针上节省了8个字节，这意味着拥有百万条目的队列节省了大约8MB的RAM。
