在平时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 = {};
  • ArrayList是基于数组的一个实现,elementData就是底层的数组。
  • size 是记录数组的个数。

构造方法

ArrayList()

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

无参构造方法,创立数据间接赋值一个空数组

ArrayList(int initialCapacity)

赋一个初始化容量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);    }}
  • 初始化容量initialCapacity大于零,新建长度initialCapacity的数组。
  • 初始化容量initialCapacity等于零,新建一个空数组。

增加数据

增加数据有两个办法:

  • 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 == 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 = 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 下标数据。

获取数据

获取数据只有通过数组下标获取数据 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

remove(int index)

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

总结

  • 数组的扩容、增加和删除都须要用到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