JDK之ArrayList源码剖析

ArrayList源码分析

基于java version "1.8.0_321"

底层实现

ArrayList底层是用数组实现的，Object数组

transient Object[] elementData; // non-private to simplify nested class access

private int size;	//元素个数

扩容分析

看一下add方法：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

在添加元素之前，会进行一个容量是否需要增长判断操作ensureCapacityInternal(size + 1); 。

//2
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {	//如果数组是默认空元素数组
        return Math.max(DEFAULT_CAPACITY, minCapacity);	// 将两者中较大的值作为minCapacity
    }
    return minCapacity;	//否则minCapacity不变
}
//1
private void ensureCapacityInternal(int minCapacity) {	//
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//3
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)	//如果需要的容量大于现有数组容量
        grow(minCapacity);
}

如果当前数组的容量不足够放下元素个数，就执行grow(minCapacity);扩容

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

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)	//如果扩容1.5倍还不满足大小，就直接扩容到minCapacity
    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) {	//判断容量是否超int大小
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

由int newCapacity = oldCapacity + (oldCapacity >> 1);判断，新的数组的容量是原来的1.5倍（>>右移等价于除以2）

要注意的是，扩容后的容量可能溢出变为负数，这时候就需要hugeCapacity(minCapacity)函数判断溢出这种情况.

ArrayList常用方法复杂度分析

add(E e)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

直接在元素列末尾添加一个元素,复杂度可看成O(1)

add(int index, E element)

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

index及后的所有元素往后移一位,复杂度近似O(n)

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);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

删除指定位置的元素,其他的所有元素往前移一位,O(n)

remove(Object o)

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

删除首个指定元素,其后所有元素往前移一位O(n)

indexOf(Object o)

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

O(n)

contains(Object o)

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

O(n)

clear()

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

将所有有元素的索引置null,不缩减容量.O(n)

addAll(Collection<? extends E> c)

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

将集合的所有元素追加至末尾,复杂度O(k),k为集合的元素个数

addAll(int index, Collection<? extends E> c)

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

将集合所有元素追加至具体位置上,其后所有元素往后移k位,复杂度O(n + k)