周围有一些数据结构非常有用,但大多数程序员都不知道。他们是哪一个?

每个人都知道链表、二叉树和散列,但比如Skip列表和Bloom过滤器。我想知道更多不太常见但值得了解的数据结构,因为它们依赖于伟大的想法,丰富了程序员的工具箱。

PS:我还对舞蹈链接等技术感兴趣,这些技术巧妙地利用了通用数据结构的财产。

编辑:请尝试包含更详细描述数据结构的页面链接。此外,试着补充几句关于数据结构为什么很酷的话(正如乔纳斯·Kölker已经指出的那样)。此外,尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。


当前回答

嵌套集用于表示关系数据库中的树并对其运行查询。例如,ActiveRecord(RubyonRails的默认ORM)附带了一个非常简单的嵌套集插件,这使得使用树变得微不足道。

其他回答

Van Emde Boas树

我想知道它们为什么很酷会很有用。一般来说,“为什么”这个问题是最重要的;)

我的答案是,他们给你O(log-logn)字典,其中包含{1..n}个键,而与使用的键的数量无关。就像重复减半得到O(log n)一样,重复平方得到O(log-log n),这就是vEB树中发生的情况。

空间索引,特别是R-树和KD树,有效地存储空间数据。它们适用于地理地图坐标数据和VLSI位置和路线算法,有时也适用于最近邻搜索。

位阵列紧凑地存储单个位,并允许快速位操作。

哈希表的一个有趣的变体叫做布谷鸟哈希。为了处理哈希冲突,它使用多个哈希函数而不是1。通过从主哈希指定的位置删除旧对象,并将其移动到备用哈希函数指定的位置,可以解决冲突。Cuckoo Hashing允许更有效地使用内存空间,因为您只需要3个哈希函数就可以将负载因子提高91%,而且访问时间也很长。

Van Emde Boas树。我甚至有一个C++实现,最多支持2^20个整数。