这篇文章是stackoverflow的一篇帖子。上面提到了很多有用的数据结构。有的听过了，经常用，有的没有听过，记录下来。

1. Trie树。应用比较多，一个比较cool的trie的应用TRASH-A dynamic LC-trie and hash data structure。

2. Bloom filter。wiki链接 删除某一项是不允许的，不过可以实现可计数的counting bloom filter

• 在BigTable，Cassandra中都有使用

• 可以用来快速检查是否拼写错误

3. Rope：rope 数据结构表示不能修改的字符序列，与 Java 的 String非常像。但是 ropes 效率奇高的字符串变换操作使得它与 String及其同一体系的可修改的 StringBuffer和 StringBuilder大不相同，非常适合那些执行繁重字符串操纵的应用程序，尤其在多线程环境下更是如此。ibm文章 包含java实现。

• stl实现：http://www.sgi.com/tech/stl/Rope.html

4. skip list：这里有一个演示：http://iamwww.unibe.ch/~wenger/DA/SkipList/

• Cassandra的索引

• redis的SortedSet

5. Spatial Indices：尤其是R-trees和KD-trees

6. Bit Array：压缩存储bit，支持快速的bit操作。

7. Zippers： 在函数式编程中非常有用。

8. Suffix tries: 字符串搜索非常有用。更酷的是suffix tree，可以O(n)的时间构建

9. Splay trees：非常酷的结构

1. 非常小巧，仅需要类似二叉树的左右孩子指针

2. 相对容易实现

3. 性能良好，wiki地址

10. Heap-ordered search trees

11. 邻接表：O(1)计算无向图的邻居节点

12. lock-free：

• http://www.research.ibm.com/people/m/michael/podc-1996.pdf

• http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

• http://www.boyet.com/Articles/LockfreeStack.html

• http://stackoverflow.com/questions/2101789/implementation-of-a-work-stealing-queue-in-c-c

• 一个非常好的这方面的博客：Mike Acton‘s

13. 并查集

14. fibonacci堆

15. BSP Trees：应用在3D渲染领域

16. 霍夫曼树：压缩

17. Finger Trees：在函数式结构中使用，wiki地址

18. Ring buffer

19. Merkle trees

20. Cukoo Hashing ：用来提升hash方法的空间利用，基本思想是利用多个hash函数，降低冲突。

21. min-max heap：

22. 缓存参数无关数据结构：Cache Oblivious datastructures

23. Left learning Red-Back Trees： 论文

24. Bootstrapped skew-binomial heaps：

• O(1) size, union, insert, minimum

• O(logn) deleteMin

25. Interval Trees: 在Cassandra中有应用

   本文链接：http://www.cnblogs.com/sing1ee/archive/2012/10/12/2765064.html，转载请注明。

建议继续学习：

1. 浅谈MySQL索引背后的数据结构及算法    (阅读：9961)
2. 爱喝啤酒的程序员是如何学习数据结构的    (阅读：5185)
3. 分布式系统的数据结构    (阅读：5021)
4. stream.js ：一个新的JavaScript数据结构    (阅读：4101)
5. 开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList    (阅读：2957)
6. 开源世界中的算法与数据结构 2 -- Linux Skbuff实现    (阅读：2780)
7. 数据结构之treap    (阅读：2747)
8. 开源世界中的算法与数据结构 1 -- Linux FIB实现    (阅读：2442)
9. 开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现    (阅读：2386)
10. 深入剖析 redis 数据结构 skiplist    (阅读：2385)