在平时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
,复制到起始索引为destPos
的dest
指标数组。
比方:
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
,返回minCapacity
和10
的最大值,否则返回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
,复制到起始索引为destPos
的dest
指标数组。 ArrayList
次要是基于Object[] elementData
动静数组实现。- 调用构造方法,无参的就赋值一个空数组,有初始容量的就赋值一个初始容量。
add
增加数组首先判断是否须要扩容,须要扩容,长度扩充成原来的1.5
倍。- add(E e) 在
size
赋值增加数据 - add(int index, E element) 将数组从
index
往后挪动一位,新数据增加到index
上。
- add(E e) 在
- 获取数据
get(int index)
利用数组的特定,依据下标获取数据。 remove(int index)
将index
之后的数据全副往前挪动一位,size - 1
赋为null
。