01 ArrayList

2024-03-18 约 600 字预计阅读 2 分钟

jdk 基于 8 版本

在平时的开发中，我们会经常用到 ArrayList, 非常有必要了解源码。

使用方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public class ArrayListTest {

    @Test
    void test() {
        List<String> ids = new ArrayList<>();
        assertThat(ids.add("1")).isEqualTo(true);
        assertThat(ids.add("2")).isEqualTo(true);
        assertThat(ids.add("3")).isEqualTo(true);
        assertThat(ids.remove("2")).isEqualTo(true);
        assertThat(ids.set(0, "4")).isEqualTo("1");
        assertThat(ids.get(0)).isEqualTo("4");
    }
}

add

添加元素到 ArrayList 中，如果空间不够，则触发 newCapacity = oldCapacity + (oldCapacity >> 1)。

源码位置: java.util.ArrayList#add

1
2
3
4
5
6
7
public boolean add(E e) {
    // 确保有足够的空间
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 存入元素
    elementData[size++] = e;
    return true;
}

源码位置: java.util.ArrayList#ensureCapacityInternal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
private void ensureCapacityInternal(int minCapacity) {
    // 先计算容量，扩展容量
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算容量，最小为10 (DEFAULT_CAPACITY = 10)
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

源码位置: java.util.ArrayList#ensureExplicitCapacity

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 确保容量足够
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        // 空间不够，需要扩容
        grow(minCapacity);
}

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);
    // 复制元素到新数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

remove

删除元素，有两个重载，一个是根据元素来删除，一个是根据下标来删除，下面以根据下标来删除说明

源码位置: java.util.ArrayList#remove(int)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public E remove(int index) {
    // 下标检查
    rangeCheck(index);

    modCount++;
    // 获取旧值
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 把 index+1 之后的元素移动到 index 位置
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // gc
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

set

设置元素

源码位置: java.util.ArrayList#set

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public E set(int index, E element) {
    // 下标检查
    rangeCheck(index);

    // 获取旧值
    E oldValue = elementData(index);
    // 设置新值
    elementData[index] = element;
    return oldValue;
}

get

获取元素

源码位置: java.util.ArrayList#get

1
2
3
4
5
6
public E get(int index) {
    // 下标检查
    rangeCheck(index);
    // 获取旧值
    return elementData(index);
}

收录于合集・源码分析 Jdk 系列 12

02 LinkedList