基礎(chǔ)說(shuō)明

HashMap 是一個(gè)散列表，它存儲(chǔ)的內(nèi)容是鍵值對(duì)(key-value)映射。

HashMap 實(shí)現(xiàn)了 Map 接口，根據(jù)鍵的 HashCode 值存儲(chǔ)數(shù)據(jù)，具有很快的訪問(wèn)速度，最多允許一條記錄的鍵為 null，不支持線程同步。

HashMap 是無(wú)序的，即不會(huì)記錄插入的順序。

HashMap 繼承于AbstractMap，實(shí)現(xiàn)了 Map、Cloneable、java.io.Serializable 接口。

下面是HashMap的類圖

在HashMap里面，我們存儲(chǔ)的每一個(gè)節(jié)點(diǎn)都是一個(gè)Node

    /*** Basic hash bin node, used for most entries.  (See below for* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)*/static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}public final K getKey()        { return key; }public final V getValue()      { return value; }public final String toString() { return key + "=" + value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}public final boolean equals(Object o) {if (o == this)return true;if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false;}}

對(duì)于HashMap，這篇文章不會(huì)對(duì)hash算法還有紅黑樹(shù)的原理進(jìn)行說(shuō)明，這個(gè)是屬于數(shù)據(jù)結(jié)構(gòu)的知識(shí)！！！

在開(kāi)始了解HashMap源碼前，先對(duì)HashMap的幾個(gè)重要成員屬性進(jìn)行說(shuō)明

    /*** The table, initialized on first use, and resized as* necessary. When allocated, length is always a power of two.* (We also tolerate length zero in some operations to allow* bootstrapping mechanics that are currently not needed.)*/transient Node<K,V>[] table;

table就是用來(lái)存儲(chǔ)元素的

    /*** The number of key-value mappings contained in this map.*/transient int size;

size表示元素個(gè)數(shù)

    /*** The default initial capacity - MUST be a power of two.*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/*** The maximum capacity, used if a higher value is implicitly specified* by either of the constructors with arguments.* MUST be a power of two <= 1<<30.*/static final int MAXIMUM_CAPACITY = 1 << 30;/*** The load factor used when none specified in constructor.*/static final float DEFAULT_LOAD_FACTOR = 0.75f;

上面幾個(gè)是關(guān)于table容量的一些屬性

    /*** The bin count threshold for using a tree rather than list for a* bin.  Bins are converted to trees when adding an element to a* bin with at least this many nodes. The value must be greater* than 2 and should be at least 8 to mesh with assumptions in* tree removal about conversion back to plain bins upon* shrinkage.*/static final int TREEIFY_THRESHOLD = 8;/*** The bin count threshold for untreeifying a (split) bin during a* resize operation. Should be less than TREEIFY_THRESHOLD, and at* most 6 to mesh with shrinkage detection under removal.*/static final int UNTREEIFY_THRESHOLD = 6;/*** The smallest table capacity for which bins may be treeified.* (Otherwise the table is resized if too many nodes in a bin.)* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts* between resizing and treeification thresholds.*/static final int MIN_TREEIFY_CAPACITY = 64;

上面這些是關(guān)于是否樹(shù)形化的一些屬性

構(gòu)造器

在HashMap中有3個(gè)構(gòu)造器，分別如下

無(wú)參構(gòu)造器

指定初始容量

指定初始容量和負(fù)載因子

通過(guò)Map創(chuàng)建

對(duì)于HashMap，一般都是使用無(wú)參構(gòu)造器。對(duì)于初始容量，默認(rèn)值就是16，對(duì)于負(fù)載因子，默認(rèn)值就是0.75。

負(fù)載因子的作用就是判斷table是否需要擴(kuò)容了，如果table的容量達(dá)到了 當(dāng)前容量*負(fù)載因子，那么就會(huì)進(jìn)行擴(kuò)容

put方法（無(wú)擴(kuò)容，無(wú)沖突）

現(xiàn)在我們就來(lái)開(kāi)始debug，下面就是要進(jìn)行debug的代碼

    public static void main(String[] args) {HashMap<Integer, String> hashMap = new HashMap<>();for (int i = 0; i < 20; i++) {hashMap.put(i, "100");}}

對(duì)于debug，我們主要是看過(guò)程，一定不要過(guò)分在意細(xì)節(jié)，不然就繞進(jìn)去了。下面就開(kāi)始debug了

首先看看創(chuàng)建HashMap后有什么

可以發(fā)現(xiàn)創(chuàng)建就是設(shè)置了一些負(fù)載因子

然后進(jìn)入put方法

該方法首先會(huì)計(jì)算傳入k的hash值，對(duì)于hash算法，這里不做說(shuō)明，請(qǐng)參考數(shù)據(jù)結(jié)構(gòu)，下面就是hash方法的內(nèi)容

計(jì)算完hash后，進(jìn)入putVal方法

這個(gè)if就是判斷當(dāng)前table是否為null，顯然是的，于是就進(jìn)入到resize方法。resize方法內(nèi)容很多，這里我不會(huì)說(shuō)明每一條語(yǔ)句，挑重要的進(jìn)行說(shuō)明。在這之前，我們應(yīng)當(dāng)看一下該方法的注釋

    /*** Initializes or doubles table size.  If null, allocates in* accord with initial capacity target held in field threshold.* Otherwise, because we are using power-of-two expansion, the* elements from each bin must either stay at same index, or move* with a power of two offset in the new table.** @return the table*/

開(kāi)始debug

繼續(xù)往下面走

上面的判斷完成后就開(kāi)始真正創(chuàng)建數(shù)組了

然后賦值，對(duì)于下面的if判斷，其實(shí)就是將oldTab的值復(fù)制過(guò)來(lái)，由于oldTab為null，所以這個(gè)方法就結(jié)束了,這個(gè)方法結(jié)束之后，table就已經(jīng)初始化了，大小為16

繼續(xù)debug

這條語(yǔ)句就是判斷指定通過(guò)hash算出來(lái)的索引位置是否已經(jīng)存放了值，顯然沒(méi)有，所以就會(huì)將其設(shè)置到指定位置

繼續(xù)往下面走，可以看見(jiàn)一個(gè)if語(yǔ)句

這個(gè)就是用來(lái)判斷是否需要擴(kuò)容的，threshold就是當(dāng)前容量*負(fù)載因子，這里的threshold就是12

繼續(xù)往下走，方法結(jié)束

下面就是添加完一個(gè)元素后的HashMap信息

---

put方法（無(wú)沖突，有擴(kuò)容）

我們通過(guò)上面的學(xué)習(xí)應(yīng)該知道了當(dāng)table數(shù)組使用3/4的時(shí)候就會(huì)擴(kuò)容了，下面來(lái)具體看一下流程

    public static void main(String[] args) {HashMap<Integer, String> hashMap = new HashMap<>();for (int i = 0; i < 20; i++) {hashMap.put(i, "100");}}

還是這個(gè)代碼，我們使用條件debug，看看i==12的時(shí)候是如何進(jìn)行擴(kuò)容的

由于大部分內(nèi)容都是和一般情況一樣的，所以我就直接跳到關(guān)鍵部分

當(dāng)i=12的時(shí)候，++size會(huì)>threshold，所以會(huì)執(zhí)行resize方法。resize方法前面部分也是一樣的，我也是直接跳到關(guān)鍵部分

由于我們的table沒(méi)有發(fā)生沖突，在這個(gè)循環(huán)里面 e.next==null 永遠(yuǎn)成立

復(fù)制完成之后就會(huì)返回新table，大小為32，threshold會(huì)更新為24

對(duì)于一般情況下的擴(kuò)容，下面的條件基本都會(huì)成立，也就是threshold和容量都會(huì)翻倍

---

put方法（有沖突，無(wú)樹(shù)化）

上面我們都是介紹的無(wú)hash沖突的情況，現(xiàn)在就來(lái)debug下出現(xiàn)hash沖突的情況

public class FixHashCat {@Overridepublic int hashCode() {return 12345678;}
}

上面的FixHashCat重寫(xiě)了hashCode，使之成為固定值，這樣方便debug

    public static void main(String[] args) {HashMap<FixHashCat, String> hashMap = new HashMap<>();hashMap.put(new FixHashCat(), "1");hashMap.put(new FixHashCat(), "2");}

上面的第二個(gè)put肯定就會(huì)產(chǎn)生hash沖突，下面就來(lái)看一下流程吧

對(duì)于重復(fù)的步驟我就跳過(guò)了，現(xiàn)在還是會(huì)進(jìn)入putVal方法

由于我們沒(méi)有重寫(xiě)equals方法，當(dāng)前也沒(méi)有樹(shù)化，所以會(huì)進(jìn)行如else語(yǔ)句

對(duì)于是否樹(shù)化，鏈表的數(shù)量要大于等于7才行，加上新加入的那個(gè)，bitCount又是從0開(kāi)始的，也就是當(dāng)鏈表個(gè)數(shù)達(dá)到9個(gè)就會(huì)進(jìn)行樹(shù)化

由于我們添加后鏈表長(zhǎng)度都才為2，所以顯然不會(huì)樹(shù)化，繼續(xù)執(zhí)行，將當(dāng)前元素添加到指定索引的鏈表末尾。繼續(xù)往下執(zhí)行，還可以發(fā)現(xiàn)一個(gè)if

我們指定map里面key是唯一的，如果添加2個(gè)相同的key，那么前面?zhèn)€key的值就會(huì)被覆蓋，這里的if就是用來(lái)完成這個(gè)事情的。繼續(xù)debug

執(zhí)行到這里，debug也就基本結(jié)束了，最后來(lái)看看table的結(jié)構(gòu)

---

put方法（有沖突，樹(shù)化）

上面看見(jiàn)了當(dāng)鏈表個(gè)數(shù)達(dá)到9個(gè)的時(shí)候會(huì)進(jìn)行樹(shù)化，鏈表變換為紅黑樹(shù)，下面就來(lái)debug這個(gè)過(guò)程

    public static void main(String[] args) {HashMap<FixHashCat, String> hashMap = new HashMap<>();for (int i = 0; i < 8; i++) {hashMap.put(new FixHashCat(), i + "");}hashMap.put(new FixHashCat(), "8");}

我使用上面代碼進(jìn)行debug，查看hashMap.put(new FixHashCat(), “8”)這條語(yǔ)句添加時(shí)候的情況

前面相同的部分我就跳過(guò)了，直接從樹(shù)化部分開(kāi)始

進(jìn)入到treeifyBin，結(jié)果由于table容量太小(這里是16)，于是會(huì)重設(shè)table大小，并不會(huì)樹(shù)化。

為了看到樹(shù)化的過(guò)程，我在創(chuàng)建HashMap的時(shí)候指定初始容量

    public static void main(String[] args) {HashMap<FixHashCat, String> hashMap = new HashMap<>(128);for (int i = 0; i < 8; i++) {hashMap.put(new FixHashCat(), i + "");}hashMap.put(new FixHashCat(), "9");}

還是debug到treeifyBin

簡(jiǎn)單看一下replacementTreeNode，代碼很簡(jiǎn)單，如下

對(duì)于do-while里面的內(nèi)容我并不關(guān)心，直接跳到if語(yǔ)句

可以看一下hd的內(nèi)容

下面就是執(zhí)行treeify方法

對(duì)于這個(gè)方法，完全就是屬于數(shù)據(jù)結(jié)構(gòu)了，這里不進(jìn)行說(shuō)明，大家可以自行查看源代碼?，F(xiàn)在我直接看看執(zhí)行完該方法后產(chǎn)生的樹(shù)

可以發(fā)現(xiàn)樹(shù)節(jié)點(diǎn)就是通過(guò)TreeNode來(lái)存儲(chǔ)的，用于快速查找。

現(xiàn)在關(guān)于樹(shù)化的debug就結(jié)束了，現(xiàn)在我想對(duì)上面提到的TreeNode進(jìn)行一下說(shuō)明

就是p instanceof TreeNode，這個(gè)在上面提到過(guò)，現(xiàn)在大家應(yīng)該可以看懂了，樹(shù)化之后的節(jié)點(diǎn)就是TreeNode，如果是TreeNode，那么就要將其添加到樹(shù)，而不是鏈表尾部。

remove方法（樹(shù)退化）

對(duì)于HashMap，不僅僅會(huì)將鏈表變化為樹(shù)，當(dāng)樹(shù)的元素個(gè)數(shù)小于某個(gè)閾值時(shí)，樹(shù)也會(huì)退化為鏈表

上面分別是樹(shù)化和退化的閾值。

當(dāng)我們刪除元素的時(shí)候可能就會(huì)進(jìn)行退化，樹(shù)變成鏈表

---

常見(jiàn)方法

在這里介紹一些HashMap里面經(jīng)常使用到的方法

方法名稱	作用
entrySet()	返回所有元素的set集合(k-v形式)
getOrDefault(Object key, V defaultValue)	返回指定key對(duì)于的value，如果不存在就返回defaultValue
keySet()	返回所有的key
values()	返回所有的value
forEach	遍歷集合元素
containsKey(Object key)	是否包含指定key
containsValue(Object value)	是否包含指定value

---

總結(jié)

HashMap使用K-V的形式存儲(chǔ)數(shù)據(jù)，Map的擴(kuò)容機(jī)制是按照2倍進(jìn)行的，當(dāng)達(dá)到閾值時(shí)就會(huì)擴(kuò)容。當(dāng)hash沖突嚴(yán)重時(shí)，鏈表會(huì)轉(zhuǎn)換為紅黑樹(shù)，當(dāng)樹(shù)元素個(gè)數(shù)很少時(shí)，又會(huì)退化為鏈表。