Java ArrayList源碼深入分析
1.ArrayList 是基數(shù)組結(jié)構(gòu)的,需要連續(xù)的內(nèi)存空間
從構(gòu)造函數(shù)可以看出,ArrayList內(nèi)部用一個Object數(shù)組來保存數(shù)據(jù)。
對于無參構(gòu)造,ArrayList會創(chuàng)建一個大小為10的初始數(shù)組,第一次擴容時會創(chuàng)建默認大小數(shù)組。
//無參構(gòu)造函數(shù),會構(gòu)造一個空數(shù)組。第一次擴容時會創(chuàng)默認大小為10的數(shù)組 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } private static final Object[] EMPTY_ELEMENTDATA = {}; //如果給定集合大小,會創(chuàng)建一個對應大小的數(shù)組 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); } }
2.對于set和get方法ArrayList效率高,因為可以直接通過下標獲取存儲對象。
//直接通過角標從數(shù)組中取出元素 public E get(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); return (E) elementData[index]; } //set 方法,直接通過index 拿到元素,進行修改就行。 public E set(int index, E element) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); E oldValue = (E) elementData[index]; elementData[index] = element; return oldValue; }
3.對于add方法,有兩種情況:
第一種是在尾部添加,不需要移動數(shù)組。
//Add 方法 ,在末端插入不需要 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
第二種情況在指定位置添加或插入數(shù)據(jù),則需要移動數(shù)組,效率比較低。如果插入在第0個位置則需要移動整個數(shù)組。
public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); ensureCapacityInternal(size + 1); // Increments modCount!! //被插入的元素在index。則移動的數(shù)組應該從index開始,向后移動一個, //移動的數(shù)組長度 size-index 從index開始的數(shù)組長度 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
在add時還需要考慮到數(shù)組的擴容問題,看ensureCapacityInternal方法
private void ensureCapacityInternal(int minCapacity) { //通過無參構(gòu)造創(chuàng)建為設(shè)置初始大小時,判斷條件為true if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //創(chuàng)建默認大小的數(shù)組,初始大小是10 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }
添加元素后,元素數(shù)量大于數(shù)組長度時,進行擴容grow,擴容大小是原數(shù)組的1.5倍
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code //新增后,數(shù)組容量已經(jīng)大于了數(shù)組長度,則進行擴容 if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //新的數(shù)組大小是原來的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //創(chuàng)建一個新長度的數(shù)組。 elementData = Arrays.copyOf(elementData, newCapacity); }
4.對應remove 刪除元素操作。如果刪除元素在最后一個,不需要移動數(shù)組,否則會將被刪除元素之后的所有元素都要向前移動,效率比較低。
//刪除 public E remove(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); modCount++; //取出被刪除的元素 E oldValue = (E) elementData[index]; int numMoved = size - index - 1; //移動的數(shù)組長度,大于0才需要移動,小于0說明被刪元素在最后一個 if (numMoved > 0) //第一個參數(shù)是源數(shù)組, //第二個參數(shù)是移動的起始位置:index+1,從被刪元素的后一個位置開始 //第三個參數(shù)是目標數(shù)組 //第四個參數(shù)是移動目標位置:index,被刪除元素的位置 //第五個參數(shù)是移動的數(shù)組長度 size - index - 1,從index+1位置開始之后的數(shù)組長度 //最終會調(diào)用到native方法進行移動。 System.arraycopy(elementData, index+1, elementData, index,numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; }
5.System.arraycopy方法參數(shù)分析。
第二個參數(shù) index+1是被移動數(shù)組的起始位置,即被刪元素后一個位置
第四個參數(shù)index,是被移動數(shù)組的起始位置,即被刪元素的位置。
最后一個參數(shù)size-index-1,被移動數(shù)組的長度,即被刪元素后一個位置到元素末尾的長度
public static native void arraycopy(java.lang.Object src, int srcPos, java.lang.Object dest, int destPos, int length);
通過對源碼的閱讀,也許會對ArrayList有一個更加直接的了解。
到此這篇關(guān)于Java ArrayList源碼深入分析的文章就介紹到這了,更多相關(guān)Java ArrayList內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Android JNI c/c++調(diào)用java的實例
這篇文章主要介紹了Android JNI c/c++調(diào)用java的實例的相關(guān)資料,需要的朋友可以參考下2017-07-07解析android中的幫助、about、關(guān)于作者、HELP等提示頁面
本篇文章是對android中的幫助、about、關(guān)于作者、HELP等提示頁面進行了詳細的分析介紹,需要的朋友參考下2013-06-06Android中BroadcastReceiver實現(xiàn)短信關(guān)鍵字自動回復功能
實現(xiàn)手機短信監(jiān)聽的方式有兩種:一是通過ContentObserver觀察者實現(xiàn)監(jiān)聽,另一種就是通過廣播即BroadcastReceiver實現(xiàn)短信監(jiān)聽,文章中通過使用BroadcastReceiver實現(xiàn)有新短信的及時監(jiān)聽及包含設(shè)定的關(guān)鍵字時自動回復2018-06-06