（一）Map方法概述

首先先看一下官方對Map接口的解釋烤惊，《Java Platform SE 8》:

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

Map是一個通過鍵值對保存的對象，一個map只能由一個key徒坡，但是一個key可以有多個value撕氧。

Map的使用很簡單：

1.1 Map的幾個常用方法

通過代碼展示一下Map中常用的方法：

public class MapTest {
    public static void main(String[] args) {
        Map map=new HashMap();
        //添加 put(key,value)
        map.put("a1",1);
        map.put("a2",1);
        map.put(null,1);
        System.out.println(map);
        //刪除 remove(key)
        map.remove("a2");
        System.out.println(map);
        //是否包含 key value
        //containsKey(key)  containsValue(value)
        System.out.println(map.containsKey("a1"));
        System.out.println(map.containsValue("1"));
        //獲取數(shù)據(jù) get(key)
        System.out.println(map.get("a1"));
        //獲取大小 size()
        System.out.println(map.size());
        //是否為空 isEmpty()
        System.out.println(map.isEmpty());
        //獲取所有的關(guān)系 entrySet()
        System.out.println(map.entrySet());
        //獲取所有的key keySet()
        System.out.println(map.keySet());
        //獲取所有的value values()
        System.out.println(map.values());
    }
}

（二）HashMap的特點

HashMap底層是一個哈希表，以數(shù)組加鏈表的形式存儲值喇完。HashMap具有以下特點：

1.HashMap允許key和value為空

2.HashMap是線程不安全的

3.HashMap的初始容量為16伦泥，負載因子大小為0.75

4.在jdk7.0中，底層是數(shù)組加鏈表锦溪；在jdk8.0中不脯，底層是數(shù)組加鏈表加紅黑樹（這一點在后面會重點講一下）

（三）HashMap的源碼分析

通過代碼斷點的方法逐個添加元素，單步觀察代碼執(zhí)行步驟刻诊，首先進入HashMap的構(gòu)造方法：

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

該構(gòu)造方法把負載因子設(shè)置為0.75防楷，負載因子的意思是當存入的數(shù)據(jù)大于總?cè)萘康?.75倍時，就擴容则涯。構(gòu)造方法結(jié)束后進入put方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

put方法直接返回putVal()方法复局，putVal方法的第一個參數(shù)是根據(jù)key計算的一個哈希值，可以看一下這個hash方法：通過hash運算和異或操作得到hash值并返回

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

接下來就進入了比較重要的putVal方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //查看此時table的容量（即哈希表數(shù)組部分的長度）粟判，如果為空（第一次進入）亿昏，則進入resize()方法
    //resize()是個初始化或擴容方法，初始化成16或擴容2倍
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //根據(jù)此時數(shù)組的長度n和計算的hash值算出索引
    //計算出的索引一定在0~n-1之間
   //如果該索引位置沒有元素档礁，則直接將元素添加進入
   if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
   //如果該索引位置存在元素角钩，執(zhí)行以下代碼塊    
   else {
        Node<K,V> e; K k;
        //如果該元素和要保存的元素相同，則覆蓋
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果不相同呻澜，并且是樹狀結(jié)構(gòu)递礼，則按樹狀結(jié)構(gòu)的方式添加元素
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //如果是鏈狀結(jié)構(gòu)，則按照鏈表的方式添加元素
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    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;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //判斷容量是否超過臨界值羹幸，如果超過了就2倍擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

源碼分析：

HashMap中維護了Node類型的數(shù)組table脊髓，當HashMap創(chuàng)建對象時，設(shè)置負載因子為0.75栅受，table還是null供炼。

當?shù)谝淮翁砑釉貢r，將table的容量設(shè)置為16窘疮，臨界值設(shè)置為12

每次添加元素調(diào)用putVal方法：

1.將key的hash值和table容量-1進行與運算，得到索引值

2.判斷該存放位置上是否有元素冀墨，如若沒有元素則直接放上去闸衫；如果該索引位置已存在元素，則繼續(xù)判斷

3.如果該位置的元素和添加元素相等诽嘉，則直接覆蓋蔚出，如果不相等弟翘，則繼續(xù)判斷是鏈表結(jié)構(gòu)還是樹狀結(jié)構(gòu)，按照相對應(yīng)的方式添加骄酗。

如果添加的數(shù)量大于臨界值稀余，執(zhí)行resize方法對容量雙倍擴容。并打亂順序重新排列趋翻。

（四）HashMap在JDK1.7和JDK1.8中的區(qū)別

前面一直提到樹狀結(jié)構(gòu)和紅黑樹睛琳，這是HashMap在JDK1.7和JDK1.8之間最大的區(qū)別。數(shù)組+鏈表的結(jié)構(gòu)下踏烙，如果一個索引后跟著的鏈表數(shù)量很多時师骗，會很影響查找效率，因此在JDK1.8中讨惩，HashMap當滿足某種條件（鏈表長度大于8辟癌，table容量大于64）時，會將鏈表轉(zhuǎn)化為紅黑樹結(jié)構(gòu)荐捻，提高效率黍少。

截取一段源碼：當鏈表長度大于等于（TREEIFY_THRESHOLD - 1）時，這個值是7处面，進入treeifyBin方法厂置。鏈表長度大于等于7，再加上數(shù)組上的一個元素鸳君，一共是8個元素农渊。

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

進入treeifyBin方法：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果進入treeifyBin但是table的容量小于64，則執(zhí)行resize擴容并重新打亂
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //鏈表長度大于8或颊，table容量大于64砸紊，轉(zhuǎn)化成紅黑樹
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

如果進入treeifyBin但是table的容量小于64，則執(zhí)行resize擴容并重新打亂囱挑。所以并非容量大于臨界容量才會擴容醉顽。

第二個差異是插入元素時的變化，JDK1.7中是用頭插法的方式插入元素平挑，在JDK1.8中這個插入方式變成了尾插法游添。這個變化的原因是用頭插法插入元素存在鏈表循環(huán)的風(fēng)險。當兩個線程同時put元素并且剛好觸發(fā)擴容通熄，就會造成鏈表死循環(huán)唆涝。

JDK1.7和JDK1.8區(qū)別總結(jié)：

1.初始化對象時，JDK1.7直接初始化對象容量為16唇辨，JDK1.8僅僅初始化負載因子為0.75

2.table類型：JDK1.7是Entry（映射key和value）廊酣，JDK1.8是Node類型（為了紅黑樹）

3.底層結(jié)構(gòu)：JDK1.7數(shù)組+鏈表，JDK1.8數(shù)組+鏈表+紅黑樹（鏈表長度大于8赏枚，table容量大于64）

4.元素插入方式：JDK1.7 頭插法亡驰，JDK1.8尾插法

（四）HashMap和HashTable的對比

HashMap和HashTable的處境有點像Vector和ArrayList晓猛，HashTable現(xiàn)在很少使用，就用一個表格來總結(jié)它和HashMap的區(qū)別

（五）TreeMap的介紹

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

根據(jù)官方文檔的介紹凡辱，TreeMap底層是一個紅黑樹戒职，map是根據(jù)keys進行自然排序或者定制排序。

自然排序和定制排序的用法和TreeSet類似透乾。

使用自然排序：需要在類中繼承Comparable接口洪燥，并重寫compareTo方法。

public class Book implements Comparable{
    private String name;
    private float price;
    public Book(String name, float price){
        this.name=name;
        this.price=price;
    }
    //.........
    @Override
    public int compareTo(Object o) {
        Book book= (Book) o;
        return Double.compare(book.price,this.price);
    }
}

使用定制排序：需要在創(chuàng)建TreeMap對象時傳入一個Comparator接口续徽，并實現(xiàn)里面的compare方法蚓曼。

TreeMap map=new TreeMap(new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        Book book1= (Book) o1;
        Book book2= (Book) o2;
        return Double.compare(book1.getPrice(),book2.getPrice());
    }
});

（六）總結(jié)

HashMap絕對是Map中的重點，也是據(jù)我所知面試中問到最多的集合知識钦扭。因此有條件的話打開源碼自己單步調(diào)試一遍纫版。HashTable、TreeMap就算沒有看過代碼但是也要了解各自的特點客情。