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

HashMap

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

HashMap與Hashtable的區(qū)別

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

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

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

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

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

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

注意：用作key的對(duì)象必須實(shí)現(xiàn)了hashCode()方法和equals()方法。并且最好兩者返回的結(jié)果一致，即如果equals()返回true萎庭，hashCode()值相等霜医。可參考Set關(guān)于這方面的介紹驳规。

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

HashMap與Hashtable判斷兩個(gè)value相等的標(biāo)準(zhǔn)是：只要兩個(gè)對(duì)象通過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值來判斷兩個(gè)對(duì)象是否相等
    @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值來判斷兩個(gè)對(duì)象是否相等
    @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);
      //雖然是不同的對(duì)象捻勉，但是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是個(gè)可變對(duì)象镀梭，在加入到集合后又修改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ù)中，了解到兩個(gè)重要的元素：容量大小(capacity)以及加載因子(loadFactor)胚想。
容量(capacity)是哈希表的容量，初始容量是哈希表在創(chuàng)建時(shí)的容量（即DEFAULT_INITIAL_CAPACITY = 1 << 4）芽隆。
加載因子 是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度浊服。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時(shí)，則要對(duì)該哈希表進(jìn)行 resize操作（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)）胚吁，從而哈希表將具有大約兩倍的桶數(shù)牙躺。
通常，默認(rèn)加載因子是 0.75(即DEFAULT_LOAD_FACTOR = 0.75f), 這是在時(shí)間和空間成本上尋求一種折衷腕扶。加載因子過高雖然減少了空間開銷孽拷，但同時(shí)也增加了查詢成本（在大多數(shù) HashMap 類的操作中，包括 get 和 put 操作半抱，都反映了這一點(diǎn)）脓恕。在設(shè)置容量時(shí)應(yīng)該考慮到映射中所需的條目數(shù)及其加載因子，以便最大限度地減少 resize操作次數(shù)窿侈。如果容量大于最大條目數(shù)除以加載因子炼幔，則不會(huì)發(fā)生 rehash 操作。

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

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

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

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

loadFactor就是加載因子。

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

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

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

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

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

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        // 指向下一個(gè)節(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;
        }
         // 判斷兩個(gè)Node是否相等
        // 若兩個(gè)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的鍵值對(duì)

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

2.遍歷HashMap的鍵

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

3.遍歷HashMap的值

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

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

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

TreeMap

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

TreeMap排序方式

TreeMap有兩種排序方式倡怎，和TreeSet一樣迅耘。

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

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

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

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

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

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

除此之外分蓖，與TreeSet類似尔艇，TreeMap根據(jù)排序特性，也添加了一部分新的方法么鹤，與TreeSet中的一致终娃。可以參考前面的文章蒸甜。

TreeMap的本質(zhì)

紅黑樹

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

紅黑樹的特性:
（1）每個(gè)節(jié)點(diǎn)或者是黑色蕊退，或者是紅色。
（2）根節(jié)點(diǎn)是黑色憔恳。
（3）每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色瓤荔。 [注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)钥组！]
（4）如果一個(gè)節(jié)點(diǎn)是紅色的输硝，則它的子節(jié)點(diǎn)必須是黑色的。
（5）從一個(gè)節(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)，確保沒有一條路徑會(huì)比其他路徑長出倆倍愉粤。因而砾医，紅黑樹是相對(duì)是接近平衡的二叉樹。

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

TreeMap遍歷方式

遍歷TreeMap的鍵值對(duì)

第一步：根據(jù)entrySet()獲取TreeMap的“鍵值對(duì)”的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ù)一個(gè)雙向鏈表搁嗓。
TreeMap比HashMap與Hashtable慢（尤其在插入芯勘、刪除key-value時(shí)更慢），因?yàn)門reeMap底層采用紅黑樹來管理鍵值對(duì)腺逛。
適用場景：
一般的應(yīng)用場景荷愕，盡可能多考慮使用HashMap，因?yàn)槠錇榭焖俨樵冊O(shè)計(jì)的棍矛。
如果需要特定的排序時(shí)安疗，考慮使用TreeMap。
如果僅僅需要插入的順序時(shí)够委，考慮使用LinkedHashMap荐类。

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

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