ArrayList集合源码分析
文章目录
- ArrayList集合源码分析
- 一、字段分析
- 二、构造方法分析
- 三、方法分析
- 四、总结
内容如有错误或者其他需要注意的知识点，欢迎指正或者探讨补充，共同进步。
一、字段分析
//默认初始化容量。这里和Vector一样，只是Vector,没有用一个变量，而是调用无参构造函数时，直接塞了个10。
private static final int DEFAULT_CAPACITY = 10;
//这里给出了两个空数组。有两个疑问，1.为什么给空数组2.为什么还给了两个
//1。在我们创建空的ArrayList集合时，为了避免创建多个空的数组，而换成统一用这里的口空数组代替，达到了节约内存和提高效率。
//2。为了区分我们在构造集合时，是用的有参构造函数，还是无参函数。不同的构造也会带来扩容机制的不同。
// - 无参构造函数，会使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA 数组，在第一次添加元素是，扩容后的容量是10。
// - 有参构造函数，如果传入的是0，则是用EMPTY_ELEMENTDATA ，扩容是1.5的扩容。0->1->2->3->4->6->9->13，如果数据很少
// 少到比10还小，能够降低内存消耗的。
//所以又有了疑问，那为什么不用一个就可以了呢，第一次扩容都用容量10。
// - 源码上面的注释是：Shared empty array instance used for default sized empty instances.
// We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.
// 这是用于默认大小的空实例的共享空数组实例。我们将其与EMPTY_ELEMENTDATA区分开来，以便在添加第一个元素时知道要扩充多少空间。
// 同时如果有那种添加很少元素的需求，元素数量小于10，这样做是可以减少内存消耗的，达到更适配相应需求的目的。
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//用来存储数据的数组
transient Object[] elementData;
//实际存储了数据的个数
private int size;
二、构造方法分析
- 从构造方法可以看出，我们在创建 ArrayList 时，并没有更新容量，就是用的默认容量10。
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果初始容量为0，则空数组代替，size = 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) {
//toArray()通常会将泛型擦除掉，比如应该是List<Integer> 会变成 Objects[];
//为何这样做呢？即便你不擦除掉，在代码编译时也会将泛型擦除掉，所以为了提高效率，加快编译速度。
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//这里为什么要加这样的判断呢？因为通常来说c.toArray();已经返回了Object[],但如果这个是个人实现的
//比如里面调用了c.toArray(Integer[]);则会返回Integer[],所以这里额外判断下
//为了确保elementData 为Object数组，如果使用系统提供的toArray()方法，会返回
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
三、方法分析
- 添加元素 方法，是非线程安全的方法。并且在添加元素的时候会校验是否需要扩容。
//向已有元素的末尾添加元素
public boolean add(E e) {
//判断是否需要扩容，所需容量最少为：已有元素数量 + 1
//但里面其实会判断，存储数据的数据是否为空，空则需最小容量为 DEFAULT_CAPACITY
//否则取Math.max（已有元素数量 + 1，DEFAULT_CAPACITY ），可向下看
ensureCapacityInternal(size + 1); // Increments modCount!!
//已有元素的末尾添加上新元素
elementData[size++] = e;
//添加成功
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//判断扩容之前，判断所需的最小容量，而calculateCapacity(elementData, minCapacity) 就是判断
//所需的容量，然后拿这个所需的最少容量去判断是否需要扩容。
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//正如上面所说的，如果数组为空，则所需取其中较大值，这不难理解
//这里也是第一次扩容采用什么决策作出了判断，如果是调用无参构造函数，第一次扩容是10。
//如果是有参，且参数0，则1.5倍扩容，具体原因，上面参数介绍时详细说了。
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//这时候我们拿到了我们所需要的最小容量，来判断是否需要扩容了
private void ensureExplicitCapacity(int minCapacity) {
//从Vector源码中我们之前到，这个是继承自Abastrack，用来记录版本号，防止迭代过程中集合被修改了，因为迭代器创建时，
//会保存创建那一时刻集合的版本号，迭代的过程的会比较自己保存的版本号和集合的版本号，从而判断跌倒过程中是否被修改。
//这里的作用是一样的。
modCount++;
// overflow-conscious code
//如果我们所需要的最小容量比elementData数组长度还大，那必须要扩容了，不然要下标越界了。
//如果是我们第一次添加元素，从构造函数可以，elementData是个空数组，这里也会扩容。 10 - 0 > 0
// ！！！从这里可以看出，在添加元素时，如果元素数量大于数组长度 才会触发扩容，就是数组已经被塞满了，不是说达到数组
//容量的百分之多少。
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//到这里就是确定要扩容了，并且我们拿到了所需的最小容量，用来判断该如何扩容
private void grow(int minCapacity) {
// overflow-conscious code
//记录当前数组长度
int oldCapacity = elementData.length;
//记录扩容后的数组长度，先按1.5倍来扩容
//oldCapacity >> 1 相当于 oldCapacity / 2
//那自己的一般 + 自己，不就是自己原来的1.5倍。
//至于最后是否会用这个值了，还需后面判断。
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容后的容量还是不够，则先用所需的最小容量最为新容量的值。
//你可能会疑问，我们添加元素都是一个一个添加的，按理说不可能扩容后容量还达不到需要的呀。
//就比如第一次添加元素，数组还是空数组{}，这里newCapacity = 0；这最少需要扩容到 10 对吧。
//还有一个可能是newCapacity 溢出了变成负数。则 新容量就是 minCapacity 了，即数组length + 1；
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量值要溢出了，注意是快要溢出，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//这时候我们继续确定新容量到底该多少
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//到这里新容量就去确定好了，去做扩容啦。
//这个方法会创建一个新的数组，将旧的数组按索引依次赋值到新数组上，未填充到的为数据类型的默认值，
//如 int 为0，Object 为 null.
//同时这是消耗新能的操作，涉及到新数组的创建和所有元素的赋值。
elementData = Arrays.copyOf(elementData, newCapacity);
}
//和 Vecotor.class 源码一样的，如果快要溢出了，则直接给所能给的容量的极限。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
//向指定索引位置添加元素
public void add(int index, E element) {
rangeCheckForAdd(index);
//判断是否需要扩容，上面分析过了
ensureCapacityInternal(size + 1); // Increments modCount!!
//上面已经进行过扩容动作了，这段代码看起来好像没必要。
//上面看见的Arrays.copyOf 其实底层最终调用就是这个方法，达到扩容的目的。
//难道这也是扩容？？此不是多此一举
//首先依次介绍下这个方法参数含义
//src：源数组，要将其内容复制到目标数组中。
//srcPos：源数组中开始复制的位置。
//dest：目标数组，源数组的内容将复制到该数组中。
//destPos：目标数组中开始复制的位置。
//length：要复制的元素个数。
//知道了含义就很好理解了，是把将要插入的位置，把该位置以及之后的所有元素往后移动一格。。。
//从这里也可看出，ArrayList 向指定下标插入元素效率低下，时间复杂度O(n),并且并不是覆盖掉
//该位置原先的元素，而是统统靠后移。
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//好了，这个位置被腾出位置了，可以插了。
elementData[index] = element;
size++;
}
-
获取元素方法：这个方法没啥好说的。
//根据索引获取元素 public E get(int index) { //检查索引是否越界 rangeCheck(index); //返回该位置值 return elementData(index); } //检查索引是否越界 private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //返回index索引位置的值 E elementData(int index) { return (E) elementData[index]; } -
扩容方法：介绍添加元素方法时说过了。
-
移除元素方法：可以根据下标位置移除元素，也可根据元素值移除元素。和Vector源码很相似
//根据索引位置删除元素(可以发现，这里和Vector 的源码一模一样)
public E remove(int index) {
//检查索引是否越界
rangeCheck(index);
//版本号+1
modCount++;
//得到该索引位置的值
E oldValue = elementData(index);
//需要移动的元素数量，就是你讲index位置的元素删了，那这个元素后院的所有的元素都要前移，这个值就是需要
//移动的元素数量即index后面元素的数量
int numMoved = size - index - 1;
//判断index后面是否有值
if (numMoved > 0)
//将要移动的元素前移，其实是吧那个要删除的元素覆盖了从而达到了删除元素的目的。
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//为什么要删除末尾元素呢，因为如果index 是最后以为元素，那么就不会触发元素前移，所以这里
//多一步，将末尾元素设置为null，就是为了处理这一特殊情况。所以如果index 后面有值，这一步是
//多余的，末尾已经是null了。
elementData[--size] = null; // clear to let GC do its work
//返回被删除的元素元素值
return oldValue;
}
//根据元素值删除元素
public boolean remove(Object o) {
//从这里也可看出,ArrayList是允许删除null元素值的，同时有相同值元素是，删除的是最靠前的那个。
//我们在分析Vector删除源码时，在获取o的下标位置时，会调用indexOf方法，和这里的判断是一样的。
//同时有个疑问？这个难道不可以统一写成elementData[index].equals(o)不就行了吗，就可以处理o是null或不是null的情况，
//且不会报错,且能达到相同效果，那这个判断不是冗余了嘛。你在说什么胡话？刚刚才说的ArrayList是允许添加null的，如果
//遍历获取到的元素如果是null那不就是报错了吗？所以这里这样写，才可以避免传入的o是null，同时遍历获取到的
//值也是null，从而判断报错的情况。
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;
}
//和上面根据索引删除元素逻辑一样的，从这里可以看出，代码冗余了(*￣︶￣)
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
}
- 迭代器设计：和Vector的一样，提供了两种的迭代器。Itr 和 ListItr。
- 不同的是，ArrayList 的迭代器在迭代过程中是不上锁的，但是Vector上锁，所以是线程不安全的。
- 相同是的都有版本号坚持机制，Itr迭代过程中不允许集合修改，而Listitr 允许修改。
//这里和Vector几乎相同，这里只标注不同的地方。
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
//和Vector 不同的是这里Vector会上锁，保证线程安全。
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
//这里和Vector不太一样。Vector 是没有这个判断的，感觉有个疑问，上面都判断了 i >= size 了，
//那么能到这里 i 肯定 < size 了， 而size是实际存储数据的个数，即便数组塞满了，那也是 size = length，
//怎么可能 i < size 却 i >= length，所以感觉这里判断多此一举了。
//要知道，ArrayLIst是非线程安全的，你在迭代的过程中，是可能有并发操作，修改了容量了，而这里做了这样的判断
//就是防止并发操作下，做下检查。
//而这种机制就是fail_fast(快速失败，敲黑板)。这里也是做了双重检查，checkForComodification也是检查是否被修改
//这里拿到 elementData 之后再次检查，尽量避免迭代过程中集合被修改。而Vector是加了锁的，锁的还是class对象
//所以检查一次即可。
//这里双重检查就可避免非线程安全问题了吗，但是不是，比如
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
//---------------------------------------------------
//比如你两次都检查过后，到了这里发生了修改，还是还会带来问题，不过概率降低了。
cursor = i + 1;
return (E) elementData[lastRet = i];
}
//这里逻辑 和 Vecotr的迭代器一样的，唯一区别少了把锁
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
//检查版本是否发生变化
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
//这里同样多了此检查结构是否变化
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
//和Vector比少了把锁，逻辑一样的
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//这个也是一样的，同样少了把锁。
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
四、总结
- ArraList 底层使用数组存储结构，删除或添加元素的效率时间复杂度O（n），效率低下。查找元素快 O（1）。
- 是线程不安全的数据结构，并发场景下可能带来非线程安全的问题。
- 扩容是按1.5来进行扩容，当然不是绝对的，比如第一次添加元素时，会判断调用的是那种构造函数，无参第一次扩容为10，有参且为0，扩容后为1。还有就是快要溢出的情况，当需要的容量 > MAX_ARRAY_SIZE,则新容量为Integer.MAA_VALUE。
