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

标签: 技术资料 | 发表时间:2012-08-19 02:18 | 作者:唐福林
出处:http://blog.fulin.org

这篇文章是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-treesKD-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:
  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中有应用

 

转自:https://singmind.sinaapp.com/?p=548

用bShare分享或收藏本文

相关 [数据结构] 推荐:

数据结构之BloomFilter

- - 编程语言 - ITeye博客
BloomFilter是什么.        BloomFilter主要提供两种操作: add()和contains(),作用分别是将元素加入其中以及判断一个元素是否在其中,类似于Java中的Set接口,它内部采用的byte数组来节 省空间. 其独特之处在于contains()方法,当我们需要查询某个元素是否包含在BloomFilter中时,如果返回true,结果可能是不正确 的,也就是元素也有可能不在其中;但是如果返回的是false,那么元素一定不在其中.

使用graphviz画数据结构

- 王者自由 - Emacs中文网
今天下午用了些时间写了个小的函数,该函数配合 autoinsert + graphviz-dot-mode ,可以很方便的将 C 语言中指定的 struct 结构画出来. 这样,画了多个数据结构之后,再手动添加几条线, 数据结构之间的关系就一目了然了. 1.2 Graphviz 的安装. 1.3 Graphviz 的使用.

数据结构之红黑树

- Shengbin - 董的博客
红黑树是一种自平衡二叉查找树. 它的统计性能要好于平衡二叉树(AVL树),因此,红黑树在很多地方都有应用. 在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持).

数据结构-二分法查找

- - 操作系统 - ITeye博客
1、二分查找(Binary Search).      二分查找又称折半查找,它是一种效率较高的查找方法.      二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构. 2、二分查找的基本思想.      二分查找的基本思想是:(设R[low..high]是当前的查找区间).

redis数据结构缓存运用

- - 企业架构 - ITeye博客
之前redis已经描述了redis 的基本作用与用处, 这一篇主要讲述redis运用场景以及分片,和spring整合. redis 存储数据结构大致5种,String 普通键值对,用的比较多. HASH针对 key 唯一标识 hashmap 键值对运用也比较多 list set 当然是集合运用 sortedSet 排序集合使用.

可视化的数据结构和算法

- greenar - 酷壳 - CoolShell.cn
还记得之前发布过的那个关于可视化排序的文章吗. 在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看. 我把这个页面的目录列在下面并翻译了一下,大家可以直接点击了. 不知道国内的教育有没有相关的教学课件,至少在我大学的时候是没有的. Queues队列: 数组实现.

为什么要学习算法和数据结构

- snowflip - TopLanguage Google Group

MySQL索引背后的数据结构及算法原理

- Mike - 博客园-EricZhang's Technology Blog
在编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”,我个人是不太赞同这句话(因为我觉得程序不仅仅是数据结构加算法),但是在日常的学习和工作中我确认深深感受到数据结构和算法的重要性,很多东西,如果你愿意稍稍往深处挖一点,那么扑面而来的一定是各种数据结构和算法知识. 例如几乎每个程序员都要打交道的数据库,如果仅仅是用来存个数据、建建表、建建索引、做做增删改查,那么也许觉得数据结构和这东西没什么关系.

Data Structure Visualizations: 数据结构及算法可视化工具

- tiger - 黑客志
Data Structure Visualizations是旧金山大学的David Galles开发的一个以可视化方式演示数据结构和算法的非常棒的工具,可以很好的帮助你理解这些抽象的数据结构和算法,不管你是需要应付考试的CS学生,还是需要对付一些公司的变态面试题的上班族,你都会发现这是一个非常有用的工具,并且这个工具同时提供Java,Flash,以及基于HTML5的Web版本.