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=)