ArrayList底层结构和源码分析

注意事项

ArrayList基本了解：

ArrayList可以加入null，并且多个；
ArrayList是由数组来实现的；
ArrayList基本等同于Vector，除了ArrayList是线程不安全（执行效率高），在多线程情况下，不建议使用ArrrayList;

Idea Debug设置
Java -version 1.8.0_221

底层操作机制

ArrayList中维护了一个Object类型的elementData数组。

transient Object[] elementData; // transient 标识瞬间，短暂的，表示该属性不会被序列化

当创建ArrayList对象时，如果使用的是无参构造器，则初始的elementData容量是0。第一次添加，则扩容elementData为10，如果需要再次扩容，则扩容elementData为原容量的1.5倍。
如果使用指定大小的构造器，则初始elementData容量为指定大小。如果需要扩容，则扩容elementData为1.5倍。

解读源码

分析使用无参构造器，创建和使用ArrayList。有参构造器阅读源码过程差不多，不一样的是初次扩容！

源程序

@SuppressWarnings(value = "all")
public class ArrayListSource {
  public static void main(String[] args) {
    // 使用无参构造器创建ArrayList
    ArrayList list = new ArrayList();
    // 使用有参构造器创建ArrayList
    // ArrayList list = new ArrayList(8);
    // 向集合添加10条数据
    for (int i = 1; i <= 10; i++) {
      list.add(i);
    }
    // 再向集合添加5条数据
    for (int i = 11; i <= 15; i++) {
      list.add(i);
    }
    list.add(100);
    list.add(200);
  }
}

分析过程

1.创建一个空的数组【elementData】

2.执行list.add(E e)

先确保内部容量,是否要扩容ensureCapacityInternal
然后再执行赋值

第一次添加的时候Debug F7 into进入源码！如果装填的数据是基本类型，塞入前会有一步装箱操作。

3.确定最小容量【minCapacity】,第一次扩容为10

4.确定是否需要扩容

modCount++ 记录集合被修改的次数
如果elementData的大小不够，就调用grow()去扩容

5.扩容，通过扩容机制来确定要扩容到多大

第一次newCapacity=10
第二次及其以后，按照数组原容量的1.5倍扩容
扩容使用的是Arrays.copyOf

6.完成扩容，数据放入数组

grow()扩容函数详解

jdk 1.8.0_221源码片段

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    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);
}

将 elementData.length 记录到 oldCapacity中，第一次值为0；
newCapacity = oldCapacity + (oldCapacity >> 1); 执行扩容，扩容大小为数组当前容量+数组当前大小右移1位(除以2)，即扩容1.5倍；
因为第一次扩容 oldCapacity与newCapacity 都为0, 所以if (newCapacity - minCapacity < 0) 条件成立，第一次扩容大小为 10；
Arrays.copyOf()方法可保留原先数据扩容；
如果容量超过2147483639，则调用hugeCapacity计算容量；