ArrayList底层结构和源码分析

发表于

注意事项

  1. ArrayList基本了解：
  • ArrayList可以加入null，并且多个；
  • ArrayList是由数组来实现的；
  • ArrayList基本等同于Vector，除了ArrayList是线程不安全（执行效率高），在多线程情况下，不建议使用ArrrayList;
  1. Idea Debug设置
  2. Java -version 1.8.0_221

底层操作机制

  • ArrayList中维护了一个Object类型的elementData数组。
1
java复制代码transient Object[] elementData; // transient 标识瞬间，短暂的，表示该属性不会被序列化
  • 当创建ArrayList对象时，如果使用的是无参构造器，则初始的elementData容量是0。第一次添加，则扩容elementData为10，如果需要再次扩容，则扩容elementData为原容量的1.5倍。
  • 如果使用指定大小的构造器，则初始elementData容量为指定大小。如果需要扩容，则扩容elementData为1.5倍。

解读源码

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

源程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
java复制代码@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】

image-20211112211822187

2.执行list.add(E e)

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

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

image-20211112212534426

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

image-20211112213515703

4.确定是否需要扩容

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

image-20211112214100490

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

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

image-20211112214427260

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

image-20211112222404029

grow()扩容函数详解

jdk 1.8.0_221源码片段

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

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%