基本java開發面試都會問到關于collection(集合)架構的問題,collection是一個接口,常用的實作類有 ArrayList,HashSet, LinkedHashSet, LinkedList 等等,這裡主要學習一下ArrayList。ArrayList平時經常用來傳回多個值的對象,比如擷取多資料等場景。ArrayList具體是怎麼實作的呢?或者說當我們添加一個元素或者對象時底層怎麼處理,我們來看一下源碼:
/**
* 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 == EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
*/
private transient Object[] elementData;
/**
* 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) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
/**
* 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();
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的構造函數源碼,我們常用的ArrayList()這個方法來建立一個list,英文的解釋是構造一個空的且容量為10的list;也就是說初始化list容量為10,因為list采用的是動态調整記憶體的方式當資料量超過10時他會自動的擴充容量(擴充函數在ArrayList源碼中也可以檢視)。在第一段源碼中我們可以看到ArrayList的資料結構是一個數組,這個很重要,說明底層的操作都是對數組進行的操作。看一下ArrayList的add函數
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
ensureCapacityInternal 動态調整容量大小的方法
我們可以看到當我調用add方法時直接在ArrayList最後面插入一個元素,也就說ArrayList集合其實是一個動态可變的數組。
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++;
}
上面的add方法多了個參數index,這參數表示你可以在指定的位置進行進行擦入。具體執行:判斷輸入位置
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
是不是大于size(預設是10)是則直接跑出異常,否則動态調整大小,并執行:
private void grow(int minCapacity) {
// overflow-conscious code
int 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);
}
将elementData指向copy後的數組。到此ArrayList的動态擴容核心操作完成。接下來是數組位置的移動:
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
參數解釋:第一個elementData源數組,index數組需要複制的開始位置,第二個elementData是目标數組,第三個參數是目标數組的開始下标,最後一個參數表示需要複制的長度。代碼如下:
int[] a = {1,4,6,7,8,9};
int[] b = {2,3,5};
//複制數組
System.arraycopy(a,2,b,0,3);
System.out.println(Arrays.toString(b));
輸出:
[6, 7, 8]
從2的位置開始複制,長度為3個元素,在b的0的位置開始插入,這樣就完成數組的移動。這裡b數組開始下标必須在b數組中初始化或者設定長度否則會抛出異常ArrayIndexOutOfBoundsException,複制的長度也必須與小于等于b數組長度。到此ArrayList add結束。