一、前言

在分析jdk1.8后的HashMap源碼時(shí)，發(fā)現(xiàn)網(wǎng)上好多分析都是基于之前的jdk，而Java8的HashMap對(duì)之前做了較大的優(yōu)化，其中最重要的一個(gè)優(yōu)化就是桶中的元素不再唯一按照鏈表組合，也可以使用紅黑樹(shù)進(jìn)行存儲(chǔ)，總之，目標(biāo)只有一個(gè)，那就是在安全和功能性完備的情況下讓其速度更快，提升性能。好~下面就開(kāi)始分析源碼。

二、HashMap數(shù)據(jù)結(jié)構(gòu)

說(shuō)明：上圖很形象的展示了HashMap的數(shù)據(jù)結(jié)構(gòu)（數(shù)組+鏈表+紅黑樹(shù)），桶中的結(jié)構(gòu)可能是鏈表，也可能是紅黑樹(shù)，紅黑樹(shù)的引入是為了提高效率。所以可見(jiàn)，在分析源碼的時(shí)候我們不知不覺(jué)就溫習(xí)了數(shù)據(jù)結(jié)構(gòu)的知識(shí)點(diǎn)，一舉兩得。

三、HashMap源碼分析

3.1 類的繼承關(guān)系　

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

可以看到HashMap繼承自父類（AbstractMap），實(shí)現(xiàn)了Map、Cloneable、Serializable接口。其中，Map接口定義了一組通用的操作；Cloneable接口則表示可以進(jìn)行拷貝，在HashMap中，實(shí)現(xiàn)的是淺層次拷貝，即對(duì)拷貝對(duì)象的改變會(huì)影響被拷貝的對(duì)象；Serializable接口表示HashMap實(shí)現(xiàn)了序列化，即可以將HashMap對(duì)象保存至本地，之后可以恢復(fù)狀態(tài)。

3.2 類的屬性　

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

// 序列號(hào)

private static final long serialVersionUID = 362498820763181265L;

// 默認(rèn)的初始容量是16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;

// 默認(rèn)的填充因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)大于這個(gè)值時(shí)會(huì)轉(zhuǎn)成紅黑樹(shù)

static final int TREEIFY_THRESHOLD = 8;

// 當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)小于這個(gè)值時(shí)樹(shù)轉(zhuǎn)鏈表

static final int UNTREEIFY_THRESHOLD = 6;

// 桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹(shù)對(duì)應(yīng)的table的最小大小

static final int MIN_TREEIFY_CAPACITY = 64;

// 存儲(chǔ)元素的數(shù)組，總是2的冪次倍

transient Node<k,v>[] table;

// 存放具體元素的集

transient Set<map.entry<k,v>> entrySet;

// 存放元素的個(gè)數(shù)，注意這個(gè)不等于數(shù)組的長(zhǎng)度。

transient int size;

// 每次擴(kuò)容和更改map結(jié)構(gòu)的計(jì)數(shù)器

transient int modCount;

// 臨界值 當(dāng)實(shí)際大小(容量*填充因子)超過(guò)臨界值時(shí)，會(huì)進(jìn)行擴(kuò)容

int threshold;

// 填充因子

final float loadFactor;

}

說(shuō)明：類的數(shù)據(jù)成員很重要，以上也解釋得很詳細(xì)了，其中有一個(gè)參數(shù)MIN_TREEIFY_CAPACITY，筆者暫時(shí)還不是太清楚，有讀者知道的話歡迎指導(dǎo)。

3.3 類的構(gòu)造函數(shù)

1.HashMap(int, float)型構(gòu)造函數(shù)

public HashMap(int initialCapacity, float loadFactor) {

// 初始容量不能小于0，否則報(bào)錯(cuò)

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal initial capacity: " +

initialCapacity);

// 初始容量不能大于最大值，否則為最大值

if (initialCapacity > MAXIMUM_CAPACITY)

initialCapacity = MAXIMUM_CAPACITY;

// 填充因子不能小于或等于0，不能為非數(shù)字

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal load factor: " +

loadFactor);

// 初始化填充因子

this.loadFactor = loadFactor;

// 初始化threshold大小

this.threshold = tableSizeFor(initialCapacity);

}

說(shuō)明：tableSizeFor(initialCapacity)返回大于等于initialCapacity的最小的二次冪數(shù)值。

static final int tableSizeFor(int cap) {

int n = cap - 1;

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

}

說(shuō)明：>>> 操作符表示無(wú)符號(hào)右移，高位取0。

2.HashMap(int)型構(gòu)造函數(shù)。

public HashMap(int initialCapacity) {

// 調(diào)用HashMap(int, float)型構(gòu)造函數(shù)

this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

3.HashMap()型構(gòu)造函數(shù)。

public HashMap() {

// 初始化填充因子

this.loadFactor = DEFAULT_LOAD_FACTOR;

}

4.HashMap(Map)型構(gòu)造函數(shù)。

public HashMap(Map<? extends K, ? extends V> m) {

// 初始化填充因子

this.loadFactor = DEFAULT_LOAD_FACTOR;

// 將m中的所有元素添加至HashMap中

putMapEntries(m, false);

}

說(shuō)明：putMapEntries(Map m, boolean evict)函數(shù)將m的所有元素存入本HashMap實(shí)例中。

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

int s = m.size();

if (s > 0) {

// 判斷table是否已經(jīng)初始化

if (table == null) { // pre-size

// 未初始化，s為m的實(shí)際元素個(gè)數(shù)

float ft = ((float)s / loadFactor) + 1.0F;

int t = ((ft < (float)MAXIMUM_CAPACITY) ?

(int)ft : MAXIMUM_CAPACITY);

// 計(jì)算得到的t大于閾值，則初始化閾值

if (t > threshold)

threshold = tableSizeFor(t);

}

// 已初始化，并且m元素個(gè)數(shù)大于閾值，進(jìn)行擴(kuò)容處理

else if (s > threshold)

resize();

// 將m中的所有元素添加至HashMap中

for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {

K key = e.getKey();

V value = e.getValue();

putVal(hash(key), key, value, false, evict);

}

}

}

3.4 重要函數(shù)分析

1.putVal函數(shù)

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

boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

// table未初始化或者長(zhǎng)度為0，進(jìn)行擴(kuò)容

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

// (n - 1) & hash 確定元素存放在哪個(gè)桶中，桶為空，新生成結(jié)點(diǎn)放入桶中(此時(shí)，這個(gè)結(jié)點(diǎn)是放在數(shù)組中)

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

// 桶中已經(jīng)存在元素

else {

Node<K,V> e; K k;

// 比較桶中第一個(gè)元素(數(shù)組中的結(jié)點(diǎn))的hash值相等，key相等

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

// 將第一個(gè)元素賦值給e，用e來(lái)記錄

e = p;

// hash值不相等，即key不相等；為紅黑樹(shù)結(jié)點(diǎn)

else if (p instanceof TreeNode)

// 放入樹(shù)中

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

// 為鏈表結(jié)點(diǎn)

else {

// 在鏈表最末插入結(jié)點(diǎn)

for (int binCount = 0; ; ++binCount) {

// 到達(dá)鏈表的尾部

if ((e =?p.next) == null) {

// 在尾部插入新結(jié)點(diǎn)

p.next?= newNode(hash, key, value, null);

// 結(jié)點(diǎn)數(shù)量達(dá)到閾值，轉(zhuǎn)化為紅黑樹(shù)

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash);

// 跳出循環(huán)

break;

}

// 判斷鏈表中結(jié)點(diǎn)的key值與插入的元素的key值是否相等

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

// 相等，跳出循環(huán)

break;

// 用于遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表

p = e;

}

}

// 表示在桶中找到key值、hash值與插入元素相等的結(jié)點(diǎn)

if (e != null) {

// 記錄e的value

V oldValue = e.value;

// onlyIfAbsent為false或者舊值為null

if (!onlyIfAbsent || oldValue == null)

//用新值替換舊值

e.value = value;

// 訪問(wèn)后回調(diào)

afterNodeAccess(e);

// 返回舊值

return oldValue;

}

}

// 結(jié)構(gòu)性修改

++modCount;

// 實(shí)際大小大于閾值則擴(kuò)容

if (++size > threshold)

resize();

// 插入后回調(diào)

afterNodeInsertion(evict);

return null;

}

說(shuō)明：HashMap并沒(méi)有直接提供putVal接口給用戶調(diào)用，而是提供的put函數(shù)，而put函數(shù)就是通過(guò)putVal來(lái)插入元素的。

2.getNode函數(shù)

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

Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

// table已經(jīng)初始化，長(zhǎng)度大于0，根據(jù)hash尋找table中的項(xiàng)也不為空

if ((tab = table) != null && (n = tab.length) > 0 &&

(first = tab[(n - 1) & hash]) != null) {

// 桶中第一項(xiàng)(數(shù)組元素)相等

if (first.hash == hash && // always check first node

((k = first.key) == key || (key != null && key.equals(k))))

return first;

// 桶中不止一個(gè)結(jié)點(diǎn)

if ((e =?first.next) != null) {

// 為紅黑樹(shù)結(jié)點(diǎn)

if (first instanceof TreeNode)

// 在紅黑樹(shù)中查找

return ((TreeNode<K,V>)first).getTreeNode(hash, key);

// 否則，在鏈表中查找

do {

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

return e;

} while ((e =?e.next) != null);

}

}

return null;

}

說(shuō)明：HashMap并沒(méi)有直接提供getNode接口給用戶調(diào)用，而是提供的get函數(shù)，而get函數(shù)就是通過(guò)getNode來(lái)取得元素的。

3.resize函數(shù)　

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

// 當(dāng)前table保存

Node<K,V>[] oldTab = table;

// 保存table大小

int oldCap = (oldTab == null) ? 0 : oldTab.length;

// 保存當(dāng)前閾值

int oldThr = threshold;

int newCap, newThr = 0;

// 之前table大小大于0

if (oldCap > 0) {

// 之前table大于最大容量

if (oldCap >= MAXIMUM_CAPACITY) {

// 閾值為最大整形

threshold = Integer.MAX_VALUE;

return oldTab;

}

// 容量翻倍，使用左移，效率更高

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

// 閾值翻倍

newThr = oldThr << 1; // double threshold

}

// 之前閾值大于0

else if (oldThr > 0)

newCap = oldThr;

// oldCap = 0并且oldThr = 0，使用缺省值（如使用HashMap()構(gòu)造函數(shù)，之后再插入一個(gè)元素會(huì)調(diào)用resize函數(shù)，會(huì)進(jìn)入這一步）

else {

newCap = DEFAULT_INITIAL_CAPACITY;

newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

}

// 新閾值為0

if (newThr == 0) {

float ft = (float)newCap * loadFactor;

newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

(int)ft : Integer.MAX_VALUE);

}

threshold = newThr;

@SuppressWarnings({"rawtypes","unchecked"})

// 初始化table

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

table = newTab;

// 之前的table已經(jīng)初始化過(guò)

if (oldTab != null) {

// 復(fù)制元素，重新進(jìn)行hash

for (int j = 0; j < oldCap; ++j) {

Node<K,V> e;

if ((e = oldTab[j]) != null) {

oldTab[j] = null;

if (e.next?== null)

newTab[e.hash & (newCap - 1)] = e;

else if (e instanceof TreeNode)

((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

else { // preserve order

Node<K,V> loHead = null, loTail = null;

Node<K,V> hiHead = null, hiTail = null;

Node<K,V> next;

// 將同一桶中的元素根據(jù)(e.hash & oldCap)是否為0進(jìn)行分割，分成兩個(gè)不同的鏈表，完成rehash

do {

next =?e.next;

if ((e.hash & oldCap) == 0) {

if (loTail == null)

loHead = e;

else

loTail.next?= e;

loTail = e;

}

else {

if (hiTail == null)

hiHead = e;

else

hiTail.next?= e;

hiTail = e;

}

} while ((e = next) != null);

if (loTail != null) {

loTail.next?= null;

newTab[j] = loHead;

}

if (hiTail != null) {

hiTail.next?= null;

newTab[j + oldCap] = hiHead;

}

}

}

}

}

return newTab;

}

說(shuō)明：進(jìn)行擴(kuò)容，會(huì)伴隨著一次重新hash分配，并且會(huì)遍歷hash表中所有的元素，是非常耗時(shí)的。在編寫程序中，要盡量避免resize。

在resize前和resize后的元素布局如下

說(shuō)明：上圖只是針對(duì)了數(shù)組下標(biāo)為2的桶中的各個(gè)元素在擴(kuò)容后的分配布局，其他各個(gè)桶中的元素布局可以以此類推。

四、針對(duì)HashMap的思考

4.1. 關(guān)于擴(kuò)容的思考

從putVal源代碼中我們可以知道，當(dāng)插入一個(gè)元素的時(shí)候size就加1，若size大于threshold的時(shí)候，就會(huì)進(jìn)行擴(kuò)容。假設(shè)我們的capacity大小為32，loadFator為0.75,則threshold為24 = 32 * 0.75，此時(shí)，插入了25個(gè)元素，并且插入的這25個(gè)元素都在同一個(gè)桶中，桶中的數(shù)據(jù)結(jié)構(gòu)為紅黑樹(shù)，則還有31個(gè)桶是空的，也會(huì)進(jìn)行擴(kuò)容處理，其實(shí)，此時(shí)，還有31個(gè)桶是空的，好像似乎不需要進(jìn)行擴(kuò)容處理，但是是需要擴(kuò)容處理的，因?yàn)榇藭r(shí)我們的capacity大小可能不適當(dāng)。

我們前面知道，擴(kuò)容處理會(huì)遍歷所有的元素，時(shí)間復(fù)雜度很高；前面我們還知道，經(jīng)過(guò)一次擴(kuò)容處理后，元素會(huì)更加均勻的分布在各個(gè)桶中，會(huì)提升訪問(wèn)效率。所以，說(shuō)盡量避免進(jìn)行擴(kuò)容處理，也就意味著，遍歷元素所帶來(lái)的壞處大于元素在桶中均勻分布所帶來(lái)的好處。如果有讀者有不同意見(jiàn)，也歡迎討論~

讀者福利：小編花了1個(gè)多月整理了一份最新架構(gòu)視頻和完整面試資料，希望可以幫到愿意提升競(jìng)爭(zhēng)力，敢于去行動(dòng)的程序員朋友們。

獲取方式：喜歡+關(guān)注+私信“架構(gòu)資料”即可獲取

五、總結(jié)

至此，HashMap的源碼就分析到這里了，其中理解了其中的核心函數(shù)和數(shù)據(jù)結(jié)構(gòu)，那么理解HashMap的源碼就不困難了。當(dāng)然，此次分析中還有一些知識(shí)點(diǎn)沒(méi)有涉及到，如紅黑樹(shù)、序列化、拷貝等，以后有機(jī)會(huì)會(huì)進(jìn)行詳細(xì)的說(shuō)明和講解