在平时Java
,存储数据需要用到列表,而大多时候都能用到ArrayList
,比如Mybatis
查询数据列表,返回列表都是ArrayList
,很多数据的存放也用到了ArrayList
。
jdk 版本: 1.8
ArrayList
是基于大小可变的数组实现,并允许添加null
值, 根据下标就能数据查询快。数组一旦初始化就确定好了大小,如果需要添加数据,就需要做数据的复制,这些操作比较耗时。数组拷贝
ArrayList
数组的扩容、添加和删除需要用到数组的拷贝,主要用到了以下两个方法:System.arraycopy
Arrays.copyOf
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 = https://www.it610.com/article/{};
ArrayList
是基于数组的一个实现,elementData
就是底层的数组。size
是记录数组的个数。
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
等于零,新建一个空数组。
- add(E e) 直接添加在数组尾部。
- add(int index, E element) 根据下标添加数据。
在列表尾部添加数据:
/**
* 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
,返回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 = https://www.it610.com/article/Arrays.copyOf(elementData, newCapacity);
}
group
主要做了两件事:- 长度扩大到原来的 1.5倍
- 拷贝数组到新长度的数组
elementData[size++] = e;
add(E e)流程总结
- 判断数据容量是否足够,如果是空数组,返回
10
,其他容量返回当前数组size + 1
。 - 返回容量和当前数组长度对比,小于做扩容处理。
- 扩容长度为原来长度的
1.5倍
,将数组赋值给长度为原来数组1.5
倍的新数组。 - 在数组的最末尾
size
赋值。
此添加数据是在指定的下标添加数据。
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];
}
这里获取数据就比较简单:
- 检查下标是否超过数组范围。
- 通过下标访问数据。
删除列表中第一个匹配的元素:
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 = 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
,复制到起始索引为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
。
推荐阅读
- 新手计算机学习路线
- #|tomcat安装配置及IDEA配置方法【亲测有效】
- html|分享 82个实用的前端开发工具
- 三.Java|3.1_4 JavaSE入门 P3 【Java基础】流程语句【循环结构】、随机数
- 面试|部门新来了个字节25K出来的,让我见识到了什么是天花板
- 面试|MYSQL中的索引与事务———javaweb(8)(面试必考)
- java-ee|网络编程(7)(网络层协议)-----------javaweb
- JavaEE初阶|创建一个线程——— Javaweb (3)
- mysql|MYSQL的JDBC编程