ArrayList
ArrayList 是 java 集合框架中比较常用的数据结构了，实现了 List 接口。
ArrayList相当于动态数组，与Java中的数组相比，它的容量能动态增长。
ArrayList的特点
- 允许插入的元素重复
- 插入的元素是有序的
- 动态扩容
- 非线程安全
- 基于动态数组的数据结构
- 擅长随机访问(get set)
ArrayList的成员变量
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
// 实际元素个数
private int size;
// 存放的元素集合
transient Object[] elementData;
// 默认初始大小10
private static final int DEFAULT_CAPACITY = 10;
//记录对List操作的次数,主要使用在Iterator中,防止迭代过程中集合被修改
protected transient int modCount = 0;
// 下面两个变量用在构造函数中,判断第一次添加元素时知道从空的构造函数还是有参构造函数被初始化的
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// ...
}
ArrayList的构造函数
1. 无参数构造
//无参数的构造方法
public ArrayList() {
//此时 elementData为{}
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
构造一个初始容量为10的空的list集合,但构造函数只是给elementData赋值了一个空的数组,其实是在第一次添加元素时扩大至10。
2.有参构造函数
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
只要保证传递参数值 不 < o，即可，小于 0，会抛异常。
3.集合参数构造函数
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); //转为数组
if ((size = elementData.length) != 0) { //集合大小不等于0
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)//集合类型不是Object类型
elementData = Arrays.copyOf(elementData, size, Object[].class);//复制
} else {//集合大小为0，指定一个空数组
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
ArrayList的API
// Collection中定义的API boolean add(E object) boolean addAll(Collection<? extends E> collection) void clear() boolean contains(Object object) boolean containsAll(Collection<?> collection) boolean equals(Object object) int hashCode() boolean isEmpty() Iterator<E> iterator() boolean remove(Object object) boolean removeAll(Collection<?> collection) boolean retainAll(Collection<?> collection) int size() <T> T[] toArray(T[] array) Object[] toArray() // AbstractCollection中定义的API void add(int location, E object) boolean addAll(int location, Collection<? extends E> collection) E get(int location) int indexOf(Object object) int lastIndexOf(Object object) ListIterator<E> listIterator(int location) ListIterator<E> listIterator() E remove(int location) E set(int location, E object) List<E> subList(int start, int end) // ArrayList新增的API Object clone() void ensureCapacity(int minimumCapacity) void trimToSize() void removeRange(int fromIndex, int toIndex)
ArrayList主要方法解析
1.add增加
public boolean add(E e) {//添加一个元素
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e; //长度+1
return true; //返回boolean 类型
}
public void add(int index, E element) {//指定索引位置添加一个元素
rangeCheckForAdd(index);//检查集合长度级索引大小
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);//复制
elementData[index] = element; //元素放到集合指定索引的位置
size++;//长度+1
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//默认长度10
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//记录修改次数
//
if (minCapacity - elementData.length > 0)//传入长度大于当前长度，扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//老容量
int newCapacity = oldCapacity + (oldCapacity >> 1);//老容量+ 老容量/2
if (newCapacity - minCapacity < 0)// 新容量 小于参数传入容量,修改新容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //新容量大于最大容量
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);//扩容拷贝
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow 传入容量 < 0 抛异常
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
添加元素时，会指定默认为10的容量，当添加元素导致集合容量大于10，触发扩容机制，扩容为原来的1.5倍。
2.remove移除
public E remove(int index) {
//校验删除位置是否合理
rangeCheck(index);
// 同add理由一样
modCount++;
// 保存待删除元素
E oldValue = elementData(index);
// 判断删除位置：如果>0不在尾部需要调用System.arraycopy，否则在尾部直接删除
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;
}
当我们调用 remove(int index) 时，首先会检查 index 是否合法，然后再判断要删除的元素是否位于数组的最后一个位置。
如果 index 不是最后一个，就再次调用 System.arraycopy() 方法拷贝数组。
如果 index 是最后一个元素那么就直接将数组的最后一个位置空，size – 1即可。
3.get获取
public E get(int index) { //获取指定索引的值
rangeCheck(index);//是否越界
return elementData(index);//返回指定下标的值
}
private void rangeCheck(int index) {
if (index >= size) //索引大于 集合长度，抛异常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
由于ArrayList底层是基于数组实现的,所以获取元素就相当简单了,直接调用数组随机访问即可。
4.set修改
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}}
修改指定位置的元素为新元素，首先需要校验给定index的值，index必须大于等于0，小于size，然后将新元素保存到index位置，并将旧元素返回。
5.扩容操作
public void ensureCapacity(int minCapacity) {
//修改计时器
modCount++;
//ArrayList容量大小
int oldCapacity = elementData.length;
/*
* 若当前需要的长度大于当前数组的长度时，进行扩容操作
*/
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
//计算新的容量大小，为当前容量的1.5倍
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
//数组拷贝，生成新的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
ensureCapacityInternal方法的目的是确保给定的参数指定的容量值。
真正的扩容逻辑位于grow方法中：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);// 扩容为原容量的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果最后决定扩容的容量比允许的最大数组容量值要大，那么则进行超限处理
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 处理超限问题
// 如果给定的minCapacity为负数（首位为1）则抛出异常错误OutOfMemoryError
// 如果给定容量大于数组最大容量，则取整数的最大值为容量，否则使用数组的最大容量作为扩容容量
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}}
ensureCapacity()，该方法就是ArrayList的扩容方法，每次扩容处理会是1.5倍。
1.5倍的扩容是最好的倍数，因为一次性扩容太大(例如2.5倍)可能会浪费更多的内存(1.5倍最多浪费33%，而2.5被最多会浪费60%，3.5倍则会浪费71%……)。
但是一次性扩容太小，需要多次对数组重新分配内存，对性能消耗比较严重。
所以1.5倍刚刚好，既能满足性能需求，也不会造成很大的内存消耗。
Fail-Fast机制
在我们每次操作集合的时候，都会记录一个修改次数。
modCount++ 其实他就是fail-fast机制，它是Java集合的一种错误检测机制。
当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。记住是有可能，而不是一定。例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
ArrayList总结
最后做一下总结，知识点归纳：
- ArrayList底层采用数组实现，拥有快速随机访问能力，但是非线程安全的集合。
- ArrayList默认容量为10，扩容规则为当要保存的新元素所需的容量不足时触发。
- 扩容机制为首先扩容为原始容量的 1.5 倍。
- 扩容之后是通过数组的拷贝来确保元素的准确性的，所以尽可能减少扩容操作。
- 如果在遍历的时候发生结构性变化，会触发ConcurrentModificationException异常。
- 结构性变化包括：添加新元素，删除元素。
- ArrayList支持序列化功能，支持克隆（浅拷贝）功能，排序功能等。
陈睿mikechen
10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》