将分析以下内容
- 字段
- 构造函数
- 扩容
- 插入和删除导致的数组大幅度移动
1.首先来看一下ArrayList里面的属性
下面是两个经常会用到的属性
这个就是用来存储元素的数组
transient Object[] elementData;
这个是数组存储元素的总数，相信size()方法大家都用过
注意不要跟数组长度混淆，数组长度是elementData.length()
private int size;
下面三个是ArrayList中定义的默认值，这里只需要记住默认初始容量为10就行了
//默认容量为10
private static final int DEFAULT_CAPACITY = 10;
//当给定容量为0时使用的数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//当未给定容量时使用的默认数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
2.接下来我们看一看ArrayList的构造函数
首先是不带参数的，会使用默认的DEFAULTCAPACITY_EMPTY_ELEMENTDATA作为数组，大家应该注意到了，该数组的长度是为0的，所以后面肯定会进行扩容
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
下面是给定初始容量的构造函数
public ArrayList(int initialCapacity) {
//如果容量大于0，使用给定容量初始化数组
//如果容量等于0，使用EMPTY_ELEMENTDATA作为存储数组
//否则就是小于0了，直接抛异常
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
这里注意【EMPTY_ELEMENTDATA】 和 【DEFAULTCAPACITY_EMPTY_ELEMENTDATA】其实是一样的，只是使用的语义不同，如果你未指定初始容量，那么使用默认的【DEFAULTCAPACITY_EMPTY_ELEMENTDATA】，如果你指定了容量为0，那么就使用【EMPTY_ELEMENTDATA】
下面这个就不过多细说了，就是把你给定的集合转换为数组，并给size赋值
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;
}
}
3.接下来我们来看一下ArrayList是怎么扩容的
public boolean add(E e) {
ensureCapacityInternal(size + 1); //这里就是执行扩容逻辑
elementData[size++] = e; //扩容完成后就执行添加
return true;
}
这里注意size + 1即使我们即将插入的元素的索引，也就是说如果此时已经有5个元素了，那么就会将6作为minCapacity（也就是最小容量，起码也得再让我装一个）传递给ensureCapacityInternal()进行扩容逻辑
——这里我们成minCapacity为最小申请容量
下面我们层层递进看一看是怎么完成扩容的
3.1-ensureCapacityInternal()——确保内部容量
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
这里可以看到需要调用calculateCapacity()
3.2-calculateCapacity()——计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
这个方法就是返回最小最小申请容量和默认容量（10）的较大值，然后作为新的容量
可以理解为如下：
第一天
儿子：爸，我要6元钱买点吃的
爸：6元钱能买什么？我这有张10块的，拿去用
第二天
儿子：爸，我要11元钱买点吃的
爸：要这么多，拿去吧！11块，省着点花
好了，完成了calculateCapacity()方法可以看到3.1我们还需要调用ensureExplicitCapacity()
3.3-ensureExplicitCapacity()——确保精准容量（也就是是否执行扩容）
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//数组修改的次数,该变量在AbstractList定义，不研究
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
从上面可以看出当最小申请容量小于我们的数组长度时，那么就要执行grow()方法，也就是扩容
3.4-grow()——扩容
//数组分配的最大容量，没人的数组想要这么大的吧，很占内存的
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
具体就是
- 获取旧容量
- 计算新容量（旧容量+旧容量右移1位）
- 判断新容量是否小于最小申请容量（因为最初容量为0）
- 判断新容量是否大于最大请求容量
- 把原来的数据复制到新分配的数组
——以上就是扩容的全过程
让我们来总结一下
- 调用add()方法添加元素
- 调用ensureCapacityInternal()开始我们的扩容逻辑
- 调用calculateCapacity()初步修改我们的最小申请容量
- 调用ensureExplicitCapacity()判断是否需要进行扩容
- 调用grow()进行扩容
放出测试代码
public class ArrayLengthTest {
public static void main(String[] args) throws Exception {
ArrayList<String> list = new ArrayList<String>();
System.out.println("刚初始化时的长度为：" + getArrayLength(list));
list.add("one");
System.out.println("添加一个元素后的长度为：" + getArrayLength(list));
for (int i = 0; i <10; i++) {
list.add("for");
}
System.out.println("添加第11个元素后的长度为：" + getArrayLength(list));
}
public static int getArrayLength(ArrayList list) throws Exception {
Class<ArrayList> clazz = ArrayList.class;
//通过反射获取elementData字段
Field field = clazz.getDeclaredField("elementData");
//设置为可访问
field.setAccessible(true);
//这就是获取到的elementData属性，注意它就是Object[]类型的
Object[] elementData = (Object[])field.get(list);
return elementData.length;
}
}
4.怎么能少得了add(),remove()方法
4.1-add()
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
//在指定的角标处插入元素
public void add(int index, E element) {
//检查插入的角标是否越界
rangeCheckForAdd(index);
//扩容逻辑
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
这里回过来看一下add()方法，第一个方法已经说过了
注
意
这里看一System.arraycopy()方法
这里只是将4个数进行了挪动，而通过看上面源码，当你在ArrayList指定位置添加元素后，将会导致整个数组后半截进行挪动
4.1-remove()
public E remove(int index) {
rangeCheck(index); //检查插入的角标是否越界
modCount++; //数组修改的次数+1
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
return oldValue;
}
同样，在移除元素时也会导致整个数组后半截进行移动
这里，相信大家应该明白ArrayList为什么不适合做从中间增删频繁的存储
