如有轉(zhuǎn)載請(qǐng)注明出處 http://www.itdecent.cn/p/7c0fbce086c6

緒論

ArrayList是線程不安全的，他的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，ArrayList保存的數(shù)據(jù)是可以重復(fù)的。由于數(shù)組具有下表，所以他查詢起來(lái)比較快，主要操作方法有add，remove，get。

add

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(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;
    }

1.在添加數(shù)據(jù)的時(shí)候首先要去擴(kuò)容，如果之前數(shù)組中是空的那么就給他一個(gè)最小長(zhǎng)度10
2.數(shù)組目前不滿足添加數(shù)據(jù)的需要時(shí)，需要去擴(kuò)容
3.默認(rèn)數(shù)組擴(kuò)容1.5倍

• 大批量添加數(shù)據(jù)的時(shí)候，老數(shù)組擴(kuò)容1.5倍不滿足需求時(shí)，就把要添加的個(gè)數(shù)作為擴(kuò)容數(shù)組的個(gè)數(shù)
• 如果要添加的數(shù)據(jù)已經(jīng)大于數(shù)組的最大值，那么就讓她擴(kuò)容到Integer.MAX_VALUE
  最后創(chuàng)建擴(kuò)容之后的數(shù)組，并且把原數(shù)組的值放入新數(shù)組中

remove

public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) 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;
    }

先將要溢出的數(shù)據(jù)拿出來(lái)，然后拿到移除數(shù)據(jù)前的index，如果移除的不是最后面的數(shù)據(jù)需要將index+1的數(shù)據(jù)向左移動(dòng)，然后將最后一個(gè)數(shù)據(jù)設(shè)置為null

get

public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }

直接將數(shù)組中index位置的值拿出來(lái)

數(shù)組

由上面的操作可以看出來(lái)，數(shù)組的查詢很快，添加和刪除的時(shí)候都需要對(duì)數(shù)組進(jìn)行復(fù)制操作，所以效率比較低
數(shù)組查詢快是因?yàn)閿?shù)組的空間都是連續(xù)的，通過(guò)index直接獲取value
數(shù)組增刪比較慢是因?yàn)樵谠黾拥臅r(shí)候，需要擴(kuò)容，并且將老的數(shù)組放到新數(shù)組中，在刪除的時(shí)候需要將要?jiǎng)h除的位置之后的數(shù)據(jù)向左移動(dòng)，然后將最后一個(gè)數(shù)據(jù)這只為null。