ArrayList
是 List
接口的一个实现类,那么 ArrayList
的底层是如何实现的呢?让我们来一探究竟。
先来看看 ArrayList
中比较重要的两个属性:
transient Object[] elementData;
private int size;
elementData
用来存储 ArrayList
中的元素,其实 ArrayList
的底层是用 Object[]
数组来实现的。size
指的是的逻辑长度,就好像一个水杯,容量是 600 毫升,但杯中只有 200 毫升的水,ArrayList
容器就是水杯, 这个 size
属性表示的就是水杯中水的容积。无参构造方法:
123 | public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;} |
---|
很简单,就一行语句,elementData
在上面我们已经知道是什么了,那 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
又是什么呢?
1 | private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; |
---|
原来只是一个空的 Object[]
。
指定容量的构造方法:
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);
}
}
也很简单,就是为 ArrayList
指定初始容量。这里主要对传入的容量做了有效性验证,当传入的参数小于 0 时,抛出异常。当参数等于 0 时,则用一个空的数组常量 EMPTY_ELEMENTDATA
来初始化。
用一个 Collection 对象进行构造的的构造方法:
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
首先将传入的参数转为对象数组赋值给 elementData
,如果传入的 Collection
参数的长度为 0,则就将空的常量数组对象 EMPTY_ELEMENTDATA
赋给了 elementData
。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
调用了 ensureCapacityInternal
函数:
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
这里判断 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
表示如果如果为没有初始化容量时,用默认容量 DEFAULT_CAPACITY
也就是 10,来开启空间,也就是上面我们说的水杯的容量。
接下来看 ensureExplicitCapacity
方法:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
继续看 grow
方法:
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 对 ArrayList 容量进行 1.5 倍扩容。
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容后的容量还不够实际占用的容量,那么需要扩容到实际占用容量的大小。
// 如当前 newCapacity 为 10,扩容后为 15,
// 但现在实际的元素数量为 16 个,那么至少应该先装下这 16 个。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 防止阔中的过大,过大时,则使用 Integer.MAX_VALUE 代替。
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 的大小,每次扩容都为当前容量的 1.5 倍,当然也进行了扩容过大或过小的限制。 其扩容原理就是创建一个容量为当前容量 1.5 倍的新数组,将旧数组的内容拷贝给新数组。
add(int index, E element)
public void add(int index, E element) {
// 判断要插入的位置不小于 0 且不大于当前最大位置
rangeCheckForAdd(index);
// 容量扩容检测,具体参见 add(E e) 方法
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
看过了 add(E e)
的源码,这里也就很好理解了,先进行插入位置有效性判断,然后判断容量是否需要扩容,然后先将插入位置开始的所有元素向后移动一位,最后将需要插入的元素插入指定位置。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
ArrayList 的底层是用数组实现的,那么获取元素也就很方便了,判断获取位置合法后,直接用下标获取即可。
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
这个方法其实就是修改指定位置的元素,先拿到要覆盖的元素,然后将新元素赋值上去,最后返回覆盖的元素即可。
public E remove(int index) {
rangeCheck(index);
modCount++;
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;
}
先进行有效性判断,然后从要删除的元素开始的所有元素都向前拷贝一位,并将最后一位设值为 null
。
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;
}
如果要找的内容 null
,则依次用 == 判断是否为要找的元素,如果不为 null
,则用 equals 来依次判断。
根据上方的源码分析,我们可以得出 ArrayList
的一些特性:
ArrayList
底层数据结构是对象数组,如不指定长度,则初始容量为 10。所以我们在使用时要注意:
ArrayList
查找元素很快,但删除元素和添加元素的效率相对较差。