朔风

Appearance

章节导航

ArrayList 源码和底层数据结构 ​

ArrayList 集成抽象类 AbstractList，抽象类 AbstractList 实现了 List 接口，List 接口继承了 Collection 接口

构造方法 ​

ArrayList 提供了三个构造方法，ArrayList 跟数组最大的却别是 数组长度是固定的，ArrayList 是可以动态扩容的。

1、无参构造 ​

无参构造会创建一个空的数组，

shell
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

2、有参构造 ​

会初始化集合的容量，如果容量大于 0，会创建爱你一个相对对应的数组；如果容量等于 0，则会创建一个空数组。

shell
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);
        }
    }

3、有参构造（集合） ​

  • 1、会将集合里面的元素转化成数组
  • 2、如果集合是空的，则会创建一个空数组
  • 3、如果是同类型的集合，会改变元素内存指向；如果类型不一样，会将以前数组的元素，拷贝到 elementData 中
shell
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 {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

核心方法 ​

1、add ​

add方法有两种形式: 添加元素至末尾或指定索引位置

添加元素至末尾 ​

shell
boolean add(E e)

指定索引位置 ​

shell
void add(int index, E element)

2、get ​

get 方法用于获取指定索引位置的元素，并进行索引越界检查； 使用 get 方法时，会现有一个索引位置判断，如果索引大于集合长度，则会抛出 IndexOutOfBoundsException 异常（索引越界异常）

shell
public E get(int index) {
        Objects.checkIndex(index, size);  // 检查索引是否越界
        return elementData(index);
    }

3、set ​

set 方法用于设置指定索引位置的元素值，会覆盖已有索引元素的值

shell
public E set(int index, E element) {
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

4、remove ​

remove 方法通过拷贝方式移除指定索引的元素。
remove 时也会做索引越界判断，删除的时候，会将 index + 1 的元素拷贝到 index，最后一位的元素会置为 null。

shell
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;
    }
    
    
    // 删除元素的核心方法
  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;
    }

扩容原理 ​

  • 扩容方法是 ensureCapacityInternal（在 JDK 21 中是 ensureCapacity），最终调用 grow 方法

在之前源码中，add 添加元素时，会调用 ensureCapacityInternal 方法，现在（JDK 21）中，add 直接调用了 grow 方法

  • 扩容时新容量是原容量的 0.5 倍，使用 Arrays.copyOf 完成扩容操作

迭代原理 ​

ArrayList 实现了 Iterator 接口,提供 iterator() 方法用于遍历内部类 Itr 实现 iterator 接口，包含 next 和 remove 方法，使用 modCount 和 expectedModCount 检测并发修改异常