ArrayList源码详解
2019-07-18 本文已影响0人
疯狂的磊哥
ArrayList概述
ArrayList是一个非线程安全，基于数组实现的一个动态数组，本源码版本：1.8.0_172
ArrayList结构
ArrayList.png
- RandomAccess接口：标记接口，用来表明支持快速随机访问，也就是说底层是数组实现的集合
- Serializable接口：标记接口，java提供的序列化接口，为对象提供标准的序列化和反序列化操作
- Cloneable接口：标记接口，只有实现了这个接口，然后才能调用类的clone()方法，否则抛出CloneNotSupportedException异常
ArrayList的源码分析
ArrayList属性
/**
* 初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 一个空数组的共享对象
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 也是一个空数组的共享对象，和EMPTY_ELEMENTDATA不同的就是，
* 在添加第一个元素时，如果elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA时
* 设置数组大小时，取初始容量和最小容量的最大值。空构造器中使用
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* ArrayList中实际存放数据的数组
*/
transient Object[] elementData;
/**
* ArrayList的大小，也就是elementData实际存放数据个数
*/
private int size;
ArrayList构造器
/**
*
* 无参数的构造器
* 将elementData指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
*
* 指定初始容器的构造器
*
* 如果初始容器大于0,
* 则elementData创建一个长度为initialCapacity的Object数组；
*
* 如果初始容量等于0
* 则将数组指向共享空数组对象EMPTY_ELEMENTDATA
*
* 如果初始容量小于0
* 抛出IllegalArgumentException异常
*
* @param 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);
}
}
/**
*
* 构造一个包含指定集合里元素的对象，按照集合的迭代器返回顺序排列
*
* elementData指向c.toArray()的数组对象
*
* 如果数组长度不等于0
* 判断数组类型是不是Object[].class，
* 如果不是，需要通过Array.copyOf将数组元素转换成Object[].class类型的数组
*
* 思考：为什么上面需要判断c.toArray()返回的类型是否是Object[].class
*
* 因为Arrays.asList()获取的List对象的toArray方法是用的clone()，
* 导致实际返回有可能不是Object数组，而是一个具体类型的数组详情可以了解
* https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
*
* 如果数组长度等于0
* 则将数组指向共享空数组对象EMPTY_ELEMENTDATA
*/
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;
}
}
ArrayList新增相关详解
/**
* 将指定的元素附加到列表的尾部
*
* @param e 要附加到列表的元素
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//增加容量，以确保它至少可以容纳由最小容量参数指定的元素数量（size + 1）。
ensureCapacityInternal(size + 1); // Increments modCount!!
//将元素添加到数组size的位置，数组大小增加1
elementData[size++] = e;
return true;
}
/**
*
* @param minCapacity 所需最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 记录ArrayList操作次数
*
* 判断当前容量是否满足所需最小容量，无法满足则需要进行扩容处理
*
* @param elementData
* @param minCapacity 所需最小容量
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* 记录ArrayList操作次数
*
* 判断当前容量是否满足所需最小容量，无法满足则需要进行扩容处理
*
* @param minCapacity 所需最小容量
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 扩容，以确保它至少可以容纳由最小容量参数指定的元素数量(minCapacity)
*
* 1、备份当前容量
*
* 2、计算新容量
* 新容量 = 当前容量 + 当前容量右移一位
* (1) 新容量 > 0 且 新容量 < Integer.MAX_VALUE
* (2) 新容量 < 0 (计算容量时，出现溢出情况，也就是大于Integer.MAX_VALUE)
*
* 3、新容量与所需最小容量比较
* 新容量减去所需最小容量小于0，新容量设置为最小容量
*
* 4、新容量与MAX_ARRAY_SIZE比较
* 新容量大于MAX_ARRAY_SIZE，根据hugeCapacity()方法获取新容量，防止溢出
*
* 思考：为啥 MAX_ARRAY_SIZE = Integer.MAX_VALUE-8，需要减去8
* 因为数组对象有一个额外的元数据，由于虚拟机的不同，可能占用的位数不一样，
* 这个元数据用于表示数组的大小
*
* 5、复制指定的数组到指定长度
*
* @param minCapacity 所需最小容量
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
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小于0，出现内存溢出，抛出OutOfMemoryError异常
*
* 如果minCapactity大于MAX_ARRAY_SIZE，设置容量为Integer.MAX_VALUE，
* 否则，设置为MAX_ARRAY_SIZE。
*
* 思考：结合上面的MAX_ARRAY_SIZE=Integer.MAX_VALUE-8，为何可以设置为
* Integer.MAX_VALUE?
*
* @param minCapacity 所需最小容量
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* 将指定元素插入到列表中的指定位置，并将当前位于该位置的元素和随后的元素向右移动一位
*
* @param index 要插入指定元素的索引
* @param element 要插入的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
//检查元素索引的范围是否合法，也就是 index > size || index < 0，
//将要抛出数组越界异常 IndexOutOfBoundsException
rangeCheckForAdd(index);
//增加容量，以确保它至少可以容纳由最小容量参数指定的元素数量（size + 1）,具体可看上面详解
ensureCapacityInternal(size + 1); // Increments modCount!!
//从index索引位置开始，将位于该位置的元素和随后的元素向右移动一位（请持续关注，后续源码分析）
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//将index的所有位置执行element元素
elementData[index] = element;
//数组长度加1
size++;
}
//判断数组是否越界，越界抛出异常
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 将集合中的所有元素加入到列表尾部
*
* @param c 需要添加的集合
* @return <tt>true</tt> 集合是否有改变
* @throws NullPointerException 传入的集合为空，抛出NullPointerException
*/
public boolean addAll(Collection<? extends E> c) {
//获取集合中的所有元素，转换成Object[]数组
Object[] a = c.toArray();
//获取集合大小
int numNew = a.length;
//增加容量，以确保它至少可以容纳由最小容量参数指定的元素数量（size + 1）,具体可看上面详解
ensureCapacityInternal(size + numNew); // Increments modCount
//将需要插入数组加入到当前数组中
System.arraycopy(a, 0, elementData, size, numNew);
//修改当前集合的大小
size += numNew;
//返回当前集合是否改变
return numNew != 0;
}
/**
* 将集合中的所有元素加入到指定index位置
*
* @param index 要插入指定元素的索引
* @param c 需要添加的集合
* @return <tt>true</tt> 集合是否有改变
* @throws NullPointerException 传入的集合为空，抛出NullPointerException
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
//判断index索引位置及之后的元素需要移动的大小
int numMoved = size - index;
//如果移动大小 > 0，将当前集合中数组elementData 中index索引位置及以后所有元素（numMoved个元素）移动到index + numNew位置开始
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//将需要插入的集合中的元素插入到elementData数组的index开始，numNew个元素结束的位置
System.arraycopy(a, 0, elementData, index, numNew);
//修改当前集合的大小
size += numNew;
//返回当前集合是否改变
return numNew != 0;
}
ArrayList移除相关解析
/**
* 移除集合中指点位置的元素，并将后续元素左移动，也就是后续元素下标减一
*
* 1、检查索引的有效范围，范围异常抛出IndexOutOfBounndsException异常
* 索引有效返回 0~size-1
* 2、记录集合修改次数
* 3、获取索引index位置元素信息
* 4、计算需要移动的元素个数
* 5、判断移动个数大于0
* 6、将索引index之后的元素都前移动一位
* 7、设置最后一位的值为null (为了gc工作，释放内存),将集合大小减一
* 8、返回异常元素信息
*
* @param index 需要移除元素的位置索引
* @return 集合中移除的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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;
}
/**
* 从集合中移除第一次出现指定元素的元素，如果指定元素不存在返回false，存在返回true
*
* 1、如果指定元素为空，则通过for 0~size，判断数组元素是否为空，
* 为空则通过fastRemove(index)异常元素，说明元素存在返回true
*
* 2、如果指定元素不为空，则通过for 0~size，判断数组元素是否equests指定元素
* 如果相等则通过fastRemove(index)异常元素，说明元素存在返回true
*
* 3、元素不存在，返回false
* @param o 需要移除的元素
* @return true-元素存在，false-元素不存在
*/
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(int index)区别
* a) 没有检查索引有效性
* b) 没有查找指定索引元素信息
* c) 没有返回指定索引元素信息
*/
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
}
/**
* 从集合中移除指定集合中所有元素
*
* 判断集合是否为空，为空抛出NullPointerException异常
*
* 通过batchRemove(c, false)删除集合中元素，其中false代码删除c中元素
*
* @param c 需要从集合中移除的所有元素集合
* @return true-集合改变，即集合中有原始被移除 false-集合未改变
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException 输入的集合参数为空抛出此异常
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
/**
* 只保留指定集合中存在的元素，其他元素删除
*
* 判断集合是否为空，为空抛出NullPointerException异常
*
* 通过batchRemove(c, true)删除集合中元素，其中true代码保留c中元素
*
* @param c 需要从集合中保留的所有元素集合
* @return true-集合改变，即集合中有原始被移除 false-集合未改变
* @throws ClassCastException
* @throws NullPointerException 输入的集合参数为空抛出此异常
*/
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
/**
* 从集合中批量移除或者保留指定集合中的元素
*
* @param c 指定集合
* @param complement 标识 true-表示从集合中保留集合c中元素
* false-标识从集合中删除集合c中的元素
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
//很巧妙的设计，r-是扫描的索引 w-是写入索引（即有效数据索引）
//当条件满足时候，w的索引位置的值指向r的索引位置的值
int r = 0, w = 0;
boolean modified = false;
try {
//遍历集合
for (; r < size; r++)
//1、先判断集合c中是否包含集合中索引位置r的元素
//2、如果complement == true，则包含需要从集合中移除，否则保留
//3、如果complement == false，则包含需要从集合中保留，否则移除
// 思考：此地方比较绕，需要细细思考代码运行情况
if (c.contains(elementData[r]) == complement)
//将索引w的原值值设置为索引r位置的值，然后索引 +1
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
// 当出现异常的时候，需要将没有遍历完的元素向前移动。
// 需要移动的元素个数 size-r。
// 需要移动的位置 w
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
//更新w索引的值
w += size - r;
}
//如果w的值不等于集合大小，说明出现删除操作，删除范围索引w到索引size
//此时需要将此区间的值设置为null,以便gc回收。同时需要设置集合大小为w
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
/**
* 根据过滤器或者条件判断是否需要移除元素，jdk1.8新增方法
*
* 思考：本方法实现可以和batchRemove实现做比较，判断优缺点
* 大家可以讨论下这两种方法的优缺点，已经你更喜欢那种实现
*
* @param filter Predicate函数式接口，主要实现test方法返回boolean
* @return boolean 集合是否改变 true-有改变
*/
@Override
public boolean removeIf(Predicate<? super E> filter) {
//判断集合是否为空，为空抛出NullPointerException异常
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
//计数器，记录需要移除记录数
int removeCount = 0;
//BitSet类，记录需要移除记录的索引，BitSet类后续分析
final BitSet removeSet = new BitSet(size);
//记录当前集合修改次数
final int expectedModCount = modCount;
//记录集合大小
final int size = this.size;
//集合被改变或者集合遍历完成，退出循环
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
//使用filter.test方法判断是否需要移除元素element，返回true
//则通过removeSet记录索引，计数器记录修改次数
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
//集合发生结构改变的调用抛出ConcurrentModificationException异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
//判断集合中是否存在元素需要移除，也就是计数器大于0
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
//获取新集合大小
final int newSize = size - removeCount;
//遍历集合，剔除需要移除的索引，将集合元素左移动
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
//获取集合索引，如果遇到需要移除的索引，自动获取下一个索引
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
//清理无效索引元素 newSize~size的索引的元素，让gc回收内存
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
//将集合大小设置为新集合大小
this.size = newSize;
//集合发生结构改变的调用抛出ConcurrentModificationException异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
ArrayList修改相关解析
/**
* 将指定索引位置的元素修改为指定元素
*
* 1、检查索引的有效范围，范围异常抛出IndexOutOfBounndsException异常
* 索引有效返回 0~size-1
* 2、获取索引index位置的元素信息
* 3、将集合索引index的元素信息改为指定元素
* 4、返回原索引index位置的元素信息
*
* @param index 指定索引位置
* @param element 指定元素
* @return 被修改元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
ArrayList其他方法解析
/**
* 主动对集合扩容，扩容最小容量为minCapacity，主要还是通过
* ensureExplicitCapacity实现，详细可以查看ensureExplicitCapacity源码分析
*
* @param minCapacity 最小容量
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
/**
* 通过Cusumer的实现类的accept方法对集合中元素做定制化操作
*
* 调用此方法不允许出现集合结构性改变，也就是modCount不允许改变，否则抛出异常
*/
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* 将集合通过Arrays.copyOf()方法返回一个Object[]的新数组
*
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* 将集合中的数据返回一个指定类型的数据集合
*
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
/**
* 将此集合的容量调整为实际集合大小的容量
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
/**
* 判断集合中是否包含指定元素o
* 实际上是通过indexOf方法获取元素o的索引是否大于0
*
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* 获取指定元素o在集合中的第一个索引位置
*
* 如果指定元素o为空，则获取第一个为空的元素位置
* 否则获取第一个元素出现元素o的索引位置
* 如果元素不存在，返回-1
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 获取指定元素o在集合中的最后一个索引位置
*
* 如果指定元素o为空，则获取最后一个为空的元素位置
* 否则获取最后一个出现元素o的索引位置
* 如果元素不存在，返回-1
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
*
* ArrayList提供的clone()方法是浅复制，元素本身不会复制
*
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
感谢大家的支持！！！
