近在回顧數(shù)據(jù)結(jié)構(gòu)，想到JDK這樣好的代碼資源不利用有點可惜，這是第一篇，花了心思。篇幅有點長，希望想看的朋友認真看下去，提出寶貴的意見。 :)
類繼承體系圖
內(nèi)部原理
ArrayList 的3個字段
private transient Object[] elementData; //對象數(shù)組，用于存儲 持有對象的 引用 private int size; //代表了 ArrayList 的長度。隨著插入 刪除 添加 而改變。 protected transient int modCount = 0; //從AbstractList繼承得到，這個字段最后介紹，先忽視它。
ArrayList保存的真的是對象嗎？
elementData 是一個Object 數(shù)組，這是為了兼容任何類型（Java泛型是所有實際類型共享一份代碼模板的?。。。?。數(shù)組保存的實質(zhì)是持有對象的引用(reference)。引用又可以理解為 對象的“遙控器”（如下圖）。
從底層點的角度說，引用實質(zhì)是指針的化身，因此ArrayList即便持有很多個對象，其本身（或者說elementData 數(shù)組）保存的只不過是引用而已，內(nèi)存開銷不會太大。
所以要強調(diào)的是：對于保存引用類型，java中的數(shù)組，和各種集合類，持有的是對象的引用，而不是對象本身。
構(gòu)造函數(shù)
空ArrayList 的優(yōu)化 ： new 一個空的ArrayList是很常見的做法，為了不讓每個空ArrayList都創(chuàng)建一個空數(shù)組實例，ArrayList內(nèi)部有一個用于共享，靜態(tài)的空數(shù)組對象。當創(chuàng)建空的ArrayList時，內(nèi)部的 elementData 就會指向這個共享的空數(shù)組： EMPTY_ELEMENTDATA
同時也會發(fā)現(xiàn)：當new 一個空ArrayList 時，不會馬上在內(nèi)存中分配 DEFAULT_CAPACITY =10 個長度的elementData數(shù)組，而是等到第一個元素被添加時，才會去申請分配默認長度 為10 的elementData 數(shù)組。
private static final Object[] EMPTY_ELEMENTDATA = {}; //用于所有空ArrayList共享的 空數(shù)組，注意它是靜態(tài)字段。
private static final int DEFAULT_CAPACITY = 10; //第一次分配容量時，默認的初始容量大小//////////////////////////////////////////////
public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; //指向空數(shù)組}
當然，如果在new 時指定了 初始容量initCapacity，就會立刻 創(chuàng)建一個 長度為 initialCapacity 大小的 elementData 數(shù)組
ArrayList( (initialCapacity < 0 IllegalArgumentException("Illegal Capacity: "+.elementData =
也可以從另一個一個集合構(gòu)造
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
容量增長策略
雖然ArrayList 號稱 動態(tài)數(shù)組，其長度自動調(diào)整，但是內(nèi)部 保存持有對象的引用的數(shù)組elementData卻是一個普通的數(shù)組（Java數(shù)組的長度是不可變的），因此，ArrayList就必須實現(xiàn)容量擴展操作，在elementData 滿 時，讓elementData指向長度更大的數(shù)組。
以保證在任何時候：elementData.length >= size
elementData 的長度就 是 ArrayList 的容量（capacity）。
以下是關(guān)于容量調(diào)配的API（綠色標記的是public方法，紅色的是private）
查看源碼時，我發(fā)現(xiàn)，向ArrayList 中添加新元素的時，都會先 使用 ensureCapacityInternal 這個函數(shù)去檢查容量是否夠用。如圖中，參數(shù)為 size+1 ，也就是要保證容量至少為size+1個，這樣新元素才能放得下。我們?nèi)タ纯催@個函數(shù)的實現(xiàn)。
/*函數(shù)作用：用于確保 ArrayList 的容量至少有 參數(shù)指定的minCapacity個*/
private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { //這個if用于處理 往 空ArrayList中添加第一個元素時的情況
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity); //內(nèi)部又委托了這個函數(shù)，繼續(xù)往下看
}
/*函數(shù)作用：用于確保 ArrayList 的容量至少有 參數(shù)指定的minCapacity個*/private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0) //如果當前容量 真的比 要求的 minCapacity 小
grow(minCapacity); //那就交給grow函數(shù)去擴張容量去吧。
}
最終的增長邏輯都是委托g(shù)row() 方法實現(xiàn)的。只要調(diào)用了grow這個函數(shù)，就一定會使容量增加。我們來看看容量到底是怎么增加的。
private void grow(int minCapacity) { // overflow-conscious code
int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //先讓 newCapacity = 原來的1.5倍，這是默認的增長策略。 //再接著來判斷這個策略是否合適
if (newCapacity - minCapacity < 0) //如果變?yōu)樵瓉淼?.5倍還是不夠
newCapacity = minCapacity; //那就要多少給多少吧。
if (newCapacity - MAX_ARRAY_SIZE > 0) //如果要求的容量超大，（大于MAX_ARRAY_SIZE），這個時候就必須慎重。怎么辦？
newCapacity = hugeCapacity(minCapacity); //交給 hugeCapacity函數(shù)去決定到底給多少，這個函數(shù)會返回 MAX_ARRAY_SIZE 或者 Integer.MAX_VALUE。
elementData = Arrays.copyOf(elementData, newCapacity); //經(jīng)過一輪輪的判斷，終于定下了新的容量，好，調(diào)整elementData的容量為 newCapacity！
}
總結(jié)如下，有3種情況：
注：newCapacit 為需求容量，oldCapacity原來的容量
1、oldCapacity < newCapacit <= oldCapacity * 1.5
平緩增長的正常情況。例如原來容量為10 ，現(xiàn)在期望達到11個，則會擴展 調(diào)整到 10 + (10 >> 1) =15個 ，也就是變?yōu)?原來的1.5倍。
2、oldCapacity*1.5 < newCapacit <= MAX_ARRAY_SIZE
默認的1.5倍增長還不夠，期望的容量有點大。例如原來容量為10 ，現(xiàn)在請求100個，那么就會實打?qū)嵉臄U展到 100 個的容量。
3、MAX_ARRAY_SIZE < newCapacit <= Interger.MAX_VALUE
極端情況，期望的容量超大 。在這個情況下，newCapacity的值最終是由hugeCapacity函數(shù)決定的，它會返回 MAX_ARRAY_SIZE 或者 Integer.MAX_VALUE
而 MAX_ARRAY_SIZE是一個比Integer.MAX_VALUE 小8 的數(shù) ，為什么要小8呢，我很奇怪。看了注釋解釋大致如下。
//有些Java虛擬機會在數(shù)組內(nèi)存的頭部保留 一些字節(jié)的容量來存儲這個內(nèi)存塊的相關(guān)信息，因此，數(shù)組的 安全最大長度是 ： Integer.MAX_VALUE - 8private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
所以，ArrayList 的最多容量不要超過 MAX_ARRAY_SIZE (Integer.MAX_VALUE - 8) , 也就是 2147483639 個 （瘋子才會使用這么多吧），否則是會拋異常的。
下面還有2個是公開的接口
公開接口：避免多余的浪費，讓容量裁剪為和size一樣大
public void trimToSize() {
modCount++; if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
}
公開接口：一次性決定ArrayList 的最大容量，避免半路上不斷的調(diào)整容量帶來開銷（如果你真的很確定你需要的ArrayList 的最大長度，否則沒必要）
public void ensureCapacity(int minCapacity) { int minExpand = (elementData != EMPTY_ELEMENTDATA) // any size if real element table
? 0 // larger than default for empty table. It's already supposed to be // at default size. : DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
總結(jié)：默認情況下，ArrayList 平緩增長時，每次增長為原來的容量的1.5倍。
順序表的短板：插入和刪除
先看一道試題：
在java中，下面哪一個復制數(shù)組的方法最高效？
A、循環(huán)賦值
B、Arrays.copyOf
C、System.arraycopy
D、clone
正確答案： C
這個函數(shù)讓我想到了C語言標準庫中的 memmove 函數(shù)，它們的功能真的很像。而且 System.arraycopy 是 native方法，實現(xiàn)會不會就是 memmove 呢？？？也許吧，可惜我看不到源碼。下面介紹 System.arraycopy這個函數(shù)。
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); /*從數(shù)組src中拷貝元素到 dest中 。我們把src數(shù)組叫做源數(shù)組，把dest數(shù)組叫做目的數(shù)組 src 源數(shù)組的引用 srcPos 源數(shù)組的拷貝起始索引 dest 目的數(shù)組的引用 destPos 目的數(shù)組的拷貝起始索引 length 有l(wèi)ength個元素會被拷貝 如果參數(shù) src 和 dest 引用相同的數(shù)組對象（注意，它允許內(nèi)存重疊），則復制的執(zhí)行過程就好像首先將 srcPos 到 srcPos+length-1 位置的組件復制到 一個帶有 length 組件的臨時數(shù)組，然后再將此臨時數(shù)組的內(nèi)容復制到目標數(shù)組的 destPos 到 destPos+length-1 位置一樣。 這就好像是C語言標準庫中的memmove 使用注意： 1、src 和 dest不能為null，否則會拋出NullPointerExcaption異常 2、src和 dest 的類型要兼容或者一樣。 3、你必須精確把握好起始索引和拷貝長度的關(guān)系，有差錯就是拋異常。 */
ArrayList在刪除和插入 移動數(shù)組元素時，就是使用的這個API。我們來看看。
插入元素
插入一個元素到指定位置
public void add(int index, E element) {
rangeCheckForAdd(index); //檢查index 的合法性：邏輯如下 ，后面不再列出
/*
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
*/
ensureCapacityInternal(size + 1); // 確保容量足夠
//elementData 的元素的移動，讓出空間
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element; //插入新的元素的引用
size++;
}
插入一個集合的元素到指定的位置
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index); //index 合法性檢查
Object[] a = c.toArray(); //先轉(zhuǎn)化為數(shù)組
int numNew = a.length;
ensureCapacityInternal(size + numNew); // 確保容量足夠
int numMoved = size - index; if (numMoved > 0) //原來的數(shù)組讓出空間
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//將新的元素拷貝到騰出的空間去。
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew; return numNew != 0;
}
畫個圖打開你的腦洞（插入2個元素的集合到ArrayList 的開頭）
刪除元素
從集合中刪除元素只是讓保存這個對象的引用為null，讓GC卻確定什么時候清理這個對象。因為java沒有free ， delete 。
刪除所有的元素 clear
/* 清空ArrayList中的所有持有對象。讓size為0.
實質(zhì)操作是讓保存持有對象的引用的數(shù)組elementData 的元素全部為null。
所以我們會試想：如果在清空操作后 ，沒有其它引用指向ArrayList原來持有的對象了，那么這個對象就會等待被GC 回收。
例子：
ArrayList<Person> arr = new ArrayList<Person>();
Person p1 = new Person();
arr.add(p1); //添加第一個持有對象
arr.add(new Person()); //添加第二個持有對象，匿名的。
arr.clear(); //第一個持有對象因為還有引用p1 的指向，所以暫時不會等待GC回收
//第二個對象由于沒有引用指向。則會等待GC回收。 */
public void clear() {
modCount++; // clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
按對象刪除：刪除第一個找到的元素，立刻返回。如果沒找到，則什么也不做，返回false 。如果o不為null，則調(diào)用equals方法去查找。時間復雜度為O(n)。
public boolean remove(Object o) { if (o == null) //如果要刪除null { for (int index = 0; index < size; index++) if (elementData[index] == null) //從前往后遍歷查找，一旦找到為null ，刪除之，返回 {
fastRemove(index); //fastRemove 是對 System.arraycopy 的封裝
return true;
}
} else //如果要刪除某個真實存在的對象 { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) //從前往后遍歷查找，一旦找到，刪除之，返回 {
fastRemove(index); //fastRemove 是對 System.arraycopy 的封裝
return true;
}
} return false;
}
按索引刪除：刪除指定索引上的元素。主要耗時是在System.arraycopy 的執(zhí)行上 。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index); 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
return oldValue;
}
只保留 ArrayList中 和 集合c 相同元素，其它的都刪除。相同是指調(diào)用equals返回 true （或者都是null）
public boolean retainAll(Collection<?> c) { return batchRemove(c, true);
}歡迎轉(zhuǎn)載，請注明出處：www.cnblogs.com/lulipro
為了獲得更好的閱讀體驗，請訪問原博客地址。
http://www.cnblogs.com/lulipro/p/6553816.html
延伸閱讀
- 珊珊老師——北京IT機構(gòu)十年一線教學經(jīng)驗 2024-08-28
- 向著Java前進 2023-04-15
- 2021年Java程序員的就業(yè)前景如何？ 2022-02-17
- 感謝萬碼，我認識到了java的魅力 2021-05-23
- 今天我成為了Java工程師 2021-05-23
- 我的JAVA生涯 ——解*泉 2020-01-15
- 以java為劍，仗劍走江湖—尚*權(quán) 2019-12-22
- 開啟我的java征途——鄭*亮 2019-11-06
- 我想這就是Java工程師的工作——劉*聰 2019-07-05
- 向Java工程師靠近——程*賞 2018-01-25
珊珊老師——北京IT機構(gòu)十年一線教學經(jīng)驗