ArrayList简介
image.png
image.png
ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable接口。
这里需要注意：
①实现Cloneable接口，即覆盖了函数clone()，能被克隆。
②实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
③和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。[图片上传中...(image.png-bee6d1-1547022393428-0)]
ArrayList数据结构
image.png
ArrayList包含了两个重要的对象：elementData 和 size。
① elementData 是"Object[]类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长，具体的增长方式，请参考源码分析中的ensureCapacity()函数。
② size 则是动态数组的实际大小。
部分源码解读
①构造方法
//创建一个指定了大小的空列表
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);
}
}
// 构造没有指定大小的空列表 ，这里没有初始化，会在第一次add元素时初始化
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 创建一个包含collection的ArrayList，也就是说是有指定元素的
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
②数组扩容
// 判断array是不是为空，但是这个方法并没有被调用，不知道写了干啥
public void ensureCapacity(int minCapacity) {
//缓冲区和默认列表比较，如果相同minExpand为10，不同minExpand为0
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
// 扩容检查
private void ensureCapacityInternal(int minCapacity) {
// 第一次add操作初始化，如果为空ArrayList，那么初始化容量为10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 调用这个方法，来判断是不是要扩容了
ensureExplicitCapacity(minCapacity);
}
// 判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 这个时候表示列表现有空间已经被元素填满了，那就要扩容了
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 要分配数组的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// (oldCapacity >> 1)就是oldCapacity/2 的意思，也就是总体扩大1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断容量是否到达long int 最大临界值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 数组浅拷贝，把原来的复制到新的里面
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 检查是否超过最大容量 0x7fffffff ，看看是否抛出异常
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
由此我们可知：
当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：新的容量是原来的1.5倍。
③增加和删除
// 在末尾添加元素
public boolean add(E e) {
// 扩容检查
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 在指定位置添加元素
public void add(int index, E element) {
// 越界了没
rangeCheckForAdd(index);
// 扩容检查
ensureCapacityInternal(size + 1); // Increments modCount!!
//复制数组，空出index用于插入新元素，其他元素后移
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
// 删除指定位置的元素
public E remove(int index) {
// 越界了没
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 确定要复制的数组个数
int numMoved = size - index - 1;
// index后的数据前移
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
// 删除指定内容的元素，只删除第一个匹配项
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;
}
// 删除指定位置的元素，这个就是被上面的remove调用的
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
}
由此我们可知：
为什么ArrayList 不适合频繁插入和删除操作？就是因为在ArrayList中我们一直会调用 System.arraycopy 这个效率很低的操作来复制数组，所以导致ArrayList在插入和删除操作中效率不高。
④缩容
// 将当前容量值设为实际元素个数
// 当我们存完元素，要根据元素个数，适当调整array的大小，避免内存浪费
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
⑤说一下copyof
我们看到不管是扩容，还是增加删除元素都频频用到copyof方法，那么他是怎么实现的呢？
image.png
我们挑一个看看
/**
* @Description 复制指定的数组, 如有必要用 null 截取或填充，以使副本具有指定的长度
* 对于所有在原数组和副本中都有效的索引，这两个数组相同索引处将包含相同的值
* 对于在副本中有效而在原数组无效的所有索引，副本将填充 null，当且仅当指定长度大于原数组的长度时，这些索引存在
* 返回的数组属于 newType 类
* @param original 要复制的数组
* @param newLength 副本的长度
* @param newType 副本的类
*
* @return T 原数组的副本，截取或用 null 填充以获得指定的长度
* @throws NegativeArraySizeException 如果 newLength 为负
* @throws NullPointerException 如果 original 为 null
* @throws ArrayStoreException 如果从 original 中复制的元素不属于存储在 newType 类数组中的运行时类型
* @since 1.6
*/
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
从代码可知，数组拷贝时调用的是本地方法 System.arraycopy() ；
Arrays.copyOf()方法返回的数组是新的数组对象，原数组对象仍是原数组对象，不变，该拷贝不会影响原来的数组。
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
额，System.arraycopy源码就这么点0.0
ArrayList的遍历方式
// 迭代器遍历
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}
// 由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。
Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
value = (Integer)list.get(i);
}
// for循环
Integer value = null;
for (Integer integ:list) {
value = integ;
}
使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！
网友评论