問題提出

• ArrayList底層采用什么數(shù)據(jù)結(jié)構(gòu)？
• ArrayList是如何擴容的？
• 頻繁擴容導致性能下降如何處理？
• 什么情況下你會使用ArrayList？
• 如何復制某個ArrayList到另一個ArrayList中去？
• ArrayList插入或刪除元素一定慢么？
• ArrayList是線程安全的么？

下面就帶著問題往下看吧~

重要屬性

//默認的初始化容量
private static final int DEFAULT_CAPACITY = 10;

//空的對象數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};

//使用默認構(gòu)造函數(shù)創(chuàng)建對象時使用該空對象數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//存放數(shù)據(jù)的容器
transient Object[] elementData;

//數(shù)組長度
private int size;

//數(shù)組最大長度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

構(gòu)造器

/**
* 傳入指定容量大小
*/
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);
    }
}

/**
* 無參的構(gòu)造方法
*/
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

添加數(shù)據(jù)

add(E e);
add(int index, E element);
addAll(int index, Collection<? extends E> c);
addAll(Collection<? extends E> c);

添加單個數(shù)據(jù)

注意：這里使用無參構(gòu)造函數(shù)，第一次添加數(shù)據(jù)作為例子

public boolean add(E e) {
    //擴容處理
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //添加數(shù)據(jù)到數(shù)組末尾
    elementData[size++] = e;
    return true;
}

先進行擴容處理

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

/**
* 如果當前還未存入數(shù)據(jù)（空數(shù)組），返回默認長度10 (第一次添加數(shù)據(jù)，數(shù)組容量為10)
* 否則，返回當前數(shù)組長度+1
*/
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) {
    //集合修改次數(shù)加1
    modCount++;
    //判斷當前數(shù)組是否有剩余空間，沒有調(diào)用grow(minCapacity);
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //擴容新容量=舊容量+舊容量/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //擴容后的新容量小于所需的容量，則新容量等于所需容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //新容量若對于最大容量值，則調(diào)用方法后獲取一個最大容量值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //拷貝已有的數(shù)組到擴容后新數(shù)組
        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;
    }

• 擴容處理邏輯如下：

  
  
  容量擴充 (1).jpg

添加數(shù)據(jù)到指定位置

邏輯：先將指定位置元素都往后移動一個位置，再將新元素放在指定位置。

public void add(int index, E element) {
    //越界檢測
    rangeCheckForAdd(index);
    //擴容處理
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //對源數(shù)組做復制處理，后移（index+1 ~ size-index）
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

添加集合數(shù)據(jù)到指定位置

public boolean addAll(int index, Collection<? extends E> c) {
    //越界檢測
    rangeCheckForAdd(index);
    //轉(zhuǎn)化為數(shù)組
    Object[] a = c.toArray();
    //需要插入的數(shù)據(jù)個數(shù)
    int numNew = a.length;
    //擴容處理
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //需要移動的位數(shù)
    int numMoved = size - index;
    //若插入位置當前已有數(shù)據(jù)，移位
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
    
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

添加集合數(shù)據(jù)

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //直接copy數(shù)據(jù)到容器中
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

刪除元素

remove(int index)；
remove(Object o)；
removeAll(Collection<?> c)；
clear();

刪除指定位置的元素

public E remove(int index) {
    rangeCheck(index);
    //集合修改次數(shù)加1
    modCount++;
    //取出需要刪除的對象賦值給oldValue
    E oldValue = elementData(index);
    //需要移動的數(shù)據(jù)長度
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //數(shù)據(jù)在末尾直接刪除
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
 }

刪除指定對象

public boolean remove(Object o) {
    //遍歷數(shù)組找出要刪除的數(shù)據(jù)，刪除它
    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;
}

private void fastRemove(int index) {
    //集合改變數(shù)據(jù)加1
    modCount++;
    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
}

刪除指定的集合元素

public boolean removeAll(Collection<?> c) {
    //判斷對象是否為null
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            //遍歷數(shù)組，找出不需要刪除的元素保存在數(shù)組前面
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        //未完成遍歷出錯的情況下。
        if (r != size) {
            System.arraycopy(elementData, r,elementData, w,size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            //w為已經(jīng)移到數(shù)組前面需要保留的數(shù)據(jù)，刪除w之后的數(shù)據(jù)
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

刪除所有元素

public void clear() {
    modCount++;

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

    size = 0;
}

set方法 get方法

/**
 * Replaces the element at the specified position in this list with
 * the specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

轉(zhuǎn)為數(shù)組

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

//轉(zhuǎn)化為任意類型的數(shù)組
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

小結(jié)

• ArrayList 采用動態(tài)數(shù)組。適合快速查找數(shù)據(jù)，不適合刪除和添加操作
• 頻繁擴容導致性能下降，可以初始化估計容量大小的arrayList
• ArrayList 線程不安全