引言
如果一個程式隻包含固定數量的且其生命周期都是已知對象，那麼這是一個非常簡單的程式——《think in java》
了解容器前，先提出一個問題，ArrayList和LinkedList誰的處理速度更快呢？
一 持有對象的方式
在Java中，我們可以使用數組來儲存一組對象。但是，數組是固定大小的，在一般情況下，我們寫程式時并不知道将需要多少個對象，是以數組固定大小對于程式設計有些受限。
java類庫中提供了一套相當完整的容器類來解決這個問題，其中基本類型有List，Queue，Set，Map，這些對象類型被稱為集合類。但是，Java類庫中使用了Collection來指代集合類中的子集{List，Queue，Set}，是以集合類也被稱為容器。容器提供了完善的方法來儲存對象。
二 類型安全的容器
java采用泛型保證我們不會向容器中插入不正确的類型，但是java的泛型隻存在于程式源碼中，在經過編譯器編譯就會将類型擦除。舉一個例子：
//經過編譯前
List list = new ArrayList<>();
list.add("ok");
System.out.println(list.get(0));
//經過編譯後
List list = new ArrayList();
list.add("ok");
System.out.println((String)list.get(0));
這樣做的好處是:在編寫程式的時候，不會将其他非導出類型的對象添加到容器中。
三 List
數組存儲多個對象的原因是它提前聲明了能存儲多少對象。那容器又是如何實作存儲不定多對象的呢？
//ArrayList部分源碼
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity) {
super();
if (initialCapacity
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
我們可以看到，在ArrayList類中有一個elementData數組。當使用無參構造函數時數組長度預設為空，當向arraylist加入對象時，會調用一個方法來判斷數組是否能放下這個對象。當數組為空時設定數組長度為10并申請相應大小空間，當數組已滿時，最少重新申請原數組大小1.5倍的空間(除非達到int類型最大值-8)。而在LinkedList中卻沒有采用這種方式，而是采用連結清單方式。
//LinkedList add方法
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
在LinkedList中，他的add方法調用了linkLast方法，直接在連結清單後邊加入一個新的節點。
四 Set
Set類型不儲存重複的元素。判斷對象元素是否相等采用的是equals方法，是以在存入自定義的對象時，如果重寫equals方法依賴于可變屬性，将會導緻一些問題。
五 Map
map類型是能夠将對象映射到其他對象的一種容器，有差別于list的get方法。hashset類中包含了一個hashmap對象，hashset的實作依靠hashmap。
hashmap的實作采用了數組連結清單的方式，即數組的每一個位置都存放的是連結清單頭。查找會先通過key的hash找到對應數組下标，再在該數組下标所對應的連結清單中找到是否有對應對象，查找方式為equals方法。
六 Queue
隊列是一種典型的先進先出的容器，LinkedList實作了Queue接口。PriorityQueue實作了優先級隊列。ArrayDeque是一個用數組實作雙端隊列的類，我們來看一下ArrayDeque類中的一些方法。
public ArrayDeque() {
elements = (E[]) new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
elements = (E[]) new Object[initialCapacity];
}
上邊的代碼是ArrayDeque的構造方法，可以看到，當沒有定義大小時，ArrayDeque預設數組大小為16，而定義大小後，會調用allocateElements方法，這個方法的作用是：當給定長度小于最小長度8時，使用最小長度。若大于等于最小長度，則找到比給定長度大的最小的2的幂數。為什麼要是2的幂數呢？原因有以下兩點：
作業系統配置設定記憶體的方法使用夥伴系統的話，每一塊的大小都是2的幂數，如果配置設定的記憶體大小為2的幂數，可以減少記憶體配置設定的時間。夥伴系統在百度百科中的解釋：http://baike.baidu.com/view/4935190.htm
在ArrayDeque的addFirst方法中不固定将頭放在數組的第一位，而是循環移位。使用2的幂數能夠有效判斷頭部所在的位址。
同樣在第二點中，如果隊列滿了，數組擴充是将容量capacity值左移一位即可擴充一倍。
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n <
if (newCapacity
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = (E[])a;
head = 0;
tail = n;
}
七 List的選擇
在文章開頭提出了一個問題，數組實作的List快還是連結清單實作的List快。模拟一下試試：
public static void add()
{
long start = 0;
long end = 0;
List alist = new ArrayList<>();
List llist = new LinkedList<>();
System.out.println("ArrayList添加1000萬資料所需毫秒數");
start = System.currentTimeMillis();
for (int i=0; i<10000000; i++)
{
alist.add(i);
}
end = System.currentTimeMillis();
System.out.println(end-start);
System.out.println("LinkedList添加1000萬資料所需毫秒數");
start = System.currentTimeMillis();
for (int i=0; i<10000000; i++)
{
llist.add(i);
}
end = System.currentTimeMillis();
System.out.println(end-start+"\n");
System.out.println("ArrayList從1000萬資料删除資料所需毫秒數");
start = System.currentTimeMillis();
alist.remove(0);
alist.remove(2000000);
alist.remove(4000000);
alist.remove(6000000);
alist.remove(8000000);
alist.remove(9999994);
end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println("LinkedList從1000萬資料删除資料所需毫秒數");
start = System.currentTimeMillis();
llist.remove(0);
llist.remove(2000000);
llist.remove(4000000);
llist.remove(6000000);
llist.remove(8000000);
llist.remove(9999994);
end = System.currentTimeMillis();
System.out.println(end - start+"\n");
System.out.println("ArrayList從1000萬資料查找資料所需毫秒數");
start = System.currentTimeMillis();
alist.contains(0);
alist.contains(2000000);
alist.contains(4000000);
alist.contains(6000000);
alist.contains(8000000);
alist.contains(10000000);
end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println("LinkedList從1000萬資料查找資料所需毫秒數");
start = System.currentTimeMillis();
llist.contains(0);
llist.contains(2000000);
llist.contains(4000000);
llist.contains(6000000);
llist.contains(8000000);
llist.contains(10000000);
end = System.currentTimeMillis();
System.out.println(end - start+"\n");
}
可以看到，無論在何種情況下，數組實作的list都比連結清單快。當我在ArrayList構造方法中設定數組初始大小1000萬時，ArrayLIst添加資料的速度慢了下來，降到5000毫秒左右，是以一般情況下不需要優化。
總結
簡單容器類圖：
Java的容器分為兩類，一類是Collection，一類是Map。collection中包含三種集合類型：Set，List，Queue。
如果想要set中的資料有序，請使用TreeSet。
HashTable和Vector是線程安全的，但是不建議使用，請使用java.util.concurrent包下的容器。
HashMap允許key/value值為null。