HashMap TreeMap LinkedListHashMap源碼淺析

Map和Collection是不同的一套接口窟她；也是常用的一種類(lèi)型欣喧。
類(lèi)圖如下

image.png

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

This interface takes the place of the Dictionary class, which was a totally abstract class rather than an interface.

The Map interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map's collection views return their elements. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.

Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals and hashCode methods are no longer well defined on such a map.

All general-purpose map implementation classes should provide two "standard" constructors: a void (no arguments) constructor which creates an empty map, and a constructor with a single argument of type Map, which creates a new map with the same key-value mappings as its argument. In effect, the latter constructor allows the user to copy any map, producing an equivalent map of the desired class. There is no way to enforce this recommendation (as interfaces cannot contain constructors) but all of the general-purpose map implementations in the JDK comply.

The "destructive" methods contained in this interface, that is, the methods that modify the map on which they operate, are specified to throw UnsupportedOperationException if this map does not support the operation. If this is the case, these methods may, but are not required to, throw an UnsupportedOperationException if the invocation would have no effect on the map. For example, invoking the putAll(Map) method on an unmodifiable map may, but is not required to, throw the exception if the map whose mappings are to be "superimposed" is empty.

Some map implementations have restrictions on the keys and values they may contain. For example, some implementations prohibit null keys and values, and some have restrictions on the types of their keys. Attempting to insert an ineligible key or value throws an unchecked exception, typically NullPointerException or ClassCastException. Attempting to query the presence of an ineligible key or value may throw an exception, or it may simply return false; some implementations will exhibit the former behavior and some will exhibit the latter. More generally, attempting an operation on an ineligible key or value whose completion would not result in the insertion of an ineligible element into the map may throw an exception or it may succeed, at the option of the implementation. Such exceptions are marked as "optional" in the specification for this interface.

Many methods in Collections Framework interfaces are defined in terms of the equals method. For example, the specification for the containsKey(Object key) method says: "returns true if and only if this map contains a mapping for a key k such that (key==null ? k==null : key.equals(k))." This specification should not be construed to imply that invoking Map.containsKey with a non-null argument key will cause key.equals(k) to be invoked for any key k. Implementations are free to implement optimizations whereby the equals invocation is avoided, for example, by first comparing the hash codes of the two keys. (The Object.hashCode() specification guarantees that two objects with unequal hash codes cannot be equal.) More generally, implementations of the various Collections Framework interfaces are free to take advantage of the specified behavior of underlying Objectmethods wherever the implementor deems it appropriate.

Some map operations which perform recursive traversal of the map may fail with an exception for self-referential instances where the map directly or indirectly contains itself. This includes the clone(), equals(), hashCode() and toString() methods. Implementations may optionally handle the self-referential scenario, however most current implementations do not do so.

Map接口代表鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)，用于替代Dictionary類(lèi)荒给，java.util確實(shí)有這么一個(gè)類(lèi)倦炒，基于這個(gè)類(lèi)實(shí)現(xiàn)了HashTable显沈，不過(guò)這兩個(gè)類(lèi)目前都是廢棄的，不要使用逢唤。

Map 可以有三個(gè)觀察視角拉讯，entry（鍵值對(duì)）的set，key的set鳖藕，value的collection魔慷。

Map默認(rèn)至少有兩個(gè)構(gòu)造函數(shù)，一個(gè)是空參數(shù)著恩，一個(gè)是使用其他map作為參數(shù)院尔，相當(dāng)于構(gòu)造器淺拷貝。

有的Map沒(méi)有實(shí)現(xiàn)所有的操作喉誊，會(huì)拋出UnsupportOperationException邀摆。

有的Map會(huì)對(duì)key和value的類(lèi)型做限制，拋出NullPointerException或者CastClassException

有一些Map的方法伍茄，依賴(lài)于equals方法栋盹，比如containKey，這些依賴(lài)不是強(qiáng)制的幻林，依賴(lài)于遵守一定的設(shè)置。

還有一些Map的方法音念，會(huì)進(jìn)行遞歸遍歷沪饺，所以Map直接或間接引用自己可能會(huì)產(chǎn)生異常，比如方法clone闷愤，equals整葡，hashCode，tostring讥脐。

AbstractMap 定義了兩個(gè)域遭居，一個(gè)是keyset，一個(gè)是value的collection旬渠，使用迭代器把一些基本功能實(shí)現(xiàn)了俱萍。最后提供了一個(gè)靜態(tài)內(nèi)部類(lèi), 不可變的Entry

public static class SimpleImmutableEntry<K,V>
        implements Entry<K,V>, java.io.Serializable

HashMap

HashMap 是基于哈希散列表的實(shí)現(xiàn)：

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

If many mappings are to be stored in a HashMap instance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than letting it perform automatic rehashing as needed to grow the table. Note that using many keys with the same hashCode() is a sure way to slow down performance of any hash table. To ameliorate impact, when keys are Comparable, this class may use comparison order among keys to help break ties.

Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

   Map m = Collections.synchronizedMap(new HashMap(...));

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

數(shù)據(jù)都保存在Node[] 數(shù)組中， 數(shù)組是Entry的實(shí)現(xiàn)告丢，并且數(shù)組的大小適中是2的次方枪蘑，這為hash算法提供了一個(gè)良好的空間。

transient Node<K,V>[] table;

/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 */
transient Set<Map.Entry<K,V>> entrySet;

static class Node<K,V> implements Map.Entry<K,V> {

查看hash是如何發(fā)生，可以查看put和remove方法岳颇，存放的時(shí)候要判斷是否碰撞照捡，遇到了碰撞就按照鏈表進(jìn)行處理，但是如果鏈表長(zhǎng)度達(dá)到8,就轉(zhuǎn)成紅黑樹(shù)话侧。 如果存放空間超過(guò)容量因子栗精，默認(rèn)是75%，就擴(kuò)容瞻鹏。

因?yàn)樘珴M(mǎn)悲立，就會(huì)太容易碰撞。

詳細(xì)可參考 ：http://www.importnew.com/18633.html

LinekdHashMap

linkedhash是在ArrayHashMap的基礎(chǔ)上乙漓，給每個(gè)Entry進(jìn)行了擴(kuò)展级历，使得Entry形成了一個(gè)雙向鏈表。而底層依然用數(shù)組進(jìn)行保存叭披，但是在使用迭代器進(jìn)行遍歷的時(shí)候寥殖，是根據(jù)鏈表進(jìn)行遍歷，因此遍歷的性能不太受到負(fù)載因子影響涩蜘。

    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
   /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;    

另外LinkedHashMap 嚼贡，是通過(guò)模板方式模式 和重載的方式，維護(hù)Entry的鏈表關(guān)系同诫，默認(rèn)情況下粤策，新增節(jié)點(diǎn)都是添加到tail，刪除節(jié)點(diǎn)都是误窖，斷開(kāi)節(jié)點(diǎn)叮盘。代碼如下：

//HashMap.java
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict){
  ....
     if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
  }
final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
 ...
  afterNodeRemoval(node);
....
 }
 
 
//LinkedHashMap.java
void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }

afterNodeRemoval和afterNodeInsertion這兩個(gè)方法維護(hù)了連接關(guān)系。

初次之外霹俺，LinkedListMap還有一種順序模式柔吼，就是訪問(wèn)順序，就是訪問(wèn)操作的元素丙唧，就是被訪問(wèn)的元素愈魏。被訪問(wèn)的元素放到鏈表的最后，因此最近訪問(wèn)的元素想际，是鏈表的末尾培漏。

這些操作屬于訪問(wèn)操作，其他操作都不是訪問(wèn)操作：

• put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent, or merge
• replace 如果元素被替換了就算訪問(wèn)
• putAll 如果發(fā)生了元素訪問(wèn)（key存在）

有一個(gè)標(biāo)志位來(lái)設(shè)置模式

final boolean accessOrder
true: 訪問(wèn)順序
false： 插入順序

因此在構(gòu)造器內(nèi)設(shè)置好模式胡本，在調(diào)用訪問(wèn)操作時(shí)牌柄，調(diào)用afterNodeAccess，保證訪問(wèn)順序侧甫。

TreeMap

TreeMap 是按照比較器(comparator)的比較順序友鼻，遍歷所有的entry傻昙，這是TreeMap的特點(diǎn)。 如果在構(gòu)造器中不提供Comparator彩扔，那么默認(rèn)假定Key一定要實(shí)現(xiàn)Comparable妆档，否則會(huì)拋CastClassException

 @SuppressWarnings("unchecked")
    final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
 }

可以注意到，TreeMap的內(nèi)部類(lèi)非常多虫碉，前面在HashMap的內(nèi)部類(lèi)比TreeNode少一些贾惦，一般那內(nèi)部類(lèi)是HahsMap的Entry實(shí)現(xiàn)（Node，TreeNode）敦捧，三個(gè)視角(key,value,entry)的 集合類(lèi)须板，分別的迭代器，分別的spliterator的迭代器兢卵。

//三個(gè)視角的容器
Values
EntrySet
KeySet
//三個(gè)視角的迭代器
PrivateEntryIterator // 抽象類(lèi)习瑰，父類(lèi)
EntryIterator
ValueIterator
KeyIterator

DescendingKeyIterator
NavigableSubMap
AscendingSubMap
DescendingSubMap
SubMap
Entry
TreeMapSpliterator

KeySpliterator
DescendingKeySpliterator
ValueSpliterator
EntrySpliterator

這里多出了DescendingKeyIterator，降序迭代器秽荤，還有一堆subMap甜奄。

則可以可以看TreeMap實(shí)現(xiàn)的接口，SortedMap , NavigableMap 的設(shè)計(jì)要求和目標(biāo)窃款。

SortedMap

Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with equals if the sorted map is to correctly implement the Map interface.
sorted map 的順序 必須 和equals的一致课兄，如果sorted map 正確的實(shí)現(xiàn)了Map的接口。

(See the Comparable interface or Comparator interface for a precise definition of consistent with equals.)
（Comparable/Comparator的接口是精確定義了要和equals一致的）

This is so because the Map interface is defined in terms of the equals operation,
這是因?yàn)镸ap接口是按照equals操作來(lái)定義的晨继，
but a sorted map performs all key comparisons using its compareTo (or compare) method, 
但 sorted map 都是使用compareTo來(lái)執(zhí)行key的比較操作烟阐。
so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal.
所以?xún)蓚€(gè)key使用比較方法認(rèn)為是相等的，從sorted map的角度上說(shuō)紊扬，是相當(dāng)?shù)摹?
The behavior of a tree map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.
tree map的行為是明確定義的蜒茄，即使它的順序和equals方法不一致；這樣的話他只是不遵循Map接口的一般約定餐屎。

概括的說(shuō)檀葛，就是sortedmap本身是按照比較來(lái)排序，最好也遵循equals的操作啤挎，如果不遵守也只是破壞了map接口的約定驻谆，sotedmap本身沒(méi)有這種約定卵凑∏炱福可以參考https://stackoverflow.com/questions/46912097/case-insensitive-comparator-breaks-my-treemap

java.util.SortedMap#comparator
//返回部分map
java.util.SortedMap#subMap  //半開(kāi)  [from, end)
java.util.SortedMap#headMap  //  [開(kāi)頭，  toKey)
java.util.SortedMap#tailMap  // (fromKey,結(jié)尾]
//頭和尾
java.util.SortedMap#firstKey
java.util.SortedMap#lastKey
//三個(gè)視角
java.util.SortedMap#keySet
java.util.SortedMap#values
java.util.SortedMap#entrySet

subMap返回的是 截取的map勺卢。

再看看 NavigableMap伙判，這個(gè)接口的目標(biāo)是更多訪問(wèn)API，得到最接近搜索的目標(biāo)的結(jié)果黑忱。

// 小于目標(biāo)值的 最大的Key或Entry  
// max( i < target )
java.util.NavigableMap#lowerEntry
java.util.NavigableMap#lowerKey   
//  max( i <= target)
java.util.NavigableMap#floorEntry
java.util.NavigableMap#floorKey
//  min( i >= target);
java.util.NavigableMap#ceilingEntry
java.util.NavigableMap#ceilingKey
// min(i > target);
java.util.NavigableMap#higherEntry
java.util.NavigableMap#higherKey

// 首尾Entry
java.util.NavigableMap#firstEntry
java.util.NavigableMap#lastEntry
// 返回頭尾宴抚，并移除勒魔，有點(diǎn)像隊(duì)列操作
java.util.NavigableMap#pollFirstEntry
java.util.NavigableMap#pollLastEntry
// 降序的map，即和默認(rèn)順序相反
java.util.NavigableMap#descendingMap
// 返回Key的Set菇曲，不過(guò)這個(gè)返回是實(shí)現(xiàn)NavigableSet接口冠绢，即排序的，可搜索的
java.util.NavigableMap#navigableKeySet
// 降序的KeySet
java.util.NavigableMap#descendingKeySet
// submap 可以要求開(kāi)區(qū)間還是閉區(qū)間常潮。
java.util.NavigableMap#subMap(K, boolean, K, boolean)

// 小于某個(gè)值的Key組成的map弟胀，可以設(shè)置開(kāi)閉區(qū)間， 必須返回navigableMap
java.util.NavigableMap#headMap(K, boolean)
java.util.NavigableMap#tailMap(K, boolean)
// 來(lái)自SortedMap接口
java.util.NavigableMap#subMap(K, K)
java.util.NavigableMap#headMap(K)
java.util.NavigableMap#tailMap(K)

再回來(lái)看TreeMap的實(shí)現(xiàn)喊式，這些subMap的內(nèi)部類(lèi)就是提供給這些接口使用

看一下數(shù)據(jù)結(jié)構(gòu)孵户，先看成員變量：

private transient Entry<K,V> root;
   // Red-black mechanics

    private static final boolean RED   = false;
    private static final boolean BLACK = true;

TreeMap是使用紅黑樹(shù)實(shí)現(xiàn)的，紅黑樹(shù)是自平衡的二叉查找樹(shù)岔留，因此迭代的過(guò)程夏哭，就是遍歷樹(shù)的過(guò)程。那么比較大小的時(shí)候就使用比較器比較献联。另外前面HashMap里不是實(shí)現(xiàn)了一個(gè)紅黑樹(shù)的Node么竖配，是不是可以拿過(guò)來(lái)用呢，不可以哦酱固，這里只需要樹(shù)械念，不需要維護(hù)一個(gè)Hash桶，因此這里又實(shí)現(xiàn)了一遍运悲。

插入刪除查找龄减，這些操作都是紅黑樹(shù)基本操作瓣铣，那么我們看一下navigateMap里的那么操作是如何實(shí)現(xiàn)的：

    /**
     * @since 1.6
     */
    public Map.Entry<K,V> firstEntry() {
        return exportEntry(getFirstEntry());
    }

    /**
     * @since 1.6
     */
    public Map.Entry<K,V> lastEntry() {
        return exportEntry(getLastEntry());
    }
    
      static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
        return (e == null) ? null :
            new AbstractMap.SimpleImmutableEntry<>(e);
    }

找到相應(yīng)的Entry页屠，并返回一個(gè)不可變的Entry，為了取得那一時(shí)刻的快照, 不可以修改淳衙。所以修改入口只能是get 之后進(jìn)行修改, 或者迭代器獲得的進(jìn)行修改署隘。Navigate的都不可以修改宠能，那是一個(gè)導(dǎo)航視角，只讀磁餐。

subMap,tailMap, headMap的實(shí)現(xiàn)借助于內(nèi)部類(lèi)AscendingSubMap, 使用委托進(jìn)行操作违崇，通過(guò)上下界控制邊界, AscendingSubMap繼承NavigableSubMap；

abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
        implements NavigableMap<K,V>, java.io.Serializable {
        private static final long serialVersionUID = -2102997345730753016L;
        /**
         * The backing map.
         */
        final TreeMap<K,V> m;

        /**
         * Endpoints are represented as triples (fromStart, lo,
         * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
         * true, then the low (absolute) bound is the start of the
         * backing map, and the other values are ignored. Otherwise,
         * if loInclusive is true, lo is the inclusive bound, else lo
         * is the exclusive bound. Similarly for the upper bound.
         */
        final K lo, hi;
        final boolean fromStart, toEnd;
        final boolean loInclusive, hiInclusive;

大體就是這樣诊霹。

小結(jié)：

1. HashMap 是2次冪大小的數(shù)組存放Entry羞延，利用HashCode >>> 16 ^ HashCode 并按照桶 求模存放，碰撞時(shí)脾还，按照鏈表存放伴箩，鏈表長(zhǎng)度超過(guò)8，按照紅黑樹(shù)處理鄙漏。
2. LinkedHashMap嗤谚，繼承HashMap棺蛛，在Entry的基礎(chǔ)上加上雙向鏈表，遍歷時(shí)不太受負(fù)載因子的影響巩步，可以支持插入順序和訪問(wèn)順序兩種模式
3. TreeMap是紅黑樹(shù)實(shí)現(xiàn)旁赊，可以自定義comparator，元素順序按照比較順序椅野，提供大量的導(dǎo)航訪問(wèn)API彤恶。

因此一般使用HashMap就夠了，如果要求最近訪問(wèn)鳄橘，插入順序声离，可以使用LinkedHashMap，如果要自定義順序瘫怜，還要各種訪問(wèn)可以選TreeMap术徊。

END