Java中的集合框架学习小结

一：集合框架总体认知
先来看一个图，对集合框架有一个全局的了解
其中实线为继承，虚线为实现接口

二：Collection类集框架

1,Collection整体架构框图
（1）List是有序的队列，List中可以有重复的元素；Set是集合，Set中没有重复元素！
（2）AbstractCollection抽象类实现了Collection中的绝大部分函数。AbstractList和AbstractSet都继承于AbstractCollection，具体的List实现类继承于AbstractList，而Set的实现类则继承于AbstractSet。
（3）Collection中有一个iterator()函数，它返回一个Iterator接口。通常，我们通过Iterator迭代器来遍历集合。ListIterator是List接口所特有的，在List接口中，通过ListIterator()返回一个ListIterator对象。

2，ArrayList
（1）ArrayList是一个动态数组队列，容量可动态增长。
（2）ArrayList中的操作不是线程安全的！建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或CopyOnWriteArrayList。
（3）ArrayList的继承关系

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳     java.util.ArrayList<E>

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

(4) ArrayList 实际上是通过一个数组去保存数据的。当构造ArrayList时；若使用默认构造函数，则ArrayList的默认容量大小是10。 当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：新的容量=“(原始容量x3)/2 + 1”。
(5) ArrayList的克隆函数，即是将全部元素克隆到一个数组中。
(6) ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写入“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
（7）ArrayList的构造函数

// 1，默认构造函数
ArrayList()

// 2，capacity是ArrayList的默认容量大小。当由于增加数据导致容量不足时，容量会添加上一次容量大小的一半。
ArrayList(int capacity)

//3， 创建一个包含collection的ArrayList
ArrayList(Collection<? extends E> collection)

(8) ArrayList支持3种遍历方式

第一种，通过迭代器遍历。即通过Iterator去遍历。（效率最低）

Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}

第二种，随机访问，通过索引值去遍历。(效率最高)

Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
    value = (Integer)list.get(i);        
}

第三种，for循环遍历。如下：

Integer value = null;
for (Integer integ:list) {
    value = integ;
}

3, LinkedList
（1）LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可被当作堆栈、队列或双端队列进行操作。
（2）LinkedList的继承关系

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳     java.util.AbstractSequentialList<E>
                     ↳     java.util.LinkedList<E>

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

（3）LinkedList实际上是通过双向链表去实现的。它的顺序访问非常高效，而随机访问效率比较低。
LinkedList是如何将“双向链表和索引值联系起来的”？实际原理就是通过一个计数索引值来实现的。例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置。
（4） LinkedList可以作为FIFO(先进先出)的队列,也可以作为LIFO(后进先出)的栈。
（5）LinkedList遍历方式
第一种：通过迭代器遍历。即通过Iterator去遍历。

for(Iterator iter = list.iterator(); iter.hasNext();)
    iter.next();

第二种：通过快速随机访问遍历LinkedList（效率太低了)

int size = list.size();
for (int i=0; i<size; i++) {
    list.get(i);        
}

第三种：for循环来遍历LinkedList

for (Integer integ:list) 
    ;

第四种： 通过pollFirst()来遍历LinkedList

while(list.pollFirst() != null)
    ;

第五种：通过pollLast()来遍历LinkedList

while(list.pollLast() != null)
    ;

第六种：通过removeFirst()来遍历LinkedList

try {
    while(list.removeFirst() != null)
        ;
} catch (NoSuchElementException e) {
}

第七种： 通过removeLast()来遍历LinkedList

try {
    while(list.removeLast() != null)
        ;
} catch (NoSuchElementException e) {
}

遍历LinkedList时，使用removeFist()或removeLast()效率最高。但用它们遍历时，会删除原始数据；若单纯只读取，而不删除，应该使用第3种遍历方式。
无论如何，千万不要通过随机访问去遍历LinkedList！

4, Vector
（1）Vector是一个矢量队列，支持相关的添加、删除、修改、遍历等功能。
（2）Vector中的操作是线程安全的。
（3）Vector的继承关系

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳     java.util.Vector<E>

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

（4）Vector是通过一个数组去保存数据的。当构造Vecotr时；若使用默认构造函数，则Vector的默认容量大小是10。当Vector容量不足以容纳全部元素时，Vector的容量会增加。若容量增加系数 >0，则将容量的值增加“容量增加系数”；否则，将容量大小增加一倍。
（5）Vector的构造函数

//1， 默认构造函数
Vector()

// 2，capacity是Vector的默认容量大小。当由于增加数据导致容量增加时，每次容量会增加一倍。
Vector(int capacity)

// 3，创建一个包含collection的Vector
Vector(Collection<? extends E> collection)

// 4，capacity是Vector的默认容量大小，capacityIncrement是每次Vector容量增加时的增量值。
Vector(int capacity, int capacityIncrement)

（6）Vector支持4种遍历方式：
第一种，通过迭代器遍历。即通过Iterator去遍历。

Integer value = null;
int size = vec.size();
for (int i=0; i<size; i++) {
    value = (Integer)vec.get(i);        
}

第二种，随机访问，通过索引值去遍历。（效率最高）

Integer value = null;
int size = vec.size();
for (int i=0; i<size; i++) {
    value = (Integer)vec.get(i);        
}

第三种，另一种for循环。

Integer value = null;
for (Integer integ:vec) {
    value = integ;
}

第四种，Enumeration遍历。如下：

Integer value = null;
Enumeration enu = vec.elements();
while (enu.hasMoreElements()) {
    value = (Integer)enu.nextElement();
}

5, Stack
(1) Stack是栈。它的特性是：先进后出(FILO, First In Last Out)。java工具包中的Stack是继承于Vector(矢量队列)的.
(2) Stack的继承关系：

java.lang.Object
↳     java.util.AbstractCollection<E>
   ↳     java.util.AbstractList<E>
       ↳     java.util.Vector<E>
           ↳     java.util.Stack<E>

public class Stack<E> extends Vector<E> {}

Stack继承于Vector，所以Vector拥有的属性和功能，Stack都拥有。
（3）Stack实际上也是通过数组去实现的。
执行push时(即，将元素推入栈中)，是通过将元素追加的数组的末尾中。
执行peek时(即，取出栈顶元素，不执行删除)，是返回数组末尾的元素。
执行pop时(即，取出栈顶元素，并将该元素从栈中删除)，是取出数组末尾的元素，然后将该元素从数组中删除。

6, fail-fast
（1）fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。
（2）fail-fast机制，是一种错误检测机制。它只能被用来检测错误，因为JDK并不保证fail-fast机制一定会发生。若在多线程环境下使用fail-fast机制的集合，建议使用“java.util.concurrent包下的类”去取代“java.util包下的类”。
（3）产生fail-fast事件，是通过抛出ConcurrentModificationException异常来触发的。
（4）fail-fast事件的产生：当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(即其它线程通过add、remove、clear等方法，改变了modCount的值)；这时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

7, List的使用场景
（1）List的整体框架图
（2）ArrayList,LinkedList,Vector,Stack的比较：

	实质	效率	线程安全性
ArrayList	动态数组队列	随机访问效率高，插删效率低	线程不安全
LinkedList	双向链表（可作队列或栈用）	随机访问效率低，插删效率高
Vector	动态矢量队列		线程安全
Stack	栈（继承自Vector）

（3）Vector和ArrayList比较
相同点：
1）它们都是List：它们都继承于AbstractList，并且实现List接口。
2）它们都实现了RandomAccess和Cloneable接口
3）它们都是通过数组实现的，本质上都是动态数组
4）它们的默认数组容量是10
5） 它们都支持Iterator和listIterator遍历
不同点：
1）线程安全性不一样
ArrayList是非线程安全； Vector是线程安全的，它支持同步。
ArrayList适用于单线程，Vector适用于多线程。
2） 对序列化支持不同
ArrayList支持序列化，而Vector不支持；即ArrayList有实现java.io.Serializable接口，而Vector没有实现该接口。
3） 构造函数个数不同
ArrayList有3个构造函数，而Vector有4个构造函数。Vector除了包括和ArrayList类似的3个构造函数之外，另外的一个构造函数可以指定容量增加系数。
4）容量增加方式不同
若ArrayList容量不足时，“新的容量”=“(原始容量x3)/2 + 1”。
而Vector的容量增长与“增长系数有关”，若指定了“增长系数”，且“增长系数有效(即，大于0)”；那么，每次容量不足时，“新的容量”=“原始容量+增长系数”。若增长系数无效(即，小于/等于0)，则“新的容量”=“原始容量 x 2”。
5）对Enumeration的支持不同。Vector支持通过Enumeration去遍历，而ArrayList不支持。
三：Map类集框架

1，Map概括
Map的框架图：

(1) Map 是“键值对”映射的抽象接口。
(2) AbstractMap 实现了Map中的绝大部分函数接口。
(3) SortedMap 是有序的“键值对”映射接口。
(4) NavigableMap 是继承于SortedMap的，支持导航函数的接口。
(5) HashMap, Hashtable, TreeMap, WeakHashMap这4个类是“键值对”映射的实现类。
2，HashMap, Hashtable, TreeMap, WeakHashMap这4个类的区别：

区别	散列表的实现	元素是否有序	适用场景
HashMap	拉链法	无序	单线程	key为强健
WeakHashMap	拉链法	无序	单线程	key为弱键
Hashtable	拉链法	无序	多线程
TreeMap	红黑树	有序	单线程

具体介绍如下：
2.1 HashMap和Hashtable的异同点
相同点：
（1）HashMap和Hashtable都是存储“键值对(key-value)”的散列表，
（2）都是采用拉链法实现的。
（3）映射无序
（4）都实现了Map、Cloneable、java.io.Serializable接口。
（5）默认的“加载因子”是0.75
不同点：
(1) 继承方式不同:
HashMap 继承于AbstractMap， Dictionary是一个抽象类，它直接继承于Object类，没有实现任何接口。
Hashtable 继承于Dictionary， AbstractMap是一个抽象类，它实现了Map接口的绝大部分API函数；
（2）线程安全不同：
Hashtable是线程安全的，支持多线程。
HashMap的函数则是非同步的，它不是线程安全的。
若要在多线程中使用HashMap，需额外的进行同步处理。 对HashMap的同步处理可以使用Collections类提供的synchronizedMap静态方法，或者直接使用JDK 5.0之后提供的java.util.concurrent包里的ConcurrentHashMap类。
（3）对null值的处理不同：
HashMap的key、value都可以为null。
Hashtable的key、value都不可以为null。
（4）支持的遍历种类不同：
HashMap只支持Iterator(迭代器)遍历。
而Hashtable支持Iterator(迭代器)和Enumeration(枚举器)两种方式遍历。
（5）通过Iterator迭代器遍历时，遍历的顺序不同：
HashMap是“从前向后”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。
Hashtable是“从后往前”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。
（6）容量的初始值 和 增加方式不一样:
HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”。
Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”。
（7）添加key-value时的hash值算法不同：
HashMap添加元素时，是使用自定义的哈希算法。
Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。
（8）部分API不同
Hashtable支持contains(Object value)方法，而且重写了toString()方法；
而HashMap不支持contains(Object value)方法，没有重写toString()方法。

HashMap和Hashtable使用的情景：
(1)， 在单线程中，选择HashMap；在多线程中，选择Hashtable。
(2)，若不能插入null元素，则选择Hashtable；否则，可以选择HashMap。

2.2 HashMap和WeakHashMap的异同点

相同点：
（1）它们都是散列表，存储的是“键值对”映射。
（2） 它们都继承于AbstractMap，并且实现Map基础。
（3） 它们的构造函数都一样。
（4） 默认的容量大小是16，默认的加载因子是0.75。
（5） 它们的“键”和“值”都允许为null。
（6） 它们都是“非同步的”，（即：线程不安全）。

不同点：
（1）HashMap实现了Cloneable和Serializable接口，而WeakHashMap没有。
（2）HashMap的“键”是“强引用(StrongReference)”，而WeakHashMap的键是“弱引用(WeakReference)”。
WeakReference的“弱键”能实现WeakReference对“键值对”的动态回收。当“弱键”不再被使用到时，GC会回收它，WeakReference也会将“弱键”对应的键值对删除。

四，Set架构

1，Set架构
Set的框架图：
(1) Set 是继承于Collection的接口。它是一个不允许有重复元素的集合。
(2) AbstractSet 是一个抽象类，它继承于AbstractCollection，AbstractCollection实现了Set中的绝大部分函数。
(3) HastSet 和 TreeSet 是Set的两个实现类。
HashSet依赖于HashMap，它实际上是通过HashMap实现的。HashSet中的元素是无序的。
TreeSet依赖于TreeMap，它实际上是通过TreeMap实现的。TreeSet中的元素是有序的。

2，HashSet

（1）HashSet是一个没有重复元素的集合，它不保证元素顺序，允许使用null元素。它是通过HashMap实现的。HashSet中含有一个"HashMap类型的成员变量"map"，HashSet的操作函数，实际上都是通过map实现的。
（2）HashSet通过iterator()返回的迭代器是fail-fast的。HashSet是不同步的。
（3）HashMap的继承关系：

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractSet<E>
               ↳     java.util.HashSet<E>

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable { }

(4)两种遍历方式：
通过Iterator遍历HashSet

for(Iterator iterator = set.iterator();
       iterator.hasNext(); ) { 
    iterator.next();
}   

通过for-each遍历HashSet

String[] arr = (String[])set.toArray(new String[0]);
for (String str:arr)
    System.out.printf("for each : %s\n", str);

3, TreeSet

（1）TreeSet的本质是一个"有序的，并且没有重复元素"的集合，通过TreeMap实现的。TreeSet中含有一个"NavigableMap类型的成员变量"m，而m实际上是"TreeMap的实例"
（2）TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
（3）TreeSet为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。
（4）TreeSet是非同步的（非线程安全）。 它的iterator 方法返回的迭代器是fail-fast的。
（5）TreeSet的继承关系

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractSet<E>
               ↳     java.util.TreeSet<E>

public class TreeSet<E> extends AbstractSet<E>        
    implements NavigableSet<E>, Cloneable, java.io.Serializable{}

（6）支持三种遍历方式
Iterator顺序遍历

for(Iterator iter = set.iterator(); iter.hasNext(); ) { 
    iter.next();
}   

Iterator顺序遍历

for(Iterator iter = set.descendingIterator(); iter.hasNext(); ) { 
    iter.next();
}

for-each遍历HashSet

String[] arr = (String[])set.toArray(new String[0]);
for (String str:arr)
    System.out.printf("for each : %s\n", str);

TreeSet不支持快速随机遍历，只能通过迭代器进行遍历！

五，Iterator 和 Enumeration
Iterator 和 Enumeration都是用来遍历集合的，那么它们之间有什么区别呢？通过一张表格来看：

	Enumeration	Iterator
函数接口	2个	3个
对集合的操作	只能读	可读可删
fail-fast	不支持	支持
使用此接口的类	vector, Hashtable,strack	HashMap, ArrayList
遍历速度	快	慢

为什么Enumeration 比 Iterator 的遍历速度更快呢？
因为Iterator是通过Enumeration去实现的，而且Iterator添加了对fail-fast机制的支持；所以，执行的操作自然要多一些。