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

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

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

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


当前回答

跳过列表非常整洁。

维基百科跳过列表是一种概率数据结构,基于多个并行、排序的链接列表,其效率与二进制搜索树相当(大多数操作的顺序日志n平均时间)。

它们可以作为平衡树的替代(使用概率平衡而不是严格执行平衡)。它们很容易实现,而且比红黑树更快。我认为他们应该在每一个优秀的程序员工具箱中。

如果你想深入了解跳过列表,这里有一个麻省理工学院算法简介讲座视频的链接。

此外,这里还有一个Java小程序,直观地演示了跳过列表。

其他回答

正确的字符串数据结构。几乎每个程序员都满足于一种语言对结构的任何原生支持,而这种支持通常是低效的(尤其是对于构建字符串,你需要一个单独的类或其他东西)。

最糟糕的是将字符串作为C中的字符数组,并依赖NULL字节来确保安全。

增强的哈希算法非常有趣。线性哈希很简单,因为它允许一次在哈希表中拆分一个“桶”,而不是重新哈希整个表。这对于分布式缓存特别有用。然而,对于大多数简单的拆分策略,您最终会快速连续地拆分所有存储桶,并且表的负载系数波动非常严重。

我认为螺旋哈希法也很好。与线性哈希一样,一次拆分一个存储桶,存储桶中的记录只有不到一半被放入同一个新存储桶中。它非常干净和快速。然而,如果每个“桶”都由具有类似规格的机器托管,则效率可能很低。为了充分利用硬件,您需要混合使用功能较弱和功能更强的机器。

Splay Trees很酷。它们以将最常查询的元素移到更靠近根的方式重新排序。

远离所有这些图形结构,我只喜欢简单的环形缓冲区。

如果实施得当,您可以在保持性能的同时,甚至可以提高性能,从而大大减少内存占用。