Java之ArrayList实现原理(jdk11)
2017-03-02 本文已影响0人
dotaer_shashen
一. 构造函数
二. 添加元素
2.1 添加一个元素到末尾
2.2 将指定的元素插入此列表中的指定位置
2.3 将一个指定collection中的所有元素添加到此列表的尾部
2.4 从指定的位置开始，将指定collection中的所有元素插入到此列表中
三. 用指定的元素替代此列表中指定位置上的元素
四. 删除元素
4.1 移除此列表中指定位置上的元素
4.2 移除此列表中首次出现的指定元素 (如果存在)
4.3 从指定collection1中移除与指定collection2中相同的所有元素;
五. 调整数组容量
六. 将底层数组的容量调整为当前列表保存的实际元素的大小
七. 总结
一. 构造函数
ArrayList是List接口的可变数组的实现，实现了所有可选列表操作，并允许包括 null 在内的所有元素；底层使用数组保存所有元素，其操作基本上是对数组的操作，无序不唯一；
transient Object[] elementData;
// ArrayList的大小（所包含元素的个数）
private int size;
// 用于空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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);
}
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
// 给elementData赋值,ArrayList实际存放元素的数组
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
从 ArrayList 的构造函数中可以看到当没有给初始大小时, 默认给初始数组赋值的是一个空数组;
二. 添加元素
2.1 添加一个元素到末尾
private static final int DEFAULT_CAPACITY = 10;
public boolean add(E e) {
// 父类中的变量 用于检测判断 ConcurrentModificationException
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
// 判断是否应该进行扩容
if (s == elementData.length)
// 对数组进行扩容的函数
// 数组里面没有元素时,第一次调grow()方法进行扩容,默认大小为10;
// 后面数组满每次进行扩容时,每次扩容原数组大小的1/2;
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
// 将旧的数组元素复制到新的数组中,新的数组长度是10或者是扩容后的数组长度;
return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}
private int newCapacity(int minCapacity) {
int oldCapacity = elementData.length;
// 每次扩容增加百分之五十的容量
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// 只有第一次添加元素扩容时这里才会走进来
// 取数组容量和默认容量10之间的最大值
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0)
throw new OutOfMemoryError();
return minCapacity;
}
// MAX_ARRAY_SIZE为Integer的最大取值
// 将扩容后的数组大小返回(非实际所存元素的个数)
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity : hugeCapacity(minCapacity);
}
在 ArrayList 添加第一个元素时, 会调 grow() 函数对初始数组进行第一次扩容并且大小为10, 也就是说ArrayList 此时的容量大小是10 但是它当前所存储的元素个数不一定是10;
后面数组满, 每次进行扩容时, 每次会扩大原容量大小的1/2;
2.2 将指定的元素插入此列表中的指定位置
public void add(int index, E element) {
// 对 index 索引进行越界检测
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
// 将旧数组复制到一个加大的新数组 并且从指定位置开始元素发生移位
System.arraycopy(elementData, index,elementData, index + 1,s - index);
elementData[index] = element;
size = s + 1;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
2.3 将一个指定collection中的所有元素添加到此列表的尾部
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// 判断是否需要扩容
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
// 对数组 elementData 进行复制元素进去的操作
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
2.4 从指定的位置开始，将指定collection中的所有元素插入到此列表中
public boolean addAll(int index, Collection<? extends E> c) {
// 检测索引是否越界
rangeCheckForAdd(index);
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// 判断是否需要扩容
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
int numMoved = s - index;
// 对数组 elementData 进行复制元素进去的操作
if (numMoved > 0)
System.arraycopy(elementData, index,elementData, index + numNew,numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
三. 用指定的元素替代此列表中指定位置上的元素
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
// 重新赋值
elementData[index] = element;
// 返回旧元素
return oldValue;
}
四. 删除元素
4.1 移除此列表中指定位置上的元素
public E remove(int index) {
// 对索引进行检测
Objects.checkIndex(index, size);
final Object[] es = elementData;
// 用变量保存index位置的元素 用于删除成功后返回
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
// 删除一个元素后的数组需要进行移位操作, ArrayList里都是复制到一个新的数组中;
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
4.2 移除此列表中首次出现的指定元素 (如果存在)
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
4.3 从指定collection1中移除与指定collection2中相同的所有元素;
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false, 0, size);
}
boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// 第一个循环检测两个集合中是否有相同的元素
for (r = from;; r++) {
if (r == end)
return false;// 两个集合是没有相同的元素
if (c.contains(es[r]) != complement)
break;
}
// 有相同的元素会继续执行
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally {
modCount += end - w;
shiftTailOverGap(es, w, end);
}
return true;
}
示例测试
ArrayList<String> list = new ArrayList<>();
list.add("rzc");
list.add("rzc01");
list.add("rzc02");
list.add("rzc03");
ArrayList<String> list2 = new ArrayList<>();
list2.add("rzc");
list2.add("rzc01");
list2.add("rzc04");
list2.removeAll(list);
list.addAll(list2);
System.out.println(list.toString());
System.out.println(list2.toString());
打印结果
[rzc, rzc01, rzc02, rzc03, rzc04]
[rzc04]
五. 调整数组容量
public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
所需最小容量与数组大小作比较，大于需要扩容，从前面的代码中可以看出扩容实际上是new了一个新的数组，然后将旧的数组中的元素复制到新的数组中；
六. 将底层数组的容量调整为当前列表保存的实际元素的大小
public void trimToSize() {
// 父类中的变量 用于检测判断 ConcurrentModificationException
modCount++;
// 将实际存储的元素个数与真实容量做比较
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
// 复制到一个容量更小的数组中
: Arrays.copyOf(elementData, size);
}
}
七. 总结
- 每个 ArrayList 实例都有一个容量，该容量是指用来存储列表元素的数组的大小，它总是至少等于列表的大小并且最始默认值为10；
- 随着向 ArrayList 中不断添加元素，其容量也自动增长；自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造 ArrayList 时指定其容量；
- 在添加大量元素前，应用程序也可以使用ensureCapacity() 操作来增加 ArrayList 实例的容量，这可以减少递增式再分配的数量（就是先将其一次性扩容，避免重复性扩容操作）；
- 可以通过trimToSize()函数将数组大小调整到所存储实际元素的个数大小，以减少对内存的消耗；
