前言
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; // non-private to simplify nested class access //记录当前已存储的数据个数 private int size;
构造函数
方法1：ArrayList(int initialCapacity)
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); } }
- 如果有指定容量，则创建指定容量大小的数组；
- 如果没有指定容量，则创建默认大小数组，默认为8；
方法2：ArrayList
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
默认初始化一个空数组，当添加第一个元素时，会进行扩容。
方法3：ArrayList(Collection<? extends E> c)
public ArrayList(Collection<? extends E> c) { //将传进来的集合转为数组 elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) //如果数组不是object类型的，则创建一个新的数组并将内容拷贝进去 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. //创建默认空数组 this.elementData = EMPTY_ELEMENTDATA; } }
- 将传递进来集合转为数组。
- 如果传递进来的集合容量为0，则将数组引用赋为默认空数组。
- 如果数组不是Object类型数据，则创建一个新的Object数据，并将内容进行拷贝。
扩容机制
private void ensureCapacityInternal(int minCapacity) { //minCapacity:当前已插入数据个数+要插入值个数的总和，代表当前需要多少容量才够存储 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果当前数组是空的，则取默认值跟最小容量值最大者值 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code //如果数组空间不够，则进行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); }
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) //如果容量大于Integer最大值-8时，再判断是否大于Integer最大值，如果大于赋值为 Integer，小于则赋值为Integer最大值-8 // newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: //新建扩容后大小的数组，并把旧容量拷贝过去 elementData = Arrays.copyOf(elementData, newCapacity); }
- 判断目前存储的容量值（包含即将插入的值）是否大于默认值8，是则返回容量值，否则返回默认值8
- 判断当前所需容量是否大于数组容量大小，这里主要判断一下够不够用
- 如果不够用则进行扩容
- 将原来的数量扩容为1.5倍
- 创建一个新的数组，并将旧数据拷贝到新数组中
添加数据
方法：add(E e)
public boolean add(E e) { //看是否需要扩容 ensureCapacityInternal(size + 1); // Increments modCount!! //通过下标赋值 //size用于记录当前存储数据的个数 elementData[size++] = e; return true; }
- 先判断是否需要扩容
- 先在当前数组位置插入数据，插入成功后再将个数+1
方法：add(int index, E element)
public void add(int index, E element) { //检查插入下标是否超出范围 rangeCheckForAdd(index); //扩容检查 ensureCapacityInternal(size + 1); // Increments modCount!! //这里相当于将index位置的数据往后移动一个位置 System.arraycopy(elementData, index, elementData, index + 1, size - index); //在index处插入 elementData[index] = element; size++; }
- 检查下标是否在范围内
- 扩容检查
- 将要插入下标及其后面数组内容向后迁移一位
- 在Index位置插入新数据
查询数据
方法：get(int index)
public E get(int index) { //检查范围 rangeCheck(index); //获取下标值 return elementData(index); }
- 检查范围
- 直接取出数组下标位置的值
方法：indexOf(Object o)
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值分开逻辑编写，再遍历比较值是否相等
删除数据
方法：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; }
- 将下标对应的旧只取出
- 将移除下标后面的数组数据都往前移动1位
- 因为是采用拷贝的方式向前移动的，所以数组最后位置的值还是存在，所以需要将其置为null
方法：clear()
public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
循环将所有数据都置为null
总结
根据源码我们可以看到ArrayList在取数据非常简单，直接根据下标即可获取值，但是在删除数据、添加数据时，如果下标位于头尾之间，则需要移动部分数据位置，这在插入时导致效率没有LinkedList高；
所以我们在使用集合时，需要根据业务场景考虑，来选择最佳集合容器。
