前言
HashMap：Java集合框架中相當(dāng)具有代表意義并且日常開發(fā)中使用率相當(dāng)高的一個(gè)工具類怔鳖，其實(shí)現(xiàn)的基本數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表+紅黑樹（JDK1.8）；
本文主要基于JDK1.8病瞳，同時(shí)也穿插提到一些JDK1.7的特性讼溺，用來對比兩個(gè)版本之間的差異；從源碼出發(fā)庐橙，學(xué)習(xí)HashMap的底層設(shè)計(jì)鼻疮，其基本用法不再贅述怯伊。
重要屬性
-
threshold：當(dāng)存儲(chǔ)元素size達(dá)到該值，并且再次插入時(shí)判沟，會(huì)進(jìn)行擴(kuò)容操作（
resize()）耿芹，并且每次HashMap容量發(fā)生變化時(shí)崭篡，值會(huì)重新計(jì)算；
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
-
loadFactor：負(fù)載因子吧秕，當(dāng)HashMap中已經(jīng)存儲(chǔ)的元素?cái)?shù)量size達(dá)到負(fù)載臨界值就會(huì)進(jìn)行擴(kuò)容琉闪；默認(rèn)值為
0.75f，可在HashMap構(gòu)造方法中自定義指定值砸彬； - size：當(dāng)前HashMap已經(jīng)存儲(chǔ)的元素?cái)?shù)量颠毙；
-
modCount：記錄HashMap被修改的次數(shù)，會(huì)在
put()操作和remove()操作時(shí)自增1砂碉，用于HashMa的快速失斨邸（fast-fail）機(jī)制，即迭代時(shí)進(jìn)行寫操作（put绽淘，remove等）涵防，拋出java.util.ConcurrentModificationException異常闹伪； - table：Node數(shù)組沪铭，存放鍵值對，key和value真正存放的地方偏瓤，JDK1.7中為Entry數(shù)組杀怠，Node是JDK1.8中新定義的數(shù)據(jù)結(jié)構(gòu)；
transient Node<K,V>[] table;
- 相比較JDK1.7厅克，JDK1.8的HashMap引入了紅黑樹的概念赔退，使得HashMap的索引性能再次提升。
在JDK1.7中证舟，當(dāng)發(fā)哈希碰撞時(shí)硕旗，所有value節(jié)點(diǎn)都會(huì)存在那個(gè)index位置開始的一個(gè)鏈表上，在1.8中女责，當(dāng)鏈表達(dá)到一定長度時(shí)就會(huì)轉(zhuǎn)化成紅黑樹以提升索引效率漆枚。
（1）TREEIFY_THRESHOLD：樹形化閾值，鏈表轉(zhuǎn)化為紅黑樹的臨界值抵知，默認(rèn)值為8墙基，同一個(gè)桶內(nèi)的鏈表長度達(dá)到這個(gè)值時(shí)就轉(zhuǎn)化為紅黑樹；
static final int TREEIFY_THRESHOLD = 8;
（2）UNTREEIFY_THRESHOLD：紅黑樹轉(zhuǎn)換為鏈表的臨界值刷喜，默認(rèn)值為6残制，當(dāng)紅黑樹的節(jié)點(diǎn)數(shù)減少到這個(gè)變量指定的值時(shí)就退化為一個(gè)鏈表；
static final int UNTREEIFY_THRESHOLD = 6;
（3）MIN_TREEIFY_CAPACITY：當(dāng)哈希表（table）容量table.length達(dá)到這個(gè)值掖疮，鏈表才會(huì)被樹形化初茶，默認(rèn)值為64，并且不能小于4 * TREEIFY_THRESHOLD浊闪；如果沒有這個(gè)閾值的控制恼布，當(dāng)桶內(nèi)元素太多時(shí)會(huì)進(jìn)行擴(kuò)容而不是樹形化吐葵；
static final int MIN_TREEIFY_CAPACITY = 64;
- 1.8新增數(shù)據(jù)結(jié)構(gòu)：
（1）Node<K, V>：HashMap的一個(gè)靜態(tài)內(nèi)部類，代替了JDK1.7中的Entry來存放鍵值對桥氏，同時(shí)增加了Node<K,V> next變量温峭，更有利于LinkedHashMap的實(shí)現(xiàn)，LinkedHashMap中的Entry就是繼承自這里定義的Node字支。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
（2）TreeNode<K, V>：紅黑樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)凤藏，繼承自LinkedHashMap中定義的LinkedHashMap.Entry<K,V>，可以追溯自己的父節(jié)點(diǎn)堕伪；
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>
- 一些常量及屬性初始值：
/**
* The default initial capacity - MUST be a power of two.
* 默認(rèn)初始化capacity大小揖庄，值為16，capacity必須為2的次方
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The load factor used when none specified in constructor.
* 默認(rèn)負(fù)載因子欠雌，值為0.75蹄梢；
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 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.
* HashMap最大容量，必須為2的倍數(shù)并且小于等于1向右位移30位富俄，即2的30次方禁炒；
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
重要方法
1. 構(gòu)造方法：
（1）public HashMap();默認(rèn)構(gòu)造方法，JDK1.7中調(diào)用public HashMap(int initialCapacity, float loadFactor)霍比，JDK1.8則只指定默認(rèn)的負(fù)載因子幕袱；
// JDK 1.8
public HashMap() {
// 初始化負(fù)載因子系數(shù)為0.75，此時(shí)并未初始化HashMap
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 其他屬性均為默認(rèn)值
}
// JDK 1.7
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
// 不同于1.8,1.7在默認(rèn)構(gòu)造方法內(nèi)就已經(jīng)初始化好了HashMap
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
??(2)public HashMap(int initialCapacity);指定HashMap初始容量大杏扑病们豌；
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
* 創(chuàng)建一個(gè)空的HashMap，傳入指定的初始化容量大小浅妆，負(fù)載因子為默認(rèn)值0.75f
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
??(3) public HashMap(int initialCapacity, float loadFactor);同時(shí)指定HashMap初始容量大小以及負(fù)載因子值望迎；
// JDK 1.7
/**
* @param initialCapacity the initial capacity
* initialCapacity：初始化空間大小，小于0則拋出參數(shù)非法異常凌外，最大值不超過 static final int MAXIMUM_CAPACITY = 1 << 30;
*
* @param loadFactor the load factor
* loadFactor：負(fù)載因子大小辩尊，小于等于0或者是一個(gè)非數(shù)字參數(shù)則拋出非法參數(shù)異常;
*/
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;
threshold = initialCapacity;
init();
}
// JDK 1.8
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity 初始化空間大小，小于0則拋出參數(shù)非法異常趴乡，最大值不超過 static final int MAXIMUM_CAPACITY = 1 << 30;
* @param loadFactor 負(fù)載因子大小对省，小于等于0或者是一個(gè)非數(shù)字參數(shù)則拋出非法參數(shù)異常;
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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;
this.threshold = tableSizeFor(initialCapacity);
}
??(4) public HashMap(Map<? extends K, ? extends V> m);用另一個(gè)Map對象來初始化一個(gè)HashMap，負(fù)載因子為默認(rèn)的0.75晾捏，初始化容量大小需要足夠容納傳入的Map對象蒿涎；
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false); // 如果傳入m為 null，會(huì)拋出空指針異常惦辛，因此使用此構(gòu)造方法之前最好做判空處理
}
2. put方法
put方法劳秋，以及后面的get方法，是HashMap使用頻率最高的兩個(gè)方法，put方法是將一個(gè)key-value鍵值對按照一定規(guī)則放到散列表對應(yīng)的桶內(nèi)玻淑，如果之前已經(jīng)針對傳入的key調(diào)用過put方法嗽冒，那么就用傳入的value替換老的value；
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
計(jì)算key的hash：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
從計(jì)算哈希值的源碼來看补履，結(jié)果是依賴于key對象的hashCode()方法的添坊。因此，如果我們自定義一個(gè)類來作為key箫锤，同時(shí)我們重寫了hashCode()方法贬蛙，并且這個(gè)hashCode()的邏輯與這個(gè)自定義類的其他屬性相關(guān)，當(dāng)這些屬性的值發(fā)生改變后谚攒，同一個(gè)對象計(jì)算的hashCode()方法就可能返回不同的值阳准。如果這個(gè)對象作為key已經(jīng)進(jìn)行過put操作，之后這些屬性的值又被修改過馏臭，那么這個(gè)對象就可能對源碼中的hash()方法產(chǎn)生影響野蝇，返回不同的哈希值，導(dǎo)致之前put的鍵值對可能永遠(yuǎn)不被訪問到括儒，同時(shí)如果這個(gè)HashMap的生命周期足夠長绕沈，就產(chǎn)生了內(nèi)存泄漏，因此在自定義類作為key時(shí)塑崖，這一點(diǎn)必須注意七冲。
對于java.lang.Object類的public native int hashCode();方法，這是一個(gè)本地方法规婆，具體的邏輯我還沒有翻閱過源碼，但是從網(wǎng)上得知蝉稳，該方法的計(jì)算邏輯和對象的內(nèi)存地址相關(guān)抒蚜，雖然不能完全保證所有不同對象都返回一個(gè)不同的哈希值，但是本身這個(gè)方法的散列程度也是比較高的耘戚，所以如果自己重寫hashCode()方法不能保證足夠高的散列度嗡髓，那么建議就不要再重寫該方法了。
由以上可知收津，put方法的主要邏輯由putVal方法完成饿这，putVal方法才是put方法的主體，事實(shí)上構(gòu)造方法public HashMap(Map<? extends K, ? extends V> m);也是在調(diào)用此方法來完成HashMap的初始化撞秋，先貼源碼：
/**
* @param hash hash for key key的hash
* @param key the key
* @param value the value to put 被放入的value
* @param onlyIfAbsent if true, don't change existing value 為true時(shí)长捧，不替換已存在的value
* @param evict if false, the table is in creation mode. 為false，則table在創(chuàng)建模式
* @return previous value, or null if none 返回之前的舊的value吻贿，如果不存在就返回null
*/
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還未被初始化串结，則直接進(jìn)行初始化，一般在HashMap被定義后，首次調(diào)用put方法時(shí)被觸發(fā)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果計(jì)算出來的位置沒有被占用肌割，則直接存存放
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 判斷是否是同一個(gè)key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 標(biāo)記沖突的頭結(jié)點(diǎn)e
// 是否已經(jīng)樹形化過
else if (p instanceof TreeNode)
// 已經(jīng)轉(zhuǎn)化為紅黑樹卧蜓，將節(jié)點(diǎn)插入紅黑樹，
// 紅黑樹的插入涉及到左旋右旋以及顏色變換等操作把敞，以滿足紅黑樹的幾大特性
// 關(guān)于紅黑樹的這些內(nèi)容大家可以自行搜索學(xué)習(xí)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 哈希沖突弥奸，鏈地址法處理初步?jīng)_突
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 鏈表深度達(dá)到樹形化閾值，觸發(fā)樹形化流程
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); // 樹形化：鏈表轉(zhuǎn)化為紅黑樹
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 相同的key奋早，用新的value替換原來的value其爵，并返回原來的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount; // modCount自增1，用于fast-fail
if (++size > threshold) // 達(dá)到擴(kuò)容閾值伸蚯，進(jìn)行擴(kuò)容
resize();
afterNodeInsertion(evict); // put操作時(shí)evict為true摩渺，僅當(dāng)構(gòu)造方法內(nèi)evict為false
return null;
從源碼來看，將一個(gè)鍵值對存入table數(shù)組剂邮，需要先計(jì)算存入的位置摇幻，計(jì)算規(guī)則是用key的hash與table容量取模tab[i = (n - 1) & hash])，如果發(fā)生哈希沖突挥萌，就先采用 鏈地址法 來處理沖突绰姻，如果鏈表長度達(dá)到了樹形化閾值TREEIFY_THRESHOLD（默認(rèn)8），但是table數(shù)組容量還未達(dá)到樹形化閾值 MIN_TREEIFY_CAPACITY（默認(rèn)64）引瀑，此時(shí)就只是做數(shù)組擴(kuò)容狂芋，不進(jìn)行樹形化：
// 鏈表長度達(dá)到閾值，但是數(shù)組容量還未達(dá)到閾值
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
當(dāng)鏈表長度以及數(shù)組容量都達(dá)到閾值后憨栽，這個(gè)桶對應(yīng)的鏈表就升華為紅黑樹帜矾，此后查找的時(shí)間復(fù)雜度就會(huì)從O(n)提升至O(logn)，帶來更高的索引性能屑柔，源碼如下：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
// 普通節(jié)點(diǎn)轉(zhuǎn)化為紅黑樹節(jié)點(diǎn)
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 樹形化
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
在沖突鏈表樹形化成紅黑樹時(shí)屡萤，或者樹形化后進(jìn)行put，remove掸宛，get等操作時(shí)死陆，都是利用key的hashCode值來進(jìn)行定位，以確定具體走左孩子或者右孩子唧瘾，如下措译，樹形化方法final void treeify(Node<K,V>[] tab)的部分代碼：
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 利用key的哈希值進(jìn)行處理
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
但是有一種極端情況，即hashCode值完全一樣饰序，并且key又未實(shí)現(xiàn)Comparable接口领虹，也就是說，key既無法通過hashCode來比較大小菌羽，本身也無法比較大小掠械，那么就無法來確定左右由缆，此時(shí)就需要一些特殊處理，使得最終能夠得到兩個(gè)key對象之間的大小關(guān)系猾蒂；
HashMap提供了一個(gè)static int tieBreakOrder(Object a, Object b)方法均唉，已處理上述極端情況，通過本地方法public static native int identityHashCode(Object x)來獲得一個(gè)identityHashCode肚菠，只要是兩個(gè)滿足==不為true的對象舔箭，這個(gè)方法的返回值就不會(huì)一樣（事實(shí)上這句話只是我的臆斷，該方法返回值類型為int蚊逢，是有一個(gè)上限值的层扶，即Integer.MAX_VALUE，當(dāng)對象數(shù)量超過這個(gè)上限值烙荷，會(huì)出現(xiàn)其中兩個(gè)對象的identityHashCode值一樣的情況嗎镜会？由于硬件環(huán)境限制，這種場景并未能順利測試）终抽，以此便能區(qū)分左右了戳表；
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
以下為tieBreakOrder方法實(shí)現(xiàn)：
/**
* Tie-breaking utility for ordering insertions when equal
* hashCodes and non-comparable. We don't require a total
* order, just a consistent insertion rule to maintain
* equivalence across rebalancings. Tie-breaking further than
* necessary simplifies testing a bit.
*/
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
3. resize方法
該方法完成HashMap的擴(kuò)容或者初始化；
- 如果table數(shù)組為空昼伴，就執(zhí)行初始化流程匾旭；
- 如果不為空，那么就執(zhí)行擴(kuò)容流程圃郊，擴(kuò)容需要先創(chuàng)建一個(gè)容量為原table數(shù)組的 2 倍length的新Entry數(shù)組价涝，然后把原數(shù)組里所有的元素都拷貝到新的數(shù)組里去，拷貝之前需要計(jì)算新的索引值持舆；其中新建數(shù)組以及拷貝都是比較耗費(fèi)資源的操作色瘩，因此初始化HashMap時(shí)盡量指定一個(gè)預(yù)估的足夠大的容量值來避免或減少擴(kuò)容，有利于提升系統(tǒng)性能吏廉；
源碼：
/**
* 初始化或者table數(shù)組擴(kuò)容（兩倍容量擴(kuò)容）
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 不是初始化泞遗，走擴(kuò)容流程
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 擴(kuò)容后的容量為原來的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 向右位移一位，達(dá)到原閾值2倍
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 容量席覆，閾值指定初值
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;
@SuppressWarnings({"rawtypes","unchecked"})
// 新建一個(gè)新容量數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 遍歷原來的數(shù)組，把所有的元素都轉(zhuǎn)移到新數(shù)組去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 原數(shù)組置空汹买，以便GC
if (e.next == null) // 原數(shù)組該位置無沖突佩伤，正常存放
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 原數(shù)組在這個(gè)位置上是一個(gè)紅黑樹
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 原數(shù)組該位置沖突，但是還未達(dá)到樹形化閾值晦毙，因此還是鏈表結(jié)構(gòu)
// low head生巡，low tail
Node<K,V> loHead = null, loTail = null;
// hight head，high tail
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 循環(huán)鏈表轉(zhuǎn)移至新數(shù)組
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;
}
4. get方法
返回key對應(yīng)的value见妒，否則返回null孤荣；相反的，如果返回的值為null，并非說明HashMap內(nèi)不存在這樣的一個(gè)鍵值對盐股，有可能這個(gè)key對應(yīng)的value本身就為null钱豁；
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
get方法大概邏輯：
- 如果key未能對應(yīng)到一個(gè)桶，那么返回
null疯汁； - 如果對應(yīng)的桶第一個(gè)元素即為傳入key對應(yīng)的Node牲尺，那么直接返回；
- 如果桶第一個(gè)元素并非傳入key對應(yīng)的Node幌蚊，需要判斷這個(gè)桶內(nèi)是鏈表結(jié)構(gòu)還是樹形結(jié)構(gòu)谤碳，鏈表則遍歷直到找到對應(yīng)的key，如果是紅黑樹結(jié)構(gòu)溢豆，需要從根節(jié)點(diǎn)（
parent為空）開始向下以B+樹方式進(jìn)行搜索找到key蜒简；
/**
* Implements Map.get and related methods
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 先判斷傳入的key在map內(nèi)是有相對應(yīng)的value的
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 總是先判斷位置上的第一個(gè)元素
// 如果第一個(gè)即符合則直接返回，不用管這個(gè)桶的位置上是一個(gè)鏈表還是紅黑樹
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 執(zhí)行到這漩仙，表示這個(gè)位置上至少會(huì)是一個(gè)鏈表了
if ((e = first.next) != null) {
// 判斷這個(gè)位置是否已經(jīng)樹形化過
if (first instanceof TreeNode)
// 從紅黑樹中搜索對應(yīng)的key搓茬，時(shí)間復(fù)雜度O(logn)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 還未樹形化，則遍歷鏈表讯赏，直到找到對應(yīng)的key垮兑，時(shí)間復(fù)雜度O(n)
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
紅黑樹節(jié)點(diǎn)搜索的實(shí)現(xiàn)：
/**
* 從根節(jié)點(diǎn)向下查找
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
5. remove方法
remove方法時(shí)將key對應(yīng)的鍵值對從HashMap中移除；
// 移除指定key對應(yīng)的鍵值對
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
以下為remove方法的實(shí)現(xiàn)主體：
/**
* @param hash key的哈希值
* @param key the key
* @param value remove方法傳值null
* @param matchValue 值為true時(shí)漱挎，僅和傳入value相等時(shí)移除系枪，由于remove方法傳入value為null，
* 因此該參數(shù)傳值false磕谅，移除時(shí)對value無要求
* @param movable 為false時(shí)不熠動(dòng)其他node節(jié)點(diǎn)私爷，remove方法傳入true
* @return 返回移除node，或者不存在對應(yīng)node時(shí)返回null
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 數(shù)組不為空膊夹，找到要移除的key對應(yīng)的node
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 哈希值相等衬浑，且與key為同一對象，記錄節(jié)點(diǎn)node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) { // next不為空放刨，證明key與其他對象發(fā)生過哈希沖突工秩，桶上至少為一個(gè)鏈表
if (p instanceof TreeNode) // 鏈表已經(jīng)樹形化過
// 獲取key對應(yīng)的紅黑樹節(jié)點(diǎn)，邏輯和get方法一致
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else { // 僅為鏈表进统，未樹形化
// 遍歷找到要移除的node節(jié)點(diǎn)
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 確定要移除的node助币，開始根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)移除node節(jié)點(diǎn)
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) // 紅黑樹
// 紅黑樹移除節(jié)點(diǎn)相對要復(fù)雜一些，因?yàn)閯h除一個(gè)節(jié)點(diǎn)很有可能會(huì)改變紅黑樹的結(jié)構(gòu)螟碎，
// 因此需要做一些左右旋以及重新著色來使得整棵樹滿足一棵紅黑樹
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // 不沖突移除
tab[index] = node.next;
else // 鏈表移除
p.next = node.next;
++modCount; // modCount自增眉菱，記錄修改次數(shù)
--size; // size做相應(yīng)減少
afterNodeRemoval(node);
return node; // 返回移除節(jié)點(diǎn)node
}
}
return null;
}
使用注意
- 當(dāng)
size達(dá)到threshold時(shí)，會(huì)觸發(fā)resize擴(kuò)容操作掉分，從而進(jìn)行再哈希俭缓，新建數(shù)組克伊，以及數(shù)據(jù)拷貝等比較耗費(fèi)資源和性能的操作，因此盡量預(yù)判HashMap的初始size华坦，減少或避免其resize操作愿吹； - HashMap是非線程安全的，從其設(shè)計(jì)來看季春，并沒有發(fā)現(xiàn)任何并發(fā)同步處理的痕跡洗搂，若要使用線程安全的Map，可以考慮
ConcurrentHashMap载弄； - 關(guān)于HashMap可能出現(xiàn)的內(nèi)存泄漏耘拇，當(dāng)我們定義一個(gè)類作為key，同時(shí)我們又重寫了
hashCode()方法宇攻，hash值的生成依賴于該類的一個(gè)屬性惫叛，這個(gè)屬性對外暴露寫方法，當(dāng)該類的一個(gè)實(shí)例作為key已經(jīng)被put進(jìn)入了HashMap逞刷，在此之后與hash值生成有關(guān)的那個(gè)屬性的值又被改變了嘉涌，那么生成的hash值就很有可能不與put時(shí)的hash值相同，那么這個(gè)key對應(yīng)的value就再也不能被檢索到夸浅，剛好這個(gè)HashMap的生命周期又足夠長仑最，就造成了內(nèi)存泄漏。當(dāng)然帆喇，內(nèi)存泄漏的場景可能不止這一種警医，這是我最先能想到的一種場景，若有其他場景坯钦，請各位不吝賜教预皇！
自定義類參考如下：
class Model {
private int value;
/**
* 獲取字段值： value.
*
* @return 返回字段值： value.
*/
public int getValue() {
return value;
}
/**
* 設(shè)置字段值： value.
*
* @param value value .
*/
public void setValue(int value) {
this.value = value;
}
@Override
public int hashCode() {
return value + Integer.valueOf(value).hashCode();
}
}
后話
事實(shí)上，關(guān)于HashMap的源碼婉刀，我還有很多并未看懂吟温，尤其是關(guān)于紅黑樹的部分，根本原因還是對于紅黑樹的掌握程度還很欠缺突颊。雖然能大致說一些紅黑樹的東西鲁豪，但是要把這個(gè)特性操作轉(zhuǎn)化為代碼，并且應(yīng)用到不同的需求律秃，這又完全不是一回事了呈昔。丟下一兩篇關(guān)于紅黑樹的文章供大家一起學(xué)習(xí)（所有連接侵刪）：
- 紅黑樹深入剖析及Java實(shí)現(xiàn) ，大廠一貫作風(fēng)友绝，很容易讓人理解，跟著作者思路學(xué)習(xí)即可肝劲；
- 史上最清晰的紅黑樹講解（上） 迁客，同下篇一起品嘗口感更佳郭宝，非常詳細(xì)的講解；
- 史上最清晰的紅黑樹講解（下）
自己還是太菜了掷漱，與大家共勉粘室！
