13518219792
今天就跟大家聊聊有关如何用源码分析ArrayList，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。
目前创新互联建站已为上千多家的企业提供了网站建设、域名、网页空间、网站托管、服务器托管、企业网站设计、迪庆州网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。
/** ArrayList的初始化容量 **/
public static final int DEFAULT_CAPACITY = 10;
/** 数组能存储的最大元素容量 **/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** 空数组，当调用无参数构造函数的时候默认给个空数组 **/
public static final Object[] EMPTY_ELEMENTDATA = {};
/** 真正保存数据的数组 **/
transient Object[] elementData;
/** 实际ArrayList的元素个数 **/
private int size;ArrayList的初始化容量为10，真正的数据是存在elementData中，实际存储的元素个数用size表示。
/** 无参构造函数 **/
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
/** 初始化容量构造函数 **/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
this.elementData = new Object[initialCapacity];
}
/** 已有集合构造函数 **/
public ArrayList(Collection c) {
elementData = c.toArray();
size = elementData.length;
if (elementData.getClass() != Object[].class) {
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
}如果构造函数不传入List容量 则初始化elementData为空数组。
如果构造函数传入List容量 则初始化elementData为传入容量的Object数组
如果构造函数传入了集合 则将集合转换为数组赋值给elementData，同时设置size值为数组的长度。
元素插入主要有以下四个方法：
boolean add(E e)
void add(int index, E e)
boolean addAll(Collection c)
boolean addAll(int index, Collection c)
/** 添加元素 **/
@Override
public boolean add(E e) {
//确保数组容量
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}在添加元素时，先通过ensureCapacityInternal方法保证elementData数组拥有足够的容量。
然后直接插入尾部位置的元素并改变元素的实际总数量。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//如果元素数量将超过数组长度 则需动态扩容
if (minCapacity - elementData.length > 0) {
grow(minCapacity);
}
}
/** 数组扩容机制 **/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
if (newCapacity > MAX_ARRAY_SIZE) {
newCapacity = minCapacity > MAX_ARRAY_SIZE ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}先判断需要保证的元素数量是否大于elementData数组的长度，如果大于，则需要将elementData数组进行扩容。
在扩容时，先设置数组长度newCapacity为原数组长度的1.5倍，然后判断需要保证的元素数量是否大于newCapacity新数组的长度，若仍然不够，则直接设置newCapacity为需要保证的元素数量。
然后将新数组长度newCapacity与常量最大数组长度对比，最后通过Arrays.copyOf方法进行扩容。
/** 在指定位置添加元素 **/
@Override
public void add(int index, E e) {
rangeCheckForAdd(index);
//确保数组容量
ensureCapacityInternal(size + 1);
//将插入位置后的所有元素往后移
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = e;
size ++;
}先判断index是否越界，然后通过ensureCapacityInternal方法保证elementData数组拥有足够的容量。
然后将index之后的所有元素往后移动。
最后插入index位置的值，并改变元素的实际总数量。
/** 往当前集合中添加集合c **/
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
//将数组a中所有元素copy到elementData中
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}先将集合c转换为Object数组a，并取出a的长度。
然后通过ensureCapacityInternal方法保证elementData数组拥有足够的容量。
将数组a复制到elementData数组的后面并改变元素的实际总数量。
/** 在当前集合中的index位置添加集合c **/
public boolean addAll(int index, Collection c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
//将index后面所有元素往后移动
System.arraycopy(elementData, index, elementData, index + numNew, size - index);
//将数组a中元素插入到elementData的index位置
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}相比addAll(Collection c)方法仅多一步，将index后面所有元素往后移动
元素移除主要有以下五个方法
void clear()
E remove(int index)
boolean remove(Object o)
boolean removeAll(Collection c)
boolean retainAll(Collection c)
/** 清空当前集合中所有元素 **/
public void clear() {
modCount ++;
//将所有元素设置为null让GC回收掉
for (int i = 0; i < size; i++) {
elementData[i] = null;
}
size = 0;
}将所有元素设置为null并设置size为0。
/** 移除指定位置index元素 **/
@Override
public E remove(int index) {
rangeCheck(index);
//获取到旧的元素
E oldValue = (E) elementData[index];
//计算需要移动的元素
int needMoveNum = size - index - 1;
if (needMoveNum > 0) {
//将移除位置后的所有元素往前移
System.arraycopy(elementData, index + 1, elementData, index, needMoveNum);
}
//将数组最后一个元素置为null
elementData[--size] = null;
return oldValue;
}
/** 检测数组是否越界 **/
private void rangeCheck(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
}
}先检测元素是否越界，然后根据索引获取到原有元素oldValue。
数组移除时，需要将index后面的元素往前移动一位，所以先根据移除元素的位置计算出需要移动元素的个数needMoveNum，如果大于0就通过System.arraycopy方法移动。
然后将最后一个元素设置为null，返回原有元素oldValue。
/** 移除指定元素o **/
@Override
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)方法，不需要检测数组越界和返回旧元素 **/
private void fastRemove(int index) {
modCount++;
//计算需要移动的元素
int needMoveNum = size - index - 1;
if (needMoveNum > 0) {
//将移除位置后的所有元素往前移
System.arraycopy(elementData, index + 1, elementData, index, needMoveNum);
}
//将数组最后一个元素置为null
elementData[--size] = null;
}如果指定的元素o是null,则循环找到一个为null的元素并移除。
否则循环数组元素，通过equals方法找到元素并移除。
/** 从当前集合中移除集合c中所有的元素 **/
public boolean removeAll(Collection c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}/** 只保留当前集合与指定集合c中都存在的元素 **/
public boolean retainAll(Collection c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}private boolean batchRemove(Collection c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++) {
//判断是保留相同的还是保留不同的
if (c.contains(elementData[r]) == complement) {
elementData[w++] = elementData[r];
}
}
} finally {
//正常情况下 r和size是相等的 如果抛出异常 则将剩余未比较的复制到elementData中
if (r != size) {
System.arraycopy(elementData, r, elementData, w, size - r);
w += size - r;
}
//如果有移除的数据，w和size是不相等的 此时将W之后的数据置空 让GC回收掉
if (w != size) {
for (int i = w; i < size; i++) {
elementData[i] = null;
}
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}/** 查询元素 **/
@Override
public E get(int index) {
//检查索引是否越界
rangeCheck(index);
//返回数组指定位置的元素
return elementData(index);
}判断数组是否越界
返回指定位置的数组元素即可。
E elementData(int index) {
return (E) elementData[index];
}/** 更改元素 **/
@Override
public E set(int index, E e) {
rangeCheck(index);
//查询原有元素
E oldValue = (E) elementData[index];
//设置为最新元素
elementData[index] = e;
return oldValue;
}先判断数组是否越界
获取到旧的元素
将当前位置设置为新的元素
返回旧元素。
总结
ArrayList底层主要通过Object数组elementData实现
ArrayList初始化容量为10，扩容时每次增加至原来的1.5倍
查询更新操作时最简单，通过数组下标可快速定位元素位置进行操作
添加删除时由于需要移动后面的元素位置，所以会更加耗时；移动元素位置时主要通过System.arraycopy方法实现
看完上述内容，你们对如何用源码分析ArrayList有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注创新互联行业资讯频道，感谢大家的支持。
