2015-05-16

Java 集合之 Collection 和 Map

热度 ℃

Java 中的两类集合对象 Collection 和 Map。

集合关系

Map
	HashMap
		LinkedHashMap
	Hashtable
	TreeMap
Collection
	List
		ArrayList
		LinkedList
		Vector
			Stack
	Set
		HashSet
			LinkedHashSet
		TreeSet

Map

HashMap

采用数组存储数据，HashMapEntry[] table，table的大小为2的幂倍数，HashMapEntry(key, value, hash, next)是一个单向链表；

put: 根据key的hash值，和table.length - 1按位与运算(实际上就是取余)，取得该存放的位置index，如果在此位置上已经有entry了，则新建一个节点，旧节点作为新节点的next被引用；

HashMap 实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

LinkedHashMap

继承自HashMap，添加了一个双向链表来记录插入的顺序，LinkedHashMapEntry相比HashMapEntry多一before和after属性，分别表示上一个节点和下一个节点；

init: 初始化的时候初始化header节点，header.before = header.after = header; header的before和after属性都指向自己；

createEntry: 重写了createEntry方法，在该方法里面添加链表的链接关系；

使用Iterator遍历节点的时候，获取到的数据和put添加的顺序相同，而HashMap则不具备这个特性；

Hashtable

HashMap的线程同步实现，继承自Dictionary，实现了Map接口，初始大小11，扩容 2n + 1；

Hashtable默认大小为什么是11? Link

TreeMap

采用树型(红黑树)结构存储数据，Node(k, v, parent, left, right, color)；

第次新增节点，或者删除节点的时候，都会重新平衡该树结构以满足红黑树的结构；

Map适用场景：

HashMap: 里面存入的键值对在取出的时候是随机的，最常用的一个Map。它根据键的HashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。在 Map 中插入、删除和定位元素，HashMap 是最好的选择。
LinkedHashMap: 输出的顺序和输入的相同，用LinkedHashMap。
TreeMap: 取出来的是排序后的键值对。如果要按自然顺序或自定义顺序遍历键，使用TreeMap。

Collection

ArrayList

采用数组存放数据，如果初始化时不指定容量，在第一次添加元素的时候，将使用初始容量10构建数组容器，单次扩容增加0.5倍，移除元素时不缩小数组大小，插入使用System.arrayCopy()；

LinkedList

采用双向链表存储数据，节点为Node实体，Node节点item表示节点值，prev指向上一个节点，next指向下一节点，插入删除时修改链表中数据的prev/next引用指向；

Vector

ArrayList的线程同步实现，初始化时直接构建默认大小(10)或者指定大小的数组容器，修改数组的操作都使用synchronized加锁，单次扩容增加1倍；

Stack

继承自Vector，last-in-first-out，栈结构，后进先出，pop(删除最后一个元素)、push(添加一个元素到栈顶)、peek(获取最后一个元素)；

Set

Set是存储无重复数值的集合，但它是无序的。

HashSet: 无序无重复集合；
LinkedHashSet: 有序无重复集合，按添加顺序进行排序；
TreeSet: 有序无重复集合，元素是可比较的(Comparable)，按Comparable顺序进行排序，或者也可以指定一个Comparator；

Set 实际是都是在里面引用了一个 Map 对象，添加/删除元素实际上都是将元素作为key添加到map对象中，由于Map的key的唯一性，所以Set中也就能自动过滤掉重复元素；

Michael Cai