Android开发数据结构算法ArrayList源码详解
Coolbreeze 人气:0简介
ArrayList是List接口的一个实现类，它是一个集合容器，我们通常会通过指定泛型来存储同一类数据，ArrayList默认容器大小为10，自身可以自动扩容，当容量不足时，扩大为原来的1.5倍，和上篇文章的Vector的最大区别应该就是线程安全了，ArrayList不能保证线程安全，但我们也可以通过其他方式来实现线程安全。
ArrayList源码讲解
开头部分代码
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
@java.io.Serial
//序列化uid
private static final long serialVersionUID = 8683452581122892189L;
//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//一个空对象
private static final Object[] EMPTY_ELEMENTDATA = {};
//一个空对象，如果使用默认构造函数创建，则默认对象内容默认是该值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//当前数据对象存放地方，当前对象不参与序列化
transient Object[] elementData; // non-private to simplify nested class access
//当前数组长度
private int size; //其他代码}
这部分可做出有关ArrayList的相关结构，如下图所示
初始化
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() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
elementData = EMPTY_ELEMENTDATA;
}
} //此处为copyOf运行代码
public static <T> T[] copyOf(T[] original,
int newLength) {
return (T[]) copyOf(original, newLength, original.getClass()); }
public static <T,U> T[] copyOf(U[] original,
int newLength,
Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
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;
}
以上代码为ArrayList的初始化，分为三种方式：
1.为给定容量的初始化，传入参数为数组的初始化长度，当该参数大于等于0时，进行初始化，当该参数小于0时，抛出异常
2.过于简单
3.首先通过c.toArray()得到了集合c对应的数据数组，如果c也是ArrayList，直接将c.toArray()赋给elementData，而关于toArray的关键代码如上代码中关于copyOf的部分所示，从该段代码中可知此处的Arrays.copyOf调用的是三参数版本的函数。这个三参数的copyOf函数比较复杂，作用就是返回一个指定的newType类型的数组，这个数组的长度是newLength，值从original拷贝而来。拷贝的功能由System.arraycopy( )完成：如果newLength大于原数组的长度，多出来的元素初始化为null；如果小于原数组长度，将会进行截断操作。在这里，两参版本调用三参版本的三个参数为original, newLength, original.getClass()，故得到的数组元素类型和原数组类型一致，长度为newLength，数据由原数组复制而来。
总之，ArrayList的无参版toArray( )返回了一个和elemantData一模一样的拷贝数组。所以判断c也是ArrayList对象时，直接令elemantData 为c.toArray( )了。否则，会执行elementData = Arrays.copyOf(a, size, Object[].class)。经过上面的分析，三参的copyOf( )是返回一个数据内容和a一模一样的数组，但是数组类型转为Object[ ]类型。之所以有这条语句，猜想可能是某些集合的toArray( )方法，返回的数组不是Object[ ]类型，比方说用一个类继承ArrayList，并且重写toArray( )方法，让它返回一些别的类型。
扩容
public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
//核心部分
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
private Object[] grow() {
return grow(size + 1);
}
//newLength部分
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
return prefLength;
} else {
// put code cold in a separate method
return hugeLength(oldLength, minGrowth);
}
}
private static int hugeLength(int oldLength, int minGrowth) {
int minLength = oldLength + minGrowth;
if (minLength < 0) { // overflow
throw new OutOfMemoryError(
"Required array length " + oldLength + " + " + minGrowth + " is too large");
} else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
return SOFT_MAX_ARRAY_LENGTH;
} else {
return minLength;
}
} public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
关于扩容部分，private Object[] grow(int minCapacity)为核心部分，故我们先看这部分，if(oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA)部分说明当该数组不是还未初始化的数组时，用newLength以及位运算来进行相应的扩容，而newLength相应的代码已经贴在了上面，让我们来进行具体分析：此处的minGrowth在grow部分为“minCapacity - oldCapacity”，即满足我们需要的容量，此处的prefGrowth在grow部分为“oldCapacity >> 1”，即原来容量的一半，当没有溢出时，扩容时所扩的容量就是这两者中最大的那个，而当溢出时，调用hugeLength()来满足minGrowth，如果还时溢出则最多只能给到 Integer.MAX_VALUE - 8 这个量。
那么当计算好长度之后，return elementData = Arrays.copyOf(elementData, newCapacity)，即得到一个长度改变，元素类型和原数组相同的新数组。而当该数组不满足oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个条件时，进行数组的初始化。
增加元素
一个元素
//在尾部添加一个元素
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length) //此处s为size的意思
elementData = grow();
elementData[s] = e;
size = s + 1;
}
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
} //在指定位置添加元素
public void add(int index, E element) {
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));
}
此处分为两个部分，一是向尾部添加一个元素的add()，如上面所示，当size与elementData.length相等时，说明数组中无多余空间进行添加，故进行扩容操作。将你要添加的值放入elementData[s]即数组的尾部，然后将size加一，这里的modCount是用来计算ArrayList中的结构性变化次数。
二是在指定位置添加元素的add()，如上面所示，首先对你想要添加的元素的位置进行判定
一堆元素
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;
//elementData剩余容量不足则进行扩容
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
//上文有提到的关于arraycopy的代码，此处为从数组尾部添加元素
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
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;
if (numMoved > 0)
//要在index位置，新增numNew个元素，所以从index位置开始，往后挪numNew位，一共有numMoved个元素需要挪动
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
//空出来的位置即为要添加的元素的位置
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
关于添加一堆元素时的代码与之前的代码较为相似，故此处直接在代码中注释标出，应该很好理解。
删除元素
一个元素
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
public staticint checkIndex(int index, int length) { return Preconditions.checkIndex(index, length, null);}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}//删除指定元素方法
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，进行删除 fastRemove(es, i); return true;}
此处的删除是按照下标删，首先检查index是否合法，接着取到oldValue值也就是要删的元素值，然后调用fastRemove( )函数。在fastRemove里，首先自增modCount，再判断要删的元素是不是elemantData的第size个元素（也就是实际上的最后一个元素），如果是，不需要挪动元素操作，直接赋值为null即可，否则，还需要将删除位置之后的元素都往前挪一位。
当然也有个删除指定元素的方法，具体如上面**public boolean remove(Object o)**所示。
一堆元素
//删除集合c中的所有元素public boolean removeAll(Collection<?> c) {
return batchRemove(c, false, 0, size);
}//保留集合c中的所有元素
public boolean retainAll(Collection<?> c) {
return batchRemove(c, true, 0, size);
}//核心代码
boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end) { //判断集合c是否为空
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// Optimize for initial run of survivors
for (r = from;; r++) {
if (r == end)
return false;
if (c.contains(es[r]) != complement)
break;
} //w用于写入保留的元素
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e; //当这个元素可以保留时，将其赋给es[]
} catch (Throwable ex) {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally { //相关善后工作
modCount += end - w;
shiftTailOverGap(es, w, end);
}
return true;
}
private void shiftTailOverGap(Object[] es, int lo, int hi) { //善后工作相关代码 System.arraycopy(es, hi, es, lo, size - hi);
// 从索引hi开始，有size-hi个元素需要往左挪，这些元素依次挪到lo以及lo之后的位置
// 它们都向左挪了hi-lo个单位
// 挪动之后，原先的索引size-1的元素，对应的是size-1-(hi-lo)，这个索引之后的元素都赋值为null for (int to = size, i = (size -= hi - lo); i < to; i++) es[i] = null;}
此处的关于多个元素的操作分为删除多个元素和保留多个元素，而这两个操作均需要调用 “batchRemove“ ，故进行关于其的具体分析。
“batchRemove“ 首先进行了变量”r“的声明，接着是一段for循环，而不管是“removeAll”还是“retainAll”都是from = 0 ，end = size，即从头到尾用r作为索引遍历数组，当c.contains(es[r]) != complement时break出去。对于“removeAll”，其complement为false，故当c.contains(es[r])为true的时候退出循环，即c中包含es[r]，即找到了要删除的元素，此时的r为第一个要删除的元素的索引。
以此类推，对于“retainAll”，r为要保留的第一个元素的索引。关于后面w的部分，w是第一个要删的元素索引，找到要保留的元素，则把索引w的元素赋值为此元素，再自增w。这样子r一遍遍历完成后，要保留的元素也都向前移动好了。最后再进行善后工作，具体代码如上所示，详细过程已做注释。
修改元素
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
public static
int checkIndex(int index, int length) {
return Preconditions.checkIndex(index, length, null);
}
public static <X extends RuntimeException>
int checkIndex(int index, int length,
BiFunction<String, List<Number>, X> oobef) {
if (index < 0 || index >= length)
throw outOfBoundsCheckIndex(oobef, index, length);
return index;
}
修改元素部分也与之前大同小异，首先对index是否合法进行判断，成功后再对这个元素的值进行修改，并返回旧值
查询元素
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
关于此处，首先是indexOf函数，就是根据元素找索引，调用”indexOfRange“，从左往右找，找到第一个索引就返回；在ArrayList中还有个lastIndexOf，与前面提到的查找正好相反，为从右往左找。
还有一些其他较为简单的函数，这里就不一一列出了，下一篇试着分析下迭代器。格式没怎么调。
加载全部内容