最近在整理JAVA 基礎知識，從jdk源碼入手，今天就jdk中 java.util包下集合類進行了解
先看圖
從類圖結構可以了解 java.util包下的2個大類：
1、Collecton：可以了解為主要存放的是單個對象
2、Map：可以了解為主要存儲key-value類型的對象
一、Collection
Collection繼承了Iterate接口，Iterate用于集合内疊代器抽象接口，其子類均實作接口中方法，看下ArrayList下實作：
1 /**
2 * Returns an iterator over the elements in this list in proper sequence.
3 *
4 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
5 *
6 * @return an iterator over the elements in this list in proper sequence
7 */
8 public Iterator<E> iterator() {
9 return new Itr(); // 傳回内部類執行個體
10 }
11
12 /**
13 * An optimized version of AbstractList.Itr
14 */
15 private class Itr implements Iterator<E> {
16 int cursor; // index of next element to return 指向下一個位置索引id
17 int lastRet = -1; // index of last element returned; -1 if no such 指向上一個位置索引id
18 int expectedModCount = modCount;
19
20 public boolean hasNext() {
21 return cursor != size;
22 }
23
24 @SuppressWarnings("unchecked")
25 public E next() {
26 checkForComodification();
27 int i = cursor;
28 if (i >= size)
29 throw new NoSuchElementException();
30 Object[] elementData = ArrayList.this.elementData;
31 if (i >= elementData.length)
32 throw new ConcurrentModificationException();
33 cursor = i + 1;
34 return (E) elementData[lastRet = i];
35 }
36
37 public void remove() {
38 if (lastRet < 0)
39 throw new IllegalStateException();
40 checkForComodification();
41
42 try {
43 ArrayList.this.remove(lastRet);
44 cursor = lastRet;
45 lastRet = -1;
46 expectedModCount = modCount;
47 } catch (IndexOutOfBoundsException ex) {
48 throw new ConcurrentModificationException();
49 }
50 }
51
52 @Override
53 @SuppressWarnings("unchecked")
54 public void forEachRemaining(Consumer<? super E> consumer) {
55 Objects.requireNonNull(consumer);
56 final int size = ArrayList.this.size;
57 int i = cursor;
58 if (i >= size) {
59 return;
60 }
61 final Object[] elementData = ArrayList.this.elementData;
62 if (i >= elementData.length) {
63 throw new ConcurrentModificationException();
64 }
65 while (i != size && modCount == expectedModCount) {
66 consumer.accept((E) elementData[i++]);
67 }
68 // update once at end of iteration to reduce heap write traffic
69 cursor = i;
70 lastRet = i - 1;
71 checkForComodification();
72 }
73
74 final void checkForComodification() {
75 if (modCount != expectedModCount)
76 throw new ConcurrentModificationException();
77 }
78 } 1、List
特點：有序結果、順序周遊、索引、允許有重複值
(1) ArrayList
以上特點實作：
transient Object[] elementData; // List内部存儲對象數組結果
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 添加對象時先識别是否越界，沒有越界則數組對象目前索引值的下一個添
// 添加對象時，不識别重複，是以有序允許重複值
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
// 清空List時順序周遊值置為null
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
其中 remove方法 ：
public E remove(int index) { // 按索引删除對象
rangeCheck(index); // 校驗輸入索引id是否越界，若越界則抛出運作時異常 IndexOutOfBoundsException
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1; // 定位到索引的下一位
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved); //調用native方法實作數組位置左移
elementData[--size] = null; // clear to let GC do its work
// 末尾元素置空
return oldValue;
}
public boolean remove(Object o) {// 按對象删除
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) { // 識别對象相等使用equals方法，使用時注意重寫equals方法
fastRemove(index);
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++; // 删除元素時，modCount值變更
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
} 可以看到ArrayList中對數組進行，操作時常用到System.arraycopy
java.lang.System下
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length); 還有在 java.util.Arrays下數組copy方法，最終也是調用System.arraycopy方法
1 public static <T> T[] copyOf(T[] original, int newLength) {
2 return (T[]) copyOf(original, newLength, original.getClass());
3 }
4
5 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
6 @SuppressWarnings("unchecked")
7 T[] copy = ((Object)newType == (Object)Object[].class)
8 ? (T[]) new Object[newLength]
9 : (T[]) Array.newInstance(newType.getComponentType(), newLength);
10 System.arraycopy(original, 0, copy, 0,
11 Math.min(original.length, newLength));
12 return copy;
13 } 示例：
1 package jdk.array;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5 import java.util.Iterator;
6
7 public class ArrayListTest1 {
8
9 public static void main(String[] args) {
10
11 ArrayList<String> l1 = new ArrayList<>();
12 l1.add("s1");
13 l1.add("s2");
14 l1.add("s1");
15 l1.add("s2");
16 l1.add("s2");
17 l1.add("s2");
18 l1.add("s3");
19 l1.add("s3");
20 l1.add("s3");
21
22 // 使用容器疊代器周遊List
23 Iterator<String> iterator = l1.iterator();
24 while (iterator.hasNext()) {
25 String str = iterator.next();
26 if ("s1".equals(str)) {
27 iterator.remove(); // 疊代器内部方法remove()
28 }
29 }
30 System.out.println(Arrays.toString(l1.toArray()));
31
32 // 使用 for循環周遊List
33 for(int i = 0 ; i < l1.size(); i++) {
34 if ("s2".equals(l1.get(1))) {
35 l1.remove(i);
36 i--;
37 }
38 }
39 System.out.println(Arrays.toString(l1.toArray()));
40
41 // 使用foreach周遊List
42 for (String str : l1) {
43 if ("s3".equals(str)) {
44 l1.remove(str); // ArrayList内部方法remove(Object)
45 }
46 }
47 System.out.println(Arrays.toString(l1.toArray()));
48 }
49
50 } View Code
可以看到出現異常：ConcurrentModificationException，出現該異常原因是：
“快速失敗”也就是fail-fast，它是Java集合的一種錯誤檢測機制。當建立Iterator後，在Iterator使用還沒有結束時，改變（删除或增添新項）集合元素就會出現上面的錯誤
看看ArrayList的排序方法：sort(Comparator<? super E> c)
1 public void sort(Comparator<? super E> c) {
2 final int expectedModCount = modCount;
3 Arrays.sort((E[]) elementData, 0, size, c);
4 if (modCount != expectedModCount) {
5 throw new ConcurrentModificationException();
6 }
7 modCount++;
8 }
9
10 public static <T> void sort(T[] a, int fromIndex, int toIndex,
11 Comparator<? super T> c) {
12 if (c == null) {
13 sort(a, fromIndex, toIndex);
14 } else {
15 rangeCheck(a.length, fromIndex, toIndex);
16 if (LegacyMergeSort.userRequested)
17 legacyMergeSort(a, fromIndex, toIndex, c);
18 else
19 TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
20 }
21 } 示例：
1 package jdk.array;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5 import java.util.Comparator;
6 import java.util.Iterator;
7
8 public class ArrayListTest2 {
9
10 public static void main(String[] args) {
11
12 ArrayList<String> l1 = new ArrayList<>();
13 l1.add("s1");
14 l1.add("s2");
15 l1.add("s1");
16 l1.add("s2");
17 l1.add("s2");
18 l1.add("s2");
19 l1.add("s3");
20 l1.add("s3");
21 l1.add("s3");
22
23 System.out.println(Arrays.toString(l1.toArray()));
24
25 l1.sort(null);
26
27 System.out.println(Arrays.toString(l1.toArray()));
28
29 l1.sort(new Comparator() {
30
31 @Override
32 public int compare(Object o1, Object o2) {
33
34 return -((String) o1).compareTo((String) o2);
35 }
36
37 });
38
39 System.out.println(Arrays.toString(l1.toArray()));
40
41 }
42
43 } View Code
(2)LinkedList
1 public class LinkedList<E>
2 extends AbstractSequentialList<E>
3 implements List<E>, Deque<E>, Cloneable, java.io.Serializable
4 // 實作了Deque接口，可以做隊列使用
5
6 /**
7 * Pointer to first node.
8 * Invariant: (first == null && last == null) ||
9 * (first.prev == null && first.item != null)
10 */
11 transient Node<E> first;
12
13 /**
14 * Pointer to last node.
15 * Invariant: (first == null && last == null) ||
16 * (last.next == null && last.item != null)
17 */
18 transient Node<E> last;
19
20 /**
21 * Constructs an empty list.
22 */
23 public LinkedList() {
24 }
25
26 // 集合對象存儲結構，通過目前節點的前後節點，維護順序集合（雙向連結清單結構）
27 private static class Node<E> {
28 E item;
29 Node<E> next;
30 Node<E> prev;
31
32 Node(Node<E> prev, E element, Node<E> next) {
33 this.item = element;
34 this.next = next;
35 this.prev = prev;
36 }
37 } 以上為 LinkedList的内部存儲結構，以Node存儲。
在看下集合元素插入、删除及擷取方法實作：
1 public boolean add(E e) {
2 linkLast(e);
3 return true;
4 }
5
6 /**
7 * Links e as last element.
8 */
9 void linkLast(E e) {
10 final Node<E> l = last; // 儲存最後個節點
11 final Node<E> newNode = new Node<>(l, e, null);// 新增節點
12 last = newNode; // 将新節點置為最後節點
13 if (l == null)
14 first = newNode;
15 else
16 l.next = newNode;
17 size++;
18 modCount++;
19 }
20
21 public E remove() {
22 return removeFirst(); // 去掉首節點
23 }
24
25 public E removeFirst() {
26 final Node<E> f = first;
27 if (f == null)
28 throw new NoSuchElementException();
29 return unlinkFirst(f);
30 }
31
32 private E unlinkFirst(Node<E> f) {
33 // assert f == first && f != null;
34 final E element = f.item;
35 final Node<E> next = f.next;
36 f.item = null;
37 f.next = null; // help GC
38 first = next;
39 if (next == null)
40 last = null;
41 else
42 next.prev = null;
43 size--;
44 modCount++;
45 return element;
46 }
47
48 // 入棧方法
49 public void push(E e) {
50 addFirst(e);
51 }
52 // 出棧方法
53 public E pop() {
54 return removeFirst();
55 }
56
57 // 入隊
58 public boolean offer(E e) {
59 return add(e);
60 }
61 public boolean add(E e) {
62 linkLast(e);
63 return true;
64 }
65 // 出隊
66 public E poll() {
67 final Node<E> f = first;
68 return (f == null) ? null : unlinkFirst(f);
69 }
70
71 //随機通路集合對象
72 public E get(int index) {
73 checkElementIndex(index);
74 return node(index).item;
75 }
76
77 /**
78 * Returns the (non-null) Node at the specified element index.
79 */
80 Node<E> node(int index) {
81 // assert isElementIndex(index);
82 // 識别 index id離首節點近還是尾節點近，減少周遊
83 if (index < (size >> 1)) {
84 Node<E> x = first;
85 for (int i = 0; i < index; i++) // 0(i)
86 x = x.next;
87 return x;
88 } else {
89 Node<E> x = last;
90 for (int i = size - 1; i > index; i--) // 0(i)
91 x = x.prev;
92 return x;
93 }
94 } 通過以上源碼了解 ArrayList 和 LinkedList 差別類似資料結構中 數組及連結清單結構差別 ，新增、删除 和 随機通路存在 效率上的差别：
ArrayList是最常用的集合，其内部實作是一個數組，ArrayList的大小是可以動态擴充的。對于元素的随機通路效率高，其通路的時間複雜度為
O(1)
，對于資料的插入與删除，從尾部操作效率高，時間複雜度和随機通路一樣是
O(1)
，若是從頭部操作則效率會比較低，因為從頭部插入或删除時需要移動後面所有元素，其時間複雜度為
O(n-i)
(n表示元素個數，i表示元素位置)
LinkList對于随機通路效率是比較低的，因為它需要從頭開始索引，是以其時間複雜度為
O(i)
。但是對于元素的增删，LinkList效率高，因為隻需要修改前後指針即可，其時間複雜度為
O(1)
。
（3）Vector
與ArrayList類型，内部也是使用資料來存儲對象，但是線程安全的，因為實作方法重寫的時候，全部加上了同步關鍵字：synchronized；（一般不建議使用，性能消耗）
（4）Stack
public
class Stack<E> extends Vector<E> {
/**
* Creates an empty Stack.
*/
public Stack() {
} 2、Queue
遵循FIFO（先入先出規則），内部出棧入棧方法，主要差別在于是否是阻塞入隊或出隊
3、Set
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
// Set 集合對象存儲在 Map的 key中
public boolean contains(Object o) {
return map.containsKey(o);
}
// 添加對象到Set集合中
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// 删除Set集合中對象
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
} 實際Set集合的實作依賴于Map的實作，通過Map的 key值唯一性來實作
二、Map
1、HashMap：基于Map接口實作、允許null 鍵值、無序、非同步
一起看下HashMap的實作
// map 内部對象連結清單存儲結構
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; // 下一節點
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
// 重寫hashCode方法
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 重寫 equals方法
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
transient Node<K,V>[] table; // 用數組儲存多條連結清單的首節點
// 擷取 key所對應的存儲JNode的 value值
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 識别是否存在key所對應的 Node
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
} // map 内部對象連結清單存儲結構
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; // 下一節點
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
// 重寫hashCode方法
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 重寫 equals方法
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
transient Node<K,V>[] table; // 用數組儲存多條連結清單的首節點
// 擷取 key所對應的存儲JNode的 value值
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 識别是否存在key所對應的 Node
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
// 插入 對象
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 調用的内部方法，
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab 為map内首節點集合
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 先識别table是否為空，為空則初始化，hashmap記憶體存儲延遲加載在這裡展現
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通過hash值以長度做按位與，識别讀取元素的存儲在tab中的位置
if ((p = tab[i = (n - 1) & hash]) == null)
// 若tab所在連結清單首節點為空，則直接構造新節點
tab[i] = newNode(hash, key, value, null);
else {
// tab所在連結清單首節點不為空，則周遊p所在連結清單或紅黑樹，找到可以存儲的位置
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} 可以看到，在HashMap中存儲的結構下， Node類型的數組儲存頭部節點（單連結清單）或根節點（紅黑樹），先以 Node的key的hash值與數組長度做位與運算（hash碰撞），初始
時使用單連結清單存儲新插入對象（newNode），當連結清單長度超過8時，會将連結清單結構轉為紅黑樹結構存儲（treeifyBin方法）
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 找到需要轉換的 單連結清單 e，周遊單連結清單，轉換為TreeNode,儲存前後節點關系
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//讓桶的第一個元素指向建立的紅黑樹頭結點，以後這個桶裡的元素就是紅黑樹而不是連結清單了
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
} 先将單連結清單轉換為 treenode，在調用 treeify方法構造紅黑樹
2、LinkedHashMap
繼承HashMap，HashMap是無序集合，而LinkedHashMap為有序集合
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V> 構造LinkedHashMap.EntreyNode<K,V> 繼承 HashMap.Node<K,V> 實作雙向連結清單
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after; // before 儲存前置節點，after儲存後置節點
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head; // 頭節點
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail; // 尾部節點
// 重寫HashMap的 建立新節點方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p); // 将新節點放到尾部節點，進而保證順序
return p;
}
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
} 3、TreeMap
TreeMap直接使用紅黑樹結構存儲集合元素，根據鍵 做排序，排序規則按内部 comparator 對象的執行個體對象的排序規則，若comparator為空，則按自然排序
1 public class TreeMap<K,V>
2 extends AbstractMap<K,V>
3 implements NavigableMap<K,V>, Cloneable, java.io.Serializable
4 {
5 /**
6 * The comparator used to maintain order in this tree map, or
7 * null if it uses the natural ordering of its keys.
8 *
9 * @serial
10 */
11 private final Comparator<? super K> comparator; // 對象比較接口
12
13 private transient Entry<K,V> root; // 根節點 root的實作邏輯為 TreeMap.Entrey<K,V> 繼承 Map.Entrey<K,V> 實作 ，與HashMap.TreeNode<K,V>實作類似
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK; 是以TreeMap put和get方法就是以鍵先進行紅黑樹的查找後操作
4、HashTable
HashTable和HashMap資料結構類似，主要差別為HashTable中操作集合元素對象的方法都加上了 同步關鍵字(synchronized), 是以說線程安全的及集合