一些不常见但是很重要的数据结构

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

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

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

• 在BigTable，Cassandra中都有使用

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

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

• Cassandra的索引

• redis的SortedSet

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

2. 相对容易实现

3. 性能良好， wiki地址

• 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

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

• O(logn) deleteMin

上面仅仅写了一半，就有好多我不熟悉的了。剩下的一半不是很火，更是没有听过。就先这些吧。

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