集合之ArrayList（含JDK1.8源码分析）
一、ArrayList的數(shù)據(jù)結(jié)構(gòu)
ArrayList底層的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，數(shù)組元素類型為Object類型，即可以存放所有類型數(shù)據(jù)。我們對(duì)ArrayList類的實(shí)例的所有的操作(增刪改查等)，其底層都是基于數(shù)組的。
定義底層數(shù)據(jù)結(jié)構(gòu)：Object[] elementData
/*** The array buffer into which the elements of the ArrayList are stored.* The capacity of the ArrayList is the length of this array buffer. Any* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA* will be expanded to DEFAULT_CAPACITY when the first element is added.*/transient Object[] elementData; // non-private to simplify nested class access===The capacity of the ArrayList is the length of this array buffer. ===
注釋中這句話的意思是ArrayList的capacity即容量是數(shù)組elementData的長(zhǎng)度。capacity = elementData.length，而不是arrayList.size()。
===Any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY when the first element is added.===
注釋中這句話的意思是當(dāng)通過(guò)如：List<String> dataList = new ArrayList<>();創(chuàng)建ArrayList的一個(gè)對(duì)象時(shí)，此時(shí)該dataList是沒(méi)有被定義容量的，當(dāng)add第一個(gè)元素的時(shí)候，此時(shí)才將dataList的容量設(shè)置為?DEFAULT_CAPACITY即10.
舉例說(shuō)明：
因?yàn)锳rrayList中數(shù)組elementData的屬性是default，所以我們通過(guò)反射來(lái)獲取數(shù)組的長(zhǎng)度即capacity。
public class Test {public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {List<String> dataList = new ArrayList<>();//初始化時(shí)獲取ArrayList的capacityint arrayListCapacity = getArrayListCapacity(dataList);System.out.println("初始化時(shí)ArrayList的capacity：" + arrayListCapacity);dataList.add("zhangsan");//添加第一個(gè)元素初始化時(shí)獲取ArrayList的capacityint arrayListCapacity1 = getArrayListCapacity(dataList);System.out.println("add第一個(gè)元素后ArrayList的capacity：" + arrayListCapacity1);}/*** 反射獲取ArrayList的容量capacity* @param arrayList* @return* @throws NoSuchFieldException* @throws IllegalAccessException*/public static int getArrayListCapacity(List arrayList) throws NoSuchFieldException, IllegalAccessException {Class<ArrayList> arrayListClass = ArrayList.class;Field elementData = arrayListClass.getDeclaredField("elementData");elementData.setAccessible(true);Object[] objects = (Object[]) elementData.get(arrayList);return objects.length;} }結(jié)果：
初始化時(shí)ArrayList的capacity：0 add第一個(gè)元素后ArrayList的capacity：10?二、ArrayList的屬性
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable{// 版本號(hào)private static final long serialVersionUID = 8683452581122892189L;// 缺省容量private static final int DEFAULT_CAPACITY = 10;// 空對(duì)象數(shù)組private static final Object[] EMPTY_ELEMENTDATA = {};// 缺省空對(duì)象數(shù)組private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 元素?cái)?shù)組transient Object[] elementData;// 實(shí)際元素大小，默認(rèn)為0private int size;// 最大數(shù)組容量private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; }ArrayList類的屬性中核心的屬性為elementData，類型為Object[]，用于存放實(shí)際元素，并且被標(biāo)記為transient，也就意味著在序列化的時(shí)候，此字段是不會(huì)被序列化的。
三、ArrayList的構(gòu)造函數(shù)
public ArrayList()型構(gòu)造函數(shù)
/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}構(gòu)造一個(gè)空的arrayList對(duì)象，初始容量為10。（該初始容量也是add第一個(gè)元素的時(shí)候設(shè)置的）。
public ArrayList(int initialCapacity)型構(gòu)造函數(shù)
/*** Constructs an empty list with the specified initial capacity.** @param initialCapacity the initial capacity of the list* @throws IllegalArgumentException if the specified initial capacity* is negative*/public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}構(gòu)造一個(gè)空的arrayList對(duì)象，并指定初始容量，不允許初始容量小于0，否則拋出異常。
public ArrayList(Collection<? extends E> c)型構(gòu)造函數(shù)
/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @param c the collection whose elements are to be placed into this list* @throws NullPointerException if the specified collection is null*/public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}舉例說(shuō)明：
public class Test {private static int size;public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {List<String> dataList = new ArrayList<>();dataList.add("zhangsan");dataList.add("lisi");dataList.add("wangwu");System.out.println("傳入的參數(shù)dataList的大小: " + dataList.size());List<String> dataList2 = new ArrayList<>(dataList);System.out.println("new ArrayList<>(dataList)的元素: " + dataList2);int arrayListCapacity = getArrayListCapacity(dataList2);System.out.println("new ArrayList<>(dataList)的capacity: " + arrayListCapacity);}/*** 反射獲取ArrayList的容量capacity* @param arrayList* @return* @throws NoSuchFieldException* @throws IllegalAccessException*/public static int getArrayListCapacity(List arrayList) throws NoSuchFieldException, IllegalAccessException {Class<ArrayList> arrayListClass = ArrayList.class;Field elementData = arrayListClass.getDeclaredField("elementData");elementData.setAccessible(true);Object[] objects = (Object[]) elementData.get(arrayList);return objects.length;} }結(jié)果：
傳入的參數(shù)dataList的大小: 3 new ArrayList<>(dataList)的元素: [zhangsan, lisi, wangwu] new ArrayList<>(dataList)的capacity: 3此種構(gòu)造方法得到的arrayList的capacity為傳入collection的size。
四、ArrayList的增刪改查
1、增：add
public class TestArrayList {public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {List<String> dataList = new ArrayList<>();int arrayListCapacity = getArrayListCapacity(dataList);System.out.println("未添加元素在時(shí)capacity：" + arrayListCapacity);dataList.add("zhangsan1");int arrayListCapacity1 = getArrayListCapacity(dataList);System.out.println("add第一個(gè)元素在時(shí)capacity：" + arrayListCapacity1);dataList.add("zhangsan2");dataList.add("zhangsan3");dataList.add("zhangsan4");dataList.add("zhangsan5");dataList.add("zhangsan6");dataList.add("zhangsan7");dataList.add("zhangsan8");dataList.add("zhangsan9");dataList.add("zhangsan10");int arrayListCapacity2 = getArrayListCapacity(dataList);System.out.println("add第十個(gè)元素在時(shí)capacity：" + arrayListCapacity2);dataList.add("zhangsan11");int arrayListCapacity3 = getArrayListCapacity(dataList);System.out.println("add第十一個(gè)元素在時(shí)capacity：" + arrayListCapacity3);}/*** 反射獲取ArrayList的容量capacity* @param arrayList* @return* @throws NoSuchFieldException* @throws IllegalAccessException*/public static int getArrayListCapacity(List arrayList) throws NoSuchFieldException, IllegalAccessException {Class<ArrayList> arrayListClass = ArrayList.class;Field elementData = arrayListClass.getDeclaredField("elementData");elementData.setAccessible(true);Object[] objects = (Object[]) elementData.get(arrayList);return objects.length;} }結(jié)果：
未添加元素在時(shí)capacity：0 add第一個(gè)元素在時(shí)capacity：10 add第十個(gè)元素在時(shí)capacity：10 add第十一個(gè)元素在時(shí)capacity：15結(jié)合以上，在添加第一個(gè)元素時(shí)進(jìn)行了擴(kuò)容，capacity為10。當(dāng)添加第十一個(gè)元素時(shí)，此時(shí)容量為10，已不夠用，又進(jìn)行了擴(kuò)容，capacity為15。
add源碼如下：
/*** Appends the specified element to the end of this list.** @param e element to be appended to this list* @return <tt>true</tt> (as specified by {@link Collection#add})*/public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true;}ensureCapacityInternal函數(shù)確保elemenData數(shù)組有合適的大小。指定minCapacity大小
private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}ensureExplicitCapacity函數(shù)判斷是否需要擴(kuò)容。當(dāng)arrayList所需的最小容量minCapacity大于當(dāng)前數(shù)組elementData的長(zhǎng)度時(shí)，就需要擴(kuò)容了。
private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}真正的擴(kuò)容方法grow。
拷貝擴(kuò)容：Arrays.copyOf(elementData, newCapacity)；根據(jù)newCapacity構(gòu)建一個(gè)新的數(shù)組，并將原數(shù)組elementData的數(shù)組復(fù)制到新數(shù)組中。最后將新的數(shù)組賦值給原數(shù)組。
/*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.** @param minCapacity the desired minimum capacity*/private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)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);}========int newCapacity = oldCapacity + (oldCapacity >> 1);=========
正常情況下會(huì)擴(kuò)容1.5倍，特殊情況下（新擴(kuò)展數(shù)組大小已經(jīng)達(dá)到了最大值）則只取最大值。
增（插入）：add(int index,E element)
舉例：
?
public class Test {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("zhangsan1");list.add("zhangsan2");list.add("zhangsan3");list.add("zhangsan4");System.out.println("list before add===" + list);list.add(1,"zhaoliu");System.out.println("list after add====" + list);} }?
結(jié)果：
list before add===[zhangsan1, zhangsan2, zhangsan3, zhangsan4] list after add====[zhangsan1, zhaoliu, zhangsan2, zhangsan3, zhangsan4]源碼分析：類似于下面的remove，都涉及到元素的移動(dòng)。
/*** Inserts the specified element at the specified position in this* list. Shifts the element currently at that position (if any) and* any subsequent elements to the right (adds one to their indices).** @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws IndexOutOfBoundsException {@inheritDoc}*/public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size + 1); // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;}?
2、刪：remove
舉例：
public class TestArrayList {public static void main(String[] args) {List<String> dataList = new ArrayList<>();dataList.add("zhangsan");dataList.add("lisi");dataList.add("wangwu");dataList.add("zhaoliu");System.out.println(dataList);dataList.remove(1);System.out.println(dataList);} }結(jié)果：
[zhangsan, lisi, wangwu, zhaoliu] [zhangsan, wangwu, zhaoliu]remove源碼：
/*** Removes the element at the specified position in this list.* Shifts any subsequent elements to the left (subtracts one from their* indices).** @param index the index of the element to be removed* @return the element that was removed from the list* @throws IndexOutOfBoundsException {@inheritDoc}*/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 workreturn oldValue;}解釋說(shuō)明：
對(duì)索引進(jìn)行校驗(yàn)后，判斷刪除后需要移動(dòng)的個(gè)數(shù)，本例中刪除索引1的元素，需要移動(dòng)索引2，3即兩個(gè)元素
移動(dòng)元素，使用的是System.arraycopy(Object src, int srcPos,Object dest, int destPos,int length)方法。
原數(shù)組
[zhangsan, lisi, wangwu, zhaoliu]變成
[zhangsan, wangwu, zhaoliu, zhaoliu]最后?elementData[--size] = null 將最后一個(gè)元素置為null。此時(shí)的size為3，即將element[3]置為null，顯示如下：
[zhangsan, wangwu, zhaoliu]=========注意這句注釋：clear to let GC do its work==========
說(shuō)明：置空原尾部數(shù)據(jù) 不再?gòu)?qiáng)引用, 可以GC掉（引用為null）
3、改：set
舉例：
public class TestArrayList {public static void main(String[] args) {List<String> dataList = new ArrayList<>();dataList.add("zhangsan");dataList.add("lisi");dataList.add("wangwu");dataList.add("zhaoliu");System.out.println(dataList);dataList.set(3,"zl");System.out.println(dataList);} }結(jié)果：
[zhangsan, lisi, wangwu, zhaoliu] [zhangsan, lisi, wangwu, zl]set源碼：
/*** Replaces the element at the specified position in this list with* the specified element.** @param index index of the element to replace* @param element element to be stored at the specified position* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}判讀所給索引是否在arrayList的size之內(nèi)，否則拋出?IndexOutOfBoundsException異常。
/*** Checks if the given index is in range. If not, throws an appropriate* runtime exception. This method does *not* check if the index is* negative: It is always used immediately prior to an array access,* which throws an ArrayIndexOutOfBoundsException if index is negative.*/private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}? 4、查：get
舉例說(shuō)明：
public class TestArrayList {public static void main(String[] args){List<String> dataList = new ArrayList<>();dataList.add("zhangsan");dataList.add("lisi");dataList.add("wangwu");dataList.add("zhaoliu");System.out.println(dataList.get(3));} }結(jié)果：
zhaoliuget源碼：
/*** Returns the element at the specified position in this list.** @param index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {rangeCheck(index);return elementData(index);}? 可以看到，ArrayList的增、刪都涉及到元素的移動(dòng)，當(dāng)元素?cái)?shù)量比較多的時(shí)候，效率相對(duì)就會(huì)降低。但是改、查不涉及到元素的移動(dòng)，根據(jù)索引值直接定位，效率比較高。
五、總結(jié)
1、ArrayList的優(yōu)缺點(diǎn)：
從上面的幾個(gè)過(guò)程總結(jié)一下ArrayList的優(yōu)缺點(diǎn)。ArrayList的優(yōu)點(diǎn)如下：
1、ArrayList底層以數(shù)組實(shí)現(xiàn)，是一種隨機(jī)訪問(wèn)模式，再加上它實(shí)現(xiàn)了RandomAccess接口，因此查找也就是get的時(shí)候非常快
2、ArrayList在順序添加一個(gè)元素的時(shí)候非常方便，只是往數(shù)組里面添加了一個(gè)元素而已
不過(guò)ArrayList的缺點(diǎn)也十分明顯：
1、刪除元素的時(shí)候，涉及到一次元素復(fù)制，如果要復(fù)制的元素很多，那么就會(huì)比較耗費(fèi)性能
2、插入元素的時(shí)候，涉及到一次元素復(fù)制，如果要復(fù)制的元素很多，那么就會(huì)比較耗費(fèi)性能
因此，ArrayList比較適合順序添加、隨機(jī)訪問(wèn)的場(chǎng)景。
2、ArrayList和Vector的區(qū)別
Vector，它是ArrayList的線程安全版本，其實(shí)現(xiàn)90%和ArrayList都完全一樣，區(qū)別在于：
1、Vector是線程安全的，ArrayList是線程非安全的
2、Vector可以指定增長(zhǎng)因子，如果該增長(zhǎng)因子指定了，那么擴(kuò)容的時(shí)候會(huì)每次新的數(shù)組大小會(huì)在原數(shù)組的大小基礎(chǔ)上加上增長(zhǎng)因子；如果不指定增長(zhǎng)因子，那么就給原數(shù)組大小*2，源碼如下：
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);參考資料：
https://blog.csdn.net/hrbeuwhw/article/details/79435934? ??集合間關(guān)系圖
https://www.cnblogs.com/leesf456/p/5308358.html
https://www.cnblogs.com/xrq730/p/4989451.html
轉(zhuǎn)載于:https://www.cnblogs.com/zfyang2429/p/10341923.html
總結(jié)
以上是生活随笔為你收集整理的集合之ArrayList（含JDK1.8源码分析）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 我的青春我的梦剧情介绍
- 下一篇： Python 2.7 cython cy