1. 集合類概述
Java中以一種比數(shù)組存儲(chǔ)更復(fù)雜的方式來存儲(chǔ)對(duì)象的一組對(duì)象---“容器類”核蘸，其基本類
型有List、Set和Map蒋得，它們被組織在以Collection及Map接口為根的層次結(jié)構(gòu)中际看，稱之為集合框架掌实。
2. Collection接口
Collection的層次結(jié)構(gòu)圖
2.1 List篇
List的特征是其元素以線性的方式的存儲(chǔ)，集合中允許放重復(fù)元素听想。
List接口主要的實(shí)現(xiàn)類有：
- ArrayList() : 代表長度可以動(dòng)態(tài)改變的數(shù)組腥刹；可以對(duì)元素進(jìn)行隨機(jī)的訪問，向ArrayList
中插入與刪除元素的速度慢汉买。
- LinkedList() : 采用鏈表結(jié)構(gòu)實(shí)現(xiàn)衔峰。其插入和刪除的速度快。
2.1.1 List遍歷方式：
(1)for循環(huán)遍歷
/**
* List中的get(int index)方法支持取指定下標(biāo)的元素
*/
1)使用一般for循環(huán)
for(int i = 0 ; i < list.size ; i ++) {
E obj = list.get(i);
}
2)使用增強(qiáng)型for循環(huán)
for(E obj : list) {
}
(2)使用迭代器（Iterator）
/**
* Collection集合接口繼承了Iterator接口蛙粘，允許集合被迭代
* 迭代方式如下：
*/
Iterator<E> it = list.iterator();
while(it.hasNext()) {
E obj = it.next();
}
2.1.2 ArrayList實(shí)現(xiàn)原理
ArrayList部分源碼分析：
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
// 存放元素的數(shù)組
private transient Object[] elementData;
/* 構(gòu)造方法垫卤，
* @param initialCapacity : 設(shè)置數(shù)組的初始容量
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
從源碼可以分析出：ArrayList采用一個(gè)Object型對(duì)象數(shù)組來存放元素，默認(rèn)初始容量為10出牧。
public boolean add(E e) {
// 當(dāng)添加元素時(shí)判斷數(shù)組容量超出可容納范圍時(shí)會(huì)自動(dòng)擴(kuò)容
// 具體會(huì)調(diào)用grow(int minCapacity)方法
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 該方法會(huì)自動(dòng)給數(shù)組擴(kuò)大一倍,數(shù)組可被擴(kuò)大的最大容量為Integer.MAX_VALUE
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
....省略部分代碼
}
2.1.3 LinkedList實(shí)現(xiàn)原理
LinkedList采用雙向鏈表結(jié)構(gòu)來實(shí)現(xiàn)的,使用結(jié)點(diǎn)來存儲(chǔ)數(shù)據(jù)域和連接前一個(gè)和后一個(gè)結(jié)點(diǎn).
static class Node<E> {
E item; // 用來保存數(shù)據(jù)域
Node<E> next; // 下一個(gè)結(jié)點(diǎn)
Node<E> prev; // 上一個(gè)結(jié)點(diǎn)
....此處省略
}
// 代指第一個(gè)結(jié)點(diǎn)
transient Node<E> first;
transient Node<E> last;
// 這里只做add方法的講解
public boolean add(E e) {
// 鏈接下一個(gè)結(jié)點(diǎn)
linkLast(e);
return true;
}
void linkLast(E e) {
// 保存當(dāng)前的最后一個(gè)結(jié)點(diǎn)
final Node<E> l = last;
//創(chuàng)建一個(gè)新添加元素的結(jié)點(diǎn)穴肘，前一個(gè)結(jié)點(diǎn)為該鏈表的最后一個(gè)結(jié)點(diǎn)
final Node<E> newNode = new Node<E>(l , e , null);
// 將新結(jié)點(diǎn)作為最后一個(gè)結(jié)點(diǎn)
last = newNode;
// 如果未添加前最后一個(gè)結(jié)點(diǎn)為空，則說明此時(shí)鏈表沒有元素舔痕，將新結(jié)點(diǎn)作為首結(jié)點(diǎn)
// 否則將新結(jié)點(diǎn)鏈接在末尾
if(l != null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
LinkedList數(shù)據(jù)結(jié)構(gòu)是鏈?zhǔn)浇Y(jié)構(gòu)评抚，具體查閱數(shù)據(jù)結(jié)構(gòu)相關(guān)的書籍。
2.1.4 ArrayList和LinkedList比較
ArrayList和LinkedList的區(qū)別：
1.ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)伯复，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)盈咳。
2.對(duì)于隨機(jī)訪問get和set，ArrayList覺得優(yōu)于LinkedList边翼，因?yàn)長inkedList要移動(dòng)指針。
3.對(duì)于新增和刪除操作add和remove鸣剪，LinedList比較占優(yōu)勢(shì)组底，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)丈积。
2.2 List使用場(chǎng)景
如果涉及到“棧”债鸡、“隊(duì)列”江滨、“鏈表”等操作，應(yīng)該考慮用List厌均，具體的選擇哪個(gè)List唬滑，根據(jù)下面的標(biāo)準(zhǔn)來取舍。
01) 對(duì)于需要快速插入棺弊，刪除元素晶密，應(yīng)該使用LinkedList。
02) 對(duì)于需要快速隨機(jī)訪問元素模她，應(yīng)該使用ArrayList稻艰。
03) 對(duì)于“單線程環(huán)境” 或者 “多線程環(huán)境，但List僅僅只會(huì)被單個(gè)線程操作”侈净，此時(shí)應(yīng)該使用非同步的類(如ArrayList)尊勿。
對(duì)于“多線程環(huán)境，且List可能同時(shí)被多個(gè)線程操作”畜侦，此時(shí)元扔，應(yīng)該使用同步的類(如Vector)。