有一些数据结构对于大多数程序员来说很有用，但是却不为人所知。它们都是哪些呢？
每个人都知道链表、二叉树和哈希表，但是例如跳表和布隆过滤器呢？我想了解更多不太常见但值得知道的数据结构，因为它们依赖于巨大的思想，并且丰富了程序员的工具箱。
PS：我还对像舞蹈链这样聪明地利用常见数据结构属性的技术感兴趣。
编辑: 请尝试在描述数据结构的页面中包含链接。此外，请尽量添加一些关于为什么某个数据结构很酷的词语（正如Jonas Kölker 已经指出的）。此外，请每次只提供一个数据结构的答案。这将使更好的数据结构根据它们的投票结果浮现在最上面。
Trie，也被称为前缀树或crit-bit树，存在已经超过40年，但仍相对较为不知名。其中一个非常酷的使用方法可以在 "TRASH - 动态LC-trie和哈希数据结构" 中找到，该方法将trie与哈希函数相结合。
布隆过滤器：由m位比特位组成的位数组，最开始所有的比特位都为0。
添加一个元素时，需要经过k个散列函数计算，得出k个在数组中对应的索引，并将它们设置为1。
检查一个元素是否在集合中时，同样需要计算k个索引并检查它们是否都被设置为1。
当然，这会导致一定的误报概率（根据维基百科的说法，误报概率约为0.61^(m/n)，其中n为插入的元素数量）。但不会发生漏报。
删除元素是不可能的，但可以使用计数型布隆过滤器，用整数数组表示并进行增量/减量操作。
Rope是一种字符串数据结构，它使得在字符串的前部添加、截取子串、中间插入和追加操作变得更加便宜。我只使用过一次，但没有其他数据结构可以胜任。常规字符串和数组的前置操作对我们需要完成的任务来说太昂贵了，而将所有内容反转则不可行。
跳表是一种很棒的数据结构。
维基百科
跳表是一种基于多个平行排序链表的概率型数据结构，其效率可媲美二叉搜索树（大多数操作的平均时间为对数级别）。
它们可以作为平衡树的替代品（使用概率平衡而不是严格平衡），易于实现且比如红黑树等其他数据结构更快。我认为每个优秀的程序员都应该掌握这项技能。
如果你想深入了解跳表，这里有麻省理工学院算法导论讲座关于跳表的视频链接。
此外，这里有一个Java applet，可以通过可视化演示跳表的操作：链接。
令人惊奇的是，您可以通过应用微积分技术到原始数据结构的类型上来推导它们！
这里有几个：
后缀树。对于几乎所有类型的字符串搜索都很有用(http://en.wikipedia.org/wiki/Suffix_trie#Functionality)。也可以看一下后缀数组；它们不如后缀树快，但要小得多。
Splay树（如上所述）。它们酷的原因有三个：
堆排序搜索树：您可以在树中存储一组（键、优先级）对，使其成为关于键的搜索树，并且与优先级有序。可以证明这样的树具有唯一的形状（并且它并不总是完全向左上方填充）。使用随机优先级，它给出了预期的O(log n)查找时间。
一个小众的数据结构是具有O(1)邻居查询的无向平面图的邻接表。这不是一种数据结构，而是组织现有数据结构的一种特定方式。这里是如何做到的：每个平面图都有一个度数不超过6的节点。选择这样的节点，将其邻居放入其邻居列表中，从图中删除它，并递归直到图为空。当给出一对（u，v）时，在v的邻居列表中查找u，在u的邻居列表中查找v。两者大小均不超过6，因此复杂度为O(1)。
我认为锁定数据结构的无锁替代方案，例如无锁队列、栈和列表，被忽视了很多。
随着并发性变得更加重要，它们变得越来越相关，并且比使用互斥锁或锁来处理并发读/写要更可贵。
以下是一些链接：
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [链接到PDF]
http://www.boyet.com/Articles/LockfreeStack.html
Mike Acton的（常常具有挑衅性）博客中有一些关于无锁设计和方法的优秀文章。
我认为不相交集合在需要将一堆项目分成不同集合并查询成员身份的情况下非常方便。好的Union和Find操作实现会导致摊销成本基本保持不变（如果我还记得我的数据结构课程正确，这是Ackerman函数的倒数）。
它们被用于一些最快的已知算法（在渐近意义下）来解决许多图相关问题，例如最短路径问题。Dijkstra算法在使用标准二叉堆时的时间复杂度为O(E log V)；使用斐波那契堆可以将时间复杂度提高到O(E + V log V)，这对于密集图来说是一个巨大的加速。不幸的是，它们具有很高的常数因子，通常使它们在实践中不切实际。
