Java集合

廢話不多說，先看下集合結(jié)構(gòu)。今天的三個主角都是繼承自AbstractList這個抽象類，所以他們有很多的相似性（增刪查操作），卻因為特性所以用在不同的場景。接下來先分別介紹下，再比較說明。

Vector :它是一個封裝好的線程安全的動態(tài)數(shù)組。通過synchronized對方法加鎖，以此保證線程安全。Vector集合平時基本用不到。如果不是不需要線程安全，就不要使用，所以這里就不重點說了。

ArrayList :平時Java開發(fā)用的最多的就是ArrayList了，他與Vector相似，內(nèi)部都是通過數(shù)組來保存元素。但是它是線程不安全的所以效率要高于Vector，但是每次超過了原來的大小就需要動態(tài)擴(kuò)容，擴(kuò)展需要進(jìn)行copy，是一個耗時操作。ArrayList擴(kuò)容增加之前的一半大小，而Vector是增加一倍大小。

LinkedList：它的內(nèi)部并不是個動態(tài)數(shù)組，而是維護(hù)者一個雙向列表，數(shù)組在物理空間中是連續(xù)的，鏈表不需要連續(xù)存儲，上個元素會保存下個元素的存儲地址。所以相對ArrayList的優(yōu)點就在于，LinkedList的插入刪除的效率很高，如果訪問的效率就很低，需要遍歷才可以。所以選擇LinkedList還是ArrayList是需要根據(jù)業(yè)務(wù)來選擇的。

這三個集合都是同一個父類，具體用法簡單相似不一一介紹。以ArrayList為例，帶著以下的問題出發(fā)。

• ArrayList動態(tài)數(shù)組的擴(kuò)容流程？
• AbstractList中的Iterator設(shè)計模式場景？
• ArrayList的Sort排序算法？

一、ArrayList動態(tài)數(shù)組的擴(kuò)容流程

先看下ArrayList的一個構(gòu)造方法，一開始就設(shè)置一個動態(tài)數(shù)組大小，如果使用ArrayList之前就已經(jīng)知道大致的長度是多少，就最好使用這個構(gòu)造方法創(chuàng)建，以減少擴(kuò)容的開銷。

    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

擴(kuò)容的觸發(fā)動機(jī)只有在添加的時候，發(fā)現(xiàn)原來的數(shù)據(jù)容量不夠了，才開始擴(kuò)容。找個add方法作為入口查看。

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 核心，確保容量夠大，就執(zhí)行下一步添加數(shù)據(jù)
        elementData[size++] = e;
        return true;
    }

    // 核心方法 minCapacity為數(shù)組大小加一
    private void ensureCapacityInternal(int minCapacity) {
         // 如果數(shù)組為{}，也就是一開始無參構(gòu)造方法中給動態(tài)數(shù)組賦值{}，那么就給一個默認(rèn)的大小，我的源碼是10
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        
        ensureExplicitCapacity(minCapacity); // 核心
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)  // 所需要的最小的長度，比現(xiàn)在的要大，那就需要擴(kuò)容
            grow(minCapacity);
    }

    // 真正的擴(kuò)容方法
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 新的長度為之前的1.5倍
        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:
        // 之間完成copy工作，Arrays是一個處理數(shù)組的工具類
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

到此，就基本知道如何實現(xiàn)擴(kuò)容的了，整體比較簡單，就是判斷數(shù)組夠不夠用了，不過再多給你一半長度，完成數(shù)組的copy

二、AbstractList中的設(shè)計模式之Iterator

個人理解，迭代器模式，就是給數(shù)據(jù)源提供一個遍歷操作方法，這里就是遍歷操作動態(tài)數(shù)組

迭代器模式結(jié)構(gòu)圖

三、ArrayList的Sort排序算法

直接看源碼，Arrays.sort的內(nèi)部使用的是一種歸并和二分插入排序相結(jié)合的方法TimSort。

    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c); // 給一個排序規(guī)則Comparator ，和ArrayList數(shù)據(jù)源
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }