技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 一些不常见但是很重要的数据结构

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

浏览:1249次  出处信息

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

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


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

建议继续学习:

  1. 浅谈MySQL索引背后的数据结构及算法    (阅读:9886)
  2. 爱喝啤酒的程序员是如何学习数据结构的    (阅读:5069)
  3. 分布式系统的数据结构    (阅读:4955)
  4. stream.js :一个新的JavaScript数据结构    (阅读:4082)
  5. 开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList    (阅读:2900)
  6. 开源世界中的算法与数据结构 2 -- Linux Skbuff实现    (阅读:2722)
  7. 数据结构之treap    (阅读:2687)
  8. 开源世界中的算法与数据结构 1 -- Linux FIB实现    (阅读:2384)
  9. 开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现    (阅读:2327)
  10. 深入剖析 redis 数据结构 skiplist    (阅读:2261)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1