肥年鱼的博客

菜单

肥年鱼
发布于 2026-05-30 / 12 阅读
0
0

Java 集合学习日记：Day1 - ArrayList 底层原理

#集合

一、类继承体系

public class ArrayList<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, Serializable{}

各接口作用

1. AbstractList：List 抽象骨架，提供迭代、批量操作公共逻辑

2. List：实现列表规范，增删改查、下标访问

3. RandomAccess：随机访问标记接口

实现该接口代表：按下标 get 遍历比迭代器更快

4. Cloneable：支持浅拷贝

5. Serializable：支持序列化

二、核心成员变量

// 底层真正存储元素的数组
transient Object[] elementData;
// 当前实际元素个数
private int size;
// 默认初始容量 10
private static final int DEFAULT_CAPACITY = 10;
// 无参构造空数组常量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 有参构造容量为0的空数组常量
private static final Object[] EMPTY_ELEMENTDATA = {};
// 最大数组容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 快速失败 版本号
protected transient int modCount = 0;

三、底层数据结构

底层：动态扩容的 一维 Object 数组

特点：

  • 内存连续

  • 支持下标随机访问

  • 固定数组长度，满了自动扩容

四、三大构造方法源码拆解

1. 无参构造

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

  • 初始化赋值空数组，不是直接创建长度 10 的数组

  • 懒加载：第一次 add 元素时才扩容到默认容量 10

2.指定初始容量构造

public ArrayList(int initialCapacity) {
this.elementData = new Object[initialCapacity];
}

3.传入带 Collection 参数的构造函数：

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 {
            elementData = EMPTY_ELEMENTDATA;
        }
    }

五、常用 API 源码底层

1.add (E e) 尾部添加

public boolean add(E e) {
    // 检查是否需要扩容
    ensureCapacityInternal(size + 1);
    // 数组末尾赋值
    elementData[size++] = e;
    return true;
}

2.get (int index) 按下标获取

public E get(int index) {
    // 下标越界检查
    rangeCheck(index);
    // 直接数组下标取值，O(1)
    return elementData(index);
}

优势：随机访问极快，直接定位内存地址

3.remove (int index) 按下标删除

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    // 需要移动的元素个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 后续元素整体向前移位
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 末尾置空，帮助GC
    elementData[--size] = null;
    return oldValue;
}

缺点：中间删除要数组移位，效率低

4. set (int index, E element) 修改某个下标的元素并返回旧值

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

5. indexOf(Object o)，查找某个元素第一次出现的位置，找到返回下标，没找到返回 -1。

public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }
int indexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = start; i < end; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = start; i < end; i++) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

6. indexOf(Object o)，查找某个元素第一次出现的位置，找到返回下标，没找到返回 -1。

六、核心底层：扩容机制

1. 核心扩容方法 grow ()

private void grow(int minCapacity) {
    // 原数组容量
    int oldCapacity = elementData.length;
    // 新容量 = 原容量 + 原容量/2  即 扩容1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 如果1.5倍还不够，直接使用最小需要容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // 超过最大限制，使用最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    // 数组复制，迁移元素到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

2. 扩容规则

  1. 默认首次 add：空数组 → 扩容到 10

  2. 后续每次扩容：原容量的 1.5 倍

  3. 若 1.5 倍仍放不下当前所需元素，直接用最小所需容量

  4. 最大容量：Integer.MAX_VALUE - 8

  5. 底层通过 Arrays.copyOf 复制数组，开辟新内存、拷贝旧元素

3. 什么时候触发扩容？

每次 add 前调用 ensureCapacityInternal()

判断：当前元素个数 == 数组长度 → 触发扩容

Java 集合学习日记：Day3 ...

评论