黑马程序员技术交流社区

标题: 常用数据结构 [打印本页]

作者: 左拉 时间: 2014-4-19 11:03
标题: 常用数据结构
1. 数组(Array)
数组最大的特点是预先要知道数组长度，长度不可变，通过索引访问效率很高，因为是直接算出内存地址去读的。
2. 列表(List)
列表可以看作是数组的延伸，最大的不一样是长度可变，列表按照结构来分一般分为两种：
i) ArrayList
这是基于数组实现的列表，内部存储用的就是数组，当当前数组长度不够的时候重新分配一个大一点的数组到底大多少有一个分配因子，那么在内部数组重新分配的时候需要把数据从原来的小数组copy到大数组里面去这是要花时间的，所以如果一开始就知道到底需要多大空间，可以在生成ArrayList的时候指定大小，这样就可以省去copy的时间了

优点：

a) 因为是基于数组实现的，所以有数组一样的优点，通过index来访问的效率很高。

缺点:
a) 因为是基于数组实现的，所以他需要一块连续的内存来存放  – 好像不是什么大缺点
b) 在中间插入数据的话则需要把所有的数据往后挪，效率较低
ii) LinkedList
LinkedList是基于链表或者说基于指针的，和ArrayList不同的是它不需要一块连续的内存来存放数据

优点:
a) 往中间插入数据不需要把后面的数据都后挪，只要改变指针指向即可

缺点:

b) 通过索引访问没有ArrayList快，因为不能通过索引直接算出内存地址，需要从链表头一直往后找第n个元素
3. Map
在Map, Set和Bag当中，Map是最基础的数据结构，在java里面， Set和Bag都是利用Map来实现的

i) HashMap

利用哈希函数对数据进行散列，所以用key来查询对应的value速度很快
ii) TreeMap
内部利用红黑树(树那部分有介绍)对数据进行有序存储，所以遍历的时候key是有序的
iii) HashTable
和HashMap几乎一样
不同点是:
a) hashtable是同步的
b) hashtable的key和value都不允许为null
4. 集合(Set)
集合中的数据都是唯一的，集合不保证其中元素的顺序
i) HashSet
内部利用HashMap实现
ii) TreeSet
内部使用TreeMap实现
iii) LinkedHashSet
LinkedHashSet利用hash函数对数据进行散列，所以查询速度很快，同时利用链表(LinkedList)维护元素的顺序。所以对LinkedHashSet进行遍历的时候key出现的顺序就是key插入时候的顺序
总结下这个set的三个特点:
a) 查询快
b) 有序的 — 插入是什么顺序就是什么顺序
c) 元素去重 — 他是set
5. 袋子(Bag)
袋子和Set类似，不一样的是: 袋子里面对每个key计数，所以如果同一个key被加入多次那么可以通过接口
获取这个key在这个袋子里面的个数。
i)  HashBag
内部利用HashMap实现
ii) TreeBag
内部利用TreeMap实现
6. 树(Tree)
i) 堆(heap)
堆是这么一种数据结构(以二叉，大根堆来说)，对于任意一个节点，它的值比它的子节点都要大，所以这个树根是这个堆里面最大的节点有名的堆排序(heap sort)就是利用堆的特性来加快排序速度的
ii) 二叉搜索树(binary search tree)
二叉搜索树是这样一种树，这个树的左子树的所有key值都比跟节点的key值小，右子树的所有key值都比根节点的key值大，并且这个树上所有的子树都是二叉搜索树。所以如果从左往右遍历二叉搜索树可以可以得到一个有序序列。
iii) Merkle Tree(Hash Tree)
merkle tree主要用在对数据的校验上，对于一个很大的文件在两个机器之间进行传输的时候，会这个文件切成很多的小块，然后对每一块计算hash值然后再把这些hash组成一个tree结构：这个tree里面的每个叶节点对应具体的文件块的hash，而非叶节点的值则是它子节点的hash的hash，这样传输好了之后计算hash tree，把这个hash tree和之前传输过来的hash tree进行对比就可以在logN的比较次数内找到那些数据有问题(如果有的话)
iv) B-/B+ Tree
B-树是二叉搜索树的一种泛化 — m叉搜索树，每个节点可以有多于两个子节点。B-/B+树多用在数据库/文件系统的设计中，树中存储的数据实际是实际数据的一级索引，二级索引，三级索引，这样可以保证在确定的时间内查找到一个具体的数据  – 具体时间取决于每个节点上的数据量以及索引的层数。

iv) 红黑树
红黑树是一种特殊的二叉搜索树，它在插入，删除数据的时候自动调整树结构，保证树结构的平衡。它比AVL树对于平衡的要求弱一点，所以在插入数据的时候比AVL树要快，在查询数据的时候比AVL可能要稍微慢一点。 TreeMap就是利用红黑树来存储数据的。
6. 图(Graph)
好像还真没用到过。。

作者: 许庭洲 时间: 2014-4-24 22:14
值得学习ing!

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2