JDK源码阅读—1.ArrayList
2019-11-08 本文已影响0人
繁书_
JDK源码阅读—1.ArrayList
1.全局变量
// 存放数据的Object类型数组
transient Object[] elementData;
// 数组的默认容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组 在使用其他构造方法使用此数组进行初始化
private static final Object[] EMPTY_ELEMENTDATA = {};
// 空数组在使用默认构造方法时会初始elementData为此数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 所允许的数组最大容量，最大容量为Integer最大值减8的原因：
// 1.避免内存溢出，减少出错概率
// 2.因为部分虚拟机会在存储对象头信息，减少的8字节实际就是对象头信息所需要的内存
// 对象头包括两部分信息：Mark Word（标记字段）和 Klass Pointer（类型指针）。 该存储其实只会在部
// 分虚拟机中才被使用。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
2.构造方法
1.默认构造方法
public ArrayList() {
// 集合在初始化时会直接将数组初始话为一个空数组，使用懒加载机制，在集合真正使用时才会计算容量
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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) {
// 如果给定的初始容量大于0,会直接按照给定的容量初始化一个Object类型数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果给定容量等于0，则初始化一个空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 如果小于0，抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
3.指定集合
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// 在子子类重写父类方法的时候，在不修改返回值的前提下，子类返回了什么类型就是什么类型，
// 不会向上转换为父类的返回值类型，所以这里得到的类型可能不为Object类型，
// 比如一个Integer类型的ArrayList，在调用toArray方法时，返回值就是Integer类
// 型，而不是Object类型
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
3.常用方法
1.add(E e) 添加元素
public boolean add(E e) {
// 添加之前进行扩容操作，将当前数组元素个数+1，作为当前所需的最小容量
// 扩容方法在下面
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将元素添加到数组尾部
elementData[size++] = e;
return true;
}
// 1.确认最小容量 ensureCapacityInternal(minCapacity)
private void ensureCapacityInternal(int minCapacity) {
// 判断当前数组是否为默认构造方法构造出来空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 在默认容量10和minCapacity中找出一个最大值当作最小容量
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
// 2.真正扩容操作 ensureExplicitCapacity(minCapacity)
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 判断是否需要扩容，如果当前所需要的容量，已经大于数组的长度，则进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 3.扩容方法 grow(int minCapacity)
private void grow(int minCapacity) {
// overflow-conscious code
// 当前数组的长度
int oldCapacity = elementData.length;
// 将原始容量右移一位，也就是将原始容量除以2，然后再加上原始容量。将得出来的结果当作 // 新容量
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 判断新容量是否小于minCapacity，如果小于，则将minCapacity作为新容量
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);
}
// 4.大容量扩容方法 hugeCapacity(minCapacity)
private static int hugeCapacity(int minCapacity) {
// 判断所需容量是否小于0，如果小于0说明发生了内存溢出
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 判断所需容量是否大于所允许的最大值，如果大于则将Integer最大值作为数组长度
// 如果小于或等于则将所允许的最大值作为数组最大长度
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
2.add(int index, E element) 在执行位置插入元素
public void add(int index, E element) {
// 检测要插入的下表是否超过数组长度
rangeCheckForAdd(index);
// 扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将原数组在index位置以后的元素全部复制到index+1的位置，这样index位置的元素
// 就会空出来
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将新元素赋值到index的位置
elementData[index] = element;
size++;
}
3.addAll(Collection<? extends E> c) 将集合内的元素全部添加到当前集合中
public boolean addAll(Collection<? extends E> c) {
// 将集合转为数组
Object[] a = c.toArray();
int numNew = a.length;
// 重新确认数组新容量
ensureCapacityInternal(size + numNew); // Increments modCount
// 将传入的数组复制到原数组后面
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
4.addAll(int index, Collection<? extends E> c) 在指定位置插入新集合
public boolean addAll(int index, Collection<? extends E> c) {
// 检测下标是否越界
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
// 扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// 计算原数组中要往后移动的下标数量，例：
// 假设原数组为Object[] a = {1,2,3,4,5},要添加的数组为Object[] b = {7,8};
// 现在要在下标2的位置将b数组插入到a数组中，首先要将a中的3,4,5元素复制到a的后面
// 复制后的数组为a = {1,2,3,4,3,4,5},复制的起始位置就是size - index,5-2 = 3,
// 3就是元素复制过来的起始位置,然后在将b数组复制到a的2,3元素上面,最终结果就是
// {1,2,7,8,3,4,5}
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
5.indexOf(Object o) 查找指定元素在集合中第一次出现的下标
public int indexOf(Object o) {
// 判断给定的元素是否为空,如果为空直接判断是否有元素为空
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
// 遍历集合,如果此下标位置的元素和给定元素相同则返回下标值，否则返回-1
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
6.lastIndexOf(Object o) 从集合尾部开始查
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;
}
7.get(int index) 返回指定下标的元素
public E get(int index) {
// 检测下标有无越界
rangeCheck(index);
// 返回集合中的此下标的元素
return elementData(index);
}
8.remove(int index) 移除指定下标的元素
public E remove(int index) {
// 检测下表有无越界
rangeCheck(index);
modCount++;
// 取出此下标位置的元素用来返回
E oldValue = elementData(index);
// 计算需要复制的元素数量，例：
// 假设数组为Object[] a = {1,2,3,4,5}, index为2,也就是说要移除元素3,
// 那么元素3右边的元素全部都要往左移动一个下标,那么要复制的元素个数就是
// 5-2-1 = 2,将元素4,5复制从index的位置开始复制，复制后的数组为a = {1,2,4,5,5}
// 最后将末尾元素置空
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;
}
9.remove(Object o) 移除数组第一个和给定元素相同的元素
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才是真正的删除方法
// 方法在下面
fastRemove(index);
return true;
}
}
return false;
}
// fastRemove(int index)
/*
* Private remove method that skips bounds checking and does not
* return the value removed
*/
private void fastRemove(int index) {
// 下面方法实际和remove(inde 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
}
10.clear() 清空元素方法
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
11.removeAll(Collection<?> c) 移除包含在给定集合中的所有元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
// 1.直接看batchRemove 批量删除
/**
* complement 为false时代表删除与给定集合中相同的元素,
* 为true时，代表保留与给定集合中相同的元素
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
// 将集合中的数组赋值转换为局部变量操作，提高效率
final Object[] elementData = this.elementData;
// r为循环次数,w为elementData最终的元素数量
int r = 0, w = 0;
// 集合有没有进行删除操作
boolean modified = false;
try {
for (; r < size; r++)
// 循环判断找出原数组内和给定数组内相同的元素，
if (c.contains(elementData[r]) == complement)
// 将不相等的元素放入到elementData中
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
// 只有当try中出现异常才会出现r!=size的情况，当出现异常时，将从r开始往后的元素
// 全部复制到w起始的位置，这样就会将需要删除的元素给覆盖调，最后将集合中需要保留的
// 元素个数计算出来
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// 判断数组内现有的元素数量是否和原数组的集合数量相同，如果相同，说明没有必要进行删除操作
if (w != size) {
// clear to let GC do its work
// 循环以元素个数为循环起始值，将后面的元素全部清空，
// 以为w代表数组内元素个数，大于w的下标也就是需要删除的元素
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
12.removeRange(int fromIndex, int toIndex) 移除给定下标范围内的元素
/**
* 这是一个用protected修饰的方法，只能通过子类去调用
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
// 计算要移动元素的个数
// 假如size = 5，fromIndex = 1 toIndex = 3,那么需要toIndex后面的元素都要移动
// 因为不包含toIndex本身的元素，所以需要移动的元素就是2个元素
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
