前面已經(jīng)介紹完了Collection接口下的集合實(shí)現(xiàn)類，今天我們來介紹Map接口下的兩個重要的集合實(shí)現(xiàn)類HashMap,TreeMap。關(guān)于Map的一些通用介紹，可以參考第一篇文章。由于Map與List、Set集合的某些特性有重合，因此觀看本篇文章的會參考到之前的一些內(nèi)容，最下方有鏈接。如果已經(jīng)有這方面的基礎(chǔ)，那么對Map的學(xué)習(xí)將會事半功倍。

HashMap

HashMap 是一個散列表，它存儲的內(nèi)容是鍵值對(key-value)映射。
既然要介紹HashMap，那么就順帶介紹HashTable,兩者進(jìn)行比對。HashMap和Hashtable都是Map接口的經(jīng)典實(shí)現(xiàn)類，它們之間的關(guān)系完全類似于之前介紹的ArrayList和Vector的關(guān)系。由于Hashtable是個古老的Map實(shí)現(xiàn)類（從Hashtable的命名規(guī)范就可以看出，t沒有大寫，并不是我寫錯了），需要方法比較繁瑣，不符合Map接口的規(guī)范。但是Hashtable也具有HashMap不具有的優(yōu)點(diǎn)。下面我們進(jìn)行兩者之間的比對。

HashMap與Hashtable的區(qū)別

1.Hashtable是一個線程安全的Map實(shí)現(xiàn)，但HashMap是線程不安全的實(shí)現(xiàn)，所以HashMap比Hashtable的性能好一些；但如果有多個線程訪問同一個Map對象時，是盜用Hashtable實(shí)現(xiàn)類會更好。

2.Hashtable不允許使用null作為key和value，如果試圖把null值放進(jìn)Hashtable中，將會引發(fā)NullPointerException異常；但是HashMap可以使用null作為key或value。

HashMap判斷key與value相等的標(biāo)準(zhǔn)

前面文章中，我們針對其他集合都分析了判斷集合元素相等的標(biāo)準(zhǔn)。針對HashMap也不例外，不同的是有兩個元素：key與value需要分別介紹判斷相等的標(biāo)準(zhǔn)。

key判斷相等的標(biāo)準(zhǔn)

類似于HashSet，HashMap與Hashtable判斷兩個key相等的標(biāo)準(zhǔn)是：兩個key通過equals()方法比較返回true,兩個key的hashCode值也相等，則認(rèn)為兩個key是相等的。

注意：用作key的對象必須實(shí)現(xiàn)了hashCode()方法和equals()方法。并且最好兩者返回的結(jié)果一致，即如果equals()返回true，hashCode()值相等?？?a href="http://m.itdecent.cn/p/9081017a2d67" target="_blank">參考Set關(guān)于這方面的介紹。

value判斷相等的標(biāo)準(zhǔn)

HashMap與Hashtable判斷兩個value相等的標(biāo)準(zhǔn)是：只要兩個對象通過equals()方法比較返回true即可。

注意：HashMap中key所組成的集合元素不能重復(fù)，value所組成的集合元素可以重復(fù)。

下面程序示范了HashMap判斷key與value相等的標(biāo)準(zhǔn)。

public class A {
    public int count;

    public A(int count) {
        this.count = count;
    }
    //根據(jù)count值來計(jì)算hashCode值
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + count;
        return result;
    }
    //根據(jù)count值來判斷兩個對象是否相等
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        A other = (A) obj;
        if (count != other.count)
            return false;
        return true;
    }
    

}

public class B {
    public int count;
    public B(int count) {
        this.count = count;
    }
     //根據(jù)count值來判斷兩個對象是否相等
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        B other = (B) obj;
        if (count != other.count)
            return false;
        return true;
    }

}

public class HashMapTest {
    public static void main(String[] args){
        HashMap map = new HashMap();
        map.put(new A(1000), "集合Set");
        map.put(new A(2000), "集合List");
        map.put(new A(3000), new B(1000));
       //僅僅equals()比較為true，但認(rèn)為是相同的value
        boolean isContainValue = map.containsValue(new B(1000));
        System.out.println(isContainValue);
      //雖然是不同的對象，但是equals()和hashCode()返回結(jié)果都相等
        boolean isContainKey = map.containsKey(new A(1000));
        System.out.println(isContainKey);
      //equals()和hashCode()返回結(jié)果不滿足key相等的條件
        System.out.println(map.containsKey(new A(4000)));
    }
    
}

輸出結(jié)果：

true
true
false

注意：如果是加入HashMap的key是個可變對象，在加入到集合后又修改key的成員變量的值，可能導(dǎo)致hashCode()值以及equal()的比較結(jié)果發(fā)生變化，無法訪問到該key。一般情況下不要修改。

HashMap的本質(zhì)

下面我們從源碼角度來理解HashMap。

HashMap的構(gòu)造函數(shù)

// 默認(rèn)構(gòu)造函數(shù)。
HashMap()

// 指定“容量大小”的構(gòu)造函數(shù)
HashMap(int capacity)

// 指定“容量大小”和“加載因子”的構(gòu)造函數(shù)
HashMap(int capacity, float loadFactor)

// 包含“子Map”的構(gòu)造函數(shù)
HashMap(Map<? extends K, ? extends V> map)

從構(gòu)造函數(shù)中，了解到兩個重要的元素：容量大小(capacity)以及加載因子(loadFactor)。
容量(capacity)是哈希表的容量，初始容量是哈希表在創(chuàng)建時的容量（即DEFAULT_INITIAL_CAPACITY = 1 << 4）。
加載因子 是哈希表在其容量自動增加之前可以達(dá)到多滿的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時，則要對該哈希表進(jìn)行 resize操作（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)），從而哈希表將具有大約兩倍的桶數(shù)。
通常，默認(rèn)加載因子是 0.75(即DEFAULT_LOAD_FACTOR = 0.75f), 這是在時間和空間成本上尋求一種折衷。加載因子過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數(shù) HashMap 類的操作中，包括 get 和 put 操作，都反映了這一點(diǎn)）。在設(shè)置容量時應(yīng)該考慮到映射中所需的條目數(shù)及其加載因子，以便最大限度地減少 resize操作次數(shù)。如果容量大于最大條目數(shù)除以加載因子，則不會發(fā)生 rehash 操作。

Node類型
HashMap是通過"拉鏈法"實(shí)現(xiàn)的哈希表。它包括幾個重要的成員變量：table, size, threshold, loadFactor。

table是一個Node[]數(shù)組類型，而Node實(shí)際上就是一個單向鏈表。哈希表的"key-value鍵值對"都是存儲在Node數(shù)組中的。

size是HashMap的大小，它是HashMap保存的鍵值對的數(shù)量。

threshold是HashMap的閾值，用于判斷是否需要調(diào)整HashMap的容量。threshold的值="容量*加載因子"，當(dāng)HashMap中存儲數(shù)據(jù)的數(shù)量達(dá)到threshold時，就需要將HashMap的容量加倍。

loadFactor就是加載因子。

要想理解HashMap，首先就要理解基于Node實(shí)現(xiàn)的“拉鏈法”。

Java中數(shù)據(jù)存儲方式最底層的兩種結(jié)構(gòu)，一種是數(shù)組，另一種就是鏈表，數(shù)組的特點(diǎn)：連續(xù)空間，尋址迅速，但是在刪除或者添加元素的時候需要有較大幅度的移動，所以查詢速度快，增刪較慢。而鏈表正好相反，由于空間不連續(xù)，尋址困難，增刪元素只需修改指針，所以查詢速度慢、增刪快。有沒有一種數(shù)組結(jié)構(gòu)來綜合一下數(shù)組和鏈表，以便發(fā)揮它們各自的優(yōu)勢？答案是肯定的！就是：哈希表。哈希表具有較快（常量級）的查詢速度，及相對較快的增刪速度，所以很適合在海量數(shù)據(jù)的環(huán)境中使用。一般實(shí)現(xiàn)哈希表的方法采用“拉鏈法”，我們可以理解為“鏈表的數(shù)組”，如下圖：

圖中，我們可以發(fā)現(xiàn)哈希表是由數(shù)組+鏈表組成的，一個長度為16的數(shù)組中，每個元素存儲的是一個鏈表的頭結(jié)點(diǎn)。那么這些元素是按照什么樣的規(guī)則存儲到數(shù)組中呢？
一般情況是通過hash(key)獲得，也就是元素的key的哈希值。如果hash(key)值相等，則都存入該hash值所對應(yīng)的鏈表中。它的內(nèi)部其實(shí)是用一個Node數(shù)組來實(shí)現(xiàn)。

所以每個數(shù)組元素代表一個鏈表，其中的共同點(diǎn)就是hash(key)相等。

下面我們來了解下鏈表的基本元素Node。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        // 指向下一個節(jié)點(diǎn)
        Node<K,V> next;
        //構(gòu)造函數(shù)。
      // 輸入?yún)?shù)包括"哈希值(hash)", "鍵(key)", "值(value)", "下一節(jié)點(diǎn)(next)"
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
         // 判斷兩個Node是否相等
        // 若兩個Node的“key”和“value”都相等，則返回true。
        // 否則，返回false
        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;
        }
    }

再此結(jié)構(gòu)下，實(shí)現(xiàn)了集合的增刪改查功能，由于本篇的篇幅有限，這里就不具體介紹其源碼實(shí)現(xiàn)了。

HashMap遍歷方式

1.遍歷HashMap的鍵值對

第一步：根據(jù)entrySet()獲取HashMap的“鍵值對”的Set集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。

2.遍歷HashMap的鍵

第一步：根據(jù)keySet()獲取HashMap的“鍵”的Set集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。

3.遍歷HashMap的值

第一步：根據(jù)value()獲取HashMap的“值”的集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。

LinkedHashMap實(shí)現(xiàn)類

HashSet有一個LinkedHashSet子類，HashMap也有一個LinkedHashMap子類；LinkedHashMap使用雙向鏈表來維護(hù)key-value對的次序。
LinkedHashMap需要維護(hù)元素的插入順序，因此性能略低于HashMap的性能；但是因?yàn)樗枣湵韥砭S護(hù)內(nèi)部順序，所以在迭代訪問Map里的全部元素時有較好的性能。迭代輸出LinkedHashMap的元素時，將會按照添加key-value對的順序輸出。
本質(zhì)上來講，LinkedHashMap=散列表+循環(huán)雙向鏈表

TreeMap

TreeMap是SortedMap接口的實(shí)現(xiàn)類。TreeMap 是一個有序的key-value集合，它是通過紅黑樹實(shí)現(xiàn)的，每個key-value對即作為紅黑樹的一個節(jié)點(diǎn)。

TreeMap排序方式

TreeMap有兩種排序方式，和TreeSet一樣。

自然排序：TreeMap的所有key必須實(shí)現(xiàn)Comparable接口，而且所有的key應(yīng)該是同一個類的對象，否則會拋出ClassCastException異常。

定制排序：創(chuàng)建TreeMap時，傳入一個Comparator對象，該對象負(fù)責(zé)對TreeMap中的所有key進(jìn)行排序。

TreeMap中判斷兩個元素key、value相等的標(biāo)準(zhǔn)

類似于TreeSet中判斷兩個元素相等的標(biāo)準(zhǔn)，TreeMap中判斷兩個key相等的標(biāo)準(zhǔn)是：兩個key通過compareTo()方法返回0，TreeMap即認(rèn)為這兩個key是相等的。

TreeMap中判斷兩個value相等的標(biāo)準(zhǔn)是：兩個value通過equals()方法比較返回true。

注意：如果使用自定義類作為TreeMap的key，且想讓TreeMap良好地工作，則重寫該類的equals()方法和compareTo()方法時應(yīng)保持一致的返回結(jié)果：兩個key通過equals()方法比較返回true時，它們通過compareTo()方法比較應(yīng)該返回0。如果兩個方法的返回結(jié)果不一致，TreeMap與Map接口的規(guī)則就會沖突。

除此之外，與TreeSet類似，TreeMap根據(jù)排序特性，也添加了一部分新的方法，與TreeSet中的一致?？梢詤⒖记懊娴奈恼?。

TreeMap的本質(zhì)

紅黑樹

R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。紅黑樹的每個節(jié)點(diǎn)上都有存儲位表示節(jié)點(diǎn)的顏色，可以是紅(Red)或黑(Black)。

紅黑樹的特性:
（1）每個節(jié)點(diǎn)或者是黑色，或者是紅色。
（2）根節(jié)點(diǎn)是黑色。
（3）每個葉子節(jié)點(diǎn)（NIL）是黑色。 [注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！]
（4）如果一個節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
（5）從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

注意：
(01) 特性(3)中的葉子節(jié)點(diǎn)，是只為空(NIL或null)的節(jié)點(diǎn)。
(02) 特性(5)，確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。

可以說TreeMap的增刪改查等操作都是在一顆紅黑樹的基礎(chǔ)上進(jìn)行操作的。

TreeMap遍歷方式

遍歷TreeMap的鍵值對

第一步：根據(jù)entrySet()獲取TreeMap的“鍵值對”的Set集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。

遍歷TreeMap的鍵

第一步：根據(jù)keySet()獲取TreeMap的“鍵”的Set集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。

遍歷TreeMap的值

第一步：根據(jù)value()獲取TreeMap的“值”的集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。

Map實(shí)現(xiàn)類的性能分析及適用場景

HashMap與Hashtable實(shí)現(xiàn)機(jī)制幾乎一樣，但是HashMap比Hashtable性能更好些。
LinkedHashMap比HashMap慢一點(diǎn)，因?yàn)樗枰S護(hù)一個雙向鏈表。
TreeMap比HashMap與Hashtable慢（尤其在插入、刪除key-value時更慢），因?yàn)門reeMap底層采用紅黑樹來管理鍵值對。
適用場景：
一般的應(yīng)用場景，盡可能多考慮使用HashMap，因?yàn)槠錇榭焖俨樵冊O(shè)計(jì)的。
如果需要特定的排序時，考慮使用TreeMap。
如果僅僅需要插入的順序時，考慮使用LinkedHashMap。

以上就是集合Map的內(nèi)容，介紹地比較粗糙，感興趣的話可以自己看源碼深入了解其內(nèi)部的結(jié)構(gòu)。

由淺入深理解java集合(一)——集合框架 Collction、Map
由淺入深理解java集合(二)——集合 Set
由淺入深理解java集合(三)——集合 List
由淺入深理解java集合(四)——集合 Queue
由淺入深理解java集合(六)——集合增刪改查的細(xì)節(jié)、性能及選擇推薦(待更新)