一、前言
很早之前便看過HashMap的源碼，記得自己當(dāng)時(shí)是大概粗略的看了下，所以時(shí)間一久便拋諸腦后了，以至于自己總是如同猴子摘玉米，摘了玉米丟了西瓜。想來如此，還不如踏踏實(shí)實(shí)用筆記記錄的形式記錄下來，自己有空便可以翻閱出來看看，也不會(huì)將之前的心血白費(fèi)。
二、源碼分析
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
/**
* 默認(rèn)初始化容量-必須是2的冪次方
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量，如果某個(gè)具有參數(shù)的構(gòu)造函數(shù)隱式指定了更高的值，則使用該值。必須是2的冪<=1<<30。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 當(dāng)構(gòu)造函數(shù)沒有指定所使用的默認(rèn)負(fù)載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 當(dāng)鏈表節(jié)點(diǎn)轉(zhuǎn)換為紅黑樹的閾值
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 當(dāng)紅黑樹轉(zhuǎn)換為鏈表的閾值
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 鏈表轉(zhuǎn)換為紅黑樹的最小表容量
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 存儲(chǔ)元素的數(shù)組，第一次使用時(shí)才會(huì)進(jìn)行初始化
*/
transient Node<K,V>[] table;
/**
* 保存緩存的entrySet
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* map集合中存放元素的個(gè)數(shù)
*/
transient int size;
/**
* 被修改的次數(shù)fast-fail機(jī)制
*/
transient int modCount;
/**
* 擴(kuò)容閾值(capacity * loadFactor)
*/
int threshold;
/**
* 負(fù)載因子
*/
final float loadFactor;
}
HashMap#Node(數(shù)組元素節(jié)點(diǎn))：
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;
}
}
HashMap#TreeNode(紅黑樹節(jié)點(diǎn))：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
HashMap#hash工具類：
static final int hash(Object key) {
int h;
//如果給定的key為null則直接返回0
//否則先獲取該key對(duì)應(yīng)的hashCode然后參與該hashCode無符號(hào)向右位移16位后進(jìn)行邏輯異或得出其最終hash值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
至于為啥要與高16位做異或運(yùn)算，是因?yàn)閿?shù)組位置的定位用的是與運(yùn)算，僅僅最后四位有效，設(shè)計(jì)者將key的哈希值與高16位做異或運(yùn)算使得在做邏輯與運(yùn)算確定數(shù)組的插入位置時(shí)，此時(shí)的低位實(shí)際上是高位與低位的結(jié)合，增加了隨機(jī)性，減少了哈希碰撞的次數(shù)。
HashMap存儲(chǔ)結(jié)構(gòu)圖如下所示：
HashMap存儲(chǔ)結(jié)構(gòu)
2.1、HashMap的幾種構(gòu)造函數(shù)：
//默認(rèn)構(gòu)造函數(shù)1：使用系統(tǒng)默認(rèn)的參數(shù)（容量、負(fù)載因子...)
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//默認(rèn)構(gòu)造函數(shù)2：使用默認(rèn)的負(fù)載因子，并使用Map集合初始化散列集合
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
//默認(rèn)構(gòu)造函數(shù)3：使用指定的初始容量并且使用系統(tǒng)默認(rèn)的負(fù)載因子
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//默認(rèn)構(gòu)造函數(shù)4：使用指定的初始容量和負(fù)載因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
//保證指定的初始容量是2的冪次方
this.threshold = tableSizeFor(initialCapacity);
}
2.2、HashMap#put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//tab存儲(chǔ)桶容器,p存儲(chǔ)該hash所在的節(jié)點(diǎn),n表示桶的容量,i表示該hash所在桶的索引位置
Node<K,V>[] tab; Node<K,V> p; int n, i;
//首次put元素時(shí)會(huì)初始化該table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通過(n-1)&hash得到該hash所在桶的索引,利用該索引定位所在桶的節(jié)點(diǎn)賦值給p
if ((p = tab[i = (n - 1) & hash]) == null)
//如果該節(jié)點(diǎn)為空,代表該節(jié)點(diǎn)不存在任何數(shù)據(jù)則直接新建一個(gè)節(jié)點(diǎn)存放在該節(jié)點(diǎn)上
tab[i] = newNode(hash, key, value, null);
else {
//如果該節(jié)點(diǎn)不為空的情況下所進(jìn)行的邏輯處理
Node<K,V> e; K k;
//如果該節(jié)點(diǎn)的hash值以及key值都與put的相同,則執(zhí)行替換操作
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果該節(jié)點(diǎn)是紅黑樹節(jié)點(diǎn)
else if (p instanceof TreeNode)
//執(zhí)行紅黑樹插入元素操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果該節(jié)點(diǎn)是鏈表節(jié)點(diǎn),則遍歷該鏈表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//實(shí)例化一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的next節(jié)點(diǎn)上
p.next = newNode(hash, key, value, null);
//如果沖突的節(jié)點(diǎn)數(shù)已經(jīng)達(dá)到8個(gè)，看是否需要改變沖突節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)，
//treeifyBin首先判斷當(dāng)前hashMap的長度，如果不足64，只進(jìn)行
//resize，擴(kuò)容table，如果達(dá)到64，那么將鏈表轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果有相同的key值就結(jié)束遍歷
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果存在該key映射的對(duì)象
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//大小遞增并且是否大于閾值，該閾值是loadFactory * capacity
//首次采用的是默認(rèn)值，這個(gè)閾值也就是0.75 * 16 = 12
//如果大小觸發(fā)了閾值則執(zhí)行擴(kuò)容操作，這個(gè)操作是插入元素之后觸發(fā)的
if (++size > threshold)
resize();//擴(kuò)容2倍
//空實(shí)現(xiàn)
afterNodeInsertion(evict);
return null;
}
HashMap#put的操作流程：
通過給定的key計(jì)算出hashCode，計(jì)算方式為獲取key的hashCode，向右無符號(hào)位移16位，再進(jìn)行異或操作得到最終的hash值；
-
通過hash值定位到數(shù)組對(duì)應(yīng)的節(jié)點(diǎn)上，如果該節(jié)點(diǎn)為空，直接new Node<>(hash,K,V,null);放入到容器對(duì)應(yīng)的索引下即可；如果節(jié)點(diǎn)不為空的情況下，分為三種情況：
2.1、如果該節(jié)點(diǎn)的hash和給定的hash一致，并且key也一致，則獲取該節(jié)點(diǎn)對(duì)象并將新值替換老值，并返回該節(jié)點(diǎn)的舊值；
2.2、如果該節(jié)點(diǎn)是紅黑樹，則調(diào)用TreeNode對(duì)象的putTreeVal(this, tab, hash, key, value)方法添加對(duì)象；
2.3、如果該節(jié)點(diǎn)是鏈表，遍歷該節(jié)點(diǎn)下的next節(jié)點(diǎn)，判斷是否有空的對(duì)象，如果有空的則將當(dāng)前存儲(chǔ)的節(jié)點(diǎn)newNode存放到對(duì)應(yīng)的p.next節(jié)點(diǎn)即可，之后再進(jìn)行判斷該鏈表節(jié)點(diǎn)長度是否大于紅黑樹閾值（8 - 1），如果大于則將鏈表轉(zhuǎn)換為紅黑樹節(jié)點(diǎn)，否則跳出該循環(huán)；如果節(jié)點(diǎn)的next節(jié)點(diǎn)不為空的情況，則判斷該hash是否相同，key是否相等，如果都匹配則將該節(jié)點(diǎn)用新接點(diǎn)進(jìn)行替換操作，和之前的步驟相同。 添加該鍵值對(duì)象后，判斷當(dāng)前大小是否超過閾值，如果超過閾值則觸發(fā)擴(kuò)容操作，參見
resize方法。
2.3、HashMap#get
public V get(Object key) {
Node<K,V> e;
//根據(jù)hash方法計(jì)算出該key的hash值,調(diào)用getNode獲取所在節(jié)點(diǎn),如果不存在返回null，反之返回該節(jié)點(diǎn)的value對(duì)象
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
//tab為容器數(shù)組對(duì)象,first為對(duì)應(yīng)hash所在的節(jié)點(diǎn),e存放節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn),n存放容器的大小,k存放節(jié)點(diǎn)的key
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//通過容器的容量-1邏輯與上hash值定位到該數(shù)組的節(jié)點(diǎn)所在位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//總是檢查首節(jié)點(diǎn)是否符合規(guī)則
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//如果節(jié)點(diǎn)是紅黑樹的情況則通過紅黑樹獲取節(jié)點(diǎn)數(shù)據(jù)
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//否則循環(huán)鏈表獲取節(jié)點(diǎn)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
HashMap#get的操作流程：
1、通過hash方法計(jì)算得到該key的hash值；
2、再調(diào)用getNode方法，通過容器的容量-1邏輯與上該key的hash值，得到該節(jié)點(diǎn)對(duì)象；
3、首先檢查該節(jié)點(diǎn)的hash值是否相等，并且key是否相等，如果相等則直接返回該節(jié)點(diǎn)；
4、如果上面的情況不匹配，則判斷該節(jié)點(diǎn)的next節(jié)點(diǎn)是否不為空，如果不為空則判斷該節(jié)點(diǎn)是否為紅黑樹節(jié)點(diǎn)，如果是紅黑樹，則執(zhí)行紅黑樹的getTreeNode方法獲取節(jié)點(diǎn)對(duì)象；否則就只有下面鏈表的結(jié)構(gòu)了，執(zhí)行遍歷操作遍歷該鏈表結(jié)果，直到直到對(duì)應(yīng)的節(jié)點(diǎn)hash值相同并且key相同的節(jié)點(diǎn)，然后返回；如果都不匹配則返回null。
2.4、HashMap#resize擴(kuò)容：
final Node<K,V>[] resize() {
//將該容器數(shù)組賦值給oldTab
Node<K,V>[] oldTab = table;
//獲取該容器的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//該容器的擴(kuò)容閾值
int oldThr = threshold;
//新的容量大小以及新的閾值
int newCap, newThr = 0;
if (oldCap > 0) {
//如果之前的容量已經(jīng)大于等于1 << 30，則該閾值為Integer的最大值，并返回該容器對(duì)象
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果之前的容量向左位移1位(即*2)小于最大容量并且容量大小大于等于默認(rèn)初始容量
//則將新的閾值為當(dāng)前容量向左位移1位(即*2)，雙倍快樂
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//首次put元素的時(shí)候會(huì)執(zhí)行該邏輯,使用默認(rèn)的初始化容量以及負(fù)載因子
//閾值為(12)=默認(rèn)負(fù)載因子(0.75) * 默認(rèn)初始化容量(16)
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//實(shí)例化容器數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//設(shè)置table為新建的容器
table = newTab;
//如果老的容器不為空則需要執(zhí)行數(shù)據(jù)遷移工作
if (oldTab != null) {
//循環(huán)遍歷容器的節(jié)點(diǎn)
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//幫助GC
oldTab[j] = null;
//如果該容器數(shù)組上的節(jié)點(diǎn)下面沒有其它節(jié)點(diǎn)，則直接存放到新的節(jié)點(diǎn)上即可
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果該節(jié)點(diǎn)是紅黑樹節(jié)點(diǎn)，則調(diào)用紅黑樹對(duì)象的split方法進(jìn)行處理
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//處理鏈表的情況,把當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的鏈表分成兩個(gè)鏈表，減少擴(kuò)容的遷移量
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
// 擴(kuò)容后不需要移動(dòng)的鏈表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 擴(kuò)容后需要移動(dòng)的鏈表
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;
// 擴(kuò)容長度為當(dāng)前index位置+舊的容量
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
三、總結(jié)
花了一天的時(shí)間把HashMap看完了，通過源碼的分析不得不佩服前輩的刀法，其中里面的很多實(shí)現(xiàn)也值得我們?nèi)ソ梃b和學(xué)習(xí)，HashMap在我們的工作過程中基本上每天都會(huì)用到，通過學(xué)習(xí)源碼，它再也不是一個(gè)黑盒子了，正所謂知其然而知其所以然，希望自己以后能不斷學(xué)習(xí)這些優(yōu)秀的源碼，不斷提升自己的能力。
