周围有一些数据结构非常有用，但大多数程序员都不知道。他们是哪一个？
每个人都知道链接列表，二叉树和哈希，但是例如跳过列表和布隆过滤器 。我想知道更多不常见的数据结构，但值得了解，因为它们依赖于很棒的想法并丰富了程序员的工具箱。
PS：我也对像跳舞链接这样的技巧感兴趣，这些技巧巧妙地使用了常见数据结构的属性。
编辑 ：请尝试更详细地包含指向描述数据结构的页面的链接 。此外，尝试添加几个关于数据结构为什么很酷的词（正如JonasKölker已经指出的那样）。此外，尝试为每个答案提供一个数据结构 。这将允许更好的数据结构根据他们的投票单独浮动到顶部。
尝试 ，也称为前缀树或暴击树 ，已存在超过 40 年，但仍然相对未知。在 “ TRASH - 动态 LC-trie 和散列数据结构 ” 中描述了一种非常酷的尝试用法，它结合了 trie 和散列函数。
布隆过滤器 ： m位的位数组，最初都设置为 0。
要添加一个项目，您可以通过k哈希函数运行它，这将在数组中为您提供k 个索引，然后将其设置为 1。
要检查项目是否在集合中，请计算k 个索引并检查它们是否都设置为 1。
当然，这给出了一些假阳性的概率（根据维基百科它约为 0.61 ^（m / n），其中 n 是插入项目的数量）。假阴性是不可能的。
删除项目是不可能的，但您可以实现计数布隆过滤器 ，由整数数组和递增 / 递减表示。
绳索 ：它是一个字符串，允许廉价的 prepends，子串，中间插入和追加。我真的只使用过一次，但没有其他结构就足够了。常规字符串和数组前置对于我们需要做的事情来说太昂贵了，并且逆转翻转是不可能的。