Map接口下主要介紹HashMap,TreeMap。HashMap與Hashtable關(guān)系跟ArrayList與Vector關(guān)系類似馁痴。ConcurrentHashMap相比于hashtable做的優(yōu)化疯搅。Hashtable是遺留類挠铲，很多常用功能與HashMap類似，不同的是它承自Dictionary類萨驶，并且是線程安全的代虾，任一時間只有一個線程能寫Hashtable进肯。Hashtable并發(fā)性不如ConcurrentHashMap，因為ConcurrentHashMap引入了分段鎖棉磨。Hashtable不建議在新代碼中使用江掩，不需要線程安全的場合可以用HashMap替換，需要線程安全的場合可以用ConcurrentHashMap替換乘瓤。

HashMap

首先大家可以可以在腦子里面有個模糊的概念频敛。HashMap大概的結(jié)構(gòu)是怎么樣的，又便于之后理解馅扣。當然Java7和Java8的內(nèi)部實現(xiàn)是不一樣的。下面先按Java7去分析理解

Java7 - HashMap

    //可以看出Entry為單向鏈表
   static class Entry<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;
   }
//以下為HashMap的一些成員變量和常量
//內(nèi)部存儲結(jié)構(gòu)着降，初次使用時創(chuàng)建和后續(xù)增長差油。
    transient Node<K,V>[] table;
// HashMap的大小，它是HashMap保存的鍵值對的數(shù)量
    transient int size;
//被修改次數(shù)任洞，使用于fail-fast機制
    transient int modCount;
 // HashMap的閾值蓄喇，用于判斷是否需要調(diào)整HashMap的容量（threshold = 容量*加載因子）
    int threshold;
// 加載因子實際大小
    final float loadFactor;     //默認0.75
// 默認的初始容量是16，必須是2的冪交掏。
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量（必須是2的冪且小于2的30次方妆偏，傳入容量過大將被這個值替換）
    static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認加載因子，0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

由代碼可以看出盅弛，大方向上钱骂，HashMap 里面是一個數(shù)組叔锐，然后數(shù)組中每個元素是一個單向鏈表。
然后我們從最常用的put方法開始见秽，跟蹤源碼并分析

public V put(K key, V value) {
    // 當插入第一個元素的時候愉烙，需要先初始化數(shù)組大小
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 如果 key 為 null，最終會將 entry 放到 table[0] 中
    if (key == null)
        return putForNullKey(value);
    //開始插入步驟
    // 1. 求 key 的 hash 值
    int hash = hash(key);
    // 2. 找到對應(yīng)的數(shù)組下標
    int i = indexFor(hash, table.length);
    // 3. 遍歷一下對應(yīng)下標[i]處的鏈表解取，看是否有重復(fù)的 key 已經(jīng)存在步责，
    //    如果有，直接覆蓋禀苦，put 方法返回舊值就結(jié)束了
    for (Entry<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++;
    // 4. 不存在重復(fù)的 key蔓肯，將此 entry 添加到鏈表中
    addEntry(hash, key, value, i);
    return null;
}

由put方法可以看出，可以大致分為三種情況振乏。

• key為null -> 放置于table[0] 中
• hash已存在 -> 在對應(yīng)下標鏈表添加/覆蓋（覆蓋時put方法返回舊值）
• hash未存在 -> 將entry添加到table中（可能會出現(xiàn)resize情況）

我們從put方法一個個節(jié)點去分析蔗包。首先table == EMPTY_TABLE時的初始化過程。

    //若表未初始化過昆码，會調(diào)用這個方法去初始化气忠。
    private void inflateTable(int toSize) {
        // 保證容器為2次冪大小
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

可以看出初始化后的容器大小為2次冪大小且為向上取整。為什么時要2次冪等下會說明赋咽。初始化完容器后旧噪，會判斷entry的key是否為null，為null由putForNullKey放置進容器中脓匿。putForNullKey方法會判斷在table[0]中是否有key==null淘钟，存在則直接替換，不存在通過 addEntry(0, null, value, 0)加入對應(yīng)entry進table[0]中陪毡。所以只允許一個key為null的元素米母。

//in jdk1.7.0_51
    final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    static int indexFor(int h, int length) {
        return h & (length-1);
    }

這里可以看出容器大小必須為2次冪的原因有兩個。

• 保證分布均勻（計算hash時會有格外的擾動毡琉，保證均勻）
• 當大小為2次冪時铁瞒，相對耗時的%操作可以替換成相對效率更高的位運算代替。因為當容量一定是2^n時桅滋，h & (length - 1) == h % length
  這里可以看到j(luò)ava7的時候HashMap的hash值是經(jīng)過了4次擾動的慧耍。而java8則只經(jīng)過一次擾動。

    void addEntry(int hash, K key, V value, int bucketIndex) {
        //如果當前 HashMap 大小已經(jīng)達到了閾值丐谋，并且新值要插入的數(shù)組位置已經(jīng)有元素了芍碧，那么要擴容
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0; //重新計算hash值
            bucketIndex = indexFor(hash, table.length);//重新獲取bucketIndex
        }

        createEntry(hash, key, value, bucketIndex);
    }
    //將新值放到鏈表的表頭，然后 size++
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

可以看到添加元素時号俐，如果當前 HashMap 大小已經(jīng)達到了閾值泌豆，并且新值要插入的數(shù)組位置已經(jīng)有元素了，那么要擴容（為原來2倍吏饿，如果沒有超過最大值時）踪危。

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

        Entry[] newTable = new Entry[newCapacity];
        //轉(zhuǎn)移對應(yīng)元素
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

擴容時蔬浙，將通過transfer方法將原來 table[i] 中的鏈表的所有節(jié)點，分拆到新的數(shù)組的 newTable[i] 和 newTable[i + oldLength] 位置上陨倡。因為擴容2倍之后indexFor返回值就發(fā)生改變了敛滋，假設(shè)原本15%15==0現(xiàn)在則時15%31==15了。

這樣子put方法分析完兴革，get方法就簡單了绎晃。

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
        //計算hash值
        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

getForNullKey()方法直接在table[0]中鏈表判斷key值是否存在，就不展開了杂曲。
getEntry()方法耶比較簡單庶艾，大概分為三步：

• 根據(jù) key通過hash()計算 hash 值。
• 通過indexFor()找到相應(yīng)的數(shù)組下標：hash & (length – 1)擎勘。
• 遍歷該數(shù)組位置處的鏈表咱揍，直到找到相等(==或equals)的 key。

Java8 HashMap

java8后棚饵，HashMap進行了優(yōu)化煤裙。引入了紅黑樹的結(jié)構(gòu)。當鏈表長度大于8之后噪漾，鏈表將轉(zhuǎn)化為紅黑樹硼砰，減低查詢時間復(fù)雜度O(logn)。
我們還是從put方法開始

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    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<K,V>[] tab; Node<K,V> p; int n, i;
        //與java7一樣欣硼，第一次進行初始化题翰。
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //對應(yīng)下標[ (n - 1) & hash]無值則直接插入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //第一個節(jié)點key值與插入key"一致"，取出該值诈胜，直接覆蓋
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)  //為紅黑樹豹障，通過紅黑樹操作設(shè)值（不展開）
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { //為鏈表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) { //插到鏈表最后
                        p.next = newNode(hash, key, value, null);
                        //鏈表長度大于8轉(zhuǎn)換為紅黑樹進行處理
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //找到"一致"的key則直接取出，直接覆蓋
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 根據(jù)onlyIfAbsent判斷是否直接覆蓋焦匈。oldValue == null直接覆蓋
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 如果 HashMap 由于新插入這個值導(dǎo)致 size 已經(jīng)超過了閾值血公，需要進行擴容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

在hash(Object key)方法在java8中進行了優(yōu)化，僅進行了一次擾動缓熟，而java7進行了4次擾動坞笙。在美團技術(shù)團隊就做了比較好的分析。java8雖然只是一次擾動荚虚，但是將高位與低位相對隨機的混淆，保證了在table較小時籍茧，高位bit也能參與到低位運算中去版述。
與put方法對比，java7中為先判斷是否需要擴容在添加寞冯，而java8為先插入再判斷是否需要擴容渴析。
在java7中晚伙，因為插入在擴容之后，插入前table中元素已經(jīng)按擴容后的位置排序俭茧，所以插入時按新的IndexFor()插入即可咆疗。

//in java8
    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) {
            if (oldCap >= MAXIMUM_CAPACITY) {//容量超過最大值則不再擴容
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }//  容量未超過最大值，則容量及閾值翻倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {//計算新的閾值
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;// 賦值新的數(shù)組母债，初始化則將直接返回 newTab
        if (oldTab != null) {
            //將每個bucket遷移到新的buckets
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)  //  單個元素直接遷移
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)  //為紅黑樹午磁，進行紅黑樹處理
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order   處理鏈表情況
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                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);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

可以看到resize還是將容量直接翻倍，但是翻倍后對原數(shù)據(jù)處理不一樣了毡们。
先看鏈表處理迅皇，這里將舊鏈表分為lo鏈表(原位置鏈表)和hi鏈表（原位置+oldCap鏈表），原數(shù)據(jù)應(yīng)該放置于那個鏈表由(e.hash & oldCap) == 0決定衙熔。(e.hash & oldCap) == 0是等價于原index登颓，而(e.hash & oldCap) == 1則等價于原index+oldCap。因為oldCap為2次冪红氯，所以oldCap可以作為一個掩碼框咙。可以參考java8對Hashmap的改進
紅黑樹處理這里就不說了痢甘。喇嘱。。比較看不懂产阱。婉称。挖坑，找個時間理解下紅黑樹相關(guān)操作再補充