一些不常见但是很重要的数据结构
这篇文章是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
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,转载请注明。
建议继续学习:
- 浅谈MySQL索引背后的数据结构及算法 (阅读:9861)
- 爱喝啤酒的程序员是如何学习数据结构的 (阅读:5041)
- 分布式系统的数据结构 (阅读:4937)
- stream.js :一个新的JavaScript数据结构 (阅读:4076)
- 开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList (阅读:2884)
- 开源世界中的算法与数据结构 2 -- Linux Skbuff实现 (阅读:2703)
- 数据结构之treap (阅读:2664)
- 开源世界中的算法与数据结构 1 -- Linux FIB实现 (阅读:2370)
- 开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现 (阅读:2310)
- 深入剖析 redis 数据结构 skiplist (阅读:2223)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:用心去做 来源: 用心去做
- 标签: 数据结构
- 发布时间:2019-02-21 21:49:23
- [66] Oracle MTS模式下 进程地址与会话信
- [66] Go Reflect 性能
- [65] 如何拿下简短的域名
- [59] android 开发入门
- [59] 图书馆的世界纪录
- [59] IOS安全–浅谈关于IOS加固的几种方法
- [58] 【社会化设计】自我(self)部分――欢迎区
- [53] 视觉调整-设计师 vs. 逻辑
- [47] 界面设计速成
- [46] 读书笔记-壹百度:百度十年千倍的29条法则