内容简介：这篇文章是stackoverflow的一篇上面仅仅写了一半，就有好多我不熟悉的了。剩下的一半不是很火，更是没有听过。就先这些吧。本文链接：
这篇文章是stackoverflow的一篇 帖子 。上面提到了很多有用的数据结构。有的听过了，经常用，有的没有听过，记录下来。
-
Trie树。应用比较多，一个比较cool的trie的应用 TRASH-A dynamic LC-trie and hash data structure。
-
Bloom filter。 wiki链接 删除某一项是不允许的，不过可以实现可计数的counting bloom filter
-
在BigTable，Cassandra中都有使用
-
可以用来快速检查是否拼写错误
Rope ：rope 数据结构表示不能修改的字符序列，与 Java 的 String非常像。但是 ropes 效率奇高的字符串变换操作使得它与 String及其同一体系的可修改的 StringBuffer和 StringBuilder大不相同，非常适合那些执行繁重字符串操纵的应用程序，尤其在多线程环境下更是如此。 ibm文章 包含java实现。
-
stl实现：http://www.sgi.com/tech/stl/Rope.html
skip list ：这里有一个演示： http://iamwww.unibe.ch/~wenger/DA/SkipList/
-
Cassandra的索引
-
redis的SortedSet
Spatial Indices ：尤其是 R-trees 和 KD-trees
Bit Array ：压缩存储bit，支持快速的bit操作。
Zippers ： 在函数式编程中非常有用。
Suffix tries : 字符串搜索非常有用。更酷的是suffix tree，可以O(n)的时间构建
Splay trees：非常酷的结构
-
非常小巧，仅需要类似二叉树的左右孩子指针
-
相对容易实现
-
性能良好， wiki地址
Heap-ordered search trees
邻接表：O(1)计算无向图的邻居节点
lock-free：
-
http://stackoverflow.com/questions/2101789/implementation-of-a-work-stealing-queue-in-c-c
-
一个非常好的这方面的博客： Mike Acton‘s
并查集
fibonacci堆
BSP Trees：应用在3D渲染领域
霍夫曼树：压缩
Finger Trees：在函数式结构中使用， wiki地址
Ring buffer
Merkle trees
Cukoo Hashing ：用来提升hash方法的空间利用，基本思想是利用多个hash函数，降低冲突。
缓存参数无关数据结构： Cache Oblivious datastructures
Left learning Red-Back Trees： 论文
-
O(1) size, union, insert, minimum
-
O(logn) deleteMin
Interval Trees : 在Cassandra中有应用
上面仅仅写了一半，就有好多我不熟悉的了。剩下的一半不是很火，更是没有听过。就先这些吧。
本文链接： http://www.cnblogs.com/sing1ee/archive/2012/10/12/2765064.html ，转载请注明。
以上所述就是小编给大家介绍的《一些不常见但是很重要的数据结构》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- 浅谈常见数据结构和算法的应用系列（一）
- 数据结构常见的八大排序算法及代码实现图解
- 数据结构与算法（三）—— 常见排序算法和swift实现
- 数据结构基础之掌握5个常见的链表操作
- 数据结构 – 用于构建文件系统的数据结构？
- 荐 用Python解决数据结构与算法问题（三）：线性数据结构之栈
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
