什么是较少知道但有用的数据结构？

2018-05-29 07:09:59

有一些数据结构是非常有用的，但大多数程序员都不知道。他们是哪一个？

每个人都知道链表，二叉树和散列，但跳过列表和布卢姆过滤器例如。我想知道更多不太常见的数据结构，但值得了解，因为它们依靠伟大的想法并丰富了程序员的工具箱。

PS：我对像跳舞链接这样的技术也很感兴趣，这些技术巧妙地使用了通用数据结构的属性。

编辑：请尝试将链接包含到更详细描述数据结构的页面中。另外，为了说明为什么数据结构很酷，尝试添加几句话（正如JonasKölker已经指出的那样）。另外，尝试为每个答案提供一个数据结构 。这将允许更好的数据结构根据他们的投票单独浮到顶部。

尝试，也被称为前缀树或暴击位树，已经存在了40多年，但仍然相对未知。在“TRASH - 动态LC-trie和散列数据结构”中描述了一个非常酷的尝试，它将trie与散列函数结合在一起。

布隆过滤器：m位的位数组，最初全部设置为0。

要添加一个项目，您可以通过k散列函数运行它，该函数将为您提供数组中的k个索引，然后将其设置为1。

要检查项目是否在集合中，计算k个索引并检查它们是否都设置为1。

当然，这给出了一些错误肯定的概率（根据维基百科它约为0.61 ^（m / n），其中n是插入项目的数量）。假阴性是不可能的。

删除项目是不可能的，但是您可以实现计数布隆过滤器，由整数和增量/减量表示。

绳：这是一个字符串，允许便宜的prepends，子字符串，中间插入和附加。我真的只用过它一次，但没有其他结构可以满足。对于我们需要做的事情来说，规则的字符串和数组的前置代码太昂贵了，而扭转事务是不可能的。

链接地址: http://www.djcxy.com/p/1031.html