Java集合源碼分析07----Map集合

目錄

Map集合綜述

Map接口

SortedMap接口

NavigableMap接口

Dictionary抽象類

AbstractMap抽象類

總結

--------------------------分析基于jdk1.8.

Map集合綜述

    Map接口是Map繼承體系中的根接口，與Collection集合沒有必然的聯系。Map集合存儲的是鍵-值映射（鍵-值對）。在Map中鍵與值是一一對應的，也就是一個鍵隻對應一個值。是以不能存在相同的鍵，值是可以一樣的。是以來通過鍵來查找值。常見的Map實作類有TreeMap,HashMap,IdentityHashMap,WeakHashMap,Hashtable,LinkedHashMap等。

    其中抽象類AbstractMap繼承接口Map，實作了Map接口中大部分的方法，而Map的大部分的實作類都直接繼承了AbstractMap,這樣節省了實作類大部分了重複的代碼。

Map接口

    Map提供的是鍵與值的映射關系，Map中不能包含重複的鍵，每個鍵最多有一個值。Map接口出現是為了替換抽象類Dictionary。

    Map接口提供了三種集合Collection視圖：鍵集合，值集合，鍵-值映射集合。映射的順序就是映射集合視圖上疊代器傳回元素的順序，有些實作類能確定順序，比如TreeMap。有些實作類不能保證順序，如HashMap。

    需要注意的是：将可變的對象作為映射鍵時要小心，比如鍵不能是Map類型，但是值可以是Map類型。

//傳回Map中鍵值對映射的數量.
int size();
//如果Map不包含任何的鍵值對映射，傳回true.
boolean isEmpty();
//如果Map中存在指定的鍵key，傳回true.
boolean containsKey(Object key);
//如果Map包含指定的值value，傳回true.
boolean containsValue(Object value);
//傳回指定的鍵所映射的值.
V get(Object key);
//将鍵與對應的值映射關系插入到Map中.
V put(K key, V value);
//從Map中移除鍵的映射關系.
V remove(Object key);
//批量操作
//将指定的Map中所有映射關系添加此映射中.
void putAll(Map<? extends K, ? extends V> m);
//從Map中移除所有的映射關系.
void clear();
//視圖檢視
//傳回此Map中所有鍵的Set視圖.
Set<K> keySet();
//傳回所有包含在Map中所有值的Collection視圖.
Collection<V> values();
//傳回此Map中鍵值映射關系的Set視圖.
Set<Map.Entry<K, V>> entrySet();
//此Map是否與指定的對象相等.
boolean equals(Object o);
//傳回此Map的HashCode值.
int hashCode();
//傳回Map中與key關聯的值，如果在映射中沒有找到此鍵，将傳回defaultValue.
default V getOrDefault(Object key, V defaultValue) {}
//對這個Map中所有的鍵/值執行action.
default void forEach(BiConsumer<? super K, ? super V> action) {}
//用鍵值對在給指定函數上的執行結果替換鍵值對的值.
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {}
//鍵沒有映射關系情況下與指定的值進行關聯.
default V putIfAbsent(K key, V value) {}
//當指定的key與指定值value關聯的情況下，移除鍵值對.
default boolean remove(Object key, Object value) {}
//當key與oldValue關聯情況下，用newValue替換oldValue與key進行關聯.
default boolean replace(K key, V oldValue, V newValue) {}
//Map中存在key的映射關系時，将key與value進行關聯.傳回key之前關聯的值
default V replace(K key, V value) {}
//如果指定key不存在映射關系，根據key計算出的函數值，将key與函數值進行關聯.
default V computeIfAbsent(K key,Function<? super K, ? extends V> mappingFunction) {}
//如果鍵對應的值存在且非空，根據key和key映射的值計算出的函數值，函數值不為空時，将key與函數值關聯.
default V computeIfPresent(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) {}
//與computeIfPresent差別是，key不存在映射時，并且函數值不為null時，會将key與函數值進行關聯.
default V compute(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) {}
//如key不存在映射時，指定value不為null時，将key與value關聯，
//否則key的映射值與指定值value的函數值不為null時，将key與函數值關聯
default V merge(K key, V value,BiFunction<? super V, ? super V, ? extends V> remappingFunction) {}
           

SortedMap接口

SortedMap直接繼承了Map接口，是有序的鍵-值映射（針對鍵進行排序）。

SortedMap的排序方式是通過鍵的自然順序或者建立SortedMap時指定的Comparator。在鍵集，值集，鍵-值映射集疊代時将會展現出這種排序。插入SortedMap中的所有鍵都必須實作Comparable接口（或被指定比較器接受）。

所有SortedMap的實作類都應該提供4個标準的構造方法（建議但不強制）：

1）無參構造方法：建立的是空的有序映射，按照鍵的自然序進行排序。

2）指定Comparator類型參數的構造方法：建立的是空的有序映射，根據指定Comparator進行排序。

3）帶有Map類型參數的有參構造方法：建立一個與參數Map相同的鍵-值映射關系的有序映射。按照鍵的自然順序進行排序。

4）帶有SortedMap類型參數的有參構造方法：建立一個與參數SortedMap相同的鍵-值關系的和排序的有序映射。

//傳回對此映射進行排序的Comparator對象，映射使用鍵的自然序時，将傳回null.
Comparator<? super K> comparator();
//傳回此映射的部分視圖，其鍵值的方位從fromKey(包含)到toKey(不包含)
SortedMap<K,V> subMap(K fromKey, K toKey);
//傳回此映射中鍵值小于toKey(不包含)的部分視圖
SortedMap<K,V> headMap(K toKey);
//傳回此映射中鍵值大于等于fromKey的部分視圖.
SortedMap<K,V> tailMap(K fromKey);
//傳回映射中的第一個鍵
K firstKey();
//傳回映射中的最後一個鍵
K lastKey();
//傳回映射中的鍵集合.
Set<K> keySet();
//傳回映射中的值集合
Collection<V> values();
//傳回映射中鍵-值映射集合
Set<Map.Entry<K, V>> entrySet();
           

NavigableMap接口

NavigableMap接口繼承自SortedMap，具有針對搜尋目标傳回最接近比對項的導航方法，可以通過鍵的升序和降序通路和周遊NavigableMap.Navigable接口包含了以下幾類方法：

1）擷取指定範圍的鍵-值映射（對）的方法：

     lowerEntry、floorEntry、ceilingEntry 和 higherEntry 方法，分别傳回與小于、小于等于、大于等于、大于給定鍵的鍵關聯的 Map.Entry 對象。

2）操作指定的鍵-值映射（對）的方法：

    firstEntry、pollFirstEntry、lastEntry 和 pollLastEntry 方法，傳回和/或移除最小和最大的映射關系（如果存在），否則傳回 null。

3）擷取指定的鍵的方法：

   lowerKey、floorKey、ceilingKey 和 higherKey 方法，分别傳回與小于、小于等于、大于等于、大于給定鍵的鍵。

4）檢視鍵-值的部分視圖：

subMap(K fromKey, K toKey)/subMap(K fromKey, boolean fromInclusive,K toKey,boolean toInclusive)、headMap(K toKey)/headMap(K toKey, boolean inclusive)、tailMap(K fromKey)/subMap(K fromKey, K toKey)方法，分别傳回fromKey到toKey之間（設定是否包含），小于或者等于(設定是否包含)toKey，大于或者等于(設定是否包含)toKey的鍵-值視圖。

5）正逆序的鍵集/鍵-值集映射：

navigableKeySet、descendingKeySet、descendingMap方法，分别是正序鍵集、逆序鍵集，以及逆序鍵-值映射。

//傳回小于指定鍵的最大鍵對應的鍵-值映射，如果不存在這樣的鍵，傳回null
Map.Entry<K,V> lowerEntry(K key);
//傳回小于指定鍵的最大鍵，如果不存在這樣的鍵，傳回null.
K lowerKey(K key);
//傳回小于等于指定鍵的最大鍵對應的鍵-值映射，如果不存在這樣的鍵，傳回null.
Map.Entry<K,V> floorEntry(K key);
//傳回小于等于指定鍵的最大鍵，如果不存在這樣的鍵，傳回null.
K floorKey(K key);
//傳回大于等于指定鍵的最小鍵對應的鍵-值映射，如果不存在這樣的鍵，傳回null.
Map.Entry<K,V> ceilingEntry(K key);
//傳回大于等于指定鍵的最小鍵,如果不存在這樣的鍵，傳回null.
K ceilingKey(K key);
//傳回大于指定鍵的最小鍵對應的鍵-值映射，如果不存在這樣的鍵，傳回null.
Map.Entry<K,V> higherEntry(K key);
//傳回大于指定鍵的最小鍵，如果不存在這樣的鍵，傳回null.
K higherKey(K key);
//傳回最小鍵對應的鍵-值映射，如果map為空，傳回null.
Map.Entry<K,V> firstEntry();
//傳回最大鍵對應的鍵-值映射，如果map為空，傳回null.
Map.Entry<K,V> lastEntry();
//移除并傳回最小鍵對應的鍵-值映射，如果map為空，傳回null.
Map.Entry<K,V> pollFirstEntry();
//移除并傳回最大鍵對應的鍵-值映射，如果map為空，傳回null.
Map.Entry<K,V> pollLastEntry();
//傳回map中鍵-值逆序的視圖.
NavigableMap<K,V> descendingMap();
//傳回map中所有鍵的NavigableSet視圖。
NavigableSet<K> navigableKeySet();
//傳回map中所有鍵的逆序的NavigableSet視圖.
NavigableSet<K> descendingKeySet();
//傳回從fromkey到tokey之間的map的部分視圖，并且分别指定了是否fromkey和tokey
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,K toKey,boolean toInclusive);
//傳回小于或者等于(由inclusive指定，true時包含)tokey的map的部分視圖.
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
//傳回大于或者等于(由inclusive指定，true時包含)tokey的map的部分視圖.
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
//等價于subMap(fromKey, true, toKey, false)
SortedMap<K,V> subMap(K fromKey, K toKey);
//等價于headMap(toKey, false)
SortedMap<K,V> headMap(K toKey);
//等價于tailMap(fromKey, true)
SortedMap<K,V> tailMap(K fromKey);
           

Dictionary抽象類

Dictionary是一些類的抽象父類，比如Hashtable，存儲的是鍵-值映射關系。每個鍵最多與一個值關聯。

需要注意的是：Dictionary已經過時，新實作的類應該繼承Map接口。

//傳回此Dictionary中鍵值對數量
abstract public int size();
//如果此Dictionary中不存在鍵-值對映射，傳回true.
abstract public boolean isEmpty();
//傳回周遊Dictionary鍵的Enumeration
abstract public Enumeration<K> keys();
//傳回周遊Dictionary值的Enumeration
abstract public Enumeration<V> elements();
//傳回此Dictionary中指定鍵對應的值
abstract public V get(Object key);
//将指定鍵和指定值映射添加到Dictionary
abstract public V put(K key, V value);
//從Dictionary中移除指定鍵對應鍵-值映射
abstract public V remove(Object key);
           

AbstractMap抽象類

AbstractMap抽象類提供了Map接口大部分實作，減少了Map實作類的重複代碼。大部分的實作類如TreeMap,HashMap,IdentityHashMap,WeakHashMap,Hashtable,LinkedHashMap直接繼承AbstractMap抽象類。

//傳回鍵集的大小
public int size() {}
//傳回鍵集是否為空
public boolean isEmpty() {}
//如果映射map中包含指定的值，傳回true.
public boolean containsValue(Object value) {}
//如果映射map中包含鍵，傳回true.
public boolean containsKey(Object key) {}
//傳回指定鍵對應的值
public V get(Object key) {}
//将指定的鍵-值映射添加到此map中
public V put(K key, V value) {}
//從此map中移除指定的鍵對應的鍵-值映射
public V remove(Object key) {}
//将指定的映射集添加到此映射map中
public void putAll(Map<? extends K, ? extends V> m) {}
//清空鍵集,底層調用entrySet().clear()
public void clear() {}
//傳回此map的鍵集
public Set<K> keySet() {}
//傳回此map的值集
public Collection<V> values() {}
//此map是否與指定對象相等
public boolean equals(Object o) {}
//傳回此map的hashCode值
public int hashCode() {}
//map的字元串表示
public String toString() {}
//傳回AbstractMap執行個體的淺度複制
protected Object clone() {}
           

關于AbstractMap的幾個實作類說明：

1）TreeMap：底層以紅黑數實作，是一個有序的鍵-值集合，不是同步的。存入TreeMap中元素要實作Comparable接口，可以通過兩種方式對元素進行排序：第一種是自然順序，第二種是建立TreeMap時指定Comparator比較器。是一種帶有subMap()方法的Map,傳回鍵-值映射集的子視圖。

2）HashMap:取代了Hashtable，底層以散清單（哈希表）資料結構實作（數組+連結清單），内部定義了一個數組，計算元素的哈希位址轉換成存放的索引，如果有沖突，使用散列連結清單的形式（單連結清單），将相同的哈希值的元素串起來。插入和查詢鍵值對的開銷固定，可以通過構造器設定容量和負載因子，以調整容器的性能。

3）LinkedHashMap:是HashMap的子類，擷取鍵值對的順序是其插入的次序或者是最近最少使用（LRU）的次序，底層以散清單（哈希表）實作（數組+連結清單），并且不是同步的，多個線程通路時，需要進行外部同步。LinkedHashMap允許存儲null值和null鍵。與HashMap相比，使用雙向連結清單來維護内部元素的順序，是以疊代通路速度較快。

4）IdentityHashMap:底層以散清單（哈希表）資料結構實作（數組+連結清單），但是鍵的散列值不是通過hashCode函數計算的，而是通過System.identityHashCode方法計算的，這是Object.hashCode方法根據對象的記憶體位址來計算散列碼時使用的方法。比較鍵（和值）時使用的是引用相等，而不是對象的相等性。也就是比較是不是同一個對象，在代碼裡面比較的是"=="，而不是equals。

5）WeakHashMap:底層資料結構與HashMap是一緻的，以散清單（哈希表）實作（數組+連結清單），鍵和值都可以是null。當WeakHashMap中某個鍵不再正常使用時，會被移除。對于給定的鍵，即使存在映射關系并不阻止垃圾回收器對鍵的回收。

6）EnumMap：是一個鍵為枚舉類型的映射，底層是對象數組，數組的下表索引是根據Map中key直接擷取的，即枚舉中ordinal值。

不是繼承AbstractMap的Map實作類：

7）Hashtable：底層資料結構與HashMap是一緻的，以散清單（哈希表）實作（數組+連結清單），鍵和值不能是null，Hashtable是同步的（線程 安全）。

總結

1）當在Map鍵集視圖上調用疊代器remove方法時，實際上回在Map删除這個鍵對應的值。但在鍵集上使用add方法會抛出UnsupportedOperationException異常。

2）HashMap，IdentityHashMap，LinkedHashMap等映射集底層都是以散清單（哈希表）實作的。java中散清單是通過數組+連結清單的形式實作的，每個散清單稱為桶（bucket），查找散清單中指定對象的位置，就需要計算對象的散列碼，然後與桶總數取餘數，所得到的結果就是儲存這個對象在桶中的索引。如果在桶中已經存在對象，就将要入存入對象和已存在的對象串起來（從連結清單的頭部插入），在桶中存儲的每一項就是一個連結清單。

3）當存儲在映射集中的元素自己實作hashCode方法時，需要與equals方法相容。如果a.equals(b)為true時，a與b必須有相同的散列碼。Java中對于equals方法與hashCode方法規定：a.相等（相同）的對象必須有相同的散列碼（哈希碼）;b.兩個對象的hashCode相同，它們并不一定是同一個對象。