JDK 1.8 HashMap面試全部知識點整理

JDK1.8實作原理，面試全部要問的知識點基本都在裡面了，拿去用吧，面試必過哦。

HashMap基本概念

1. 允許null value和null key
2. 不保證所有key的周遊順序
3. 如果沒有hash沖突，put和get操作的時間複雜度是O(1)
4. 對HashMap周遊的時間複雜度是O(m + n)，其中m是bucket個數，n是元素個數
5. 裝載因子(load factor) 用于判斷HashMap何時擴容。元素個數n 大于等于capacity * load factor，則會擴容；進而保證bucket個數維持在元素個數的2倍左右。
6. load factor預設值是0.75，調大可以節省空間，但是查詢速度變慢；
7. HashMap不是線程安全的

HashMap基本設計

1. 預設采用拉連結清單，但是當一個連結清單中的節點數過多時，轉換為樹結構（類似于TreeMap中的結構，紅黑樹），以加快hash沖突情況下的查詢速度。
2. 隻有當拉連結清單table的大小超過一定值時，才會開始建立紅黑樹。
3. 紅黑樹中的節點按照hash code排序，如果hash code相同，看是否實作了相同的Comparable接口，如果實作了則根據Comparable接口判斷順序（這裡尼瑪用到了反射）
4. 當紅黑樹中的節點數低于一定值，則退化回連結清單。
5. bucket個數一定是2^n，因為：1）用2^n – 1與hash code進行位運算可直接找到bucket；2）每次擴容是把bucket個數擴大2倍，原來的hash code要麼位置不變，要麼往後移動2^(n-1)個位置。缺點：如果hash函數在生成hash code的時候，隻利用了低比特位，則尋找bucket位置容易導緻hash沖突，例如把Float類型作為key存入hashmap，且float數字是連續整數。如何解決？hash code高比特位與低比特位再進行一次異或位運算。

核心操作實作

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)

實作：根據參數Map的大小判斷是否需要擴容，然後調用putVal。用于實作putAll操作。

public int size()

實作：直接傳回size

public boolean isEmpty()

實作：判斷size是否等于0.

public V get(Object key)

實作：直接調用getNode實作

final Node<K,V> getNode(int hash, Object key)

實作：先用hash值找到table入口，然後比較key與根節點，如果根節點hash不比對，則分别針對紅黑樹和連結清單執行一次查找操作。

public boolean containsKey(Object key)

實作：直接調用getNode，傳回null則傳回false，否則true。

public V put(K key, V value)

實作：直接調用putVal。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

實作：如果table為空則先擴容，然後根據hash值找到入口。如果入口位置為空，則直接建立一個Node放在數組的這個位置；如果入口不為空，則判斷key是否是重複put（幂等性），是重複put則直接傳回，不是則繼續。然後根據hash值查找原節點，找到節點則直接修改value；如果沒找到，對于紅黑樹觸發紅黑樹插入節點操作；對于連結清單，在連結清單末尾插入Node（JDK 1.7是在連結清單的頭部插入，多線程環境下通路易引發死循環）。

final Node<K,V>[] resize()

說明：用于對HashMap進行擴容。

實作：首先根據容量、裝載因子、threshold計算擴容大小，然後建立table數組，把原table中的Node逐個存入新table。轉移資料的時候，如果原table中的一個bucket隻有一個節點，則直接放入新table；如果是一個紅黑樹，則觸發紅黑樹split操作；如果是一個連結清單，則原來的一個連結清單會被拆成2個連結清單（因為模運算的底數變了），分别放入新table的兩個位置，且在2個新連結清單中，Node的相對順序與原來保持一緻。

final void treeifyBin(Node<K,V>[] tab, int hash)

如果table長度小于8，則擴容；如果大于8，則根據hash值找到table入口，然後周遊連結清單，建立TreeNode。TreeNode形成一個雙向連結清單，然後再調用TreeNode上的treeify操作，形成紅黑樹（連結清單轉紅黑樹）

public void putAll(Map<? extends K, ? extends V> m)

直接調用putMapEntries

public V remove(Object key)

直接調用removeNode實作删除功能。

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)

說明：内部實作

實作：根據hash值找到table中的項，然後直接在紅黑樹或連結清單中删除節點即可。沒有特殊之處（面試也不會問，因為這裡沒啥好問的）

public void clear()

說明：清空HashMap

實作：table中的每個元素指派為null，table空間不會重新配置設定。

public boolean containsValue(Object value)

說明：判斷是否包含指定value

實作：第一層循環周遊table通路每個Node，再在第二層循環中周遊每個Node（通過next指針找到下一個Node）。注：紅黑樹Node也有next指針。

public Set<K> keySet();

說明：傳回HashMap中的所有key且與HashMap綁定，HashMap中資料變化則這裡傳回的Set也會跟着變化。支援删除操作（HashMap也會跟着變），不支援新增操作。

實作：直接傳回HashMap中的keySet成員，這個keySet由put等其他操作維護。

紅黑樹

1. 什麼是紅黑樹？

紅黑樹是一種平衡二叉樹，它的查找操作是logN的，但是比完全平衡的二叉樹慢。它的插入和删除操作比平衡二叉樹更快。

2. 紅黑樹滿足哪5條性質：

性質一：節點是紅色或者黑色；

性質二：根節點必須是黑色；

性質三：每個葉節點（NIL或空節點）必須是黑色；

性質四：每個紅色節點的兩個子節點必須都是黑色的；