language-agnostic - 什么是鲜为人知但有用的数据结构？(What are the lesser known but useful data structures?)

Question

There are some data structures around that are really useful but are unknown to most programmers. (周围有一些数据结构非常有用，但大多数程序员都不知道。) Which ones are they? (他们是哪一个？)

Everybody knows about linked lists, binary trees, and hashes, but what about Skip lists and Bloom filters for example. (每个人都知道链接列表，二叉树和哈希，但是例如跳过列表和布隆过滤器 。) I would like to know more data structures that are not so common, but are worth knowing because they rely on great ideas and enrich a programmer's tool box. (我想知道更多不常见的数据结构，但值得了解，因为它们依赖于很棒的想法并丰富了程序员的工具箱。)

PS: I am also interested in techniques like Dancing links which make clever use of properties of a common data structure. (PS：我也对像跳舞链接这样的技巧感兴趣，这些技巧巧妙地使用了常见数据结构的属性。)

EDIT : Please try to include links to pages describing the data structures in more detail. (编辑 ：请尝试更详细地包含指向描述数据结构的页面的链接 。) Also, try to add a couple of words on why a data structure is cool (as Jonas K?lker already pointed out). (此外，尝试添加几个关于数据结构为什么很酷的词（正如JonasK?lker已经指出的那样）。) Also, try to provide one data-structure per answer . (此外，尝试为每个答案提供一个数据结构 。) This will allow the better data structures to float to the top based on their votes alone. (这将允许更好的数据结构根据他们的投票单独浮动到顶部。)

  ask by community wiki translate from so

Answer 1

Tries , also known as prefix-trees or crit-bit trees , have existed for over 40 years but are still relatively unknown. (尝试 ，也称为前缀树或暴击树 ，已存在超过40年，但仍然相对未知。) A very cool use of tries is described in " TRASH - A dynamic LC-trie and hash data structure ", which combines a trie with a hash function. (在“ TRASH - 动态LC-trie和散列数据结构 ”中描述了一种非常酷的尝试用法，它将trie与散列函数结合起来。)