摘要：迭代器迭代器簡單來說就是用來對集合的元素進行遍歷操作的。調用集合的或方法將實例出從第一個結點開始的迭代器，也可以傳入參數作為第一個迭代的結點。

List

- LinkedList
- ArrayList
- Vector
    - Stack

Queue

- PriorityQueue
- Deque
     - ArrayDeque       

Set

- HashSet
     - LinkedHashSet
- TreeSet

HashMap

- LinkedHashMap
- TreeMap

HashTable

先看字段聲明

    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node last;

我們看到有三個字段，分別是size、first、last，命名和注釋已非常簡單明顯，不難看出這是一個雙向鏈表。
注意到這三個字段都有個修飾關鍵字transient，這是比較不常見的，這是與類序列化相關的內容，為了不讓這篇將集合的文章太跳，將會在寫完LinkedList相關的內容后再講述。
最核心內容，LinkedList的信息儲存單元是一個內部類Node。

三個字段分別是前驅結點，后繼結點、節點內容，沒什么特別的。

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

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

關于對鏈表的增刪結點，獲取結點，更換結點等操作比較簡單，下面只挑在某個結點前插入一個結點的操作進行講述：

    /**
     * Inserts element e before non-null Node succ.
     */
    //非public方法，public void add(int index, E element)為上層方法
    void linkBefore(E e, Node succ) {//在succ結點前加入以e為值的結點
        // assert succ != null;
        final Node pred = succ.prev;
        //1.將e構造成結點，后繼結點為succ，前驅結點為succ的前驅結點，這用在e結點的角度就已經加入到鏈表中succ前面的位置了，但此時e結點的前后結點指針還未指向e
        final Node newNode = new Node<>(pred, e, succ);
        //2.將e后面的結點即succ的前驅指向e
        succ.prev = newNode;
        //3.將e前面的結點的后繼指向e，若e此時為第一個結點則將first指針指向e
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        //4.鏈表容量增加1
        size++;
        //5.鏈表修改次數記錄加1
        modCount++;
    }

通過了解在某個結點前插入一個結點這個操作的實現，不難發現鏈表一個兩個非常重要的特點，一是方便動態增刪結點，只需要調整鏈表局部位置的結點指向，二是隨機查詢速度較慢，因為需要從頭結點一直向前查詢。
注意到，其實會對鏈表結構發生改變的每一個操作，鏈表都會將修改次數記錄modCount加1，那這個modCount的作用是什么呢？其實是用于輔助迭代器正常使用的。

迭代器簡單來說就是用來對集合的元素進行遍歷操作的。調用集合的iterator()或listIterator()方法將實例出從第一個結點開始的迭代器，也可以傳入int參數作為第一個迭代的結點。

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

        ListItr(int index) {
            // assert isPositionIndex(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;
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }

        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

        public void forEachRemaining(Consumer action) {
            Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size) {
                action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

從內部類ListItr看到，LinkedList的迭代器可以雙向進行迭代的，迭代過程中只能使用迭代器的add()、set()、remove()對鏈表進行修改，為什么重點標出只能，因為很多新手很容易寫出這樣的代碼：

            //雖然沒有顯式地使用迭代器，但其實底層實現也是使用迭代器進行迭代
            for (Object o : linkedList) {
                if(o.equals(something)){
                    linkedList.remove(o);
                }
            }

這樣是會報錯的，通過注釋，我們可以看到這是在迭代過程中是不允許直接修改鏈表的結構的，fail-fast機制，可以看到，在迭代器的代碼中，有個非public方法checkForComodification(),迭代器中幾乎每個操作都會調用一下該方法，而該方法的方法體內僅僅做的一件事就是檢查鏈表的modCount是否等于迭代器expectedModCount，不相等將拋出ConcurrentModificationException，從而實現不允許在迭代過程中直接修改鏈表結構，至于為什么要這樣做則自行研究上述迭代的代碼看如果在迭代過程中修改了鏈表結構會有什么錯誤發生。因此，正確的使用迭代器刪除元素應該是像下面這樣：

      
        while (iterator.hasNext()){
            Object o = iterator.next();
            if(o.equals(something)){
                iterator.remove();
            }
        }

從LinkedList的迭代器代碼中可以看到一個方法forEachRemaining(),我們查看Iterator接口的描述：

    /**
     * Performs the given action for each remaining element until all elements
     * have been processed or the action throws an exception.  Actions are
     * performed in the order of iteration, if that order is specified.
     * Exceptions thrown by the action are relayed to the caller.
     *
     * @implSpec
     * 
The default implementation behaves as if:
     * 
{@code
     *     while (hasNext())
     *         action.accept(next());
     * }
     *
     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @since 1.8
     */
    default void forEachRemaining(Consumer action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }

看到該方法是在jdk1.8版本后才加入的，用于實現對集合每個元素做特定操作，傳入參數為Consumer接口，Consumer接口是一個只有一個方法需要實現的接口，所以不難看出其實該方法是用于配合lambda來使用的，以此更加簡化java的表達，舉例：

     iterator.forEachRemaining(System.out::println);
    
     iterator.forEachRemaining(item -> {
            System.out.println(item);
     });

繼續看Linked的源代碼，我們看到一個Spliterator，這是jdk1.8才加入的迭代器，該迭代器其實就是可分割的迭代器，可分割，意味著可以將迭代過程分給不同的線程去完成，從而提高效率。為了方便，源碼分析將在下述代碼以注釋方式進行：

    @Override
    public Spliterator spliterator() {
        return new LLSpliterator(this, -1, 0);
    }

    /** A customized variant of Spliterators.IteratorSpliterator */
    //變種的IteratorSpliterator，區別：IteratorSpliterator使用interator進行迭代，LLSpliterator直接使用Node的next指針迭代，原則上迭代速度更快
    static final class LLSpliterator implements Spliterator {
        static final int BATCH_UNIT = 1 << 10;  // batch array size increment;分割的長度增加單位，每分割一次下次分割長度增加1024
        static final int MAX_BATCH = 1 << 25;  // max batch array size;最大分割長度，大于2^25分割長度將不再增加
        final LinkedList list; // null OK unless traversed
        Node current;      // current node; null until initialized
        int est;              // size estimate; -1 until first needed
        int expectedModCount; // initialized when est set
        int batch;            // batch size for splits;當前分割長度

        LLSpliterator(LinkedList list, int est, int expectedModCount) {
            this.list = list;
            this.est = est;
            this.expectedModCount = expectedModCount;
        }

        final int getEst() {
            int s; // force initialization
            final LinkedList lst;
            if ((s = est) < 0) {
                if ((lst = list) == null)
                    s = est = 0;
                else {
                    expectedModCount = lst.modCount;
                    current = lst.first;
                    s = est = lst.size;
                }
            }
            return s;
        }

        public long estimateSize() { return (long) getEst(); }

        //分割出batch長度的Spliterator
        public Spliterator trySplit() { 
            Node p;
            int s = getEst();
            if (s > 1 && (p = current) != null) {
                //每次分割長度增加BATCH_UNIT，達到MAX_BATCH便不再增加
                int n = batch + BATCH_UNIT;
                if (n > s)
                    n = s;
                if (n > MAX_BATCH)
                    n = MAX_BATCH;
                //將需要分割的元素生成數組
                Object[] a = new Object[n];
                int j = 0;
                do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
                current = p;
                batch = j;
                est = s - j;
                //返回新的Spliterator，注意：新的Spliterator為ArraySpliterator類型，實現上有所區別，ArraySpliterator每次分割成一半一半，而IteratorSpliterator算術遞增
                return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
            }
            return null;
        }
        
        //遍歷當前迭代器中所有元素并對獲取元素值進行action操作（操作所有元素）
        public void forEachRemaining(Consumer action) {
            Node p; int n;
            if (action == null) throw new NullPointerException();
            if ((n = getEst()) > 0 && (p = current) != null) {
                current = null;
                est = 0;
                do {
                    E e = p.item;
                    p = p.next;
                    action.accept(e);
                } while (p != null && --n > 0);
            }
            if (list.modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
        
        //對當前迭代元素的元素值進行action操作（只操作一個元素）
        public boolean tryAdvance(Consumer action) {
            Node p;
            if (action == null) throw new NullPointerException();
            if (getEst() > 0 && (p = current) != null) {
                --est;
                E e = p.item;
                current = p.next;
                action.accept(e);
                if (list.modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                return true;
            }
            return false;
        }

        public int characteristics() {
            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
        }
    }

來自百度百科的解釋：

java語言的關鍵字，變量修飾符，如果用transient聲明一個實例變量，當對象存儲時，它的值不需要維持。換句話來說就是，用transient關鍵字標記的成員變量不參與序列化過程。

解釋了跟沒解釋差不多。好，其實對象存儲就是一個對象序列化的過程，下面提供一個程序以便更好的理解：

package Serializable;

import java.io.*;

public class SerializableTest {
    private static void testSerializable(AbstractClass cl) throws IOException {
        //依次讀取對象的各個字段值
        System.out.printf("Minor version number: %d%n", cl.getMinorVer());
        System.out.printf("Major version number: %d%n", cl.getMajorVer());
        cl.showString();
        System.out.println();

        //將對象寫入硬盤
        File file = new File("resource/ObjectRecords.txt");
        if (!file.exists()) {
            file.createNewFile();
        }
        try (FileOutputStream fos = new FileOutputStream(file);
             ObjectOutputStream oos = new ObjectOutputStream(fos))
        {
            oos.writeObject(cl);
        }
        
        //置空對象的引用
        cl = null;

        //將對象重新從硬盤讀回
        try (FileInputStream fis = new FileInputStream("resource/ObjectRecords.txt");
             ObjectInputStream ois = new ObjectInputStream(fis))
        {
            cl = (AbstractClass) ois.readObject();
            //依次讀取反序列化后的對象的各個字段值
            System.out.printf("Minor version number: %d%n", cl.getMinorVer());
            System.out.printf("Major version number: %d%n", cl.getMajorVer());
            cl.showString();
            System.out.println();
        } catch (ClassNotFoundException cnfe) {
            System.err.println(cnfe.getMessage());
        }
    }
    
    public static void main(String[] args) throws IOException {
        ClassSerializable cl1 = new ClassSerializable("string");
        testSerializable(cl1);
        ClassAllSerializable cl2 = new ClassAllSerializable("string");
        testSerializable(cl2);
        ClassNotSerializable cl3 = new ClassNotSerializable("string");
        testSerializable(cl3);
    }
}
 

從main方法可以看到這里用來測試的有三個類，分別是ClassSerializable、ClassAllSerializable、ClassNotSerializable，其中前兩個實現了Serializable接口，代表這兩個類是可以進行序列化的，所以前兩個類的對象在進行writeObject的時候不會報錯，而ClassNotSerializable則拋出java.io.NotSerializableException: Serializable.ClassNotSerializable，而前兩個類區別在于ClassSerializable所有字段均帶有Transient關鍵字，而ClassAllSerializable沒有，以下是程序輸出結果：

ClassSerializable called
Minor version number: 1
Major version number: 2
string

Minor version number: 0
Major version number: 0
null

ClassAllSerializable called
Minor version number: 1
Major version number: 2
string

Minor version number: 1
Major version number: 2
string

ClassNotSerializable called
Minor version number: 1
Major version number: 2
string

Exception in thread "main" java.io.NotSerializableException: Serializable.ClassNotSerializable
    at java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1184)
    at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:348)
    at Serializable.SerializableTest.testSerializable(SerializableTest.java:19)
    at Serializable.SerializableTest.main(SerializableTest.java:42)

可以明顯看到，被transient修飾的字段經過對象的序列化和反序列化后沒有被保存起來。

先看字段聲明進行初步分析：

     /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

顯然，elementData是用來存儲元素的，也就是說ArrayList底層由數組維護的。
我們都知道，數組的大小初始化之后就是固定的，而數組表的元素是需要進行增刪操作的，那么ArrayList是如何實現改變大小的呢？

不難想象，當進行add()操作的時候需要進行擴容：

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    public boolean addAll(Collection c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    
    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);
    }

可以看到，重點是grow()方法，我們分析一下grow()的行為，參數變量minCapacity其實只是一個參考大小，通常為當前大小加新增元素個數，grow首要考慮是將容量增加兩倍，若此時minCapacity更大的話才考慮取minCapacity，最后考慮值若比MAX_ARRAY_SIZE還要大則只能盡可能大進行擴容，最后使用Arrays.copyOf()進行新建數組后復制。
其實Arraylist的所有add和remove操作都是基于Arrays.copyOf()進行的，此時，ArrayList相較于LinkedList的特點很明顯了，一是因為其底層是數組，所以ArrayList非常擅長與隨機讀取，二是因為基于Arrays.copyOf()實現的原因，ArrayList增刪元素效率很低，而且導致內存占用增加，提高GC觸發的幾率。

分別是foreach、removeIf、replaceAll、sort，其參數均可使用lumbda表達式，這四個方法來自不同的接口，其實LinkedList也有這幾個方法，不過LinkedList均使用的是上級接口的default實現，而ArrayList則對其進行覆蓋了，下面將在代碼中增加注釋加以分析：

    @Override
    //default使用迭代器迭代，下面實現原理一樣，簡化檢查過程
    public void forEach(Consumer action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
    
    
    @Override
    //default使用迭代器迭代，后滿足條件進行remove()，上面也講了ArrayList隨機增減元素效率很低，所以default的實現是絕對不可取的，下面實現的思想其實是吧需要刪除的元素序號記錄下來，然后跳過這些元素把剩余元素按順序排回this.elementData中
    public boolean removeIf(Predicate filter) {
        Objects.requireNonNull(filter);
        // figure out which elements are to be removed
        // any exception thrown from the filter predicate at this stage
        // will leave the collection unmodified
        int removeCount = 0;
        final BitSet removeSet = new BitSet(size);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            @SuppressWarnings("unchecked")
            final E element = (E) elementData[i];
            if (filter.test(element)) {
                removeSet.set(i);
                removeCount++;
            }
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

        // shift surviving elements left over the spaces left by removed elements
        final boolean anyToRemove = removeCount > 0;
        if (anyToRemove) {
            final int newSize = size - removeCount;
            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }
            for (int k=newSize; k < size; k++) {
                elementData[k] = null;  // Let gc do its work
            }
            this.size = newSize;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }

        return anyToRemove;
    }

    @Override
    @SuppressWarnings("unchecked")
    //default使用迭代器迭代，下面實現原理一樣，簡化檢查過程
    public void replaceAll(UnaryOperator operator) {
        Objects.requireNonNull(operator);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            elementData[i] = operator.apply((E) elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    @Override
    @SuppressWarnings("unchecked")
    //default方法先將集合用toArray()轉換成數組再用Arrays.sort,而這對于ArrayList來說肯定是多余的，因為ArrayList的元素容器就是數組
    public void sort(Comparator c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

簡單翻看了Vector的源碼和注釋，發現它在jdk1.0就存在的，而ArrayList、LinkedList這種都是jdk1.2才增加的，然后在jdk1.2版本的時候稍微改造增加了對List的實現，而其大部分內容和ArrayList沒什么大的差別，只是對public方法加上了synchronized關鍵字，也就是說jdk1.2以后Vector其實相當于是線程安全的ArrayList，這一點注釋上也有提及：

 /** 
   ...

 * 
As of the Java 2 platform v1.2, this class was retrofitted to
 * implement the {@link List} interface, making it a member of the
 * 
 * Java Collections Framework.  Unlike the new collection
 * implementations, {@code Vector} is synchronized.  If a thread-safe
 * implementation is not needed, it is recommended to use {@link
 * ArrayList} in place of {@code Vector}.
   
   ...
 */

而Stack，繼承自Vector，在它之上增加了棧的操作（push、pop）。
在注釋中我們也注意到，對棧這種后進先出的操作也在雙端隊列Deque接口的實現中提供，例子給出的是ArrayDeque，關于隊列及雙端隊列我們后續在講：

/**
 ...

 * 
A more complete and consistent set of LIFO stack operations is
 * provided by the {@link Deque} interface and its implementations, which
 * should be used in preference to this class.  For example:
 * 
   {@code
 *   Deque stack = new ArrayDeque();}

 ...
 */

我們先看Queue接口方法：

public interface Queue extends Collection {
    /**
     * Inserts the specified element into this queue if it is possible to do so
     * immediately without violating capacity restrictions, returning
     * {@code true} upon success and throwing an {@code IllegalStateException}
     * if no space is currently available.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean add(E e);

    /**
     * Inserts the specified element into this queue if it is possible to do
     * so immediately without violating capacity restrictions.
     * When using a capacity-restricted queue, this method is generally
     * preferable to {@link #add}, which can fail to insert an element only
     * by throwing an exception.
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this queue, else
     *         {@code false}
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean offer(E e);

    /**
     * Retrieves and removes the head of this queue.  This method differs
     * from {@link #poll poll} only in that it throws an exception if this
     * queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E remove();

    /**
     * Retrieves and removes the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E poll();

    /**
     * Retrieves, but does not remove, the head of this queue.  This method
     * differs from {@link #peek peek} only in that it throws an exception
     * if this queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E element();

    /**
     * Retrieves, but does not remove, the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E peek();
}

element()和peek()均是獲取隊列頭元素，但不刪除，區別是在隊列空時peek()返回null，element()拋出NoSuchElementException。
對于隊列來說，我們知道，普通隊列的特性是先進先出（區別于棧的先進后出），比如LinkedList，隊列的特有方法offer()和poll()就是用來對隊列插入和取出元素的，而另外兩個方法add()和remove()通常也是在隊列尾插入在隊列頭取出，因此通常與offer()和poll()實現的其實是一樣的，但是在使用隊列時，使用后者方法名語義更強。而PriorityQueue與普通的隊列不同，因為元素有優先級，所以不具備先進先出的特點，下面看PriorityQueue的源碼,還是先來看字段信息：

    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements"
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     */
    transient Object[] queue; // non-private to simplify nested class access

    /**
     * The number of elements in the priority queue.
     */
    private int size = 0;

    /**
     * The comparator, or null if priority queue uses elements"
     * natural ordering.
     */
    private final Comparator comparator;

    /**
     * The number of times this priority queue has been
     * structurally modified.  See AbstractList for gory details.
     */
    transient int modCount = 0; // non-private to simplify nested class access

很明顯，queue是底層存儲元素的隊列，是一個Object數組，但是不同的是，該數組其實代表的是一顆平衡二叉堆（上面的元素小，下面的元素大），queue[n]為父節點時，queue[2n+1]為左孩子，queue[2(n+1)]為右孩子，其大小關系也就是優先級關系通過comparator作比較決定。
繼續看插入過程的源碼：

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }
    
    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }
    
    private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }

可以看到，插入的過程充分體現堆的特點，從二叉樹的最后的位置依次向上與父節點比較，比父節點小（優先級大）則將父節點下移，繼續比較，知道比父節點大停止并且插入，目的是將優先級小的放到堆的下面使得取出時優先取出優先級大的元素，下面看取出元素的方法：

    public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }
    
    private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }
    
        private void siftDownComparable(int k, E x) {
        Comparable key = (Comparable)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

取出０號元素（即優先級最大的元素），然后從０號的左孩子依次向上填補直至最后的元素小于當前左孩子則填補。

Deque繼承于queue，區別在于Deque是一個雙端隊列，兩頭均可當作隊列頭或隊列尾。

比較有代表性的雙端隊列實現為ArrayDeque，基于數組實現的雙端循環隊列,雖然使用對象模擬C語言前驅后繼指針的方式實現雙端循環隊列更為直觀，但是在不需要隨機增刪節點情況下在java使用數組實現比模擬鏈表開銷更小，下面直接看源碼：

    /**
     * The array in which the elements of the deque are stored.
     * The capacity of the deque is the length of this array, which is
     * always a power of two. The array is never allowed to become
     * full, except transiently within an addX method where it is
     * resized (see doubleCapacity) immediately upon becoming full,
     * thus avoiding head and tail wrapping around to equal each
     * other.  We also guarantee that all array cells not holding
     * deque elements are always null.
     */
    transient Object[] elements; // non-private to simplify nested class access

    /**
     * The index of the element at the head of the deque (which is the
     * element that would be removed by remove() or pop()); or an
     * arbitrary number equal to tail if the deque is empty.
     */
    transient int head;

    /**
     * The index at which the next element would be added to the tail
     * of the deque (via addLast(E), add(E), or push(E)).
     */
    transient int tail;

我們看到有兩個int字段，從名字上看也能判斷到是頭尾指針（并不是說它是真的指針，就是那個效果相當于指針），方法源碼不贅述，循環的原理就是移動頭尾指針，而不需要說比如獲取0號元素后將后面元素依次向前移動，這種操作十分花費開銷，增加頭尾指針只需直接修改頭尾指針數值，因此整個數組雖然是線性的但是可以實現環形的效果。

依然先看看字段信息，這個PRESENT先不理，直接看不太知道是什么，先看這個map，看到這個map其實可以猜HashSet的底層是通過HashMap儲存的了：

    private transient HashMap map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

不過我們還沒開始看HashMap的源碼，所以可以先從注釋等方面簡單了解HashSet和HashMap的關系：

/**
 * This class implements the Set interface, backed by a hash table
 * (actually a HashMap instance).  It makes no guarantees as to the
 * iteration order of the set; in particular, it does not guarantee that the
 * order will remain constant over time.  This class permits the null
 * element.

...
**/

首先基于HashTable（實際上是HashMap），然后沒辦法保證Set的迭代順序，也沒辦法保證Set元素的順序不會因為時間而變化，同時允許空值null存入。接下來繼續往下看源碼，看看是怎么通過HashMap存元素的：

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

原來，是吧Set的元素當成HashMap的Key值存儲，而Value值則存入PRESENT這個常量對象，利用了Map的Key值不能重復的特性。至此，對HashSet源代碼的了解已經足夠，翻看下面基本都是對HashMap的調用。
而LinkedHashSet則繼承HashSet，然后調用HashSet的另一個構造器，以LinkedHashMap作為底層存儲容器：

    //輸入變量dummy只用作區分其他以initialCapacity和loadFactor作為輸入變量的構造函數
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

仍然通過注釋簡單了解LinkedHashSet：

/**
 * 
Hash table and linked list implementation of the Set interface,
 * with predictable iteration order.  This implementation differs from
 * HashSet in that it maintains a doubly-linked list running through
 * all of its entries.  This linked list defines the iteration ordering,
 * which is the order in which elements were inserted into the set
 * (insertion-order).  Note that insertion order is not affected
 * if an element is re-inserted into the set.  (An element e
 * is reinserted into a set s if s.add(e) is invoked when
 * s.contains(e) would return true immediately prior to
 * the invocation.)

通過HashTable（實際上是HashMap）和LinkedList實現Set接口，不同于HashSet的是LinkedHashSet通過維護一個雙向鏈表來保證元素的順序，其順序則是元素的插入順序。
而TreeSet則繼承NavigableSet再繼承與SortedSet，以TreeMap作為底層存儲容器，方法的實現同樣是調用TreeMap的方法：

/**
 * A {@link NavigableSet} implementation based on a {@link TreeMap}.
 * The elements are ordered using their {@linkplain Comparable natural
 * ordering}, or by a {@link Comparator} provided at set creation
 * time, depending on which constructor is used.
 *
 * 
This implementation provides guaranteed log(n) time cost for the basic
 * operations ({@code add}, {@code remove} and {@code contains}).
 *

TreeSet的元素會使用Comparator對元素大小進行排序，不過因此add和remove以及contains操作將會花費log(n)的時間復雜度（比HashSet多）。

先來提取一下注釋中的重點：

 * 
An instance of HashMap has two parameters that affect its
 * performance: initial capacity and load factor.  The
 * capacity is the number of buckets in the hash table, and the initial
 * capacity is simply the capacity at the time the hash table is created.  The
 * load factor is a measure of how full the hash table is allowed to
 * get before its capacity is automatically increased.  When the number of
 * entries in the hash table exceeds the product of the load factor and the
 * current capacity, the hash table is rehashed (that is, internal data
 * structures are rebuilt) so that the hash table has approximately twice the
 * number of buckets.

這里說有兩個參數是會影響HashMap的性能的，一個是initial capacity（初始容量），另一個是load factor（暫且稱作負荷系數），initial capacity就創建HashMap時Hash表的大小，load factor則是用來觸發Hash表自動擴容的標準衡量值。當HashMap中的實體數量超過了load factor和當前容量的乘積，HashMap將會觸發rehash，調整一下整個哈希表的結構，一般來說調整一次會將Hash表容量編程原來的兩倍。

     * This map usually acts as a binned (bucketed) hash table, but
     * when bins get too large, they are transformed into bins of
     * TreeNodes, each structured similarly to those in
     * java.util.TreeMap. Most methods try to use normal bins, but
     * relay to TreeNode methods when applicable (simply by checking
     * instanceof a node).  Bins of TreeNodes may be traversed and
     * used like any others, but additionally support faster lookup
     * when overpopulated. However, since the vast majority of bins in
     * normal use are not overpopulated, checking for existence of
     * tree bins may be delayed in the course of table methods.
     *

注釋把hash表的每一個格比喻成箱子，箱子里面存儲的元素（有時為hash沖突的多個元素）有兩種結構，這兩種情況對應該箱子有兩種稱呼，一是normal bins，這是一般情況，箱子中元素較少的時候，以鏈表形式連接各個元素，第二種是tree bins，此時為因為hash相同放到同一個箱子中元素較多時，這些元素將轉化成一種叫紅黑樹的結構儲存。

有了上述基本認識后，正式看源碼。
首先，當然先看字段信息：

    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node[] table;

table，顯然是底層存儲map元素的Hash表，是個Node數組，每一項就是注釋中所說的bin

上面說了箱子里的元素有兩種結構，一開始為Node構成的鏈表，當箱子內元素數量達到超過8個則轉化成TreeNode構成的紅黑樹

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;
       
        
    ...


    /**
     * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
     * extends Node) so can be used as extension of either regular or
     * linked node.
     */
    static final class TreeNode extends LinkedHashMap.Entry {
        TreeNode parent;  // red-black tree links
        TreeNode left;
        TreeNode right;
        TreeNode prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node next) {
            super(hash, key, val, next);
        }
        
        
    ...

有兩種情況箱子結構會從紅黑樹變回鏈表：
一是在紅黑樹中刪除節點后，該紅黑樹節點太少時。下面截取注釋片段和代碼片段，具體看HashMap.TreeNode的removeTreeNode方法。

                    ...If the current tree appears to have too few nodes,
         * the bin is converted back to a plain bin. (The test triggers
         * somewhere between 2 and 6 nodes, depending on tree structure).
         */
         final void removeTreeNode(HashMap map, Node[] tab,
                                  boolean movable) {
             ...
             if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
                tab[index] = first.untreeify(map);  // too small
                return;
             }

二是擴容后，元素重新分配位置時，本來在紅黑樹中的節點也會因為擴容而一部分節點分開，在進行分開操作時同時檢查分開后的兩部分元素數量是否小于等于6，是則構造鏈表，不是則重新構造紅黑樹或保持原本紅黑樹結構：

        /**
         * Splits nodes in a tree bin into lower and upper tree bins,
         * or untreeifies if now too small. Called only from resize;
         * see above discussion about split bits and indices.
         
         ...
         */ 
         final void split(HashMap map, Node[] tab, int index, int bit) {
             ...
             //通過hash計算后在低位置的元素
             if (loHead != null) {
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            //通過hash計算后在高位置的元素
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set> entrySet;

entrySet，用于儲存所有元素的Set集合，同樣的還有繼承自AbstractMap的keySet和values，它們是比較特殊的Set，不是想象的那樣重新存儲一遍HashMap的所有元素，它們均不存儲元素，只是在使用時通過調用HashMap的迭代器獲取元素。

    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient int modCount;

    /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;

threshold，是一個閾值，達到這個閾值進行rehash操作（調用resize()），然后threshold增大，threshold的值在HashMap實例化后為大于initialCapacity的第一個2次冪數，之后的增大的值為原本的兩倍。
下面重點解析插入元素的方法：

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        //table空，則進行第一次擴容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //通過hash計算的位置無占用則直接將引用指向一個新的Node
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //通過hash計算的位置有占用
        else {
            Node e; K k;
            //占用的元素key值相同，則先增加e對占用元素的引用，后續進行替換value值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //占用的元素為TreeNode，也就是該位置下是一顆紅黑樹，則調用TreeNode的putTreeVal方法插入節點
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            //占用的元素為普通的Node，遍歷到鏈表尾添加節點    
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //在鏈表中添加節點后箱子元素數量達到8則轉換成紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //鏈表中的元素與插入元素key值相同，跳出循環后續替換value值
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //key值相同時統一在此替換value值，并直接返回，因為元素數量無變化
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //元素數量大于閾值則進行擴容操作
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

配合流程圖更好理解：

理解了插入流程后，關于刪除和查找其實已經不難，唯一的重點則是關于紅黑樹的內容。

紅黑樹是一個平衡的二叉樹，但不是一個完美的平衡二叉樹。雖然我們希望一個所有查找都保持在O(lgn)的時間復雜度，但是這樣在動態插入中保持樹的完美平衡代價太高，所以，我們稍微放松一下限制，希望找到一個能在對數時間內完成查找的數據結構。這個時候，紅黑樹站了出來。
首先，一顆紅黑樹需要滿足以下五條性質：
性質一：節點是紅色或者是黑色；
在樹里面的節點不是紅色的就是黑色的，沒有其他顏色，要不怎么叫紅黑樹呢，是吧；
性質二：根節點是黑色；
根節點總是黑色的。它不能為紅；
性質三：每個葉節點（NIL或空節點）是黑色；
性質四：每個紅色節點的兩個子節點都是黑色的（也就是說不存在兩個連續的紅色節點）；
就是連續的兩個節點不能是連續的紅色，連續的兩個節點的意思就是父節點與子節點不能是連續的紅色；
性質五：從任一節點到其沒個葉節點的所有路徑都包含相同數目的黑色節點。

為了保證所有的插入刪除操作都使紅黑樹保持這五個性質，需先知道平衡二叉樹的兩個基本操作：
左旋

右旋

基本介紹完了，下面是紅黑樹插入和刪除操作的介紹：

因為要滿足紅黑樹的五條性質，如果我們插入的是黑色節點，那就違反了性質五，需要進行大規模調整，如果我們插入的是紅色節點，那就只有在要插入節點的父節點也是紅色的時候違反性質四或者是當插入的節點是根節點時，違反性質二，所以，我們把要插入的節點的顏色變成紅色。
插入節點的父節點為黑色或插入節點為根節點時，直接插入：
1.插入的節點是根節點，直接插入黑色根節點
2.插入的節點的父節點是黑色節點，直接插入紅色節點
插入節點的父節點為紅色，無法直接插入，分三種情況考慮：（以下例子均假設插入節點的父節點是祖父節點的左支，右支的情況為鏡像）

下面我們再講講刪除的操作：

首先你要了解普通二叉樹的刪除操作：
1.如果刪除的是葉節點，可以直接刪除；
2.如果被刪除的元素有一個子節點，可以將子節點直接移到被刪除元素的位置；
3.如果有兩個子節點，這時候就可以把被刪除元素的右支的最小節點（被刪除元素右支的最左邊的節點）和被刪除元素互換，我們把被刪除元素右支的最左邊的節點稱之為后繼節點（后繼元素），然后在根據情況1或者情況2進行操作。如圖：

將被刪除元素與其右支的最小元素互換，變成如下圖所示：

然后再將被刪除元素刪除：

下面所稱的被刪除元素，皆是指已經互換之后的被刪除元素。
加入顏色之后，被刪除元素和后繼元素互換只是值得互換，并不互換顏色，這個要注意。
下面開始講一下紅黑樹刪除的規則：
1.當被刪除元素為紅時，對五條性質沒有什么影響，直接刪除。
2.當被刪除元素為黑且為根節點時，直接刪除。
3.當被刪除元素為黑，且有一個右子節點為紅時，將右子節點涂黑放到被刪除元素的位置。如圖：
由

變成

4.當被刪除元素為黑，且兄弟節點為黑，兄弟節點兩個孩子也為黑，父節點為紅，此時，交換兄弟節點與父節點的顏色；NIL元素是指每個葉節點都有兩個空的，顏色為黑的NIL元素，需要他的時候就可以把它看成兩個黑元素，不需要的時候可以忽視他。 如圖：
由

變成：

5.當被刪除元素為黑、并且為父節點的左支，且兄弟顏色為黑，兄弟的右支為紅色，這個時候需要交換兄弟與父親的顏色，并把父親涂黑、兄弟的右支涂黑，并以父節點為中心左轉。如圖：
由：

變成：

6.當被刪除元素為黑、并且為父節點的左支，且兄弟顏色為黑，兄弟的左支為紅色，這個時候需要先把兄弟與兄弟的左子節點顏色互換，進行右轉，然后就變成了規則5一樣了，在按照規則5進行旋轉。如圖：
由

先兄弟與兄弟的左子節點顏色互換，進行右轉，變成：

然后在按照規則5進行旋轉，變成：

7.當被刪除元素為黑且為父元素的右支時，跟情況5.情況6 互為鏡像。
8.被刪除元素為黑且兄弟節點為黑，兄弟節點的孩子為黑，父親為黑，這個時候需要將兄弟節點變為紅，再把父親看做那個被刪除的元素（只是看做，實際上不刪除），看看父親符和哪一條刪除規則，進行處理變化如圖：
由：

變成：

8.當被刪除的元素為黑，且為父元素的左支，兄弟節點為紅色的時候，需要交換兄弟節點與父親結點的顏色，以父親結點進行左旋，就變成了情況4，在按照情況四進行操作即可，變化如下：
由：

交換兄弟節點與父親結點的顏色，以父親結點進行左旋 變成：

在按照情況四進行操作，變成：

好了，刪除的步驟也講完，沒有講到的一點就是，在添加刪除的時候，時刻要記得更改根元素的顏色為黑。

TreeMap繼承自NavigableMap和SortedMap，在Map的基礎上增加了獲取特定范圍的元素（如大于某個值的所有元素，最小的元素），同時因為其底層是紅黑樹結構，其查找、插入和刪除的操作都能保證在O(n)的時間復雜度內完成，最優情況下時間復雜度為O(logN)

 * 
This implementation provides guaranteed log(n) time cost for the
 * {@code containsKey}, {@code get}, {@code put} and {@code remove}
 * operations.  Algorithms are adaptations of those in Cormen, Leiserson, and
 * Rivest"s Introduction to Algorithms.

繼續看字段信息：

    /**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     *
     * @serial
     */
    private final Comparator comparator;

    private transient Entry root;

    /**
     * The number of entries in the tree
     */
    private transient int size = 0;

    /**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;

其中有兩個字段是最重要的，一個是comparator，因為TreeMap是一個有序的Map，所以comparator是非常的重要；二是root，從名字來看就知道這是紅黑樹的根指針，整個TreeMap就是一顆紅黑樹。基本的紅黑樹也講解了，在此不做贅述。

LinkedHashMap其實就是在HashMap的基礎上增加鏈表用以記錄元素插入順序，那么它是怎么維護這個鏈表的呢？從源碼中我們首先我們發現，LinkedHashMap的實體類繼承了HashMap的實體類并在此基礎上增加前后指針：

    static class Entry extends HashMap.Node {
        Entry before, after;
        Entry(int hash, K key, V value, Node next) {
            super(hash, key, value, next);
        }
    }

LinkedHashMap的普通元素（區別于樹元素）和HashMap直接使用的是不相同的，但是從LinkedHashMap的構造方法來看，LinkedHashMap又是直接構造HashMap實例來存儲的，而且并沒有修改插入的方法，也就是說，插入元素使用的是HashMap的put方法，那這兩者是怎么區別出來的呢？我們回頭看看HashMap的put方法：

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            //1
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //2
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
                
        ...

有兩個需要注意的地方，在上面代碼用注釋標記出來了，第一個是插入普通節點（區別于樹節點）的地方，我們看到，該方法在創建新節點時并不是直接使用構造方法構造node，而是使用了newNode方法：

    // Create a regular (non-tree) node
    Node newNode(int hash, K key, V value, Node next) {
        return new Node<>(hash, key, value, next);
    }

而LinkedHashMap同樣有這個方法，也就是說，LinkedHashMap是通過覆蓋了newNode方法實現創建帶有前驅后繼指針的節點的，而上面插入方法中第二個需要注意的地方就是插入樹節點的地方，這個其實也是一樣的，在putTreeVal中同樣調用newTreeNode方法：

    //HashMap
    Node newNode(int hash, K key, V value, Node next) {
        return new Node<>(hash, key, value, next);
    }
    
    TreeNode newTreeNode(int h