Java Collection框架 - ArrayList
基于jdk1.8
簡(jiǎn)介
ArrayList是基于數(shù)組實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組，不是線程安全的
時(shí)間復(fù)雜度：
- 查找和修改 ==> O(1)
- 刪除和添加(除了向末尾添加) ==> O(n)
數(shù)據(jù)結(jié)構(gòu)
先看下ArrayList的數(shù)據(jù)結(jié)構(gòu)：
ArrayList的數(shù)據(jù)結(jié)構(gòu)很簡(jiǎn)單，就是一個(gè)數(shù)組跟一個(gè)size屬性作為尾指針
主要屬性與方法列表
//代表ArrayList默認(rèn)容量 10
DEFAULT_CAPACITY : int
//內(nèi)部數(shù)組
elementData : Object[]
//容量
size : int
//最大容量 Integer.MAX_VALUE - 8
MAX_ARRAY_SIZE : int
trimToSize() : void
ensureCapacity(int) : void
size() : int
isEmpty() : boolean
contains(Object) : boolean
indexOf(Object) : int
lastIndexOf(Object) : int
clone() : Object
toArray() : Object[]
toArray(T[]) : T[]
get(int) : E
set(int, E) : E
add(E) : boolean
add(int, E) : void
remove(int) : E
remove(Object) : boolean
clear() : void
addAll(Collection<? extends E>) : boolean
addAll(int, Collection<? extends E>) : boolean
removeAll(Collection<?>) : boolean
retainAll(Collection<?>) : boolean
listIterator(int) : ListIterator<E>
listIterator() : ListIterator<E>
subList(int, int) : List<E>
sort(Comparator<? super E>) : void
主要代碼分析
- 查找
ArrayList提供了get(int index)用于讀取數(shù)組中的元素。由于ArrayList使用數(shù)組實(shí)現(xiàn)，所以可以直接使用下標(biāo)來獲取元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
- 增加
ArrayList提供了add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)四個(gè)方法來添加元素
-
add(E e)：將元素添加到ArrayList末尾public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }這里的
ensureCapacityInternal()方法的作用是嘗試對(duì)數(shù)組進(jìn)行擴(kuò)容 -
add(int index, E element)：將元素添加至指定位置，并將之后的元素向后移一位public void add(int index, E element) { //判斷索引位置是否合法 rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! //將原數(shù)組從index之后的元素，全部向后移動(dòng)一位 //其目的是將index位置空出來 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }這里的
rangeCheckForAdd(index)方法的作用是檢查index的值是否在0~size之間。ensureCapacityInternal()方法的作用與上面一樣，都是嘗試對(duì)數(shù)組進(jìn)行擴(kuò)容。System.arraycopy()方法用于將elementData從index開始的元素復(fù)制到elementData的index+1位置，一共復(fù)制size-index個(gè)元素，目的是將index位置空出來，方便后來的重新賦值 -
addAll(Collection<? extends E> c)：將集合內(nèi)的所有元素依次添加到ArrayList末尾public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount //將a數(shù)組內(nèi)的元素添加到內(nèi)部數(shù)組中 System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; }這里的
System.arraycopy()方法用于將a數(shù)組從0開始的所有元素復(fù)制到elementData的size位置，一共復(fù)制numNew個(gè)，使用System.arraycopy()方法相比于一個(gè)個(gè)復(fù)制速度更快 -
addAll(int index, Collection<? extends E> c)：將集合內(nèi)所有元素依次添加到指定位置public boolean addAll(int index, Collection<? extends E> c) { //確定索引位置是否合法 rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount //計(jì)算需要后移的元素個(gè)數(shù) int numMoved = size - index; //如果大于0，就將指定元素后移 if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }在這里
System.arraycopy()的作用是先將指定元素后移numNew位（如果有必要），然后將a數(shù)組中的元素復(fù)制到指定位置
- 修改
ArrayList提供了set(int index, E element)方法來修改指定位置的元素
-
set(int index, E element)：將index位置的元素設(shè)置為elementpublic E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }與
add(int index, E element)方法類似，只不過不需要后移元素了
- 刪除
ArrayList提供了remove(int index)、remove(Object o)、removeAll(Collection<?> c)、retainAll(Collection<?> c)四個(gè)方法來刪除元素
-
remove(int index)：刪除指定位置的元素public E remove(int index) { rangeCheck(index); modCount++; //獲取指定位置的元素 E oldValue = elementData(index); //計(jì)算需要移動(dòng)的元素個(gè)數(shù) 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; } -
remove(Object o)：刪除指定元素public boolean remove(Object o) { if (o == null) { //刪除元素為null的情況 for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { //不為null for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); //將最后的多余元素清除，防止內(nèi)存泄漏 elementData[--size] = null; // clear to let GC do its work } -
removeAll(Collection<?> c)：刪除所有集合中包含的元素public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); } private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) //保留元素策略取決于complement參數(shù) //用于實(shí)現(xiàn)removeAll跟retainAll方法 if (c.contains(elementData[r]) == complement) //將保留元素移動(dòng)到列表頭部 elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. //當(dāng)contains方法拋出異常時(shí)，r不會(huì)等于size if (r != size) { //0~w：需要保留 //w~r：需要?jiǎng)h除 //r~size：不能確定 //只刪除必定需要?jiǎng)h除的元素 System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }removeAll()方法依賴于batchRemove()方法，通過complement屬性指定需要?jiǎng)h除的元素為c集合包含的元素 -
retainAll(Collection<?> c)：刪除所有集合中不包含的元素public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); }與
removeAll()方法類似，通過complement屬性指定需要?jiǎng)h除的元素為c集合不包含的元素
- 擴(kuò)增
ArrayList提供了ensureCapacity(int minCapacity)、ensureCapacityInternal(int minCapacity)兩個(gè)方法供其他方法調(diào)用，用于擴(kuò)增容量。這兩個(gè)方法都依賴ensureExplicitCapacity(int minCapacity)方法，ensureExplicitCapacity(int minCapacity)方法又依賴grow(int minCapacity)方法
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//計(jì)算新的數(shù)組容量，以1.5倍擴(kuò)容
//1.5倍是通過測(cè)試得到的一個(gè)最佳值
//以1.5倍擴(kuò)容。既不會(huì)消耗太多性能，也不會(huì)消耗太多內(nèi)存
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);
}
- 迭代器
ArrayList實(shí)現(xiàn)了Itr、ListItr兩個(gè)迭代器。ArrayList的迭代器能在遍歷的同時(shí)添加或刪除元素，是由于在這兩個(gè)方法中修改了迭代器的expectedModCount記錄
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
//修改記錄
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
//修改記錄
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
總結(jié)
- ArrayList的默認(rèn)初始容量為10
- ArrayList以1.5倍擴(kuò)容
