1. 屬性
package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import sun.misc.SharedSecrets;
/**
* Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)
* 翻譯: ArrayList是一個動态數組,實作了List接口以及List相關的所有方法,它允許所有元素的插入,包括null.另外,ArrayList相較于Vector除了線程不同步之外,大緻相等.
*/
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
//1.屬性
private static final long serialVersionUID = 8683452581122892189L;
//預設容量的大小
private static final int DEFAULT_CAPACITY = 10;
//空數組常量
private static final Object[] EMPTY_ELEMENTDATA = {};
//預設的空數組常量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存放元素的數組,從這可以發現ArrayList的底層實作就是一個Object數組
transient Object[] elementData;
//數組中包含的元素個數
private int size;
//數組的最大上限
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/* ArrayList的屬性非常少,就隻有上面這些,其中最重要的莫過于elementData了,ArrayList所有方法的操作都是建立在elementData之上. */
//ArrayList内部的具體方法見下文分析.
}
2. 構造器
//預設情況下elementData是一個大小為0的空數組,隻有在使用到時(add方法),才會通過grow方法去建立一個大小為10的數組.
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//當我們指定了初始容量時,elementData的初始大小就變成了我們所指定的初始大小了.
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);
}
}
3. get 方法
//因為ArrayList是采用數組結構來存儲的,是以它的get方法非常簡單.
public E get(int index) {
//先判斷一下有沒有越界
rangeCheck(index);
//直接通過數組下标來擷取元素,是以get方法的時間複雜度是O(1).
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
4. add 方法
//第一個add方法的複雜度為O(1),雖然有時候會涉及到擴容的操作,但是擴容的次數是非常少的,是以這一部分的時間可以忽略不計.
public boolean add(E e) {
//在插入元素之前,會先檢查是否需要擴容,然後再把元素添加到數組中最後一個元素的後面.
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//第二個帶指定下标的add方法的複雜度為O(n),因為涉及到對數組中元素的移動,這一操作是非常耗時的.
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//調用一個native的複制方法,把index位置開始的元素都往後挪一位.
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果當elementData為空數組時,會使用預設的大小去擴容.
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
5. set 方法
//set方法的作用是把下标為index的元素替換成element,實作跟get類似,時間複雜度度為O(1).
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
6. remove方法
//remove方法與帶指定下标的add方法非常類似,也是調用系統的arraycopy方法來移動元素,時間複雜度為O(n).
public E remove(int index) {
rangeCheck(index);
modCount++; //modCount是AbstractList抽象類的一個屬性,表示List結構被修改的次數.
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;
}
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
//The number of times this list has been structurally modified.
//Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.
protected transient int modCount = 0;
}
7. grow 方法
//grow方法是在數組進行擴容的時候用到的,ArrayList每次擴容都是擴1.5倍,然後調用Arrays類的copyOf方法,把元素重新拷貝到一個新的數組中去.
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
8. size 方法
//size方法非常簡單,它直接傳回size屬性的值,也就是傳回數組中元素的個數,時間複雜度為O(1).
//注意:size方法傳回的并不是數組的實際大小.
public int size() {
return size;
}
9. indexOf 方法
//indexOf方法的作用是傳回第一個等于給定元素的值的下标,它是通過周遊比較數組中每個元素的值來查找的,是以它的時間複雜度是O(n).
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//lastIndexOf的原理跟indexOf一樣,而它僅僅是從後往前找起罷了.
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
10. Vector 類
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = -2767605614048989439L;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
protected Object[] elementData;
protected int elementCount;
//Vector比ArrayList多了一個capacityIncrement屬性
//這個屬性是在擴容的時候用到的,它表示每次擴容隻擴capacityIncrement 個空間就足夠了,該屬性可以通過構造方法給它指派.
protected int capacityIncrement;
//從構造方法中可以看出Vector的預設大小也是10,而且它在初始化的時候就已經建立了數組了,這點跟ArrayList不一樣.
//從grow方法中我們可以發現,newCapacity預設情況下是兩倍的oldCapacity,而當指定了capacityIncrement的值之後,newCapacity變成了oldCapacity+capacityIncrement.
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
//Vector的很多方法都跟ArrayList一樣,隻是多加了個synchronized來保證線程安全罷了.
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
}
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)