1. ArrayList

基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，可以插入空數(shù)據(jù)，支持隨機(jī)訪問(wèn)。
ArrayList在調(diào)用 add() 方法的時(shí)候

• 首先進(jìn)行擴(kuò)容校驗(yàn)。如果容量不夠時(shí)，需要使用 grow() 方法進(jìn)行擴(kuò)容，每次擴(kuò)容大小是原數(shù)組的 1.5 倍。
• 將插入的值放到尾部。

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

如果是在指定位置添加數(shù)據(jù)的話

• 也是首先擴(kuò)容校驗(yàn)。
• 接著對(duì)數(shù)據(jù)進(jìn)行復(fù)制，目的是把 index 位置空出來(lái)放本次插入的數(shù)據(jù)，并將后面的數(shù)據(jù)向后移動(dòng)一個(gè)位置。

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

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //復(fù)制，向后移動(dòng)
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

那么刪除數(shù)據(jù)也是一樣的思路

將 index+1 后面的元素都復(fù)制到 index 位置上，然后將數(shù)組大小減一，該操作的時(shí)間復(fù)雜度為 O(N)，可以看出 ArrayList 刪除元素的代價(jià)是非常高的。

擴(kuò)容
添加元素時(shí)使用 ensureCapacityInternal() 方法來(lái)保證容量足夠，如果不夠時(shí)，需要使用 grow() 方法進(jìn)行擴(kuò)容，新容量的大小為舊容量的 1.5 倍。

擴(kuò)容操作需要調(diào)用 Arrays.copyOf() 把原數(shù)組整個(gè)復(fù)制到新數(shù)組中，這個(gè)操作代價(jià)很高，因此最好在創(chuàng)建 ArrayList 對(duì)象時(shí)就指定大概的容量大小，減少擴(kuò)容操作的次數(shù)。

Vector

Vector 底層數(shù)據(jù)結(jié)構(gòu)和 ArrayList 類似,也是一個(gè)動(dòng)態(tài)數(shù)組存放數(shù)據(jù)。不過(guò)是在 add() 方法的時(shí)候使用 synchronized 進(jìn)行同步寫(xiě)數(shù)據(jù),開(kāi)銷比較大

與 ArrayList 的比較
Vector 是同步的，因此開(kāi)銷就比 ArrayList 要大，訪問(wèn)速度更慢。
Vector 每次擴(kuò)容請(qǐng)求其大小的 2 倍空間，而 ArrayList 是 1.5 倍。

CopyOnWriteArrayList

特點(diǎn)是：讀寫(xiě)分離
寫(xiě)操作在一個(gè)復(fù)制的數(shù)組上進(jìn)行，讀操作還是在原始數(shù)組中進(jìn)行，讀寫(xiě)分離，互不影響。

適用場(chǎng)景
CopyOnWriteArrayList 在寫(xiě)操作的同時(shí)允許讀操作，大大提高了讀操作的性能，因此很適合讀多寫(xiě)少的應(yīng)用場(chǎng)景。

但是 CopyOnWriteArrayList 有其缺陷：

內(nèi)存占用：在寫(xiě)操作時(shí)需要復(fù)制一個(gè)新的數(shù)組，使得內(nèi)存占用為原來(lái)的兩倍左右；
數(shù)據(jù)不一致：讀操作不能讀取實(shí)時(shí)性的數(shù)據(jù)，因?yàn)椴糠謱?xiě)操作的數(shù)據(jù)還未同步到讀數(shù)組中。
所以 CopyOnWriteArrayList 不適合內(nèi)存敏感以及對(duì)實(shí)時(shí)性要求很高的場(chǎng)景。

LinkedList

基于雙向鏈表實(shí)現(xiàn)，使用 Node 存儲(chǔ)鏈表節(jié)點(diǎn)信息

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

每個(gè)節(jié)點(diǎn)存儲(chǔ)了 prev 和 next 指針：

image.png

新增

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
     /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

從以上可以看出插入數(shù)據(jù)都是移動(dòng)指針，改變前驅(qū)指針和后繼指針的指向，當(dāng)然刪除數(shù)據(jù)也是一樣的。

查找

 public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

查找方法，利用了雙向鏈表的特性，如果index離鏈表頭比較近，就從節(jié)點(diǎn)頭部遍歷。否則就從節(jié)點(diǎn)尾部開(kāi)始遍歷。
也就是索引值大于鏈表大小的一半，那么將從尾結(jié)點(diǎn)開(kāi)始遍歷
這樣的效率是非常低的，特別是當(dāng) index 越接近 size 的中間值時(shí)。

總結(jié)：

• LinkedList 插入，刪除都是移動(dòng)指針效率很高。
• 查找需要進(jìn)行遍歷查詢，效率較低。

HashMap

HashMap 底層是基于數(shù)組和鏈表實(shí)現(xiàn)的。其中有兩個(gè)重要的參數(shù)：

• 容量
• 負(fù)載因子
  容量的默認(rèn)大小是 16，負(fù)載因子是 0.75，當(dāng) HashMap 的 size > 16*0.75 時(shí)就會(huì)發(fā)生擴(kuò)容(容量和負(fù)載因子都可以自由調(diào)整)。

put 方法

首先會(huì)將傳入的 Key 做 hash 運(yùn)算計(jì)算出 hashcode,然后根據(jù)數(shù)組長(zhǎng)度取模計(jì)算出在數(shù)組中的 index 下標(biāo)。