一木西、集合框架源碼分析
- 集合框架 （第 01 篇） 源碼分析：Collection<E> 框架總覽
- 集合框架 （第 02 篇） 源碼分析：Map<K,V > 框架總覽
- 集合框架 （第 03 篇） 源碼分析：ArrayList<E>
- 集合框架 （第 04 篇） 源碼分析：LinkedList
- 集合框架 （第 05 篇） 源碼分析：Map<K, V>接口與其內(nèi)部接口Entry<K,V>
- 集合框架 （第 06 篇） 源碼分析：哈希沖突(哈希碰撞)與解決算法
- 集合框架 （第 07 篇） 源碼分析：jdk1.7版 HashMap
- 集合框架 （第 08 篇） 源碼分析：HashMap畴栖、Hashtable、ConcurrentHashMap之間的區(qū)別
- 集合框架 （第 09 篇） 源碼分析：jdk1.7版 ConcurrentHashMap
- 集合框架 （第 10 篇） 源碼分析：二叉樹户魏、平衡二叉樹驶臊、二叉查找樹、AVL樹叼丑、紅黑樹
- 集合框架 （第 11 篇） 源碼分析：jdk1.8版 HashMap
- 集合框架 （第 12 篇） 源碼分析：jdk1.8版 ConcurrentHashMap
- 集合框架 （第 13 篇） 源碼分析：LinkedHashMap
- 集合框架 （第 14 篇） 源碼分析：TreeMap
- 集合框架 （第 15 篇） 源碼分析：Set<E> 集合
- 集合框架 （第 16 篇） 源碼分析：BlockingQueue 接口
- 集合框架 （第 17 篇） 源碼分析：CopyOnWriteArrayList 與 CopyOnWriteArraySet
原文持續(xù)更新鏈接: https://github.com/about-cloud/JavaCore
正文
本文關(guān)注點
★★★★★本文重點：ArrayList自動擴(kuò)容機(jī)制（1.5倍或1.5倍-1 擴(kuò)容）
一关翎、ArrayList
ArrayList是動態(tài)數(shù)組，其動態(tài)性體現(xiàn)在能夠
動態(tài)擴(kuò)容鸠信、動態(tài)縮容纵寝。（其原理是構(gòu)建一個新Object數(shù)組，將原數(shù)組復(fù)制進(jìn)去。借助Arrays.copyOf(T[] original, int newLength)）爽茴。
ArrayList繼承關(guān)系
重要的屬性
// 默認(rèn)初始容量為 10（當(dāng)ArrayList的容量低于9時才會用到）
private static final int DEFAULT_CAPACITY = 10;
// 存放數(shù)據(jù)的數(shù)組葬凳，數(shù)組的每個位置并不一定都填充數(shù)據(jù)，用transient修飾避免序列化室奏、避免浪費資源
transient Object[] elementData;
// 記錄實際存放的元素個數(shù)
private int size;
// 記錄著ArrayList的修改次數(shù),也就每次add或remove火焰，它的值都會加1
protected transient int modCount = 0;
1.1、一般添加元素的方法 public boolean add(E e)
public boolean add(E e) {
// modCount++胧沫，并且校驗容量昌简，不夠用就擴(kuò)容
ensureCapacityInternal(size + 1); // 增加 modCount
// 將新元素添加到新數(shù)組size位置，并將size加1（千萬不要理解成將新元素添加到size+1的位置）
elementData[size++] = e;
return true;
}
// 確保容量夠用
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 下標(biāo)溢出表示容量不夠用
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
本文重點方法★★★★★ ArrayList 擴(kuò)容方法 grow(int minCapacity)
// 擴(kuò)容方法
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// ArrayList 的擴(kuò)容是 1.5 倍 或 1.5 倍 - 1
// oldCapacity為偶數(shù)按1.5倍擴(kuò)容绒怨，oldCapacity為奇數(shù)按1.5倍-1擴(kuò)容
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 該拷貝為深拷貝纯赎，將原來的數(shù)組復(fù)制到新的數(shù)組并返回新的數(shù)組
elementData = java.util.Arrays.copyOf(elementData, newCapacity);
}
雖然上面的代碼不多，但是添加元素遇到經(jīng)常擴(kuò)容的現(xiàn)象要格外留心南蹂，因為頻繁的擴(kuò)容勢必帶來頻繁的數(shù)組拷貝犬金，這會大大犧牲性能，所以有必要在 ArrayList 初始化時指定容量六剥。初始化的容量也不要太大于實際存儲容量晚顷，不然會造成空間浪費，所以都要權(quán)衡利弊疗疟。
1.2音同、在指定位子添加方法 public void add(int index, E element)
// 注意：在指定 index 位置添加元素，并不會覆蓋該處的元素秃嗜，而是 index位置及其之后的元素后移
public void add(int index, E element) {
// 只要有index，必定會檢查range
rangeCheckForAdd(index);
// 確保容量夠用（否則就擴(kuò)容）
ensureCapacityInternal(size + 1); // Increments modCount!!
// 這里是在指定位置index添加元素的關(guān)鍵：從index處顿膨，將數(shù)據(jù)后移 1 位锅锨，空出index處給新元素用
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 上一步已將index處的位置空出來，現(xiàn)在將新元素添加到index處
elementData[index] = element;
// 實際存儲的元素數(shù)加1
size++;
}
2.1恋沃、刪除元素 public boolean remove(Object o)
public boolean remove(Object o) {
// 兩種情況必搞，被刪除的元素是否為 null
// for 循環(huán)遍歷、判斷囊咏、刪除（請注意：千萬不要使用 foreach 進(jìn)行刪除Ｋ≈蕖！Ｃ犯睢）
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])) {
fastRemove(index);
return true;
}
}
// 如果刪除了霜第，返回為true，否則返回false户辞。
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
* 跳過邊界檢查的私有移除方法泌类，并且不返回刪除的值
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
// 重點在這里，數(shù)據(jù)向前移動
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 清除 size-1 位置上的元素（設(shè)置空引用）底燎，讓GC去收集該元素刃榨，同時 size 減 1
elementData[--size] = null;
}
注意:
- 如果存在多個對象o,僅僅刪除距離 index = 0 處最近的一個元素;
- 元素被刪除后弹砚，該位置不會空出來，后面的元素會前移枢希。
所以 ArrayList 適合讀多刪少場景桌吃。
3、重新設(shè)置指定index位置的元素值 public E set(int index, E element)
public E set(int index, E element) {
// 有index苞轿，必檢查
rangeCheck(index);
// 返回舊的（被重置的）元素
E oldValue = elementData(index);
// 直接把 index位置的元素覆蓋掉行了
elementData[index] = element;
return oldValue;
}
4茅诱、獲取指定index位置的元素 public E get(int index)
public E get(int index) {
// 還是那句話，凡是遇到index索引呕屎，必檢查
rangeCheck(index);
// 直接返回index的元素让簿，數(shù)組查詢還不快嗎。
return elementData(index);
}
E elementData(int index) {
// 因為 ArrayList 本質(zhì)上是個數(shù)組秀睛，直接通過index獲取元素
return (E) elementData[index];
}
5尔当、判斷元素是否存儲 public boolean contains(Object o) 判斷是否存在某個元素
public boolean contains(Object o) {
// 簡單粗暴，直接遍歷查看index是否大于0
return indexOf(o) >= 0;
}
// 查找元素是否存在蹂安，如果存在返回下標(biāo)椭迎，否則返回 -1
public int indexOf(Object o) {
// 遍歷的時候分兩種情況，是否為 null
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
// 用 equals 判斷值是否相等
if (o.equals(elementData[i]))
return i;
}
return -1;
}
二田盈、ArrayList的親兄弟 Vector
Vector 的大部分方法是被
synchronized修飾的畜号。
線程安全的ArrayList，幾乎所有的方法都加synchronized修飾允瞧；
三简软、Stack
Stack 繼承至 Vector，是一個
后進(jìn)先出LIFO的隊列述暂。
它實現(xiàn)了一個標(biāo)準(zhǔn)的后進(jìn)先出LIFO的棧痹升。
