1.集合框架

Java中集合是用來存儲對象的工具類容器正勒，它實現(xiàn)了常用的數(shù)據(jù)結(jié)構(gòu)，提供了一系列公開的方法用于增加悼尾、刪除柿扣、修改、查找和遍歷數(shù)據(jù)闺魏，降低了日常開發(fā)成本未状。集合的種類非常多，如下圖所示析桥，集合主要分為兩類：第一類是按照單個元素存儲的Collection司草，在繼承樹的Set和List都實現(xiàn)了Collection接口；第二類是按照Key-Value存儲的Map泡仗。以上兩類集合體系翻伺，無論數(shù)據(jù)存取還是遍歷，都存在非常大的差異沮焕。

Collection

1. List

• Arraylist：數(shù)組（查詢快,增刪慢 線程不安全,效率高 ）
• Vector：數(shù)組（查詢快,增刪慢 線程安全,效率低 ）
• LinkedList：鏈表（查詢慢,增刪快 線程不安全,效率高 ）

2. Set

• HashSet（無序吨岭，唯一）:哈希表或者叫散列集(hash table)
• LinkedHashSet：鏈表和哈希表組成 。 由鏈表保證元素的排序 峦树， 由哈希表證元素的唯一性
• TreeSet（有序辣辫，唯一）：紅黑樹(自平衡的排序二叉樹。)

Map

• HashMap：基于哈希表的Map接口實現(xiàn)（哈希表對鍵進行散列魁巩，Map結(jié)構(gòu)即映射表存放鍵值對）
• LinkedHashMap:HashMap 的基礎(chǔ)上加上了鏈表數(shù)據(jù)結(jié)構(gòu)
• HashTable:哈希表
• TreeMap:紅黑樹（自平衡的排序二叉樹）

2.源碼分析

首先拿兩個List的類學習一下：ArrayList和LinkedList急灭，主要了解二者數(shù)據(jù)結(jié)構(gòu)以及什么情況下選擇哪種集合類。

2.1 ArrayList

ArrayList 是一種變長的集合類谷遂，基于定長數(shù)組實現(xiàn)葬馋。ArrayList 允許空值和重復(fù)元素，當往 ArrayList 中添加的元素數(shù)量大于其底層數(shù)組容量時肾扰，其會通過擴容機制重新生成一個更大的數(shù)組畴嘶。另外，由于 ArrayList 底層基于數(shù)組實現(xiàn)集晚，所以其可以保證在 O(1) 復(fù)雜度下完成隨機查找操作窗悯。其他方面，ArrayList 是非線程安全類偷拔，并發(fā)環(huán)境下蒋院，多個線程同時操作 ArrayList亏钩，會引發(fā)不可預(yù)知的錯誤。

2.1.1 構(gòu)造方法

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData; 

    private int size;

    // 構(gòu)造方法1
    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)造方法2
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    // 構(gòu)造方法3
    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 {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

構(gòu)造方法1是傳入初始容量值欺旧，構(gòu)造方法2是無參的姑丑，構(gòu)造方法3是傳入一個集合。一般情況下辞友，我們用無參的構(gòu)造方法即可栅哀。倘若在可知道將會向 ArrayList 插入多少元素的情況下，應(yīng)該使用有參構(gòu)造方法踏枣。按需分配昌屉，避免浪費。

2.1.2 插入

    /**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

    public void add(int index, E element) {
        // 檢測index是否合理
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            // 當元素的size等于數(shù)組長度時茵瀑，進行擴容
            elementData = grow();
        // 將index及其之后的元素向后移一位
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        // 插入新元素
        elementData[index] = element;
        size = s + 1;
    }

插入方法有3種间驮，add(E e, Object[] elementData, int s)方法是從add(E e)中分離出來的，算是一個優(yōu)化吧(至于為啥保持方法字節(jié)碼大小低于35马昨，Google了一下也沒找到竞帽。。鸿捧。)屹篓，第1和第2算是一個方法吧，都是在數(shù)組尾部插入匙奴，時間復(fù)雜度為O(1)堆巧，第3種是在指定索引處插入，需要先將指定索引以及其后面的元素都向后移一位泼菌，然后將新元素插入谍肤，時間復(fù)雜度就變成了O(N)。
需要注意的是第3種add方法中的 grow() 方法哗伯，這就涉及到ArrayList中比較核心的擴容機制了荒揣，看下源碼流程：

    private Object[] grow() {
        return grow(size + 1);
    }

    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

    private int newCapacity(int minCapacity) {
        int oldCapacity = elementData.length;
        // newCapacity = (1 + 0.5) * oldCapacity 擴容之后是之前的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0)
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

    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.5倍，其它地方都是邊界檢查焊刹，數(shù)組越界會報 OutOfMemoryError 異常系任。

2.1.3 刪除

    // 刪除指定位置的元素
    public E remove(int index) {
        Objects.checkIndex(index, size);
        final Object[] es = elementData;

        @SuppressWarnings("unchecked") 
        E oldValue = (E) es[index];
        fastRemove(es, index);

        return oldValue;
    }

    // 刪除指定元素
    public boolean remove(Object o) {
        final Object[] es = elementData;
        final int size = this.size;
        int i = 0;
        found: {
            if (o == null) {
                for (; i < size; i++)
                    if (es[i] == null)
                        break found;
            } else {
                for (; i < size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }
        fastRemove(es, i);
        return true;
    }

    // 快速刪除，不做邊界檢查也不返回元素值
    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }

刪除邏輯也不復(fù)雜虐块，第2個方法要比第1個方法多了查找元素位置的操作俩滥，在 fastRemove 方法中將 index + 1 及之后的元素向前移動一位，然后將最后一個元素置null非凌，size 減 1举农。

2.1.4 遍歷

下面是我們用到的三種遍歷方式：

    ArrayList<String> list = new ArrayList<String>();
    // list.add()添加元素
    // 1.普通for循環(huán)遍歷
    for(int i = 0; i < list.size(); i++){}

    // 2.增強for循環(huán)遍歷，語法糖
    for(String s : list){}

    // 3.迭代器敞嗡，增強for循環(huán)也是轉(zhuǎn)換成迭代器
    Iterator iterator = list.iterator();
    while(iterator.hasNext()){
        String s = iterator.next();
    }

看下 iterator() 的實現(xiàn):

    public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        // prevent creating a synthetic constructor
        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        // 省略部分源碼
    }

list.iterator() 方法返回 Iterator 的子類 Itr 颁糟，Itr也是一個私有的內(nèi)部類，主要用到就是 hasNext() 判斷 list 中 cursor 處是否存在元素喉悴，還有 next() 方法返回 cursor 處的元素棱貌。
至于 Itr 中 remove() 方法，引用阿里巴巴開發(fā)手冊中的話：

【強制】不要在 foreach 循環(huán)里進行元素的 remove/add 操作箕肃。remove 元素請使用 Iterator 方式婚脱，如果并發(fā)操作，需要對 Iterator 對象加鎖勺像。

2.2 LinkedList

2.2.1 構(gòu)造方法

    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

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

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    public LinkedList() {
    }

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

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

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

LinkedList 數(shù)據(jù)結(jié)構(gòu)為鏈表障贸，節(jié)點 Node 包含了前驅(qū)節(jié)點、后繼節(jié)點和自身數(shù)據(jù) element吟宦，構(gòu)造方法有無參和傳入集合兩種篮洁，傳入集合調(diào)用了 addAll() 方法將傳入的集合元素順序遍歷添加到鏈表的尾部。

2.2.2 查詢

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    Node<E> node(int 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;
        }
    }

查詢中 checkElementIndex() 方法判斷入?yún)⑹欠袷乾F(xiàn)有元素的索引殃姓，node() 方法利用了二分查找(簡化版的袁波，通過比較 index 與 size/2 的大小決定從頭節(jié)點還是為節(jié)點進行查找)，獲取入?yún)⑺饕诘脑亍?/p>

2.2.2 插入

LinkedList 沒有像ArrayList中的容量蜗侈，所以也沒有擴容一說篷牌，只要把新元素添加到鏈表上即可

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

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

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    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++;
    }

    void linkBefore(E e, Node<E> succ) {
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
    

add(E e) 將新節(jié)點添加在鏈表尾部，將當前 last 節(jié)點的 next 節(jié)點指向新節(jié)點踏幻，然后將新節(jié)點變成 last 節(jié)點枷颊；如果 last 節(jié)點為空，鏈表為空该面，新節(jié)點變成 first 首節(jié)點夭苗。

add(int index, E element) 在指定索引處添加新節(jié)點，如果 index 為 size吆倦，就相當于在添加在鏈表尾部听诸；不是的話，先調(diào)用 node() 方法查詢當前 index 位置的 node 節(jié)點蚕泽，然后將新節(jié)點添加在該 node 前晌梨，改變該 node 節(jié)點的 prev 指向新節(jié)點以及該 node 節(jié)點前驅(qū)節(jié)點的 next 指向。

2.2.3 刪除

    // 無參remove
    public E remove() {
        return removeFirst();
    }

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    private E unlinkFirst(Node<E> f) {
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    // 指定索引remove
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

remove()默認刪除鏈表首節(jié)點须妻，將首節(jié)點的 next 指向的節(jié)點變?yōu)?first 首節(jié)點仔蝌，將 f.item 、 f.next 和 next.prev 置null是為了虛擬機進行垃圾回收(GC)荒吏。

remove(int index) 主要是先通過 node() 方法找到指定索引位置節(jié)點敛惊，然后判斷該節(jié)點的前驅(qū)和后繼節(jié)點是否為null，不為null绰更，則將前驅(qū)節(jié)點的 next 指向后繼節(jié)點瞧挤，將后繼節(jié)點的 prev 指向前驅(qū)節(jié)點锡宋，最后將刪除節(jié)點的 prev 和 next 置null。

2.2.4 遍歷

    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        //省略部分源碼
    }

使用 foreach 遍歷 LinkedList 時也是轉(zhuǎn)換成迭代器形式特恬，在上面的迭代器實現(xiàn)中执俩，可以看到 new ListItr(index) 時也會先調(diào)用 node() 方法定位 next 后繼節(jié)點的索引位置，效率比較低癌刽，然后返回后繼節(jié)點的 item役首，最后賦值 next = next.next 將 next 變成后繼節(jié)點的后繼節(jié)點， nextIndex++即可显拜。

3. 總結(jié)

從上面分析中衡奥，也不難看出 ArrayList 便于查找，LinkedList 便于增刪远荠，源碼并不是很復(fù)雜矮固，可以耐心看一看。