1. 簡介
HashMap
Java中的HashMap是符號(hào)表的一種哈希實(shí)現(xiàn)（采用拉鏈法）饰序，HashMap用來存儲(chǔ)鍵值對(duì)，鍵和值都可以為Null，其中鍵是唯一的守伸。在Java7中的實(shí)現(xiàn)是用數(shù)組+鏈表，在Java8中的實(shí)現(xiàn)是數(shù)組+鏈表+紅黑樹辕漂。因?yàn)橐M(jìn)了紅黑樹的呢灶，所以Java8中的HashMap的查找效率提高了不少。以下的講解的源碼也是Java8的源碼钉嘹。
拉鏈法
- 拉鏈法是一種處理哈希沖突的一種方法鸯乃，其他的還有線性探測法、平方探測法跋涣、雙散列法缨睡。
- 拉鏈法將產(chǎn)生沖突的元素放在數(shù)組沖突位置上的一個(gè)存儲(chǔ)結(jié)構(gòu)上（一般是鏈表）
2. 實(shí)現(xiàn)
HashMap內(nèi)部結(jié)構(gòu)
- 在HashMap中，數(shù)組
table的大小是2的n次冪陈辱。 - 當(dāng)HashMap中的鍵值對(duì)數(shù)量超過
threshold這個(gè)閾值時(shí)奖年，需要對(duì)數(shù)組進(jìn)行擴(kuò)容。為了避免數(shù)組過小導(dǎo)致每個(gè)數(shù)組位置存儲(chǔ)的鏈表過長或紅黑樹過大沛贪，導(dǎo)致查找效率低下陋守。這其實(shí)是一種以空間換時(shí)間的方法。 - 當(dāng)數(shù)組中的鏈表超過8時(shí)利赋，將鏈表換成紅黑樹以提高查找效率水评。
HashMap內(nèi)部結(jié)構(gòu)圖
屬性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; /默認(rèn)初始容量
static final int MAXIMUM_CAPACITY = 1 << 30; /最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; /加載因子
static final int TREEIFY_THRESHOLD = 8; /由鏈表轉(zhuǎn)換為紅黑樹時(shí)鏈表長度的閾值
static final int UNTREEIFY_THRESHOLD = 6; /由紅黑樹轉(zhuǎn)換為鏈表時(shí)紅黑樹大小的閾值
static final int MIN_TREEIFY_CAPACITY = 64; /由鏈表轉(zhuǎn)換為紅黑樹時(shí)桶的閾值
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size; /哈希表當(dāng)前的鍵值對(duì)數(shù)量
transient int modCount; /哈希表內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)
int threshold; /擴(kuò)容的閾值
final float loadFactor; /負(fù)載因子
結(jié)點(diǎn)類型
在HashMap中存儲(chǔ)的鍵值對(duì)都是Node或是Node的子類，鏈表的結(jié)點(diǎn)類型是Node媚送，紅黑樹的結(jié)點(diǎn)類型是TreeNode之碗。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; /儲(chǔ)存對(duì)key使用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;
}
}
構(gòu)造函數(shù)
-
initialCapacity參數(shù)用來確定哈希表初始容量（桶的數(shù)量），不過并不直接使用initialCapacity來作為初始容量季希，而是使用由tableSizeFor方法來得出不小于initialCapacity的第一個(gè)2的n次冪的正整數(shù)（例如輸入8返回8褪那，輸入9返回16）作為初始容量。 -
loadFactor用來指定負(fù)載因子
當(dāng)構(gòu)造函數(shù)執(zhí)行完并不會(huì)創(chuàng)建Node的數(shù)組式塌，而是等到put方法執(zhí)行時(shí)由resize方法創(chuàng)建博敬。
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);
}
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;
}
hash方法
進(jìn)行查找操作最重要的一步就是確定鍵在哪個(gè)桶中，其中第一步就用到hash方法峰尝，使用到hash方法是為了使鍵在數(shù)組中的分布更加均勻偏窝，減少?zèng)_突：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
接著利用(n - 1) & hash（n是數(shù)組table的大小）得出鍵在哪個(gè)桶中武学，那這里為什么不用hash % n呢祭往？因?yàn)槲贿\(yùn)算的速度比求余快。這里的table的大小必須是2的n次冪火窒，原因有兩個(gè)：
- 因?yàn)閚 - 1之后高位為0硼补，低位部分為1，使得哈希方法結(jié)果在參與與運(yùn)算之后有意義熏矿，從而減少?zèng)_突已骇。
- 為之后的擴(kuò)容方法做優(yōu)化
put方法
數(shù)組table就是第一次執(zhí)行put方法時(shí)創(chuàng)建出來的离钝。
put方法執(zhí)行流程圖
put方法執(zhí)行流程圖
源碼分析
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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
/數(shù)組還沒創(chuàng)建或者數(shù)組大小為0
if ((tab = table) == null || (n = tab.length) == 0)
/執(zhí)行擴(kuò)容操作
n = (tab = resize()).length;
/求得鍵所在的桶，并判斷是否為空
if ((p = tab[i = (n - 1) & hash]) == null)
/若為空直接添加結(jié)點(diǎn)作為鏈表頭結(jié)點(diǎn)到該位置上
tab[i] = newNode(hash, key, value, null);
else {
/e是用來存儲(chǔ)找到的結(jié)點(diǎn)
Node<K,V> e; K k;
/如果該桶的第一個(gè)結(jié)點(diǎn)就是褪储，則找到
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/否則判斷該桶存儲(chǔ)的是否為一棵紅黑樹
else if (p instanceof TreeNode)
/調(diào)用putTreeVal方法向該樹插入該結(jié)點(diǎn)卵渴，如果返回為空則插入成功，否則在樹中找到該結(jié)點(diǎn)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
/遍歷該桶的鏈表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
/當(dāng)發(fā)現(xiàn)下個(gè)結(jié)點(diǎn)為空鲤竹，證明已經(jīng)遍歷完所有結(jié)點(diǎn)還沒發(fā)現(xiàn)key所在的結(jié)點(diǎn)
那就直接插入新結(jié)點(diǎn)
p.next = newNode(hash, key, value, null);
/判斷鏈表長度是否超過8浪读，是就將鏈表樹形化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
/找到key所在的結(jié)點(diǎn)則退出
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
/判斷結(jié)點(diǎn)是否為空，不為空則找到
if (e != null) { // existing mapping for key
V oldValue = e.value;
/如果允許結(jié)點(diǎn)存在時(shí)替換舊的值或者舊的值為null則替換舊值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
擴(kuò)容方法
Java 1.8里的擴(kuò)容方法比較特別的一個(gè)優(yōu)化就是擴(kuò)容后結(jié)點(diǎn)的轉(zhuǎn)移辛藻，例如對(duì)于原數(shù)組的一個(gè)桶中的所有元素要轉(zhuǎn)移到新數(shù)組中需要一個(gè)個(gè)重新用hash & (n - 1)計(jì)算新位置嗎碘橘？當(dāng)然不用。得益于數(shù)組大小的特點(diǎn)（2的n次冪）揩尸，我們可以輕易知道原數(shù)組的一個(gè)桶中所有結(jié)點(diǎn)轉(zhuǎn)移到新數(shù)組中只會(huì)存在于兩個(gè)位置：
- 原索引
-
原索引 + oldCap
image
關(guān)于這個(gè)的原理觀察一下這個(gè)hash & (n - 1)和上圖你就能發(fā)現(xiàn)擴(kuò)容后改變的是n伞辛，而與hash進(jìn)行與運(yùn)算的n - 1比原來多了一位1幕帆，與運(yùn)算后出來的索引比原來多一種可能，而這種可能就是在原索引的基礎(chǔ)上加上oldCap恭金。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
/若原數(shù)組的大小已經(jīng)大于0
if (oldCap > 0) {
/ 若原數(shù)組大小已經(jīng)達(dá)到最大值坟瓢，則設(shè)置閾值為Integer.MAX_VALUE勇边，即以后不能再執(zhí)行擴(kuò)容方法
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}/否則將數(shù)組擴(kuò)大一倍，
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
/擴(kuò)容后數(shù)組的大小未達(dá)到最大值并且舊數(shù)組大小不小于默認(rèn)初始容量則將閾值也擴(kuò)大一倍
newThr = oldThr << 1;
}/否則如果舊閾值大于0（即在構(gòu)造函數(shù)中給出了initialCapacity）
else if (oldThr > 0)
newCap = oldThr;
else {
/未給定initialCapacity就使用默認(rèn)初始容量折联，閾值也是默認(rèn)的
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
/如果沒有設(shè)置新閾值
if (newThr == 0) {
/計(jì)算出新閾值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
/當(dāng)舊數(shù)組不為空時(shí)粒褒，將舊數(shù)組里的所有結(jié)點(diǎn)轉(zhuǎn)移到新數(shù)組里去
if (oldTab != null) {
/遍歷數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
/判斷桶是否為空
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
/如果該桶只有一個(gè)結(jié)點(diǎn)，就直接將該結(jié)點(diǎn)轉(zhuǎn)移到新數(shù)組對(duì)應(yīng)的桶中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
/否則如果結(jié)點(diǎn)是TreeNode類型诚镰，執(zhí)行split方法
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
/兩條鏈表
第一條是代表原索引位置上的鏈表
第二條是代表原索引 + oldCap位置上的鏈表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
/遍歷該鏈表
do {
next = e.next;
/若該結(jié)點(diǎn)在新數(shù)組中的索引為原索引
if ((e.hash & oldCap) == 0) {
/若鏈表為空奕坟，添加該結(jié)點(diǎn)為頭結(jié)點(diǎn)
if (loTail == null)
loHead = e;
else /否則在尾部添加該結(jié)點(diǎn)
loTail.next = e;
loTail = e;
}/否則該結(jié)點(diǎn)在新數(shù)組中的索引為原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
/如果鏈表不為空將該鏈表添加到新數(shù)組
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
樹形化
當(dāng)添加一個(gè)結(jié)點(diǎn)后如果結(jié)點(diǎn)所在鏈表的長度大于8時(shí)，要將鏈表樹形化（轉(zhuǎn)換為紅黑樹）清笨。但是進(jìn)行樹形化還需要滿足一個(gè)條件月杉，就是數(shù)組的大小要不小于MIN_TREEIFY_CAPACITY。
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;
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);
}
}
remove方法
remove方法執(zhí)行過程圖
remove方法執(zhí)行過程圖
源碼分析
-
matchValue是一個(gè)布爾型參數(shù)抠艾，為false表示不需要匹配值苛萎，為true表示需要匹配值，值一樣才算找到 -
movable表示移除紅黑樹結(jié)點(diǎn)時(shí)需不需要移動(dòng)其他結(jié)點(diǎn)
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
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;
/只有在表不為空且找到鍵所在的桶也不為空才能繼續(xù)
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;
/判斷第一個(gè)結(jié)點(diǎn)是否是要找的結(jié)點(diǎn)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
/否則當(dāng)存在下一個(gè)結(jié)點(diǎn)才繼續(xù)
else if ((e = p.next) != null) {
/判斷桶中的結(jié)點(diǎn)是否是紅黑樹的結(jié)點(diǎn)
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {/否則遍歷鏈表尋找結(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);
}
}
/結(jié)點(diǎn)不為空則為找到
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
迭代器
在HashMap里一共有三種迭代器：
KeyIteratorValueIteratorEntryIterator
這三種迭代器都繼承了HashIterator類并實(shí)現(xiàn)了Iterator接口供KeySet检号、Values腌歉、EntrySet使用。其中最重要的HashIterator是用來迭代哈希表中的結(jié)點(diǎn)齐苛。
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
/找到第一個(gè)不為空的桶
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
/如果modCount != expectedModCount則表示可能有其他線程修改了哈希表或者當(dāng)前線程調(diào)用非迭代器的方法修改
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
/設(shè)置current為當(dāng)前結(jié)點(diǎn)并找到下一個(gè)結(jié)點(diǎn)賦值給next
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
在HashMap中的modCount是和迭代器中expectedModCount搭配起來提供快速失敗機(jī)制（fail-fast）的翘盖。 體現(xiàn)在用迭代器遍歷HashMap時(shí)，如果遍歷過程中對(duì)集合對(duì)象的內(nèi)容進(jìn)行了修改凹蜂，可能會(huì)導(dǎo)致迭代器遍歷出現(xiàn)異常最仑。所以每次使用next藐俺、remove方法都會(huì)先判斷modCount與expectedModCount是否相等，如果不相等則表示被修改過泥彤，就會(huì)拋出ConcurrentModificationException欲芹。在迭代器遍歷HashMap時(shí)如果想移除遍歷到的值可以使用Iterator的remove方法。
3. 最后
- HashMap是無序的吟吝，即無法維持鍵值對(duì)的先后插入順序菱父，也無法提供按鍵排序的功能，如要使用有序的map（符號(hào)表）剑逃，可以使用下面兩種：
-
LinkedHashMap：LinkedHashMap是HashMap的子類浙宜，可以保證插入的先后順序，用迭代器遍歷LinkedHashMap時(shí)蛹磺，先得到的記錄是先插入的粟瞬，也可以在構(gòu)造時(shí)指定參數(shù)，按照訪問次序進(jìn)行排序萤捆。 -
TreeMap: TreeMap實(shí)現(xiàn)SortedMap接口裙品，可以把記錄按鍵的大小排序，默認(rèn)是升序排序俗或，也可以指定比較器進(jìn)行排序市怎，當(dāng)用迭代器遍歷TreeMap時(shí)，得到的記錄是排過序的辛慰。
-
- HashMap不是線程安全的類区匠，不能適用于多線程的環(huán)境。不過有三種方式使用線程安全的map（符號(hào)表）：
-
Hashtable： 已過時(shí)的類不推薦使用帅腌。 -
ConcurrentHashMap：推薦使用驰弄，使用CAS機(jī)制使得并發(fā)情況下效率比Hashtable高 -
Collections.synchronizedMap(map)：使用靜態(tài)工廠方法將HashMap對(duì)象封裝成一個(gè)線程安全的類，因?yàn)?code>SynchronizedMap使用了synchronized關(guān)鍵字速客，所以并發(fā)效率不如ConcurrentHashMap高戚篙。
-
