ArrayList源码解析

在平时Java,存储数据需要用到列表,而大多时候都能用到ArrayList,比如Mybatis查询数据列表,返回列表都是ArrayList,很多数据的存放也用到了ArrayList

jdk 版本: 1.8
ArrayList 是基于大小可变的数组实现,并允许添加null值, 根据下标就能数据查询快。数组一旦初始化就确定好了大小,如果需要添加数据,就需要做数据的复制,这些操作比较耗时。
数组拷贝 ArrayList数组的扩容、添加和删除需要用到数组的拷贝,主要用到了以下两个方法:
  • System.arraycopy
  • Arrays.copyOf
System.arraycopy
System.arraycopy()Java的原生的静态方法,该方法将源数组元素拷贝到目标数组中去。
参数详解:
  • src 源数组
  • srcPos 源数组拷贝的起始索引
  • dest 目标数组
  • destPos 拷贝到目标数组的起始索引
  • length 拷贝元素的个数
    src源数组,起始索引为srcPos,个数为length,复制到起始索引为destPosdest目标数组。
比如:
int[] srcArray = new int[]{1,2,3,4,5,6}; int[] desArray = new int[5]; System.arraycopy(srcArray,1,desArray,2,3); System.out.println("desArray: " + Arrays.toString(desArray));

输出:
[0, 0, 2, 3, 4]

Arrays.copyOf
Arrays.copyOf本质也是调用System.arraycopy方法:
public static int[] copyOf(int[] original, int newLength) { int[] copy = new int[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }

首先创建一个新的数组copy,将original数组全部复制给copy数组。
主要字段:
// 底层数组 transient Object[] elementData; // 数组个数大小 private int size; // 默认空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = https://www.it610.com/article/{};

  • ArrayList是基于数组的一个实现,elementData就是底层的数组。
  • size 是记录数组的个数。
构造方法 ArrayList()
public ArrayList() { this.elementData = https://www.it610.com/article/DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

无参构造方法,创建数据直接赋值一个空数组。
ArrayList(int initialCapacity)
赋一个初始化容量initialCapacity:
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = https://www.it610.com/article/new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }

  • 初始化容量initialCapacity大于零,新建长度initialCapacity的数组。
  • 初始化容量initialCapacity等于零,新建一个空数组。
添加数据 【ArrayList源码解析】添加数据有两个方法:
  • add(E e) 直接添加在数组尾部。
  • add(int index, E element) 根据下标添加数据。
add(E e)
在列表尾部添加数据:
/** * Appends the specified element to the end of this list. */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }

ensureCapacityInternal 判断添加数据后的容量是否足够,如果不够,做扩容操作。
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData =https://www.it610.com/article/= 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); }

ensureCapacityInternal 作用是判断容量当前容量是否足够存放新的数据,如果不够就做扩容操作。
calculateCapacity计算容量,如果数组为null,返回minCapacity10的最大值,否则返回minCapacity。这个方法就是返回数组的大小。
调用无参构造方法ArrayList(),再调用add()方法,首先数组容量会变成10。这也是为什么无参构造方法ArrayList()上面有会有注解Constructs an empty list with an initial capacity of ten.
ensureExplicitCapacity 判断需要的容量minCapacity大于当前数组的长度elementData.length,将会做扩容处理,也是调用grow方法:
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); // 拷贝数组到新的长度数组 elementData = https://www.it610.com/article/Arrays.copyOf(elementData, newCapacity); }

group 主要做了两件事:
  • 长度扩大到原来的 1.5倍
  • 拷贝数组到新长度的数组
做完判断是否要做扩容之后,直接在size位置上赋值要添加的元素,然后size再自增。
elementData[size++] = e;

add(E e)流程总结
  • 判断数据容量是否足够,如果是空数组,返回10,其他容量返回当前数组size + 1
  • 返回容量和当前数组长度对比,小于做扩容处理。
  • 扩容长度为原来长度的1.5倍,将数组赋值给长度为原来数组1.5倍的新数组。
  • 在数组的最末尾size赋值。
add(int index, E element)
此添加数据是在指定的下标添加数据。
public void add(int index, E element) { // 下标是否越界 rangeCheckForAdd(index); // 判断是否要扩容 ensureCapacityInternal(size + 1); // Increments modCount!! // 复制i到size的数据到i+1 到size +1 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }

add(int index, E element) 在index下标添加数据,
  • 首先判断index 是否在0 ~size之间。
  • 判断是否要扩容,需要扩容,进行1.5倍扩容。
  • 数据迁移,把index以后的数据全部往后移动一位。
  • 赋值index 下标数据。
ArrayList源码解析
文章图片

获取数据 获取数据只有通过数组下标获取数据 get(int index)
public E get(int index) { //检查是否超过数组范围 rangeCheck(index); return elementData(index); }@SuppressWarnings("unchecked") E elementData(int index) { // 通过下标获取数据 return (E) elementData[index]; }

这里获取数据就比较简单:
  • 检查下标是否超过数组范围。
  • 通过下标访问数据。
删除数据 remove(Object o)
删除列表中第一个匹配的元素:
public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; }

判断要删除数据是否为null:
  • 为空,判断elementData[index]是否为空。
  • 不为空,判断元素equals是否匹配elementData[index]
上面判断都为true时,调用fastRemove方法:
private void fastRemove(int index) { modCount++; 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 }

移动数组数据,index+1 以及之后的数据往前移动一位,最后一位size-1赋值为null
ArrayList源码解析
文章图片

remove(int index)
根据index下标删除数据。
public E remove(int index) { // 是否越界 rangeCheck(index); modCount++; E oldValue = https://www.it610.com/article/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 workreturn oldValue; }

总结
  • 数组的扩容、添加和删除都需要用到System.arraycopy方法,System.arraycopy是将src源数组,起始索引为srcPos,个数为length,复制到起始索引为destPosdest目标数组。
  • ArrayList主要是基于Object[] elementData动态数组实现。
  • 调用构造方法,无参的就赋值一个空数组,有初始容量的就赋值一个初始容量。
  • add 添加数组首先判断是否需要扩容,需要扩容,长度扩大成原来的1.5倍。
    • add(E e) 在size赋值添加数据
    • add(int index, E element) 将数组从index往后移动一位,新数据添加到index上。
  • 获取数据get(int index)利用数组的特定,根据下标获取数据。
  • remove(int index)index之后的数据全部往前移动一位,size - 1赋为null

    推荐阅读