一、概述
在Java開(kāi)發(fā)中，HashMap使用的頻率還是比較多的，主要通過(guò)key-value的形式來(lái)存儲(chǔ)數(shù)據(jù)，但是HashMap的原理是怎樣的呢？他是如何進(jìn)行增刪改查的呢？所以今天我們就帶著這些問(wèn)題來(lái)看源碼，主要看它的put，get，remove方法。本文我們使用的JDK版本為1.8。
二、源碼分析
在分析源碼之前，我們先來(lái)看一下HashMap的簡(jiǎn)單使用：
public static void main(String[] args) {
HashMap hashMap = new HashMap();
hashMap.put("key","張三");
System.out.println(hashMap.get("key"));
}
我們按照這個(gè)順序來(lái)繼續(xù)分析源碼，首先來(lái)看一下四個(gè)構(gòu)造方法：相關(guān)解釋已經(jīng)寫(xiě)在了注釋中。
構(gòu)造一個(gè)空的HashMap，默認(rèn)的初始容量為：16，默認(rèn)的加載因子為：0.75。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
構(gòu)造一個(gè)空的 指定容量的HashMap，默認(rèn)的加載因子為：0.75。
public HashMap(int initialCapacity) {
//繼續(xù)調(diào)用了第三個(gè)調(diào)用方法
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
構(gòu)造一個(gè)空的HashMap，指定初始容量，和 加載因子。
public HashMap(int initialCapacity, float loadFactor) {
//一些驗(yàn)證的操作
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);
//設(shè)置加載因子和初始容量
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
構(gòu)造一個(gè)與指定Map相同映射的HashMap 可以理解為將Map轉(zhuǎn)為HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
二、增和改
現(xiàn)在我們帶著第一個(gè)問(wèn)題：HashMap是如何插入數(shù)據(jù)的呢？我們直接來(lái)看put方法：
@param key 鍵
@param value 值
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
可以看到HashMap的put方法又調(diào)用了putVal方法，第一個(gè)參數(shù)中又調(diào)用了hash(key)，我們先來(lái)看看hash(key的作用)：這里問(wèn)題，為什么進(jìn)行位運(yùn)算
static final int hash(Object key) {
int h;
//如果key為空，返回0，否則返回key.hashCode的異或運(yùn)算 位移16位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這里簡(jiǎn)單舉例一個(gè)異或運(yùn)算：比如
h=2987074，在位運(yùn)算中都是通過(guò)二進(jìn)制進(jìn)行，
h的二進(jìn)制：0010 1101 1001 0100 0100 0010
h位移16位之后的二進(jìn)制：0000 0000 0000 0000 0010 1101
這兩個(gè)二進(jìn)制數(shù)再進(jìn)行^（異或）運(yùn)算，
結(jié)果為：0010 1101 1001 0100 0110 1111，轉(zhuǎn)為十進(jìn)制為：2987119。
看完hash方法之后繼續(xù)看putVal方法，但是在看putVal方法之前，我們先了解一下HashMap的一個(gè)內(nèi)部類，Node。
在Node類中，存儲(chǔ)了hash，key,value,和next，next就是當(dāng)前node指向的下一個(gè)節(jié)點(diǎn)，這就是一個(gè)鏈表結(jié)構(gòu)。
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;
}
}
繼續(xù)來(lái)看putVal方法：
/**
* @param hash key 的hash
* @param key
* @param value
* @param onlyIfAbsent 如果為true，則不更改現(xiàn)有值
* @param evict 如果為false，則表處于創(chuàng)建模式
* @return valur or 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為空，或 長(zhǎng)度為0時(shí)
//這里的table為Node<K,V>[] table，是一個(gè)數(shù)組，Node相當(dāng)于鏈表，所以到這里我們可以知道HashMap
//底層使用的是數(shù)組+鏈表
if ((tab = table) == null || (n = tab.length) == 0)
//n = 創(chuàng)建一個(gè)新的tab并返回長(zhǎng)度
//這里的n就是tab的長(zhǎng)度，即Node<K,V>[]數(shù)組長(zhǎng)度
n = (tab = resize()).length;
//通過(guò)數(shù)組長(zhǎng)度-1 與 hasn進(jìn)行與運(yùn)算拿到i即下標(biāo)，再通過(guò)下標(biāo)取數(shù)組中的node，
//如果為null是，創(chuàng)建一個(gè)新的node，賦值給tab[i]
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e;
K k;
//如果p中和傳入的hash相等，與 key相等時(shí)，
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//將p即node，賦值給e
e = p;
//否則 p是一個(gè)樹(shù)節(jié)點(diǎn)，將其插入到樹(shù)中，并賦值給e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//如果p的下一個(gè)節(jié)點(diǎn)為空，則創(chuàng)建一個(gè)node，賦值給p.next，
//這里采用的是尾插法，
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果數(shù)量大于 TREEIFY_THRESHOLD 即8時(shí)，將鏈表Node，轉(zhuǎn)換為樹(shù)（紅黑樹(shù)）
//到這里 HashMap的結(jié)構(gòu)就成為了數(shù)組+鏈表+紅黑樹(shù)。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果hash相等，則直接跳出循環(huán)，
//到這里就表示當(dāng)前的e（node）和傳入的值已經(jīng)相等了，所以沒(méi)必要循環(huán)了
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果node不為空，保存value為oldValue，
if (e != null) { // existing mapping for key
V oldValue = e.value;
//如果需要改變現(xiàn)有值，value為空時(shí)，將傳入的value賦值給node.value
//這里對(duì)應(yīng)的就是修改key的value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果當(dāng)前長(zhǎng)度大于默認(rèn)長(zhǎng)度
//++size 就是每次put后size+1，getSize()就是這個(gè)size
if (++size > threshold)
//執(zhí)行擴(kuò)容
resize();
afterNodeInsertion(evict);
return null;
}
三、查
put方法已經(jīng)分析完成了，相關(guān)的注釋我已經(jīng)寫(xiě)在了上面，大家可以認(rèn)真看，其實(shí)并不太難，接下來(lái)我們來(lái)看下一個(gè)問(wèn)題，HashMap中是如何通過(guò)key獲取Value的呢？接下來(lái)繼續(xù)看get方法：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n;
K k;
//如果tab不為null，與 查找到的node不為空時(shí)，
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果第一個(gè)node hash 和key和我們想要的hash key相同，直接返回此node
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果node的next不為空，
if ((e = first.next) != null) {
//如果node時(shí)TreeNode（樹(shù)節(jié)點(diǎn)）
if (first instanceof TreeNode)
//從樹(shù)中查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//通過(guò)循環(huán) 遍歷節(jié)點(diǎn)的next，如果找到hash和key相同的則返回。
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//沒(méi)有找到 返回null
return null;
}
四、刪
到這里，增改查就已經(jīng)分析完畢，最后來(lái)看刪除的方法：remove();
public V remove(Object key) {
Node<K,V> e;
//通過(guò)removeNode方法查找對(duì)應(yīng)的Node節(jié)點(diǎn)返回node.value
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
在removeNode方法中，和getNode原理大致相同，我們來(lái)簡(jiǎn)單看一下：
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; //n為長(zhǎng)度，index為下標(biāo)
//如果tab不為空 與 查找到的node不為空時(shí)，
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;
//如果node中的hash和傳入的hash相等，且key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//將p賦值給node
node = p;
//如果next不為空時(shí)，
else if ((e = p.next) != null) {
//如果p是樹(shù)節(jié)點(diǎn)
if (p instanceof TreeNode)
//node = 從樹(shù)節(jié)點(diǎn)中查找
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//否則 遍歷table，知道找到要?jiǎng)h除的node
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不為空，與 值相等時(shí)
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果node時(shí)樹(shù)節(jié)點(diǎn)，就從樹(shù)節(jié)點(diǎn)中刪除。
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//更改node的next為要?jiǎng)h除的next，就是更改當(dāng)前node的next引用 為 要?jiǎng)h除的next的引用
//這樣就相當(dāng)于與要?jiǎng)h除的節(jié)點(diǎn)斷開(kāi)了連接 從而實(shí)現(xiàn)了刪除
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
//size-1
--size;
afterNodeRemoval(node);
//最后返回刪除的node
return node;
}
}
return null;
}
到這里HashMap的增刪改查的源碼我們已經(jīng)看完了，所對(duì)應(yīng)的為：put()，get()，remove()。在上面的代碼中，我都已經(jīng)寫(xiě)好了注釋，根據(jù)注釋結(jié)合代碼看還是非常通俗易懂的。
五、總結(jié)
通過(guò)上面的分析，我們已經(jīng)基本理解了HashMap增刪改查的大致流程了，我們總結(jié)如下：
- 增(put)：
①：通過(guò)key的hashcode和hashcode的位移16位進(jìn)行異或運(yùn)算得到一個(gè)hash值。
②：如果存儲(chǔ)節(jié)點(diǎn)(Node)的數(shù)組為空，則創(chuàng)建一個(gè)新的數(shù)組。
③：通過(guò)數(shù)組的長(zhǎng)度-1 和 上面得到的hash進(jìn)行&運(yùn)算，得到一個(gè)node即p；
④：如果p為空，說(shuō)明該位置沒(méi)有存儲(chǔ)節(jié)點(diǎn)，則創(chuàng)建一個(gè)node對(duì)象，并存入對(duì)應(yīng)的下標(biāo)中。
⑤：否則，p不為空時(shí)，判斷Node是否是TreeNode(樹(shù)節(jié)點(diǎn))，如果是則插入到樹(shù)節(jié)點(diǎn)。
⑥：如果不是樹(shù)節(jié)點(diǎn)，則遍歷鏈表，直到鏈表的next為空時(shí)，將此node賦值給next。
⑦：同時(shí)判斷遍歷的次數(shù)，如果大于等于TREEIFY_THRESHOLD即8-1時(shí)，將鏈表轉(zhuǎn)換為紅黑樹(shù)。
⑧：如果key hash相同，且需要修改value時(shí)，則修改value。
⑨：最后進(jìn)行收尾工作，++size，如果長(zhǎng)度大于threshold，進(jìn)行擴(kuò)容。
- 改：
其實(shí)改的方法是包含在put方法之中的，當(dāng)傳入的key相同時(shí)，則根據(jù)參數(shù)onlyIfAbsent來(lái)決定是否更新這個(gè)值。
- 查(get)：
①：判斷tab不為空時(shí)，算出數(shù)組中的index，找到頭節(jié)點(diǎn)node。
②：如果頭節(jié)點(diǎn)的key和hash與傳入的相同，直接返回此node。
③：如果沒(méi)找到，繼續(xù)判斷，如果node為紅黑樹(shù)結(jié)構(gòu)，則從紅黑樹(shù)中查找。
④：如果沒(méi)找到，遍歷鏈表，繼續(xù)查找key hash和傳入相同的node，找到則返回。
⑤：沒(méi)找到，返回null。
- 刪(remove)：
查和刪的原理大致相同，首先都是通過(guò)一系列判斷查找出對(duì)應(yīng)的node節(jié)點(diǎn)，最后通過(guò)更改next的指向來(lái)達(dá)到刪除的效果。其中有一個(gè)參數(shù)：matchValue，如果為true時(shí)，則只會(huì)在兩個(gè)value相等的情況下才會(huì)刪除。
最后上一張HashMap的結(jié)構(gòu)圖，以供大家理解。
