今天要分享的Java集合是Map，主要是針對它的常見實現類HashMap進行講解（jdk1.8）

什麼是Map核心方法源碼剖析1.文檔注釋2.成員變量3.構造方法4.put()5.get()

什麼是Map

  Map是非線性數據結構的主要實現，用來存放一組鍵-值型數據，我們稱之為散列表。在其他語言中，也被稱為字典。
  HashMap是一個非常重要的數據結構，在我們的項目中有大量的運用，或充當參數，或用於緩存。而在面試中，HashMap也幾乎成為了一個“必考項”，所以今天我們就從源碼的角度，對這種數據結構進行剖析。
  首先我們先就使用上，給出幾個先入為主的概念。有了概念，再去看源碼就會容易很多。
  HashMap的查詢速度是O(1)，它為什麼會這麼快呢？因為散列表利用的是數組支持按下標隨機訪問的特性，所以散列表其實是對數組的一種擴充，是由數組演化而來的。
  我們來舉一個例子，A班一共有64個學生，學號是唯一的9位數。在一場期末考試中，如果我們想知道一個學生的成績，那麼就可以通過學號來定位學生，然後獲取所有的考試信息。為了便於存儲和查詢，我們將學生的學號，通過編碼映射到下標從1-63的數組中。

  將例子和HashMap中的概念對應起來：學號就是鍵(key),也叫做關鍵字，學生的信息就是值,將學號轉換成數組下標的映射方法就叫做散列函數（散列函數是散列表的核心），散列函數計算得到的值就叫作散列值，也叫做Hash值或哈希值。
  如果這個班擴充到了100個人，存儲成績的方法不變，那麼一定會有至少2個同學的成績經過散列函數計算出的值相同。這種現象叫做散列衝突。為了解決散列衝突，不出現數據相互覆蓋的情況，散列表會將這兩個學生的信息組成一個鏈表，存儲在數組中，從而保存多個同學的考試信息，這種解決散列衝突方法叫做鏈表法。（解決散列衝突的方法不止這一種，還有其他的方法，比如線性探測法）。
  對這些只要有一個大致的印象就可以，接下來我們會通過剖析源碼的方式，對散列表的工作原理進行深入的分析。

核心方法源碼剖析

  這一部分，選取了HashMap的一些核心內容進行講解。分別是：文檔注釋,成員變量,構造方法，put()、hash()、get()、remove()。

1.文檔注釋

  permits null values and the null key
  允許存儲null值和null鍵

  The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.
  HashMap近似於Hashtable，除了它不同步並且允許null值

  This class makes no guarantees as to the order of the map
  這個類存儲數據是無序的

  An instance of HashMap has two parameters that affect its performance: initial capacity and load factor
  一個散列表有兩個影響其性能的參數：初始值和負載因子

  so that the hash table has approximately twice the number of buckets
  每次擴容2倍

2.成員變量

 1// 默認容量
 2static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
 3
 4// 最大容量
 5static final int MAXIMUM_CAPACITY = 1 << 30;
 6
 7// 負載因子：已用空間 / 總空間，負載因子平衡了時間和空間成本，如果負載因子過高，導致空間成本減少，查找成本增加，反之亦然。
 8static final float DEFAULT_LOAD_FACTOR = 0.75f;
 9
10// 一個哈系桶存儲的元素超過8，就會將鏈錶轉換成紅黑二叉樹
11static final int TREEIFY_THRESHOLD = 8;
12
13// 一個哈希桶存儲的元素小於6，並且是紅黑二叉樹存儲，那麼此時就會將紅黑二叉樹重新轉換成鏈表
14static final int UNTREEIFY_THRESHOLD = 6;
15
16// 數據量閾值，數據量只有大於這一個值，才會發生樹化
17static final int MIN_TREEIFY_CAPACITY = 64;

3.構造方法

HashMap的構造方法有4種,我們一般不會修改它的負載因子，常用的構造方法只有無參構造和傳入初始值的構造方法。

1HashMap()
2HashMap(int initialCapacity)
3HashMap(int initialCapacity, float loadFactor)
4HashMap(Map<? extends K,? extends V> m)

4.put()

  put中有一個核心的方法，hash()，即散列方法

1public V put(K key, V value) {
2   return putVal(hash(key), key, value, false, true);
3}
4
5static final int hash(Object key) {
6    int h;
7    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
8}

  從hash方法中可以看出，如果傳入的key是null，就會固定的返回0位置。如果傳入的key不是null，那麼就會取key的hashCode方法的返回值，記做h，返回h與h高16位的異或值。
  hash()方法的這段代碼，又被稱為擾動函數，我們可以思考一下，h的值是一個int,它的範圍是[-2147483648, 2147483647],大概包含了40億的映射空間。如果直接存到內存中，肯定是存不下的，而且HashMap的初始值只有16，那麼我們就需要將h映射到這16個哈希桶中，可以直接取模，但是這樣的效率不是很高，所以這裡jdk使用了位與的方法，代碼抽象如下：

1private int getIndex(int length, int h){
2    return h & (length - 1);
3}

  這裡可以解釋一下，為什麼HashMap要求初始值是2的整次冪？，這樣length – 1正好相當於一個低位掩碼，只截取了低位的值.

  但是這裡有一個問題，即使我們的散列函數設計的再鬆散，那麼當屏蔽掉高位，只看低位的時候，還是會容易發生散列衝突。此時擾動函數的價值就體現出來了，它將自身的高半區(32bit)和低半區(32bit)做異或，這樣既增加了隨機性，又將高位的信息變相的參雜了進來。
  這裡的getIndex函數除了位運算性能高，還有一個好處，這裡擴容前後，h的值是不變的，只跟key有關。那麼length – 1的值，只會增加一個高位1，所以經過getIndex計算的值，有一定幾率保持不變（增加的高位，對應h的位是0），擴容時，就會少進行一些數據的搬運，即擴容時數據是黏性的。
  講完了hash()，put()方法的核心思想就差不多講完了，接下來我們將屏蔽一些實現細節，來講一下剩下的putVal()。

 1final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
 2    Node<K,V>[] tab;
 3    Node<K,V> p;
 4     int n, i;
 5    // 當散列表為null的時候，調用resize()進行初始化
 6    if ((tab = table) == null || (n = tab.length) == 0)
 7        n = (tab = resize()).length;
 8    // 如果沒有發生哈希碰撞，直接將元素存進哈希桶
 9    if ((p = tab[i = (n - 1) & hash]) == null)
10        tab[i] = newNode(hash, key, value, null);
11    else {
12        // 如果發生了哈希碰撞
13        Node<K,V> e; K k;
14        if (p.hash == hash &&
15            ((k = p.key) == key || (key != null && key.equals(k))))
16            // 記錄要插入的元素
17            e = p;
18        else if (p instanceof TreeNode)
19            // 如果是樹結構，就調用樹的插入方法
20            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
21        else {
22            // 如果是鏈表結構，就調用鏈表的插入方法
23            for (int binCount = 0; ; ++binCount) {
24                if ((e = p.next) == null) {
25                    p.next = newNode(hash, key, value, null);
26                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
27                        treeifyBin(tab, hash);
28                    break;
29                }
30                if (e.hash == hash &&
31                    ((k = e.key) == key || (key != null && key.equals(k))))
32                    break;
33                p = e;
34            }
35        }
36        if (e != null) { // 覆蓋元素
37            V oldValue = e.value;
38            if (!onlyIfAbsent || oldValue == null)
39                e.value = value;
40            afterNodeAccess(e);
41            return oldValue;
42        }
43    }
44    ++modCount;
45    if (++size > threshold)
46        resize();
47    afterNodeInsertion(evict);
48    return null;
49}    

  這裡的擴容方法是resize()，每次擴容2倍，採用的也是數據搬運的方式，所以我們要儘可能的去避免HashMap的擴容。

5.get()

 1public V get(Object key) {
 2    Node<K,V> e;
 3    return (e = getNode(hash(key), key)) == null ? null : e.value;
 4}
 5
 6final Node<K,V> getNode(int hash, Object key) {
 7    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
 8    if ((tab = table) != null && (n = tab.length) > 0 &&
 9        (first = tab[(n - 1) & hash]) != null) {
10        // 如果在桶的首位就可以找到，那麼就直接返回（提升效率，哈希衝突並不那麼容易出現）
11        if (first.hash == hash && // always check first node
12            ((k = first.key) == key || (key != null && key.equals(k))))
13            return first;
14        if ((e = first.next) != null) {
15            // 根據節點類型，在紅黑二叉樹或者鏈表中查詢數據
16            if (first instanceof TreeNode)
17                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
18            do {
19                if (e.hash == hash &&
20                    ((k = e.key) == key || (key != null && key.equals(k))))
21                    return e;
22            } while ((e = e.next) != null);
23        }
24    }
25    return null;
26}

  get()的思想和put()類似，根據不同的Node類型，進行查找

  最後，期待您的訂閱和點贊，專欄每周都會更新，希望可以和您一起進步，同時也期待您的批評與指正！