【分析：ArrayList源码】

时间：2023-02-07 11:14:53

注：本系列文章中用到的jdk版本均为​​java8​​

​​ArrayList​​类图如下：

【分析：ArrayList源码】

​​ArrayList​​的底层是由数组实现的，数组的特点是​​固定​​大小，而​​ArrayList​​实现了​​动态扩容​​。

​​ArrayList​​部分变量如下，在下面的分析中会用到这些变量。


/**
* 默认容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空的对象数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 无参构造器创建的空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存放数据的数组的缓存变量
*/
transient Object[] elementData;
/**
* 元素数量
*/
private int size;

一、初始化ArrayList

初始化​​ArrayList​​一般会使用以下两个构造器

1.1 无参构造器

初始化​​ArrayList​​的时候如果不指定大小，则会创建一个空数组。


public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

1.2 指定数组大小的构造器

创建一个预估大小的数组，指定大小后只是指定了数组初始值的大小，不影响后面扩容，指定的好处就是可以节省内存及时间上的开销。


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.add(E e)源码：


public boolean add(E e) {
ensureCapacityInternal(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}

​​add()​​中​​elementData[size++] = e​​很好理解，就是将元素插入第​​size​​个位置，然后将​​size++​​，我们重点来看看​​ensureCapacityInternal(size + 1)​​方法；


private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
ensureExplicitCapacity(minCapacity);
}

​​ensureCapacityInternal()​​方法中判断缓存变量​​elementData​​是否为空，也就是判断是否是第一次添加元素，如果是第一次添加元素，则设置初始化大小为默认容量​​10​​，否则为传入的参数。这个方法的目的就是获取初始化数组容量。获取到初始化容量后调用​​ensureExplicitCapacity(minCapacity)​​方法；


private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

​​ensureExplicitCapacity(minCapacity)​​方法用来判断是否需要扩容，假如第一次添加元素，​​minCapacity​​为​​10​​，​​elementData​​容量为​​0​​，那么就需要去扩容。调用​​grow(minCapacity)​​方法。


// 数组的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 扩容大小为原来数组长度的1.5倍
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);
}

​​grow(minCapacity)​​方法对数组进行扩容，扩容大小为原数组的​​1.5​​倍，如果计算出的扩容容量比需要的容量小，则扩容大小为需要的容量，如果扩容容量比数组最大容量大，则调用​​hugeCapacity(minCapacity)​​方法，将数组扩容为整数的最大长度，然后将​​elemetData​​数组指向新扩容的内存空间并将元素复制到新空间。

当需要的集合容量特别大时，扩容​​1.5​​倍就会非常消耗空间，因此建议初始化时预估一个容量大小。

三、删除元素

​​ArrayList​​提供两种删除元素的方法，可以通过​​索引​​和​​元素​​进行删除。两种删除大同小异，删除元素后，将后面的元素一次向前移动。

ArrayList.remove(int index)源码：


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;
}

删除元素时，首先会判断索引是否大于​​ArrayList​​的大小，如果索引范围正确，则将索引位置的下一个元素赋值到索引位置，将​​ArrayList​​的大小​​-1​​，最后返回移除的元素。操作图如下，假如我要移除索引为​​1​​的元素：

【分析：ArrayList源码】

四、总结

​​ArrayList​​底层是数组实现的，可以进行动态扩容，扩容大小为原来的1.5倍，虽然可以通过动态扩容，但是数组非常大时会特别浪费空间，因此建议初始化时预估数组大小。​​ArrayList​​允许插入重复值和空值。​​ArrayList​​实现了​​RandomAccess​​接口，支持快速随机访问，就是可以通过索引快速查到某个元素，因此遍历时使用for循环的方式效率更高。​​ArrayList​​是线程不安全的，可以通过​​Collections.synchronizedList​​将其转变为线程安全的集合，不过一般不会使用，​​Vector​​和​​CopyOnWriteArrayList​​是线程安全的，​​Vector​​性能一般，逐渐被​​CopyOnWriteArrayList​​取代了。


标签：

相关文章