底层实现

底层实现为数组

扩容机制

以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。

jdk8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public boolean add(E e) {
    
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

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);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    
   if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

从jdk1.8 源码中可以看出当添加元素时，调用ensureCapacityInternal方法来判断一下容量，然后计算容量calculateCapacity 然后判断容量是否够大ensureExplicitCapacity 装不下时进行扩容grow 每次扩大到原来的1.5倍，当他超过最大MAX_ARRAY_SIZE的时候看实际容量是否大于MAX_ARRAY_SIZE，大于则为Integer.MAX_VALUE。

jdk17

从JDK11开始移除了 ensureCapacityInternal() 和 ensureExplicitCapacity() 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public boolean add(E e) {
    
    modCount++;
    add(e, elementData, size);
    return true;
}
private void add(E e, Object[] elementData, int s) {
    
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
private Object[] grow() {
    
    return grow(size + 1);
}
private Object[] grow(int minCapacity) {
    
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
    
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

只要实际大小不等于数组长度就去扩容 扩容方法去掉了最大长度的限制

在jdk 1.8与jdk17中 有两个方法普遍在ArrayList中使用

System.arraycopy()

1
2
3
4
@IntrinsicCandidate
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

IntrinsicCandidate注解表明是一个是Java库的内部 是从jdk16引入的
native 本地方法 非java 实现

src – 源数组。
srcPos – 源数组中的起始位置。
dest – 目标数组。
destPos – 目标数据中的起始位置。
length – 要复制的数组元素的数量。

Arrays.copyOf()

1
2
3
4
5
6
7
8
9
10
11
@IntrinsicCandidate
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

original – 要复制的数组
newLength – 要返回的副本的长度
newType – 要返回的副本的类

两者联系和区别

联系

看两者源代码可以发现 copyOf()内部实际调用了 System.arraycopy() 方法

区别：

arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组。

如何减少扩容次数 从而提高性能

理论上来说，最好在向 ArrayList 添加大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
jdk 1.8 
public void ensureCapacity(int minCapacity) {
    
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
    
        ensureExplicitCapacity(minCapacity);
    }
}
jdk 17
public void ensureCapacity(int minCapacity) {
    
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
    
        modCount++;
        grow(minCapacity);
    }
}

作者声明

1
如有问题，欢迎指正！