Map接口簡(jiǎn)要類圖

HashMap是基于哈希表的Map接口的實(shí)現(xiàn)仰猖。此實(shí)現(xiàn)提供所有可選的映射操作棵逊，并且允許使用null鍵和null值杏节。（除了是非同步的以及允許使用null之外扒披，HashMap和Hashtable大致相同兵睛。）此類不保證映射的順序肯骇，特別是它不保證該順序恒久不變。

為什么HashMap不保證映射的順序呢祖很？
因?yàn)樵贖ashMap中笛丙，當(dāng)桶中存儲(chǔ)的元素大于某個(gè)值時(shí)，就會(huì)將鏈表式存儲(chǔ)結(jié)構(gòu)轉(zhuǎn)換成紅黑樹存儲(chǔ)結(jié)構(gòu)假颇。后面會(huì)詳細(xì)介紹這一點(diǎn)胚鸯。

先學(xué)習(xí)一下兩個(gè)名詞：

• 初始容量：容量指的是哈希表中桶的數(shù)量，初始容量即哈希表在創(chuàng)建時(shí)的容量笨鸡。（如果在使用構(gòu)造函數(shù)創(chuàng)建對(duì)象時(shí)沒有指定容量的話蠢琳，默認(rèn)容量為DEFAULT_INITIAL_CAPACITY = 1 << 4啊终，即16）

• 加載因子：加載因子用來衡量哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時(shí)傲须，則對(duì)該哈希表進(jìn)行rehash操作（即重新構(gòu)建內(nèi)部數(shù)據(jù)結(jié)構(gòu)）蓝牲，從而哈希表將具有兩倍的桶數(shù)。

當(dāng)加載因子過高雖然可以減少空間開銷泰讽，但是會(huì)增加查詢成本例衍。所以默認(rèn)加載因子為0.75，為了在時(shí)間和空間成本上尋找一種折衷已卸。

對(duì)HashMap進(jìn)行簡(jiǎn)單地概括

• HashMap是對(duì)Map最簡(jiǎn)單的實(shí)現(xiàn)

• HashMap中的元素按照hash值分布在不同的桶(bin)中佛玄。如果散列特性較好，那么元素分布會(huì)比較均勻累澡。
• 單個(gè)桶的尺寸過大時(shí)梦抢，桶的數(shù)據(jù)結(jié)構(gòu)會(huì)由鏈?zhǔn)睫D(zhuǎn)換成一個(gè)紅黑樹
  ，以保證對(duì)其操作的時(shí)間復(fù)雜度為O（logN）
• key類型推薦實(shí)現(xiàn)Comparable愧哟，以提高效率
• KeySet奥吩、Values、EntrySet三個(gè)視圖集合只支持update/remove操作蕊梧，不支持add
• 迭代子利用modCount屬性來實(shí)現(xiàn)樂觀鎖霞赫，來如發(fā)生競(jìng)態(tài)的寫操作，則迭代子將直接失效（fast-fail）
• 代碼用了很多賦值表達(dá)式來精簡(jiǎn)代碼量肥矢，但是略影響可讀性

下面開始探究HashMap的源碼（主要的入口方法實(shí)現(xiàn)）

/** 
 * <pre> 
 *  以哈希表方式實(shí)現(xiàn)的Map接口端衰，允許key和value為null 
 *  （除非線程安全及允許null值外，HashMap基本與Hashtable等價(jià)） 
 *   
 *  本類不保證元素的順序甘改，特別地旅东，順序也可能隨時(shí)間改變 
 *   
 *  在散列特性較好（元素基本均勻分布于bucket）時(shí)，本類get和put操作均為O(1)量級(jí) 
 *  遍歷整個(gè)map的時(shí)間正比于：HashMap的容量（capacity）+元素總數(shù)（注意不只是元素?cái)?shù)） 
 *  因此最好不要把初始容量設(shè)置過高或負(fù)載因子（load factor）設(shè)置過低 
 *   
 *  容量指HashMap中桶的個(gè)數(shù)十艾，負(fù)載因子指HashMap填充到多大比例時(shí)允許自動(dòng)擴(kuò)容 
 *  當(dāng)size>load factor*capacity時(shí), 哈希表將重組（rehashed）玉锌，其內(nèi)部結(jié)構(gòu)會(huì)發(fā)生改變。rehash以后桶的數(shù)量將大致翻倍 
 *  根據(jù)經(jīng)驗(yàn)疟羹，負(fù)載因子=0.75（默認(rèn)值）時(shí)時(shí)空效率達(dá)到較好的平衡值 
 *  設(shè)置初始容量時(shí)主守，最好綜合考慮元素?cái)?shù)的估計(jì)值和負(fù)載因子，從而減少rehash的次數(shù) 
 *   
 *  注意如果很多key的hashCode相同必然會(huì)降低HashMap的速度 
 *  為改善這點(diǎn)榄融，當(dāng)key實(shí)現(xiàn){@link Comparable}時(shí)参淫，本類會(huì)利用Comparable的順序來處理hashCode相同 
 *   
 *  本類不是線程同步的，如果多線程訪問HashMap愧杯，且至少有一個(gè)線程進(jìn)行了結(jié)構(gòu)更改涎才，那么這個(gè)需要在外層synchronize  
 *  （結(jié)構(gòu)更改指增刪元素，不包含更新已有key的value值） 
 *  使用Collections.synchronizedMap(new HashMap(...)是另一種同步方式 
 *  
 * 本類返回的所有迭代子都是fail-fast的 
 * 即迭代子生成后如果發(fā)生任何結(jié)構(gòu)更改（迭代子自身的remove方法除外），迭代子都會(huì)拋出{@link ConcurrentModificationException} 
 * 注意fail-fast特征并不能嚴(yán)格保證耍铜，而只是盡可能實(shí)現(xiàn)（有可能漏拋） 
 * 因此不能利用是否拋ConcurrentModificationException來保證程序的正確性邑闺，這個(gè)異常的作用是輔助發(fā)現(xiàn)bug 
 *  
 * @param <K> the type of keys maintained by this map 
 * @param <V> the type of mapped values 
 *  
 * @author Doug Lea,Josh Bloch,Arthur van Hoff,Neal Gafter 
 * @see Object#hashCode(),Collection,Map,TreeMap,Hashtable 
 * @since 1.2 
 */  
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {  
  
    /** 
     * 實(shí)現(xiàn)說明 
     *  
     * <pre> 
     * 本類通常是由桶組成的哈希表，然而當(dāng)桶的尺寸過大時(shí)棕兼，會(huì)將節(jié)點(diǎn)重構(gòu)為TreeNode（每個(gè)節(jié)點(diǎn)類似java.util.TreeMap） 
     * 大部分方法實(shí)現(xiàn)會(huì)判斷節(jié)點(diǎn)的instanceof陡舅，如果是TreeNode，則會(huì)采取不同的實(shí)現(xiàn)方式 
     * TreeNode元素支持普通元素的所有操作（對(duì)外透明）伴挚，但提供更快的查詢速度 
     *  
     * 包含TreeNode的桶首先按hashCode排序靶衍，在tie時(shí)如果實(shí)現(xiàn)了Comparable，則會(huì)根據(jù)Comparable決定順序 
     * （這里通過反射來判斷茎芋，參見comparableClassFor方法） 
     * TreeNode機(jī)制使得在散列特性不好的情況下颅眶，也能保證最差O(log n)的時(shí)間性能 
     *  
     * 由于TreeNode的尺寸是常規(guī)節(jié)點(diǎn)大約2倍，因此僅當(dāng)桶的尺寸大于TREEIFY_THRESHOLD時(shí)才會(huì)使用TreeNode 
     * 如果TreeNode的尺寸減小到一定程度（由于remove或resize）田弥，還會(huì)重新變回普通節(jié)點(diǎn) 
     * 如果散列值的隨機(jī)性較好涛酗，則桶的尺寸與桶數(shù)大致服從Poisson分布，因此基本不會(huì)用到TreeNode 
     * (http://en.wikipedia.org/wiki/Poisson_distribution) 
     *  
     * 一個(gè)TreeNode桶的根節(jié)點(diǎn)通常是第一個(gè)節(jié)點(diǎn)偷厦，但有些時(shí)候（目前只有Iterator.remove）也會(huì)是其他元素 
     * but can be recovered following parent links  (method TreeNode.root()). 
     *  
     * 所有具體實(shí)現(xiàn)的內(nèi)部方法都包含hashcode參數(shù)（通常在調(diào)用public方法是生成）商叹，用以在互相調(diào)用時(shí)不必重新計(jì)算hashCode 
     * 大部分方法包含tab參數(shù)，其值大部分情況下就是當(dāng)前的哈希表自身沪哺，但在resizing或converting時(shí)可能不同 
     *  
     * 當(dāng)桶列表發(fā)生建樹（treeify）沈自、分裂酌儒、退化（untreeify）時(shí)辜妓，仍然維護(hù)其原先鏈結(jié)構(gòu)(i.e., Node.next)  
     * 樹結(jié)構(gòu)中按照hash值、Comparator忌怎、tie-breakers三層優(yōu)先方式進(jìn)行排序 
     *  
     * 樹結(jié)構(gòu)與鏈結(jié)構(gòu)的轉(zhuǎn)換在子類LinkedHashMap中會(huì)更復(fù)雜一些籍滴，本類中預(yù)留了一些回調(diào)方法給LinkedHashMap 
     */  
  
    // 一些常量/////////////////  
  
    // 默認(rèn)的初始容量，必須是2的冪次  
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16  
    // 最大容量  
    static final int MAXIMUM_CAPACITY = 1 << 30;  
    // 默認(rèn)負(fù)載因子  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;  
    // 建樹閾值榴啸，桶內(nèi)元素大于這個(gè)數(shù)值時(shí)會(huì)轉(zhuǎn)為TreeNode桶  
    // 這個(gè)數(shù)值至少為8以兼容remove操作時(shí)退化為普通節(jié)點(diǎn)的機(jī)制  
    static final int TREEIFY_THRESHOLD = 8;  
    // 退樹閾值孽惰，TreeNode桶內(nèi)元素小于這個(gè)數(shù)值時(shí)會(huì)退化為普通節(jié)點(diǎn)  
    // 數(shù)值必須小于TREEIFY_THRESHOLD，至少為6  
    static final int UNTREEIFY_THRESHOLD = 6;  
    // 最小的建樹容量鸥印，這個(gè)數(shù)值不能小于4 * TREEIFY_THRESHOLD以免resize和treeify機(jī)制相互沖突  
    static final int MIN_TREEIFY_CAPACITY = 64;  
  
    /** 
     * 基礎(chǔ)的桶節(jié)點(diǎn)（bin node）勋功，大部分Entry的實(shí)現(xiàn)類 
     */  
    static class Node<K, V> implements Map.Entry<K, V> {  
        final int hash;  
        final K key;  
        V value;  
        Node<K, V> next;  
  
        Node(int hash, K key, V value, Node<K, V> next) {  
            this.hash = hash;  
            this.key = key;  
            this.value = value;  
            this.next = next;  
        }  
  
        @Override  
        public final int hashCode() {  
            return Objects.hashCode(key) ^ Objects.hashCode(value);  
        }  
  
        @Override  
        public final V setValue(V newValue) {  
            V oldValue = value;  
            value = newValue;  
            return oldValue;  
        }  
  
        @Override  
        public final boolean equals(Object o) {  
            if (o == this)  
                return true;  
            if (o instanceof Map.Entry) {  
                Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;  
                if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))  
                    return true;  
            }  
            return false;  
        }  
    }  
  
    // 一些靜態(tài)輔助方法/////////////////////  
  
    /** 
     * 計(jì)算key的hashCode，并將高低16字節(jié)異或（注意不是直接key.hashCode()拿來用） 
     *  
     * 由于容量是2的冪次库说，僅高位不同的hashCode總會(huì)落到同一個(gè)桶（例如整數(shù)部分相同的若干浮點(diǎn)數(shù)） 
     * 這使得原始的hashCode很可能造成不好的散列特性狂鞋，因此通過xor操作將高位的影響擴(kuò)散到低位 
     */  
    static final int hash(Object key) {  
        int h;  
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
    }  
  
    /** 
     * 通過反射判斷對(duì)象x是否實(shí)現(xiàn)Comparable<C>接口 
     * 
     * @return 如果實(shí)現(xiàn)了Comparable，返回x的實(shí)際類型潜的，也就是Class<C>骚揍，否則返回null. 
     */  
    static Class<?> comparableClassFor(Object x) {  
        if (x instanceof Comparable) {  
            Class<?> c;  
            Type[] ts, as;  
            Type t;  
            ParameterizedType p;  
            if ((c = x.getClass()) == String.class) // bypass checks  
                return c;  
            if ((ts = c.getGenericInterfaces()) != null) {  
                for (int i = 0; i < ts.length; ++i) {  
                    if (((t = ts[i]) instanceof ParameterizedType)  
                            && ((p = (ParameterizedType) t).getRawType() == Comparable.class)  
                            && (as = p.getActualTypeArguments()) != null && as.length == 1  
                            && as[0] == c) // type arg is c  
                        return c;  
                }  
            }  
        }  
        return null;  
    }  
  
    /** 
     * 如果x實(shí)際類型是kc，則返回k.compareTo(x)啰挪，否則返回0 
     *  
     * @param kc 必須實(shí)現(xiàn)Comparable 
     * @param k 類型為kc 
     * @param x 類型無限制 
     */  
    @SuppressWarnings({ "rawtypes", "unchecked" })  
    static int compareComparables(Class<?> kc, Object k, Object x) {  
        return (x == null || x.getClass() != kc ? 0 : ((Comparable) k).compareTo(x));  
    }  
  
    /** 
     * 返回不小于cap的最小的2的冪次 
     */  
    static final int tableSizeFor(int cap) {  
        // 低位全部用1填充  
        int n = cap - 1;  
        n |= n >>> 1;  
        n |= n >>> 2;  
        n |= n >>> 4;  
        n |= n >>> 8;  
        n |= n >>> 16;  
        // 上下限  
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;  
    }  
  
    // 實(shí)例屬性/////////////////////  
  
    // 實(shí)際數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)信不，尺寸可能變更  
    transient Node<K, V>[] table;  
    // entrySet()緩存  
    transient Set<Map.Entry<K, V>> entrySet;  
    // 實(shí)際元素個(gè)數(shù)  
    transient int size;  
    // HashMap發(fā)生結(jié)構(gòu)變更的計(jì)數(shù)器嘲叔，結(jié)構(gòu)變更包括增刪元素、rehash等抽活，這個(gè)屬性為實(shí)現(xiàn)迭代子的fast-fail特性  
    transient int modCount;  
    // 下一個(gè)resize的元素個(gè)數(shù) (capacity * load factor).  
    int threshold;  
    // 負(fù)載因子  
    final float loadFactor;  
  
    // public方法/////////////////////  
  
    /** 
     * 含參構(gòu)造函數(shù) 
     * 
     * @param initialCapacity 
     * @param loadFactor 
     * @throws IllegalArgumentException initialCapacity<0或loadFactor<=0 
     */  
    public HashMap(int initialCapacity, float loadFactor) {  
        if (initialCapacity < 0)  
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);  
        if (initialCapacity > MAXIMUM_CAPACITY)  
            initialCapacity = MAXIMUM_CAPACITY;  
        if (loadFactor <= 0 || Float.isNaN(loadFactor))  
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);  
        this.loadFactor = loadFactor;  
        this.threshold = tableSizeFor(initialCapacity);  
    }  
  
    public HashMap() {  
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted  
    }  
  
    /** 
     * 根據(jù)已有Map構(gòu)造一個(gè)新的HashMap硫戈，負(fù)載因子取默認(rèn)值，初始容量根據(jù)m.size()確定 
     * 
     * @throws NullPointerException if m==null 
     */  
    public HashMap(Map<? extends K, ? extends V> m) {  
        this.loadFactor = DEFAULT_LOAD_FACTOR;  
        putMapEntries(m, false);  
    }  
  
    /** 
     * 將m的所有元素放入本對(duì)象酌壕，實(shí)現(xiàn)Map.putAll和構(gòu)造函數(shù) 
     * 
     * @param m the map 
     * @param evict 初始化調(diào)用為false掏愁，否則為true 
     */  
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {  
        int s = m.size();  
        if (s > 0) {  
            if (table == null) {  
                // 初始化情形，根據(jù)m.size初始化threshold  
                float ft = (s / loadFactor) + 1.0F;  
                int t = ((ft < MAXIMUM_CAPACITY) ? (int) ft : MAXIMUM_CAPACITY);  
                if (t > threshold)  
                    threshold = tableSizeFor(t);  
            } else if (s > threshold) {  
                // 非初始化卵牍，如果m.size已經(jīng)超過threshold果港，則立刻resize  
                // 注意不包含現(xiàn)有元素，putVal()還有尺寸操作  
                resize();  
            }  
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {  
                K key = e.getKey();  
                V value = e.getValue();  
                putVal(hash(key), key, value, false, evict);  
            }  
        }  
    }  
  
    /** 
     * 返回key對(duì)應(yīng)的value糊昙，如果沒有返回null 
     * 
     * 是否包含通過key.equals()確定 
     * 
     * @return 注意返回null不一定代表key不存在辛掠，有可能對(duì)應(yīng)的value就是null。如需區(qū)分可使用{@link #containsKey containsKey} 
     * @see #put(Object, Object) 
     */  
    @Override  
    public V get(Object key) {  
        Node<K, V> e;  
        return (e = getNode(hash(key), key)) == null ? null : e.value;  
    }  
  
    /** 
     * get的實(shí)現(xiàn) 
     * 
     * @param hash 
     * @return the node 不存在返回null 
     */  
    final Node<K, V> getNode(int hash, Object key) {  
        Node<K, V>[] tab; // table的快照  
        Node<K, V> first, e;  
        int n;  
        K k;  
        // first = tab[(n - 1) & hash]是hash對(duì)應(yīng)桶的第一個(gè)元素  
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {  
            if (first.hash == hash && // always check first node  
                    ((k = first.key) == key || (key != null && key.equals(k)))) {  
                return first; // 第一個(gè)equal就直接返回了  
            }  
  
            // 否則如果是TreeNode就調(diào)用TreeNode的get释牺，不是就直接根據(jù).next遍歷桶  
            if ((e = first.next) != null) {  
                if (first instanceof TreeNode)  
                    return ((TreeNode<K, V>) first).getTreeNode(hash, key);  
                do {  
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))  
                        return e;  
                } while ((e = e.next) != null);  
            }  
        }  
        return null;  
    }  
  
    /** 
     * 是否包含萝衩，這個(gè)實(shí)際邏輯與get基本是一樣的 
     */  
    @Override  
    public boolean containsKey(Object key) {  
        return getNode(hash(key), key) != null;  
    }  
  
    /** 
     * 放入一個(gè)kv對(duì)，如果key已經(jīng)存在没咙，則value被替換 
     * 
     * @return 如果原先包含key猩谊，則返回舊的value，否則返回null 
     */  
    @Override  
    public V put(K key, V value) {  
        return putVal(hash(key), key, value, false, true);  
    }  
  
    /** 
     * put的實(shí)現(xiàn) 
     * 
     * @param hash 
     * @param onlyIfAbsent true表示僅當(dāng)key不存在的情況才執(zhí)行put（不修改已存在的值） 
     * @param evict false表示創(chuàng)建過程中 
     * @return 如果原先包含key祭刚，則返回舊的value牌捷，否則返回null 
     */  
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {  
        Node<K, V>[] tab;  
        Node<K, V> p;  
        int n, i;  
        if ((tab = table) == null || (n = tab.length) == 0)  
            // 初始化情況  
            n = (tab = resize()).length;  
        if ((p = tab[i = (n - 1) & hash]) == null)  
            // key對(duì)應(yīng)的桶不存在情況（key也必然不存在），new一個(gè)新node就行了  
            tab[i] = newNode(hash, key, value, null);  
        else { // 桶存在情況  
            Node<K, V> e; // 表示key的（可能有的）現(xiàn)有節(jié)點(diǎn)  
            K k;  
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))  
                e = p; // 第一個(gè)就是涡驮，直接拿過來  
            else if (p instanceof TreeNode) {  
                // TreeNode情況  
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);  
            } else {  
                // 非TreeNode暗甥，循環(huán)遍歷桶  
                for (int binCount = 0;; ++binCount) {  
                    if ((e = p.next) == null) { // 確實(shí)沒有，new一個(gè)新node  
                        p.next = newNode(hash, key, value, null);  
                        // 如果桶的尺寸超過了TREEIFY_THRESHOLD捉捅，這個(gè)桶要轉(zhuǎn)化為樹  
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                            treeifyBin(tab, hash);  
                        break;  
                    }  
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))  
                        break; // 找到了撤防，退出循環(huán)  
                    p = e;  
                }  
            }  
            if (e != null) { // 所有的已存在情況，更新value并返回舊value  
                V oldValue = e.value;  
                if (!onlyIfAbsent || oldValue == null)  
                    e.value = value;  
                afterNodeAccess(e); // 子類回調(diào)  
                return oldValue;  
            }  
        }  
  
        // 到這說明新加了節(jié)點(diǎn)棒口，modCount+1  
        // 注意這里只處理增加節(jié)點(diǎn)寄月，如果觸發(fā)resize或者treeify，會(huì)在對(duì)應(yīng)方法里繼續(xù)維護(hù)modCount  
        ++modCount;  
        if (++size > threshold) // size超過閾值无牵，觸發(fā)resize  
            resize();  
        afterNodeInsertion(evict); // 子類回調(diào)  
        return null;  
    }  
  
    /** 
     * 初始化或擴(kuò)容 
     *  
     * 由于容量是2的冪次漾肮，resize后元素下標(biāo)或者不變，或者增加2的冪次 
     * 
     * @return 擴(kuò)容后的表 
     */  
    final Node<K, V>[] resize() {  
        Node<K, V>[] oldTab = table;  
        int oldCap = (oldTab == null) ? 0 : oldTab.length;  
        int oldThr = threshold;  
        int newCap, newThr = 0;  
        if (oldCap > 0) { // 擴(kuò)容情況  
            if (oldCap >= MAXIMUM_CAPACITY) { // 超過上限了就不能再擴(kuò)容了  
                threshold = Integer.MAX_VALUE;  
                return oldTab;  
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY // 擴(kuò)容合敦，容量*2  
                    && oldCap >= DEFAULT_INITIAL_CAPACITY)  
                newThr = oldThr << 1; // double threshold  
        } else if (oldThr > 0) // 初始化情況  
            newCap = oldThr;  
        else { // zero initial threshold signifies using defaults  
            newCap = DEFAULT_INITIAL_CAPACITY;  
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
        }  
  
        // 更新threshold  
        if (newThr == 0) {  
            float ft = newCap * loadFactor;  
            newThr = (newCap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY ? (int) ft  
                    : Integer.MAX_VALUE);  
        }  
        threshold = newThr;  
  
        @SuppressWarnings({ "unchecked" })  
        Node<K, V>[] newTab = new Node[newCap]; // 新表  
        table = newTab;  
        if (oldTab != null) { // 移動(dòng)舊表的元素  
            for (int j = 0; j < oldCap; ++j) {  
                Node<K, V> e;  
                if ((e = oldTab[j]) != null) {  
                    oldTab[j] = null; // 舊表置null以便空間快速回收  
                    if (e.next == null) { // 只有一個(gè)元素的桶初橘，直接扔到新的桶（新桶一定是空的）  
                        newTab[e.hash & (newCap - 1)] = e;  
                    } else if (e instanceof TreeNode) { // 處理TreeNode分裂  
                        ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);  
                    } else { // 普通的桶，逐個(gè)處理  
                        Node<K, V> loHead = null, loTail = null; // 原桶的首位指針  
                        Node<K, V> hiHead = null, hiTail = null; // 新桶(+oldCap)的首位指針  
                        Node<K, V> next;  
                        do {  
                            next = e.next;  
                            if ((e.hash & oldCap) == 0) { // 保持不動(dòng)  
                                if (loTail == null) {  
                                    loHead = e;  
                                } else {  
                                    loTail.next = e;  
                                }  
                                loTail = e;  
                            } else { // 挪到新桶  
                                if (hiTail == null) {  
                                    hiHead = e;  
                                } else {  
                                    hiTail.next = e;  
                                }  
                                hiTail = e;  
                            }  
                        } while ((e = next) != null);  
  
                        // 把更新后的兩個(gè)桶放到表里  
                        if (loTail != null) {  
                            loTail.next = null;  
                            newTab[j] = loHead;  
                        }  
                        if (hiTail != null) {  
                            hiTail.next = null;  
                            newTab[j + oldCap] = hiHead;  
                        }  
                    }  
                }  
            }  
        }  
        return newTab;  
    }  
  
    /** 
     * 將指定的桶轉(zhuǎn)化為TreeNode 
     */  
    final void treeifyBin(Node<K, V>[] tab, int hash) {  
        int n, index;  
        Node<K, V> e;  
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  
            resize(); // 如果容量小于MIN_TREEIFY_CAPACITY，則直接擴(kuò)容  
        else if ((e = tab[index = (n - 1) & hash]) != null) {  
            TreeNode<K, V> hd = null, tl = null;  
            do { // 先把Node鏈表轉(zhuǎn)成TreeNode鏈表  
                TreeNode<K, V> p = replacementTreeNode(e, null); // 當(dāng)前節(jié)點(diǎn)生成的TreeNode  
                if (tl == null) {  
                    hd = p;  
                } else {  
                    p.prev = tl;  
                    tl.next = p;  
                }  
                tl = p;  
            } while ((e = e.next) != null);  
  
            // 然后將TreeNode鏈表轉(zhuǎn)成樹  
            if ((tab[index] = hd) != null) {  
                hd.treeify(tab);  
            }  
        }  
    }  
  
    /** 
     * 批量put 
     */  
    @Override  
    public void putAll(Map<? extends K, ? extends V> m) {  
        putMapEntries(m, true);  
    }  
  
    /** 
     * 刪除對(duì)應(yīng)Key的元素 
     * 
     * @param key 注意是Object保檐，類型不要傳錯(cuò) 
     * @return 如果key存在耕蝉，返回刪除前的value，否則返回null 
     */  
    @Override  
    public V remove(Object key) {  
        Node<K, V> e;  
        return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;  
    }  
  
    /** 
     * 刪除節(jié)點(diǎn)實(shí)現(xiàn) 
     * 
     * @param hash 
     * @param key 
     * @param value 如果matchValue=true夜只，表示匹配的value垒在，否則無作用 
     * @param matchValue true表示僅當(dāng)key對(duì)應(yīng)value等于matchValue時(shí)才刪除 
     * @param movable false表示不移動(dòng)其他元素（迭代子使用） 
     * @return 如果刪了，返回被刪的元素扔亥，否則返回null 
     */  
    final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue,  
            boolean movable) {  
        Node<K, V>[] tab;  
        Node<K, V> p;  
        int n, index;  
        if ((tab = table) != null && (n = tab.length) > 0  
                && (p = tab[index = (n - 1) & hash]) != null) {  
            Node<K, V> node = null, e; // node為待刪元素  
            K k;  
            V v;  
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))  
                node = p; // 第一個(gè)就匹配场躯，直接就他了  
            else if ((e = p.next) != null) {  
                if (p instanceof TreeNode) // 如果是TreeNode，從TreeNode取key的元素  
                    node = ((TreeNode<K, V>) p).getTreeNode(hash, key);  
                else { // 否則遍歷鏈表找  
                    do {  
                        if (e.hash == hash  
                                && ((k = e.key) == key || (key != null && key.equals(k)))) {  
                            node = e;  
                            break;  
                        }  
                        p = e;  
                    } while ((e = e.next) != null);  
                }  
            }  
  
            if (node != null  
                    && (!matchValue || (v = node.value) == value || (value != null && value  
                            .equals(v)))) { // 這條件表示確實(shí)要?jiǎng)h  
  
                // TreeNode就按TreeNode刪旅挤，否則在鏈表刪  
                if (node instanceof TreeNode) {  
                    ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);  
                } else if (node == p)  
                    tab[index] = node.next;  
                else {  
                    p.next = node.next;  
                }  
                ++modCount; // 刪除元素造成的結(jié)構(gòu)變更  
                --size;  
                afterNodeRemoval(node); // 子類回調(diào)  
                return node;  
            }  
        }  
        return null;  
    }  
  
    /** 
     * 清空（全部刪除） 
     */  
    @Override  
    public void clear() {  
        Node<K, V>[] tab;  
        modCount++;  
        if ((tab = table) != null && size > 0) {  
            size = 0;  
            for (int i = 0; i < tab.length; ++i) { // 所有的桶都置為null  
                tab[i] = null;  
            }  
        }  
    }  
  
    /** 
     * 包含（一個(gè)或多個(gè)）value踢关。因?yàn)闆]有倒排，這個(gè)方法要遍歷全表粘茄，慎用 
     * 
     * @param value 
     */  
    @Override  
    public boolean containsValue(Object value) {  
        Node<K, V>[] tab;  
        V v;  
        if ((tab = table) != null && size > 0) {  
            for (int i = 0; i < tab.length; ++i) { // 遍歷表  
                for (Node<K, V> e = tab[i]; e != null; e = e.next) {  
                    // 遍歷桶签舞。注意TreeNode還是維持打平的鏈表關(guān)系，所以不用特別處理  
                    if ((v = e.value) == value || (value != null && value.equals(v)))  
                        return true;  
                }  
            }  
        }  
        return false;  
    }  

參考博客：http://distantlight1.iteye.com/blog/2256651
（因?yàn)橛X得人家總結(jié)得非常好柒瓣，所以就搬了很多東西來儒搭，打算一邊閱讀源碼一邊參照別人的博客然后進(jìn)行完善。）