集合相關(guān)

List跟Set的區(qū)別
兩個(gè)接口都繼承Collection，區(qū)別list有序且可以添加多個(gè)null元素供嚎，也可以添加重復(fù)元素甸箱；set不能添加重復(fù)元素伶贰，最多允許一個(gè)null，若要有序需實(shí)現(xiàn)comprable接口娃肿；

list 子類(lèi)：ArrayList咕缎，LinkedList，Vector

ArrayList料扰，源碼比較簡(jiǎn)單凭豪，實(shí)際內(nèi)部是Object[]數(shù)組，可以傳入大小记罚，默認(rèn)是10墅诡，最大是Integer最大值，最大特點(diǎn)是增容桐智，在add的時(shí)候判斷容器大小是否需要擴(kuò)容

/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    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;
    }

還有一個(gè)特殊的部分是Iterator類(lèi)

/**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        // The "limit" of this iterator. This is the size of the list at the time the
        // iterator was created. Adding & removing elements will invalidate the iteration
        // anyway (and cause next() to throw) so saving this value will guarantee that the
        // value of hasNext() remains stable and won't flap between true and false when elements
        // are added and removed from the list.
        protected int limit = ArrayList.this.size;

        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor < limit;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            int i = cursor;
            if (i >= limit)
                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();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

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

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;

            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    /**
     * An optimized version of AbstractList.ListItr
     */
    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

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

        @SuppressWarnings("unchecked")
        public E previous() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
                limit++;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

Vector跟ArrayList同樣繼承AbstractList末早，方法都一樣只是在跟數(shù)組操作的相關(guān)方法都加上了synchronized關(guān)鍵字，由此可知他是線程安全的ArrayList说庭；

LinkedList然磷，通過(guò)查看LinkedList源碼我們很容易發(fā)現(xiàn)，他同樣繼承了AbstractList刊驴，但是多實(shí)現(xiàn)了Deque（雙向隊(duì)列）姿搜，進(jìn)一步查看顧名思義內(nèi)部使用了雙向列表的數(shù)據(jù)結(jié)構(gòu)。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

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

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

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

看node代碼

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

當(dāng)然既然是鏈表就不能向ArrayList的Iterator那樣通過(guò)移動(dòng)cursor了捆憎，下面是它的Iterator的實(shí)現(xiàn)舅柜，里面也是鏈表。

private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned = null;
        private Node<E> 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<E> 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++;
        }

        @Override
        public void forEachRemaining(Consumer<? super E> 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();
        }
    }

到此躲惰，list分析完畢致份，ArrayList內(nèi)部使用數(shù)組存儲(chǔ)，LinkedList是雙向鏈表础拨，ArrayList查詢(xún)效率高氮块，LinkedList插入，刪除效率高诡宗；

Set的實(shí)現(xiàn)子類(lèi)HashSet滔蝉、LinkedHashSet 以及 TreeSet
對(duì)比list的接口發(fā)現(xiàn)主要有以下的方法不同,從中可以發(fā)現(xiàn)主要是跟index的相關(guān)的也就是順序相關(guān)的操作，由此得知set的基因就跟序列無(wú)關(guān)塔沃，即無(wú)序

// Positional Access Operations

    /**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException if the index is out of range
     *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    E get(int index);

    /**
     * Replaces the element at the specified position in this list with the
     * specified element (optional operation).
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws UnsupportedOperationException if the <tt>set</tt> operation
     *         is not supported by this list
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this list
     * @throws NullPointerException if the specified element is null and
     *         this list does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this list
     * @throws IndexOutOfBoundsException if the index is out of range
     *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    E set(int index, E element);

    /**
     * Inserts the specified element at the specified position in this list
     * (optional operation).  Shifts the element currently at that position
     * (if any) and any subsequent elements to the right (adds one to their
     * indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws UnsupportedOperationException if the <tt>add</tt> operation
     *         is not supported by this list
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this list
     * @throws NullPointerException if the specified element is null and
     *         this list does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this list
     * @throws IndexOutOfBoundsException if the index is out of range
     *         (<tt>index &lt; 0 || index &gt; size()</tt>)
     */
    void add(int index, E element);

    /**
     * Removes the element at the specified position in this list (optional
     * operation).  Shifts any subsequent elements to the left (subtracts one
     * from their indices).  Returns the element that was removed from the
     * list.
     *
     * @param index the index of the element to be removed
     * @return the element previously at the specified position
     * @throws UnsupportedOperationException if the <tt>remove</tt> operation
     *         is not supported by this list
     * @throws IndexOutOfBoundsException if the index is out of range
     *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    E remove(int index);


    // Search Operations

    /**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for
     * @return the index of the first occurrence of the specified element in
     *         this list, or -1 if this list does not contain the element
     * @throws ClassCastException if the type of the specified element
     *         is incompatible with this list
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if the specified element is null and this
     *         list does not permit null elements
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     */
    int indexOf(Object o);

    /**
     * Returns the index of the last occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the highest index <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for
     * @return the index of the last occurrence of the specified element in
     *         this list, or -1 if this list does not contain the element
     * @throws ClassCastException if the type of the specified element
     *         is incompatible with this list
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if the specified element is null and this
     *         list does not permit null elements
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     */
    int lastIndexOf(Object o);

HashSet繼承AbstractSet蝠引，打開(kāi)源碼，一驚，竟然是基于HashMap實(shí)現(xiàn)的立肘，源碼完全沒(méi)什么內(nèi)容边坤，等等，hashmap是鍵值對(duì)啊谅年，看代碼：

private transient HashMap<E,Object> map;

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

 /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

    /**
     * Constructs a new set containing the elements in the specified
     * collection.  The <tt>HashMap</tt> is created with default load factor
     * (0.75) and an initial capacity sufficient to contain the elements in
     * the specified collection.
     *
     * @param c the collection whose elements are to be placed into this set
     * @throws NullPointerException if the specified collection is null
     */
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * the specified initial capacity and the specified load factor.
     *
     * @param      initialCapacity   the initial capacity of the hash map
     * @param      loadFactor        the load factor of the hash map
     * @throws     IllegalArgumentException if the initial capacity is less
     *             than zero, or if the load factor is nonpositive
     */
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, 

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

add操作實(shí)際就是放了一個(gè)空Object當(dāng)value茧痒，這有點(diǎn)浪費(fèi)內(nèi)存吧，存疑融蹂，等分析HashMap再來(lái)分析這塊旺订；

LinkedHashSet繼承HashSet方法上沒(méi)有差異只是復(fù)寫(xiě)了構(gòu)造方法，內(nèi)部實(shí)現(xiàn)是LinkedHashMap

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

TreeSet內(nèi)部實(shí)現(xiàn)是TreeMap

接下來(lái)看一下Map
Map是一個(gè)接口里面Entry接口來(lái)存儲(chǔ)鍵值對(duì)
Map的子類(lèi)主要包含HashMap,TreeMap,HashTable,LinkedHashMap幾個(gè)超燃，下面分別從源碼來(lái)分析一下幾個(gè)子類(lèi)区拳；

HashMap，了解hashMap之前我們先帶著幾點(diǎn)疑問(wèn)意乓，1樱调，HashSet是基于HashMap他們之前是什么關(guān)系？2届良，HashMap是怎么快速根據(jù)key拿到值的笆凌？3，HashMap內(nèi)部的數(shù)據(jù)結(jié)構(gòu)是什么樣的士葫？帶著思考去做事情往往能獲取更高的效率乞而。

查詢(xún)HashMap源碼，首先尋找數(shù)據(jù)結(jié)構(gòu)：發(fā)現(xiàn)了HashMapEntry<?,?>結(jié)構(gòu)的數(shù)組慢显，接著查看HashMapEntry的實(shí)現(xiàn),HashMapEntry實(shí)現(xiàn)了 Map.Entry的接口爪模，內(nèi)部是個(gè)單向鏈表，一個(gè)單向列表的數(shù)組荚藻？輪廓已經(jīng)有了屋灌，繼續(xù)看

 /**
     * An empty table instance to share when the table is not inflated.
     */
    static final HashMapEntry<?,?>[] EMPTY_TABLE = {};

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;

 /** @hide */  // Android added.
    static class HashMapEntry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        HashMapEntry<K,V> next;
        int hash;

        /**
         * Creates new entry.
         */
        HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }

        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {
        }
    }

瞅瞅構(gòu)造方法，沒(méi)有發(fā)現(xiàn)什么數(shù)據(jù)結(jié)構(gòu)初始化相關(guān)应狱。

 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        } else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
            initialCapacity = DEFAULT_INITIAL_CAPACITY;
        }

        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // Android-Note: We always use the default load factor of 0.75f.

        // This might appear wrong but it's just awkward design. We always call
        // inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
        // to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
        // the load factor).
        threshold = initialCapacity;
        init();
    }

看put方法共郭， inflateTable(threshold);threshold這個(gè)值在構(gòu)造方法里見(jiàn)過(guò)，果然這里就是初始化table的地方侦香，一部一部分析，感覺(jué)有意思了

 public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
        int i = indexFor(hash, table.length);
        for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

  
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);

        // Android-changed: Replace usage of Math.min() here because this method is
        // called from the <clinit> of runtime, at which point the native libraries
        // needed by Float.* might not be loaded.
        float thresholdFloat = capacity * loadFactor;
        if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
            thresholdFloat = MAXIMUM_CAPACITY + 1;
        }

        threshold = (int) thresholdFloat;
        table = new HashMapEntry[capacity];
    }
    private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        int rounded = number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (rounded = Integer.highestOneBit(number)) != 0
                    ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
                    : 1;

        return rounded;
    }

static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

初始化時(shí)候傳過(guò)來(lái)的容量這時(shí)候被更改了 int capacity = roundUpToPowerOf2(toSize);實(shí)際把toSize變?yōu)?的乘冪纽疟，table = new HashMapEntry[capacity];table初始成了2的乘冪的數(shù)組罐韩，回到put方法，if (key == null) return putForNullKey(value);發(fā)現(xiàn)key可以為空污朽；int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);這句關(guān)鍵了HashMap散吵，hash來(lái)了，這里通過(guò)key生成一個(gè)hash值，int i = indexFor(hash, table.length);
length 為2的乘冪矾睦，length-1說(shuō)就是111111·····h & 11111晦款，就會(huì)消掉不同的值，通過(guò)這個(gè)方法可以得到key在table里面的一個(gè)索引枚冗，這里就有一個(gè)疑問(wèn)了缓溅，那不同的hash值& (length-1)后是會(huì)相同的，這應(yīng)該就是傳說(shuō)中的hash碰撞吧赁温，這也就明白了為什么數(shù)組中放的是鏈表了坛怪，如果出現(xiàn)了hash碰撞，值就可以像列表中添加了股囊，但是列表越來(lái)越長(zhǎng)袜匿，又怎么來(lái)保證get(key)的效率呢？先記錄一下問(wèn)題稚疹，慢慢解開(kāi)謎團(tuán)居灯；

接下來(lái)通過(guò)循環(huán)看索引下的鏈表中是否存在此hash的entry如果存在，更新entry值内狗，否則add entry

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

void resize(int newCapacity) {
        HashMapEntry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        HashMapEntry[] newTable = new HashMapEntry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
void transfer(HashMapEntry[] newTable) {
        int newCapacity = newTable.length;
        for (HashMapEntry<K,V> e : table) {
            while(null != e) {
                HashMapEntry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

resize(2 * table.length)擴(kuò)容怪嫌，擴(kuò)容就可以減小hash碰撞，從而提高效率其屏，問(wèn)題又來(lái)了喇勋，擴(kuò)容后h & (length-1)就會(huì)變了，key的hash還能正確找到位置嗎偎行？進(jìn)入
resize方法transfer(newTable);解決我的疑問(wèn)遍歷老的table川背，將所有的HashMapEntry元素重新indexFor放入新的table這樣就沒(méi)問(wèn)題了；至此我們解決了上述3的問(wèn)題和2的問(wèn)題indexFor拿到index可以高效的拿到HashMapEntry蛤袒，通過(guò)擴(kuò)容來(lái)減少hash碰撞熄云；關(guān)于上述問(wèn)題1肯定跟Iterator相關(guān)

public Set<K> keySet() {
        Set<K> ks = keySet;
        return (ks != null ? ks : (keySet = new KeySet()));
    }

    private final class KeySet extends AbstractSet<K> {
        public Iterator<K> iterator() {
            return newKeyIterator();
        }
        public int size() {
            return size;
        }
        public boolean contains(Object o) {
            return containsKey(o);
        }
        public boolean remove(Object o) {
            return HashMap.this.removeEntryForKey(o) != null;
        }
        public void clear() {
            HashMap.this.clear();
        }
        public final Spliterator<K> spliterator() {
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super K> action) {
            HashMapEntry<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (HashMapEntry<K,V> e = tab[i]; e != null; e = e.next) {
                        action.accept(e.key);
                        // Android-modified - this was outside of the loop, inconsistent with other
                        // collections
                        if (modCount != mc) {
                            throw new ConcurrentModificationException();
                        }
                    }
                }

            }
        }
    }


private abstract class HashIterator<E> implements Iterator<E> {
        HashMapEntry<K,V> next;        // next entry to return
        int expectedModCount;   // For fast-fail
        int index;              // current slot
        HashMapEntry<K,V> current;     // current entry

        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                HashMapEntry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

        final Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            HashMapEntry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();

            if ((next = e.next) == null) {
                HashMapEntry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
            current = e;
            return e;
        }

        public void remove() {
            if (current == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Object k = current.key;
            current = null;
            HashMap.this.removeEntryForKey(k);
            expectedModCount = modCount;
        }
    }

    private final class ValueIterator extends HashIterator<V> {
        public V next() {
            return nextEntry().getValue();
        }
    }

    private final class KeyIterator extends HashIterator<K> {
        public K next() {
            return nextEntry().getKey();
        }
    }

說(shuō)一下這段有意思的代碼：先取當(dāng)前鏈表中的節(jié)點(diǎn)，直到為空if ((next = e.next) == null) 妙真，接著 while (index < t.length && (next = t[index++]) == null)缴允，將next指向table的下一個(gè)元素，不得不感慨這樣的代碼看著太過(guò)清爽珍德；练般；；锈候；薄料；

if ((next = e.next) == null) {
                HashMapEntry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }

到此hashMap分析完成，解決了自己的疑問(wèn)泵琳；

LinkedHashSet繼承了HashMap,不同之處LinkedHashMapEntry記錄了插入順序

 private transient LinkedHashMapEntry<K,V> header;
 /**
     * LinkedHashMap entry.
     */
    private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        LinkedHashMapEntry<K,V> before, after;

        LinkedHashMapEntry(int hash, K key, V value, HashMapEntry<K,V> next) {
            super(hash, key, value, next);
        }

        /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        /**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }

    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        LinkedHashMapEntry<K,V> nextEntry    = header.after;
        LinkedHashMapEntry<K,V> lastReturned = null;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;

        public boolean hasNext() {
            return nextEntry != header;
        }

        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }

        Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            LinkedHashMapEntry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
    }

HashTable,因?yàn)橐呀?jīng)完成的看了HashMap摄职，所以再看跟他相關(guān)的類(lèi)的時(shí)候誊役，我就先看他們的不同點(diǎn)，首先他并沒(méi)有跟前面兩個(gè)map一樣繼承AbstractMap而是繼承了Dictionary（Dictionary是干嘛的谷市？）蛔垢，然后看到了一大堆synchronized修飾的方法，可知HashTable操作都是線程安全的迫悠；接著又發(fā)現(xiàn)一張陌生的面孔
public synchronized Enumeration<K> keys() {
return this.<K>getEnumeration(KEYS);
}
看樣子跟iterator有點(diǎn)相似芭羝帷？是不是呢及皂？等會(huì)看再接下來(lái)
if (value == null) {
throw new NullPointerException();
}
哎甫男，值為空的話會(huì)報(bào)空指針，這是個(gè)坑验烧，HashTable的值不能等于空板驳，以后使用的時(shí)候要判斷，那key呢碍拆？相關(guān)聯(lián)想若治，
int hash = hash(key);
private static int hash(Object k) {
return k.hashCode();
}
哎，這個(gè)跟之前的hash算法不同感混，key不能等于null的疑問(wèn)也能揭曉端幼，
int index = (hash & 0x7FFFFFFF) % tab.length;通過(guò)構(gòu)造方法我們也能看到初始化的initialCapacity也并不是2的乘冪了，通過(guò)上述 int index = (hash & 0x7FFFFFFF) % tab.length;HashTable是對(duì)數(shù)組長(zhǎng)度取模弧满，也是為了數(shù)組的均勻分布婆跑，減少碰撞，但是這個(gè)計(jì)算效率比h&length-1庭呜，那就差很多了滑进，但是為什么HashTable不采取效率更高的方式呢？

public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new HashtableEntry[initialCapacity];
        threshold = (initialCapacity <= MAX_ARRAY_SIZE + 1) ? initialCapacity : MAX_ARRAY_SIZE + 1;
    }

回頭看Enumeration,比Iterator少了remove的方法募谎，從他的實(shí)現(xiàn)類(lèi)也可以看出他同時(shí)實(shí)現(xiàn)了Iterator接口扶关，這就有點(diǎn)矛盾了，在remove方法中
public void remove() {
if (!iterator)
throw new UnsupportedOperationException();
可以看到boolean iterator;是來(lái)控制Enumeration還是Iterator的

public interface Enumeration<E> {
    /**
     * Tests if this enumeration contains more elements.
     *
     * @return  <code>true</code> if and only if this enumeration object
     *           contains at least one more element to provide;
     *          <code>false</code> otherwise.
     */
    boolean hasMoreElements();

    /**
     * Returns the next element of this enumeration if this enumeration
     * object has at least one more element to provide.
     *
     * @return     the next element of this enumeration.
     * @exception  NoSuchElementException  if no more elements exist.
     */
    E nextElement();
}

private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
        HashtableEntry[] table = Hashtable.this.table;
        int index = table.length;
        HashtableEntry<K,V> entry = null;
        HashtableEntry<K,V> lastReturned = null;
        int type;

        /**
         * Indicates whether this Enumerator is serving as an Iterator
         * or an Enumeration.  (true -> Iterator).
         */
        boolean iterator;

        /**
         * The modCount value that the iterator believes that the backing
         * Hashtable should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        protected int expectedModCount = modCount;

        Enumerator(int type, boolean iterator) {
            this.type = type;
            this.iterator = iterator;
        }

        public boolean hasMoreElements() {
            HashtableEntry<K,V> e = entry;
            int i = index;
            HashtableEntry[] t = table;
            /* Use locals for faster loop iteration */
            while (e == null && i > 0) {
                e = t[--i];
            }
            entry = e;
            index = i;
            return e != null;
        }

        public T nextElement() {
            HashtableEntry<K,V> et = entry;
            int i = index;
            HashtableEntry[] t = table;
            /* Use locals for faster loop iteration */
            while (et == null && i > 0) {
                et = t[--i];
            }
            entry = et;
            index = i;
            if (et != null) {
                HashtableEntry<K,V> e = lastReturned = entry;
                entry = e.next;
                return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
            }
            throw new NoSuchElementException("Hashtable Enumerator");
        }

        // Iterator methods
        public boolean hasNext() {
            return hasMoreElements();
        }

        public T next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            return nextElement();
        }

        public void remove() {
            if (!iterator)
                throw new UnsupportedOperationException();
            if (lastReturned == null)
                throw new IllegalStateException("Hashtable Enumerator");
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            synchronized(Hashtable.this) {
                HashtableEntry[] tab = Hashtable.this.table;
                int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;

                for (HashtableEntry<K,V> e = tab[index], prev = null; e != null;
                     prev = e, e = e.next) {
                    if (e == lastReturned) {
                        modCount++;
                        expectedModCount++;
                        if (prev == null)
                            tab[index] = e.next;
                        else
                            prev.next = e.next;
                        count--;
                        lastReturned = null;
                        return;
                    }
                }
                throw new ConcurrentModificationException();
            }
        }
    }

Dictionary沒(méi)看出有什么特殊的功能多了兩個(gè)方法数冬，說(shuō)白了是返回不能刪除的Iterator

abstract public Enumeration<K> keys();

    /**
     * Returns an enumeration of the values in this dictionary. The general
     * contract for the <tt>elements</tt> method is that an
     * <tt>Enumeration</tt> is returned that will generate all the elements
     * contained in entries in this dictionary.
     *
     * @return  an enumeration of the values in this dictionary.
     * @see     java.util.Dictionary#keys()
     * @see     java.util.Enumeration
     */
    abstract public Enumeration<V> elements();

TreeMap,同樣帶著思考节槐，HashMap跟TreeMap選擇的時(shí)候，無(wú)需排序選擇HashMap需要就選擇TreeMap拐纱，所以TreeMap是怎么實(shí)現(xiàn)排序的铜异？

查看源碼先找不同點(diǎn)，跟HashMap一樣繼承AbstractMap類(lèi)秸架，但是多實(shí)現(xiàn)了NavigableMap接口揍庄，可通行的Map是個(gè)什么鬼？迎面向我們走來(lái)的是
private final Comparator<? super K> comparator;
跟心想的一樣咕宿，排序嗎怎少得了Comparator币绩，當(dāng)然陌生苗孔SortedMap出現(xiàn)，
數(shù)據(jù)結(jié)構(gòu)這不想其他entry[]了府阀，而是出現(xiàn)了
private transient TreeMapEntry<K,V> root = null;
根節(jié)點(diǎn)缆镣，？试浙？董瞻？非hash怎么保證效率，往下看田巴，好吧钠糊，這貨跟上面的不是一回事，沒(méi)有什么一樣的壹哺，那就只能細(xì)細(xì)讀了
從SortedMap開(kāi)始吧抄伍，他只是一個(gè)接口繼承Map，多了一些head管宵，tail截珍，frist，last的字眼箩朴，NavigableMap多了一些比較的名詞在上面岗喉，可知這些都跟排序有著極大的關(guān)系；

public interface SortedMap<K,V> extends Map<K,V> {
  Comparator<? super K> comparator();
  SortedMap<K,V> headMap(K toKey);
  SortedMap<K,V> tailMap(K fromKey);
  ···
}

public interface NavigableMap<K,V> extends SortedMap<K,V> {
    ···
     K floorKey(K key);
     Map.Entry<K,V> ceilingEntry(K key);
    ····
}

查看結(jié)構(gòu)TreeMapEntry,left ,right ,parent代表它是一顆樹(shù)炸庞，color = BLACK钱床，紅黑二叉樹(shù)，treeMap內(nèi)部使用了紅黑樹(shù)來(lái)實(shí)現(xiàn)有序排列

private static final boolean RED   = false;
private static final boolean BLACK = true;
static final class TreeMapEntry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        TreeMapEntry<K,V> left = null;
        TreeMapEntry<K,V> right = null;
        TreeMapEntry<K,V> parent;
        boolean color = BLACK;

構(gòu)造方法沒(méi)什么特別埠居，添加構(gòu)造器了铝宵，添加map集合了這些州袒，應(yīng)該從查找，添加，刪除操作商玫，揭開(kāi)它的神秘面紗；
從getEntry可以看出key不能等于null
if (key == null)
throw new NullPointerException();
如果Comparator不等于空的皮官，就從根節(jié)點(diǎn)华坦，通過(guò)比較逐步找到節(jié)點(diǎn)，否則key就要實(shí)現(xiàn)Comparable接口金踪，然后也是通過(guò)比較找到浊洞；看到這里又有疑問(wèn)如果可以沒(méi)有實(shí)現(xiàn)Comparable接口，是不是在put的時(shí)候有什么特殊的處理胡岔？如果有多個(gè)key比較相同呢法希？可能還得往下看

public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
···
final TreeMapEntry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        TreeMapEntry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }
//構(gòu)造器不空
final TreeMapEntry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
            K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            TreeMapEntry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

接下來(lái)查看put方法,當(dāng)根節(jié)點(diǎn)為null，比較器不為null的時(shí)候key可以為null靶瘸，否則key不等于null苫亦，解決上述key不實(shí)現(xiàn)comparable的疑問(wèn) (!(key instanceof Comparable)是會(huì)報(bào)異常的毛肋；

else if (!(key instanceof Comparable)) {
throw new ClassCastException(
"Cannot cast" + key.getClass().getName() + " to Comparable.");
}
如果找到相同節(jié)點(diǎn)只會(huì)更新value， t.setValue(value);所以不會(huì)有重復(fù)節(jié)點(diǎn)屋剑，key比較相同的润匙，可能會(huì)被替換，慎用唉匾；
下面的插入很簡(jiǎn)單就是比較大于右邊孕讳，小于左邊，直至插入合適的位置巍膘；那么疑問(wèn)來(lái)了厂财，有可能根節(jié)點(diǎn)一側(cè)的數(shù)據(jù)特別特別多，另外一側(cè)沒(méi)有數(shù)據(jù)峡懈，偏樹(shù)璃饱，這樣查詢(xún)效率就會(huì)低了；接著看肪康，肯定有讓樹(shù)平衡的算法帜平，下面有個(gè)方法fixAfterInsertion，插入后修理梅鹦，那應(yīng)該就是他了裆甩，看了一下他的算法，然后用筆在紙上花了一下齐唆，就明白了他的算法嗤栓，之前看了紅黑二叉樹(shù)的算法，不是特別的理解箍邮，看了這個(gè)一下就通了茉帅；下面在系統(tǒng)的說(shuō)明一下：

public V put(K key, V value) {
        TreeMapEntry<K,V> t = root;
        if (t == null) {
           
            if (comparator != null) {
                if (key == null) {
                    comparator.compare(key, key);
                }
            } else {
                if (key == null) {
                    throw new NullPointerException("key == null");
                } else if (!(key instanceof Comparable)) {
                    throw new ClassCastException(
                            "Cannot cast" + key.getClass().getName() + " to Comparable.");
                }
            }

            root = new TreeMapEntry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        TreeMapEntry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }


 /** From CLR */
    private void fixAfterInsertion(TreeMapEntry<K,V> x) {
        x.color = RED;

        while (x != null && x != root && x.parent.color == RED) {
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                TreeMapEntry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

之前就通過(guò)各種途徑了解過(guò)紅黑二叉樹(shù)，因?yàn)闆](méi)有看實(shí)際的例子所以有些抽象锭弊，集合TreeMap一下就通了堪澎，以此記錄一下：
首先什么是紅黑二叉樹(shù)，有什么特點(diǎn)味滞？
1.根節(jié)點(diǎn)是黑色
2.葉子節(jié)點(diǎn)是黑色
3.每個(gè)節(jié)點(diǎn)只能是黑色或者紅色的一種
4.不可能出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)
5.從任何一個(gè)節(jié)點(diǎn)出發(fā)樱蛤，包含黑色節(jié)點(diǎn)的個(gè)數(shù)是一樣的
順序是left<parent<right，注意上述并沒(méi)有說(shuō)不可能存在兩個(gè)相同的黑色節(jié)點(diǎn)剑鞍，實(shí)際業(yè)火發(fā)生這種情況昨凡。
回到代碼
put方法顯示根據(jù)一系列比較算法將對(duì)應(yīng)的節(jié)點(diǎn)插入對(duì)應(yīng)的父親下，接著進(jìn)入fixAfterInsertion方法（這個(gè)就是紅黑樹(shù)保持平衡的關(guān)鍵所在）蚁署，首先將最后插入的節(jié)點(diǎn)顏色設(shè)置為紅便脊， while (x != null && x != root && x.parent.color == RED) 說(shuō)明根節(jié)點(diǎn)或者父節(jié)點(diǎn)為黑色的話，樹(shù)不需要平衡光戈，大家動(dòng)手畫(huà)畫(huà)還是畫(huà)畫(huà)吧比較清晰

來(lái)源于網(wǎng)絡(luò)

接著判斷父節(jié)點(diǎn)在爺爺節(jié)點(diǎn)的左側(cè)還是右側(cè)哪痰，如果是在左側(cè)判斷叔叔節(jié)點(diǎn)是不是紅色遂赠，如果是紅色把父親和叔叔的顏色設(shè)置成黑色，爺爺改成紅色晌杰，然后把當(dāng)前節(jié)點(diǎn)移到爺爺節(jié)點(diǎn)繼續(xù)遍歷解愤；如果叔叔節(jié)點(diǎn)是黑色，判斷當(dāng)前節(jié)點(diǎn)如果在右側(cè)乎莉，然后做一個(gè)左旋轉(zhuǎn)，將父設(shè)置成黑色奸笤，爺爺設(shè)成紅色對(duì)爺爺右旋惋啃。左旋右旋看圖片可能比較好，自己照著畫(huà)一下监右，就更清晰了

左旋

右旋

/** From CLR */
    private void rotateLeft(TreeMapEntry<K,V> p) {
        if (p != null) {
            TreeMapEntry<K,V> r = p.right;
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            r.parent = p.parent;
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
                p.parent.left = r;
            else
                p.parent.right = r;
            r.left = p;
            p.parent = r;
        }
    }

    /** From CLR */
    private void rotateRight(TreeMapEntry<K,V> p) {
        if (p != null) {
            TreeMapEntry<K,V> l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }

"刪除常規(guī)二叉查找樹(shù)中刪除節(jié)點(diǎn)的方法是一樣的"边灭。分3種情況：
① 被刪除節(jié)點(diǎn)沒(méi)有兒子，即為葉節(jié)點(diǎn)健盒。那么绒瘦，直接將該節(jié)點(diǎn)刪除就OK了。
② 被刪除節(jié)點(diǎn)只有一個(gè)兒子扣癣。那么惰帽，直接刪除該節(jié)點(diǎn)，并用該節(jié)點(diǎn)的唯一子節(jié)點(diǎn)頂替它的位置父虑。
③ 被刪除節(jié)點(diǎn)有兩個(gè)兒子该酗。那么，先找出它的后繼節(jié)點(diǎn)士嚎；然后把“它的后繼節(jié)點(diǎn)的內(nèi)容”復(fù)制給“該節(jié)點(diǎn)的內(nèi)容”呜魄；之后，刪除“它的后繼節(jié)點(diǎn)”莱衩。在這里爵嗅，后繼節(jié)點(diǎn)相當(dāng)于替身，在將后繼節(jié)點(diǎn)的內(nèi)容復(fù)制給"被刪除節(jié)點(diǎn)"之后笨蚁，再將后繼節(jié)點(diǎn)刪除睹晒。這樣就巧妙的將問(wèn)題轉(zhuǎn)換為"刪除后繼節(jié)點(diǎn)"的情況了，下面就考慮后繼節(jié)點(diǎn)括细。 在"被刪除節(jié)點(diǎn)"有兩個(gè)非空子節(jié)點(diǎn)的情況下册招，它的后繼節(jié)點(diǎn)不可能是雙子非空。既然"的后繼節(jié)點(diǎn)"不可能雙子都非空勒极，就意味著"該節(jié)點(diǎn)的后繼節(jié)點(diǎn)"要么沒(méi)有兒子是掰，要么只有一個(gè)兒子。若沒(méi)有兒子辱匿，則按"情況① "進(jìn)行處理键痛；若只有一個(gè)兒子炫彩，則按"情況② "進(jìn)行處理。
處理完后這個(gè)樹(shù)可能就不符合二叉樹(shù)的要求絮短，需要做一下修整修整算法

 /** From CLR */
    private void fixAfterDeletion(TreeMapEntry<K,V> x) {
        while (x != root && colorOf(x) == BLACK) {
            if (x == leftOf(parentOf(x))) {
                TreeMapEntry<K,V> sib = rightOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));
                }

                if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(rightOf(sib)) == BLACK) {
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x));
                    x = root;
                }
            } else { // symmetric
                TreeMapEntry<K,V> sib = leftOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));
                    sib = leftOf(parentOf(x));
                }

                if (colorOf(rightOf(sib)) == BLACK &&
                    colorOf(leftOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(x));
                    x = root;
                }
            }
        }

        setColor(x, BLACK);
    }

看著代碼都能看懂江兢，但是這樣的操作是怎么保持平衡的，畫(huà)一畫(huà)丁频，就會(huì)清晰
從網(wǎng)上截一些圖杉允，主要是跟兄弟節(jié)點(diǎn)，和侄子節(jié)點(diǎn)有關(guān)系

待刪除節(jié)點(diǎn)D的兄弟節(jié)點(diǎn)S為紅色席里，D沒(méi)了這個(gè)樹(shù)肯定就無(wú)法保持平衡叔磷。

調(diào)整做法是將父親節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的顏色互換，也就是p變成紅色奖磁，S變成黑色改基，然后將P樹(shù)進(jìn)行左旋型操作，結(jié)果如下圖咖为，D刪掉秕狰，同樣不平衡，還需要繼續(xù)向下操作躁染，等會(huì)說(shuō)明

情況2：兄弟節(jié)點(diǎn)為黑色，且遠(yuǎn)侄子節(jié)點(diǎn)為紅色吞彤。
D為左孩子對(duì)的情況诺舔，這時(shí)D的遠(yuǎn)侄子節(jié)點(diǎn)為S的右孩子

沒(méi)有上色的節(jié)點(diǎn)表示黑色紅色均可，注意如果SL為黑色备畦，則SL必為NULL節(jié)點(diǎn)低飒。

這個(gè)時(shí)候，如果我們刪除D懂盐，這樣經(jīng)過(guò)D的子節(jié)點(diǎn)（NULL節(jié)點(diǎn)）的路徑的黑色節(jié)點(diǎn)個(gè)數(shù)就會(huì)減1褥赊，但是我們看到S的孩子中有紅色的節(jié)點(diǎn)，如果我們能把這棵紅色的節(jié)點(diǎn)移動(dòng)到左側(cè)莉恼，并把它改成黑色拌喉，那么就滿足要求了，這也是為什么P的顏色無(wú)關(guān)俐银，因?yàn)檎{(diào)整過(guò)程只在P整棵子樹(shù)的內(nèi)部進(jìn)行尿背。

調(diào)整過(guò)程為，將P和S的顏色對(duì)調(diào)捶惜，然后對(duì)P樹(shù)進(jìn)行類(lèi)似AVL樹(shù)RR型的操作田藐，最后把SR節(jié)點(diǎn)變成黑色，并刪除D即可。

另外一邊也一樣

情況3：兄弟節(jié)點(diǎn)S為黑色汽久，遠(yuǎn)侄子節(jié)點(diǎn)為黑色鹤竭，近侄子節(jié)點(diǎn)為紅色
D為左孩子的情況，此時(shí)近侄子節(jié)點(diǎn)為S的左孩子

做法是景醇，將SL右旋臀稚，并將S和SL的顏色互換

情況4：父親節(jié)p為紅色，兄弟節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的兩個(gè)孩子（只能是NULL節(jié)點(diǎn)）都為黑色的情況三痰。

所以做法是蜓肆，將父親節(jié)點(diǎn)P改成黑色颜凯，將兄弟節(jié)點(diǎn)S改成紅色，然后刪除D即可仗扬。如下圖：

情況5：父親節(jié)點(diǎn)p症概，兄弟節(jié)點(diǎn)s和兄弟節(jié)點(diǎn)的兩個(gè)孩子（只能為NULL節(jié)點(diǎn)）都為黑色的情況