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

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

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

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


当前回答

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

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

其他回答

循环或环形缓冲区-用于流式传输等。

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

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

Fast Compact尝试:

Judy数组:用于位、整数和字符串的非常快速且内存高效的有序稀疏动态数组。Judy数组比任何二进制搜索树都更快、更节省内存。HAT-trie:一种基于缓存的字符串数据结构基于磁盘的字符串管理的B次尝试

我认为保罗·费拉吉纳和乔凡尼·曼奇尼的FM指数真的很酷。尤其是在生物信息学方面。它本质上是一个压缩的全文索引,利用了后缀数组和参考文本的burrows-wheeler变换的组合。可以在不解压缩整个索引的情况下搜索索引。

我有时使用反转列表来存储范围,它们通常用于在正则表达式中存储字符类。例如,请参见http://www.ibm.com/developerworks/linux/library/l-cpinv.html

另一个很好的用例是加权随机决策。假设你有一个符号和相关概率的列表,你想根据这些概率随机选择它们

   a => 0.1
   b => 0.5
   c => 0.4

然后,你对所有概率进行一次连续求和:

  (0.1, 0.6, 1.0)

这是你的反转列表。生成一个介于0和1之间的随机数,并查找列表中下一个较高条目的索引。你可以用二进制搜索来实现,因为它是排序的。一旦获得了索引,就可以在原始列表中查找符号。

如果有n个符号,则每个随机选择的符号都有O(n)个准备时间,然后是O(log(n))个访问时间,与权重分布无关。

反转列表的一种变体使用负数来指示范围的端点,这使得计算某一点上有多少范围重叠变得容易。看见http://www.perlmonks.org/index.pl?node_id=841368例如。