HashMap也是我們使用非常多的Collection，它是基于哈希表的 Map 接口的實(shí)現(xiàn)，以key-value的形式存在。在HashMap中，key-value總是會(huì)當(dāng)做一個(gè)整體來(lái)處理，系統(tǒng)會(huì)根據(jù)hash算法來(lái)來(lái)計(jì)算key-value的存儲(chǔ)位置，我們總是可以通過(guò)key快速地存、取value。下面就來(lái)分析HashMap的存取。
一. 定義
HashMap實(shí)現(xiàn)了Map接口，繼承AbstractMap。這是使用了模板方法模式，其中Map接口定義了鍵映射到值的規(guī)則，而AbstractMap類提供 Map 接口的骨干實(shí)現(xiàn)，為 Map 的實(shí)現(xiàn)類提供了一些通用方法。
public class HashMap<K, V> extends AbstractMap<K, V>
implements Map<K, V>, Cloneable, Serializable
二. 構(gòu)造函數(shù)
HashMap 有多個(gè)構(gòu)造函數(shù)，在處理 threshold 和 loadFactor 時(shí)有所不同，所以在 resize() 方法在初始化時(shí)會(huì)對(duì)不同的情況采用相應(yīng)的處理邏輯。
/*
* 構(gòu)造一個(gè)具有默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75) 的空 HashMap
* 這個(gè)方法沒(méi)有初始化 threshold 和 loadFactor
* 所以此時(shí)兩個(gè)變量的值都為零，與其他構(gòu)造函數(shù)不一樣
*/
public HashMap() {}
// 構(gòu)造一個(gè)帶指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap
public HashMap(int initialCapacity) {}
// 通過(guò)傳入的 Map 構(gòu)造一個(gè)使用默認(rèn)的加載因子的 HashMap
public HashMap(Map<? extends K, ? extends V> m) {}
// 構(gòu)造一個(gè)帶指定初始容量和加載因子的空 HashMap
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException();
this.loadFactor = loadFactor;
/* tableSizeFor() 把threshold 設(shè)置為最靠近且比 initialCapacity 大的2的冪次方，
* 保證容量是2的冪次方
* HashMap 中并沒(méi)有用于存儲(chǔ) initialCapacity 的變量
* 而且散列表的數(shù)組 table 是懶加載的，所以在初始化前使用 threshold 存儲(chǔ) initialCapacity
* 這種情況下在 table 初始化時(shí)會(huì)使用 threshold 作為 table 的容量
*/
this.threshold = tableSizeFor(initialCapacity);
}
三. 數(shù)據(jù)結(jié)構(gòu)
我們知道在 Java中 最常用的兩種結(jié)構(gòu)是數(shù)組和模擬指針(引用)，幾乎所有的數(shù)據(jù)結(jié)構(gòu)都可以利用這兩種來(lái)組合實(shí)現(xiàn)，HashMap 也是如此。HashMap 是一個(gè)“鏈表散列”，與 JDK 1.7 以及之前的版本不同，JDK1.8 在鏈表長(zhǎng)度大于8時(shí)會(huì)轉(zhuǎn)為用紅黑樹存儲(chǔ)，當(dāng)長(zhǎng)度減少為6時(shí)又會(huì)轉(zhuǎn)為用鏈表存儲(chǔ)。如下是它數(shù)據(jù)結(jié)構(gòu)：
哈希桶數(shù)組和節(jié)點(diǎn) Node
哈希桶數(shù)組 Node<K,V>[] table使用一個(gè)用于存放鏈表或紅黑樹根節(jié)點(diǎn)的數(shù)組，使用哈希表進(jìn)行存儲(chǔ)。
transient Node<K,V>[] table;
Node 是 HashMap 的一個(gè)內(nèi)部類，實(shí)現(xiàn)了 Map.Entry 接口，本質(zhì)是就是一個(gè)映射(鍵值對(duì))。上圖中的每個(gè)黑色圓點(diǎn)就是一個(gè) Node 對(duì)象。
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) {...}
public final K getKey() {...}
public final V getValue() {...}
public final String toString() {...}
public final int hashCode() {...}
public final V setValue(V newValue) {...}
public final boolean equals(Object o) {...}
}
哈希表存儲(chǔ)
HashMap 就是使用哈希表來(lái)存儲(chǔ)的。Java 中 HashMap 采用了鏈地址法。鏈地址法，簡(jiǎn)單來(lái)說(shuō)，就是數(shù)組加鏈表的結(jié)合。在每個(gè)數(shù)組元素上都一個(gè)鏈表結(jié)構(gòu)，當(dāng)數(shù)據(jù)被Hash后，得到數(shù)組下標(biāo)，把數(shù)據(jù)放在對(duì)應(yīng)下標(biāo)元素的鏈表上。
在 HashMap 獲取 key 的 hashCode 時(shí)，會(huì)調(diào)用 key 的 hashCode() 方法得到其hashCode，然后再通過(guò) hash(）方法進(jìn)行二次哈希來(lái)定位該鍵值對(duì)的存儲(chǔ)位置，有時(shí)兩個(gè) key 會(huì)定位到相同的位置，表示發(fā)生了 Hash 碰撞。當(dāng)然 Hash 算法計(jì)算結(jié)果越分散均勻，Hash 碰撞的概率就越小，map的存取效率就會(huì)越高。
如果哈希桶數(shù)組很大，即使較差的Hash算法也會(huì)比較分散，如果哈希桶數(shù)組數(shù)組很小，即使好的Hash算法也會(huì)出現(xiàn)較多碰撞，所以就需要在空間成本和時(shí)間成本之間權(quán)衡，其實(shí)就是在根據(jù)實(shí)際情況確定哈希桶數(shù)組的大小，并在此基礎(chǔ)上設(shè)計(jì)好的hash算法減少Hash碰撞。那么通過(guò)什么方式來(lái)控制map使得Hash碰撞的概率又小，哈希桶數(shù)組（Node[] table）占用空間又少呢？答案就是好的 Hash 算法和擴(kuò)容機(jī)制。
在理解Hash和擴(kuò)容流程之前，我們得先了解下HashMap的幾個(gè)字段。從HashMap的默認(rèn)構(gòu)造函數(shù)源碼可知，構(gòu)造函數(shù)就是對(duì)下面幾個(gè)字段進(jìn)行初始化，源碼如下：
transient int size; // 當(dāng)前 HashMap 存儲(chǔ)的元素?cái)?shù)量
transient int modCount; // 修改計(jì)數(shù)器，用于 fail-fast 機(jī)制
int threshold; // capacity * loadFactor，能容納的元素極限
final float loadFactor; // 加載因子
由公式** threshold = capacity * loadFactor **可知，threshold就是在此loadFactor 和 capacity (數(shù)組長(zhǎng)度)對(duì)應(yīng)下允許存儲(chǔ)的最大元素?cái)?shù)目，超過(guò)這個(gè)數(shù)目就重新resize(擴(kuò)容)，擴(kuò)容后的HashMap容量是之前容量的兩倍。默認(rèn)的負(fù)載因子0.75是對(duì)空間和時(shí)間效率的一個(gè)平衡選擇，顯然 loadFactor 越大碰撞就越不容易發(fā)生但會(huì)耗費(fèi)更多的空間；loadFactor 越小，耗費(fèi)的空間會(huì)減少但是碰撞會(huì)增多導(dǎo)致時(shí)間效率下降。如果內(nèi)存空間很多而又對(duì)時(shí)間效率要求很高，可以降低負(fù)載因子Load factor的值；相反，如果內(nèi)存空間緊張而對(duì)時(shí)間效率要求不高，可以增加負(fù)載因子loadFactor的值，這個(gè)值可以大于1。
在 HashMap 中，哈希桶數(shù)組table的長(zhǎng)度length大小必須為2的n次方，這是一種非常規(guī)的設(shè)計(jì)，常規(guī)的設(shè)計(jì)是把桶的大小設(shè)計(jì)為素?cái)?shù)。相對(duì)來(lái)說(shuō)素?cái)?shù)導(dǎo)致沖突的概率要小于合數(shù)，具體證明可以參考
http://blog.csdn.net/liuqiyao_01/article/details/14475159，Hashtable 初始化桶大小為11，就是桶大小設(shè)計(jì)為素?cái)?shù)的應(yīng)用（Hashtable 擴(kuò)容后不能保證還是素?cái)?shù)）。HashMap 采用這種非常規(guī)設(shè)計(jì)，主要是為了在取模和擴(kuò)容時(shí)做優(yōu)化，同時(shí)為了減少?zèng)_突，HashMap 定位哈希桶索引位置時(shí)，也加入了高位參與運(yùn)算的過(guò)程。但這里存在一個(gè)問(wèn)題，即使負(fù)載因子和Hash算法設(shè)計(jì)的再合理，也免不了會(huì)出現(xiàn)拉鏈過(guò)長(zhǎng)的情況，一旦出現(xiàn)拉鏈過(guò)長(zhǎng)，則會(huì)嚴(yán)重影響HashMap的性能。于是，在 JDK1.8 版本中，對(duì)數(shù)據(jù)結(jié)構(gòu)做了進(jìn)一步的優(yōu)化，引入了紅黑樹。而當(dāng)鏈表長(zhǎng)度太長(zhǎng)（默認(rèn)超過(guò)8）時(shí)，鏈表就轉(zhuǎn)換為紅黑樹，利用紅黑樹快速增刪改查的特點(diǎn)提高 HashMap 的性能。
方法實(shí)現(xiàn)
HashMap的內(nèi)部功能實(shí)現(xiàn)很多，本文主要從根據(jù)key獲取哈希桶數(shù)組索引位置、put方法的詳細(xì)執(zhí)行、擴(kuò)容過(guò)程三個(gè)具有代表性的點(diǎn)深入展開講解
1. 二次哈希 - hash() 方法
前面說(shuō)過(guò)HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，HashMap 通過(guò) hashCode 確定 key 在數(shù)組的位置。所以 HashMap 里面的元素位置分布得越均勻越好，盡量使得每個(gè)位置上的元素?cái)?shù)量只有一個(gè)，那么當(dāng)我們根據(jù) hashCode 找到指定位置時(shí)就不用遍歷鏈表，大大優(yōu)化了查詢的效率。先看看源碼的實(shí)現(xiàn)：
static final int hash(Object key) {
int h;
// h = key.hashCode() 取 hashCode 值
// h ^ (h >>> 16) 將高位與低位進(jìn)行異或，
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
在 JDK1.8 的實(shí)現(xiàn)中，優(yōu)化了高位運(yùn)算的算法，通過(guò) hashCode() 的高16位異或低16位實(shí)現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質(zhì)量來(lái)考慮的，這么做可以在數(shù)組 table 的 length 比較小的時(shí)候，也能保證考慮到高低位都參與到 HashCode 的計(jì)算中，同時(shí)不會(huì)有太大的開銷。
在 JDK1.8 中通過(guò) (n - 1) & hash 定位 key 在數(shù)組中位置，其中由于 table 的大小總是2的n次方，所以通過(guò)位與替代了取模（二者是等效的）大大提升了效率。
下面舉例說(shuō)明下，n為table的長(zhǎng)度。
2. 存儲(chǔ)實(shí)現(xiàn) - put() 方法
下面是 put() 方法的流程圖，結(jié)合流程圖可以更好的理解源碼
// 與 JDK 1.7 不同，JDK 1.8 將存儲(chǔ)過(guò)程的實(shí)際處理邏輯放在 putVal() 方法中
public V put(K key, V value) {
// 對(duì) key 進(jìn)行二次 hash
return putVal(hash(key), key, value, false, true);
}
// onlyIfAbsent 為 true, 不修改已經(jīng)存在的 value
// evict 為 false, 數(shù)組 table 處于 creation 模式
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判斷數(shù)組 table 是否為空或長(zhǎng)度為零，否則執(zhí)行resize()進(jìn)行擴(kuò)容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根據(jù) hash 值獲得對(duì)應(yīng)的數(shù)組索引 i，如果table[i]==null，則直接添加新節(jié)點(diǎn)
// 此時(shí) p 為table[i] 的首元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//此時(shí) table[i] 不為空，即發(fā)生了 hash 碰撞
else {
Node<K,V> e; K k;
// 如果根節(jié)點(diǎn)的 key 和 傳入的 key 相同則在下一個(gè) if 語(yǔ)句修改 value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判斷 table[i] 是否為 treeNode (紅黑樹)，如果是紅黑樹則在樹中插入鍵值對(duì)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 遍歷 table[i] 的鏈表
for (int binCount = 0; ; ++binCount) {
// 要是下一個(gè)元素為空則插入一個(gè)新的節(jié)點(diǎn)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 要是鏈表長(zhǎng)度大于 8，則將鏈表轉(zhuǎn)為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) t
treeifyBin(tab, hash);
break;
}
// 要是 key 已經(jīng)存在則下一個(gè) if 語(yǔ)句修改其 value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 在這里集中進(jìn)行 value 修改，要是需要修改 value 則 e 肯定不為空
if (e != null) {
V oldValue = e.value;
// onlyIfAbsent 為 true 則不修改已經(jīng)存在的 value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// HashMap 中為空，留給 LinkedHashMap 實(shí)現(xiàn)
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 要是當(dāng)前元素的數(shù)量超過(guò) threshold 則擴(kuò)容
if (++size > threshold)
resize();
// HashMap 中為空，留給 LinkedHashMap 實(shí)現(xiàn)
afterNodeInsertion(evict);
return null;
}
3. 擴(kuò)容實(shí)現(xiàn) - resize() 方法
HashMap 對(duì)數(shù)組 table 是懶加載的，只有當(dāng)?shù)谝淮握{(diào)用 put() 方法時(shí)才會(huì)調(diào)用 resize() 方法進(jìn)行初始化。resize() 方法的主要功能有兩個(gè)：
- 對(duì)數(shù)組 table 進(jìn)行初始化，默認(rèn)容量為16；
- 對(duì)數(shù)字 table 進(jìn)行擴(kuò)容，保證其 capacity 是上一次的兩倍，而且始終為2的n次方。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 如果 table 沒(méi)有初始化則為零，否則為數(shù)組的長(zhǎng)度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
/*
* 擴(kuò)容或初始化前的準(zhǔn)備操作：設(shè)置 newCap 和 newThr
* 如果 table 已經(jīng)初始化則進(jìn)行擴(kuò)容
* 否則根據(jù)初始化使用的構(gòu)造函數(shù)進(jìn)行相應(yīng)的初始化準(zhǔn)備操作
*/
// 初始化前 oldCap=0，oldCap>0 則表示已初始化
if (oldCap > 0) {
// oldCap > 0，此時(shí) table 已經(jīng)初始化，進(jìn)行擴(kuò)容操作
// 如果 oldCap 大于 2^30 則把 threshold 設(shè)為最大，不再對(duì)數(shù)組擴(kuò)容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量擴(kuò)大兩倍后小于 MAXIMUM_CAPACITY 且 oldCap>16,則將threshold擴(kuò)大兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 要是條件不成立 newThr=0
}
// 此時(shí) oldCap=0 需要進(jìn)行初始化的準(zhǔn)備
else if (oldThr > 0)
// 此時(shí) oldThr 被設(shè)置(即 threshold），new HashMap 時(shí)使用下面的構(gòu)造函數(shù)
// HashMap(int initialCapacity)
// HashMap(int initialCapacity, float loadFactor)
newCap = oldThr;
else {
// threshold=0，對(duì)應(yīng)構(gòu)造方法 HashMap()
newCap = DEFAULT_INITIAL_CAPACITY; // 將 newCap 設(shè)置為默認(rèn)值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 對(duì)應(yīng)構(gòu)造函數(shù)
// HashMap(int initialCapacity)
// HashMap(int initialCapacity, float loadFactor)
// 或者在下面條件不成立時(shí)重新計(jì)算 newThr
// (newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY
float ft = (float)newCap * loadFactor;
// 因?yàn)槭褂玫氖侵付ǖ?nitialCapacity,所以需要對(duì) newThr 進(jìn)行判斷處理
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 根據(jù) newCap 創(chuàng)建新數(shù)組，和 設(shè)置新的 threshold
threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
/****** 初始化到此結(jié)束，下面是擴(kuò)容操作 *****/
if (oldTab != null) {
// 將數(shù)據(jù)從舊數(shù)組遷移到新數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果首元素后面沒(méi)有元素則直接遷移到新數(shù)組
// 因?yàn)閿U(kuò)容后會(huì)與首元素發(fā)生 hash 碰撞的只能是其后面跟著的元素
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是紅黑樹則轉(zhuǎn)到紅黑樹的處理方法
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
/*
* 處理鏈表，擴(kuò)容后 hash 不一定仍相同
* 假設(shè)容量從 16 增加到32
* 首元素和下一個(gè)元素 hash 前五位為 00001 和 10001
* 容量為16時(shí)，hash&(cap-1) 均為 0001
* 而容量為32時(shí)， hash&(cap-1) 則為 00001 和 10001
* 同時(shí)容量為16時(shí)， hash&cap 則為 00000 和 10000
* */
Node<K,V> loHead = null, loTail = null; // 低位 hash
Node<K,V> hiHead = null, hiTail = null; // 高位 hash
Node<K,V> next;
do {
next = e.next;
// 擴(kuò)容時(shí)增加的那一位為零，hash 不變
// loHead 指向第一個(gè)元素，loTail 指向最后一個(gè)元素
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 擴(kuò)容時(shí)增加的那一位為一，hash = hash + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 向新數(shù)組添加遷移數(shù)據(jù)
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
相關(guān)文章
