# HashMap 的底層實現原理

# Java 7 實現

HashMap map = new HashMap();

在實例化以後，底層創建了一個長度為 16 的一維數組 Entry[] table
然後可能已經進行很多次 put 了

map.put(key1, value1);
1. 首先，調用 key1 所在類的 hashCode() , 再通過 HashMap 的 hash() 計算出 key1 的哈希值，此哈希值經過某種算法計算後，得到在 Entry[] 數組中所存在的位置 (bucket)
2. 如果此位置上的數據為空
  1. 此時 key1-value1 添加成功 情況一
3. 如果此位置上的數據不為空，意味著此位置上已存在一個或多個數據（以鏈表形式存在），然後比較 key1 和已經存在的一個或多個數據的哈希值，分為兩種情況：
  1. 情況二 ：如果 key1 的哈希值和已經存在的數據的哈希值都不相同
    1. key1-value1 添加成功
  2. 情況三 ：如果 key1 的哈希值和已經存在的某數據 (key2-value2) 的哈希值相同，繼續比較：調用 key1 所在類的 equals(key2)
    1. 如果 equals(key2) 返回 false : 此時 key1-value1 添加成功
    2. 如果 equals(key2) 返回 true : 使用 value1 替換 value2，也就是修改了 value2
      1. e.g. (”Tom”, 22) → (”Tom”, 44); 44 就成新的 value

補充：關於情況二和三：

此時的 key-value1 和原來的數據以鏈表的方式存儲。

在不斷添加的過程中，會涉及到擴容問題，當等於或超出臨界值時（其要存放的位置還要保證是非空），默認的擴容方式：擴容為原來容量的 2 倍，並將原有的數據複制過來。

# JDK8 和 JDK7 在底層實現方面的不同

new HashMap() : 底層沒有創建一個長度為 16 的數組
jdk 8 底層的數組是： Node[] , 而不是 Entry[]
首次調用 put() 時，底層創建長度為 16 的數組
jdk 7 底層結構只有：數組＋鏈表
1. jdk 8 的是：數組＋鏈表＋紅黑樹
  當數組的某一個索引位置上的元素以鏈表形式存在的數據個數 > 8 且當前數組的長度為 > 64 時：
  - 此時此索引上位置上的所有數據改為使用紅黑樹存儲。

# 面試題：

談談你對 HashMap 中的 put/get 方法的認識？如果了解再談談 HashMap 的擴容機制？默認大小是多少？甚麼是負載因子（或者填充比）？甚麼是吞臨界值（threshold

# Java7 擴容

	//Constructor
	public HashMap(){
	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
	}

DEFAULT_INITIAL_CAPACITY = 16
DEFAULT_LOAD_FACTOR = 0.75f

如果要擴容，要重新 hash，分配新的位置（見下圖 line 853)
擴容後，進行 line 857，把 要插入的object 插入進去，過程為：

# Java 8 擴容或轉成紅黑樹

DEFAULT_INITIAL_CAPACITY : HashMap 的默認容量: 16
DEFAULT_LOAD_FACTOR : HashMap 的默認加載因子：0.75
threshold : 擴容的臨界值：容量 * 加載因子：16 * 0.75 = > 12
TREEIFY_THRESHOLD : Bucket 中鏈表的長度大於該默認值，轉化為紅黑樹：8
MIN_TREEIFY_CAPACITY ：桶中的 Node 被樹化時最小的 hash 表容量：64

	public HashMap(){
	this.loadFactor = DEFAULT_LOAD_FACTOR;
	}
	// 對比 java 7 沒有初始化 capacity = 16

# HashpMap 的 put ()

HashMap 的 V put (K key, V value) 裡面的 putVal ()

查看 putVal 的源碼
分了三個情況:
- 情況一：當 table 為空時，需要調用 resize ()
  - 進入 else (line693
- 情況二：當 bucket 裡為空
  - 插入元素成功
- 情況三：當 bucket 裡存在元素
  - 如果和存在的元素相等：情況一：
    - 會把舊的 value 替代成現在要插入元素的 value
- 如果和存在的元素相等：情況二：
  - 擴容 line 644 : treeifyBin(tab, hash)
  - 如果 HashMap 的 array 的長度是空，或者小於 64, 那建議擴容而不是轉成紅黑樹
    - 如果圖 A 的 array 長度 n < 64 而又要把它轉成紅黑樹的話，其實效率也很慢
    - 所以可以讓它 resize 變成圖 B 那樣，就不需要轉成紅黑樹了
- 當 bucket 裡的 object 大於等於 8 個時，且 array 的 n > 64
  - 要轉成紅黑樹

以上便是實現 HashMap 基本的過程