Map詳解：

先看圖，便于宏觀了解Map的地位。

Map接口中鍵和值一一映射. 可以通過鍵來獲取值。

• 給定一個鍵和一個值，你可以將該值存儲在一個Map對象. 之后，你可以通過鍵來訪問對應(yīng)的值。
• 當(dāng)訪問的值不存在的時候，方法就會拋出一個NoSuchElementException異常.
• 當(dāng)對象的類型和Map里元素類型不兼容的時候，就會拋出一個 ClassCastException異常。
• 當(dāng)在不允許使用Null對象的Map中使用Null對象，會拋出一個NullPointerException 異常。
• 當(dāng)嘗試修改一個只讀的Map時，會拋出一個UnsupportedOperationException異常。

Map基本操作：

Map 初始化

Map<String, String> map = new HashMap<String, String>();

插入元素

map.put("key1", "value1");

獲取元素

map.get("key1")

移除元素

map.remove("key1");

清空map

map.clear();

hashMap原理：

hashMap是由數(shù)組和鏈表這兩個結(jié)構(gòu)來存儲數(shù)據(jù)。

數(shù)組：存儲區(qū)間是連續(xù)的，占用內(nèi)存嚴(yán)重，故空間復(fù)雜的很大。但數(shù)組的二分查找時間復(fù)雜度小，為O(1)；尋址容易，插入和刪除困難；

鏈表：存儲區(qū)間離散，占用內(nèi)存比較寬松，故空間復(fù)雜度很小，但時間復(fù)雜度很大，達O(N)；尋址困難，插入和刪除容易。

hashMap則結(jié)合了兩者的優(yōu)點，既滿足了尋址，又滿足了操作，為什么呢？關(guān)鍵在于它的存儲結(jié)構(gòu)。

它底層是一個數(shù)組，數(shù)組元素就是一個鏈表形式，見下圖：

Entry: 存儲鍵值對。

Map類在設(shè)計時提供了一個靜態(tài)修飾接口Entry。Entry將鍵值對的對應(yīng)關(guān)系封裝成了鍵值對對象，這樣我們在遍歷Map集合時，就可以從每一個鍵值對對象中獲取相應(yīng)的鍵與值。之所以被修飾成靜態(tài)是為了可以用類名直接調(diào)用。

每次初始化HashMap都會構(gòu)造一個table數(shù)組，而table數(shù)組的元素為Entry節(jié)點，它里面包含了鍵key，值value，下一個節(jié)點next，以及hash值。

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
}

查看hashMap的API發(fā)現(xiàn)，它有4個構(gòu)造函數(shù)：

1、構(gòu)造一個具有默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75) 的空 HashMap。

2、指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap。

3、指定初始容量和默認(rèn)加載因子的空HashMap。

4、構(gòu)造一個映射關(guān)系與指定Map相同的新HashMap。

注意：HashMap使用的是懶加載，構(gòu)造完HashMap對象后，只要不進行put方法插入元素之前，HashMap并不會去初始化或者擴容table。

Put方法：

首先判斷是否是空數(shù)組（table == EMPTY_TABLE），如果是，開始初始化HashMap的table數(shù)據(jù)結(jié)構(gòu)，然后執(zhí)行擴容函數(shù)，如果未指定容量，默認(rèn)是大小為16的表，然后根據(jù)加載因子計算臨界值。什么是加載因子呢？hashMap的大小是一定的，如果不夠存儲了肯定要擴容，那么擴容的依據(jù)是什么呢，什么時候確定要擴容了呢？這個時候就需要引入加載因子這個概念，我們假使依舊使用默認(rèn)大小16，加載因子0.75，那么當(dāng)hashMap的size大于12（16*0.75=12）的時候，那么就會進行擴容。

回來說put方法，如果key是null，調(diào)用putForNullKey方法，保存null與key，這是HashMap允許為null的原因。然后計算hash值和用indexFor計算數(shù)據(jù)存在的位置，然后從i出開始迭代e,找到 key 保存的位置。

上面說到如果數(shù)組擴容，那么每次要怎么擴容呢？

當(dāng)size大于等于某一個閾值thresholdde時候且該table并不是一個空table，因為size 已經(jīng)大于等于閾值了，說明Entry數(shù)量較多，哈希沖突嚴(yán)重，那么若該Entry對應(yīng)的桶不是一個空桶，這個Entry的加入必然會把原來的鏈表拉得更長，因此需要擴容；若對應(yīng)的桶是一個空桶，那么此時沒有必要擴容。如果擴容，table會擴容為原來的兩倍，直到達到數(shù)組的最大長度1<<30（2的30次方）,如果size大于這個值，那么就直接修改為Integer.MAX_VALUE。擴容后的元素hash值對應(yīng)的新的桶位置，然后在指定的桶位置上，創(chuàng)建一個新的Entry。

這里需要說明的是，hashmap是可以存放key和value均為null的，存放在table[0]的位置，此時使用put方法在添加元素的時候，如果在table[0]中已經(jīng)存入key為null的元素則給null賦上新的value值并返回后面的值，否則則初始化null的元素，存入put里面存放的值。

public static void main(String[] args) {
        HashMap hashMap = new HashMap();
        hashMap.put(null, null);
        System.out.println(hashMap.get(null));
        Integer a = (Integer) hashMap.put(null, 1);
        System.out.println(a);
        System.out.println(hashMap.get(null));
}

輸出為：
null
null
1

Get方法：

Get比較好理解，判斷key是不是null，如果是，返回getForNullKey的函數(shù)返回值，如果不是，則在table中去找。

Remove方法：

判斷，如果hashMap的size是0，返回null；找到需要移除的元素的前一個節(jié)點，然后把前驅(qū)節(jié)點的next指向刪除節(jié)點的next節(jié)點，此時當(dāng)前節(jié)點沒有任何引用指向，它在程序結(jié)束之后就會被gc回收。

final Entry<K,V> removeEntryForKey(Object key) {
    		if (size == 0) {
    		    return null;
    		}
   		 int hash = (key == null) ? 0 : hash(key);
   		 int i = indexFor(hash, table.length);
    		Entry<K,V> prev = table[i];
    		Entry<K,V> e = prev;
		 while (e != null) {
        		Entry<K,V> next = e.next;
       		 Object k;
       		 if (e.hash == hash &&
        		    ((k = e.key) == key || (key != null && key.equals(k)))) {
        		    modCount++;
         		   size--;
         		   if (prev == e)
          		      table[i] = next;
         		   else
          		      prev.next = next;
          		  e.recordRemoval(this);
         		   return e;
        		}
        		prev = e;
        		e = next;
   		 }
		 return e;
	}

Map的遍歷：

map這里可以用增強for和迭代器兩種方式遍歷：

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class MapDemo {
    public static void main(String[] args) {
        HashMap<String, String> sets = new HashMap<>();
        sets.put("username", "value1");
        sets.put("password", "value2");
        sets.put("key3", "value3");
        sets.put("key4", "value4");
        sets.put(null,null);
        // 增強for循環(huán) =========== keySet ===================
        for (String s : sets.keySet()) {
            System.out.println(s + ".." + sets.get(s));
        }
        //================== entrySet ======================
        for (Map.Entry<String, String> m : sets.entrySet()) {
            System.out.println(m.getKey() + ".." + m.getValue());
        }
        // 迭代器 ================ keySet ===================
        Iterator it = sets.keySet().iterator();
        while (it.hasNext()) {
            String key = (String) it.next();
            System.out.println(key + ".." + sets.get(key));
        }
        //================== entrySet ======================
        Iterator<Map.Entry<String, String>> iterator = sets.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, String> m = iterator.next();
            System.out.println(m.getKey() + ".." + m.getValue());
        }
    }
}

TreeMap

這里簡要介紹下：TreeMap 是一個有序的key-value集合，繼承于AbstractMap，它是通過紅黑樹實現(xiàn)的。TreeMap 實現(xiàn)了NavigableMap接口，實現(xiàn)了Cloneable接口，實現(xiàn)了java.io.Serializable接口。

TreeMap基于紅黑樹（Red-Black tree）實現(xiàn)。該映射根據(jù)其鍵的自然順序進行排序，或者根據(jù)創(chuàng)建映射時提供的 Comparator 進行排序，具體取決于使用的構(gòu)造方法。TreeMap的基本操作 containsKey、get、put 和 remove 的時間復(fù)雜度是 log(n) 。另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實現(xiàn)關(guān)聯(lián)數(shù)組。它有五個特點如下：

性質(zhì)1：節(jié)點是紅色或黑色。

性質(zhì)2：根節(jié)點是黑色。

性質(zhì)3：每個葉節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的。

性質(zhì)4：每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)。

性質(zhì)5：從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。

詳細(xì)了解請點擊。

LinkedHashMap：

HashMap是無序的，只要不涉及線程安全問題，Map基本都可以使用HashMap。如果我們期待一個有序的Map，這個時候，LinkedHashMap就派上用場了，它雖然增加了時間和空間上的開銷，但是通過維護一個運行于所有條目的雙向鏈表，LinkedHashMap保證了元素迭代的順序，該迭代順序可以是插入順序或者是訪問順序。那么是如何維護的呢，首先參考HashMap的存儲結(jié)構(gòu)，將其中的Entry元素增加一個pre指針和一個next指針，這樣，根據(jù)插入元素的順序?qū)⒏鱾€元素依次連接起來，這樣LinkedHashMap就保證了元素的順序。

繼承自HashMap，實現(xiàn)了Map接口，LinkedHashMap重寫了父類HashMap的get方法，實際在調(diào)用父類getEntry()方法取得查找的元素后，再判斷當(dāng)排序模式accessOrder為true時（即按訪問順序排序），先將當(dāng)前節(jié)點從鏈表中移除，然后再將當(dāng)前節(jié)點插入到鏈表尾部。

實現(xiàn)LRU緩存：

LinkedHashMap和HashMap+LinkedList的操作都是類似的，LRU緩存是我最近看到一個很巧妙的東西，所以推薦大家看一下這篇文章。

對比下Hashmap、Hashtable和ConcurrentHashmap：

第一、Hashmap是線程不安全的，Hashtable和ConcurrentHashMap是線程安全的，在Hashtable中使用了關(guān)鍵字synchronized修飾，加上了同步鎖;ConcurrentHashMap在JDK1.7中采用了鎖分離的技術(shù)，每一個Segment都獨立上鎖，保證了并發(fā)的安全性；每一個Segment元素存儲的是HashEntry數(shù)組+ 鏈表，Segment的大小是一開始就確定的，后期不能再進行擴容，但是單個Segment里面的數(shù)組是可以擴容的。

但是在JDK1.8上則摒棄了Segment的概念，而是直接用Node數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，如下圖所示，并發(fā)控制使用Synchronized和CAS來操作，每一個Node節(jié)點都是用volatile修飾的，整個看起來就像是優(yōu)化過且線程安全的HashMap。

第二、Hashmap是可以存放key和value均為null的，存放在table[0]的位置，此時使用put方法在添加元素的時候，如果在table[0]中已經(jīng)存入key為null的元素則給null賦上新的value值并返回后面的值，否則則初始化null的元素，存入put里面存放的值。Hashtable和ConcurrentHashMap是不可以存放null的key或者value的，原因和并發(fā)狀態(tài)下的操作有關(guān)，當(dāng)在并發(fā)狀態(tài)下執(zhí)行無法分辨是key沒找到的null還是有key值為null，這在多線程里面是模糊不清的，所以不允許put、get為null的元素，如果強行操作就會報空指針異常。

總結(jié)

本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評論