周围有一些数据结构非常有用，但大多数程序员都不知道。他们是哪一个？
每个人都知道链表、二叉树和散列，但比如Skip列表和Bloom过滤器。我想知道更多不太常见但值得了解的数据结构，因为它们依赖于伟大的想法，丰富了程序员的工具箱。
PS：我还对舞蹈链接等技术感兴趣，这些技术巧妙地利用了通用数据结构的财产。
编辑：请尝试包含更详细描述数据结构的页面链接。此外，试着补充几句关于数据结构为什么很酷的话（正如乔纳斯·Kölker已经指出的那样）。此外，尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。
当前回答
我不确定这个数据结构是否有名字，但是提议的包含在Boost中的tokenmap数据结构有点有趣。这是一个动态调整大小的映射，其中查找不仅是O（1），而且是简单的数组访问。我写了关于这个数据结构的大部分背景材料，其中描述了它如何工作的基本原理。
操作系统使用类似于tokenmap的东西来将文件或资源句柄映射到表示文件或资源的数据结构。
其他回答
任何有3D渲染经验的人都应该熟悉BSP树。通常，这是一种通过构造3D场景来进行渲染的方法，该方法可以在知道相机坐标和方位的情况下进行管理。
二进制空间分区（BSP）是一种递归细分a的方法通过超平面将空间划分为凸集。该细分产生通过方法表示场景树数据结构的BSP树。换句话说，这是一种方法形状复杂的破碎多边形转化为凸集，或更小多边形完全由非反射角（小于180°). 更一般的描述空间分区，请参见空间分区。最初，提出了这种方法在3D计算机图形方面渲染效率。其他一些应用程序包括执行具有形状的几何操作（构造实体几何），机器人和3D中的碰撞检测计算机游戏和其他计算机涉及处理的应用程序复杂的空间场景。
Fenwick树（或二进制索引树）是一个值得添加的工具。如果您有一个计数器数组，并且需要在查询累积计数时不断更新它们（如PPM压缩），Fenwick树将在O（logn）时间内完成所有操作，并且不需要额外的空间。另请参阅本面漆教程，了解详细介绍。
我有时使用反转列表来存储范围，它们通常用于在正则表达式中存储字符类。例如，请参见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例如。
环境跟踪递归结构。
编译器使用递归但不像树的结构。内部作用域有一个指向封闭作用域的指针，因此嵌套是由内向外的。验证变量是否在范围内是从内部范围到封闭范围的递归调用。
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;
}
}
我不确定这个结构是否有名字。我称之为一份由内而外的清单。
Van Emde Boas树
我想知道它们为什么很酷会很有用。一般来说，“为什么”这个问题是最重要的；）
我的答案是，他们给你O（log-logn）字典，其中包含｛1..n｝个键，而与使用的键的数量无关。就像重复减半得到O（log n）一样，重复平方得到O（log-log n），这就是vEB树中发生的情况。
