前言
今天代碼也不想寫查刻，突然想起了HashMap，以前一直覺得還沒到看源碼的能力（當(dāng)然現(xiàn)在也感覺沒有），那就硬啃吧风钻。我們就從最經(jīng)常使用的的幾個操作進行HashMap的源碼分析英妓，此次的源碼分析基于Jdk1.8版本來進行挽放。文章一些相關(guān)內(nèi)容參考了網(wǎng)絡(luò)上的大佬绍赛，如有錯誤也請多多指教。
正文
HashMap的介紹
1.HashMap是一種根據(jù)鍵（key）值（value）來進行存儲的數(shù)據(jù)結(jié)構(gòu)辑畦，而且存儲多個值的時候吗蚌，key是不能相同的，也可以對已經(jīng)有key的值進行修改并覆蓋之前存在的值纯出。
2.HashMap最多只允許一條存儲數(shù)據(jù)的key為null蚯妇，可允許多個value為null。
3.HashMap是線程不安全的潦刃，Hashtable是線程安全的侮措。
HashMap的基本使用
public static void main(String[] args) {
//創(chuàng)建一個HashMap的實例，可以傳入泛型乖杠，以保存任意的數(shù)據(jù)類型
HashMap<String, String> map = new HashMap<>();
//插入一個key為1分扎，value為hello進行保存。
map.put("1", "hello");
//查找一個key為1里面的內(nèi)容胧洒，返回值根據(jù)泛型畏吓。
map.get("1");
//刪除一個key為1的值，包括key也進行刪除卫漫。
map.remove("1");
}
在JDK1.8之前菲饼，HashMap采用數(shù)組+鏈表實現(xiàn)，即使用鏈表處理沖突列赎，同一hash值的節(jié)點都存儲在一個鏈表里宏悦。但是當(dāng)位于一個桶中的元素較多，即hash值相等的元素較多時包吝，通過key值依次查找的效率較低饼煞。而JDK1.8中，HashMap采用數(shù)組+鏈表+紅黑樹實現(xiàn)诗越，當(dāng)鏈表長度超過閾值（8）時砖瞧，將鏈表轉(zhuǎn)換為紅黑樹，這樣大大減少了查找時間嚷狞。至于紅黑樹是什么块促，以后我會也會專門寫一篇文章記錄一下。
源碼分析之實例化
//實例化構(gòu)造函數(shù)
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
這個就是一個很簡單點的無參數(shù)的構(gòu)造函數(shù)床未，這也是我們最常用的一種構(gòu)造函數(shù)散罕，它初始化了加載因子為默認的值赃泡。
//加載因子的默認值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
加載因子是表示Hsah表中元素的填滿的程度延旧。
加載因子越大,填滿的元素越多,空間利用率越高甲捏，但沖突的機會加大了擅威。
反之,加載因子越小,填滿的元素越少,沖突的機會減小,但空間浪費多了。
源碼分析之put函數(shù)分析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
進行插入函數(shù)的時候會調(diào)用putVal這個函數(shù)，然后分別傳進key和value進行實現(xiàn)遍希，這里注意的是hash這個函數(shù)方法，它是計算key合適的hash值裂允。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
它通過把key的hashcode的值往右移了16位损离，即丟棄低16位，高16位全為0 绝编，然后進行異或運算僻澎，這樣做的同時可以保證最小的開銷，擾動處理次數(shù)也從 4次位運算 + 5次異或運算 降低到 1次位運算 + 1次異或運算十饥。
然后是putVal函數(shù)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
//這里是判斷是否第一次添加元素窟勃，如果是的話，調(diào)用resize方法進行擴容逗堵。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //獲得擴容后的長度秉氧。
// i = (n - 1) & hash 即上邊講得元素存儲在 map 中的數(shù)組角標(biāo)計算
//如果對應(yīng)位置有已經(jīng)有元素了 且 key 是相同的則覆蓋元素
if ((p = tab[i = (n - 1) & hash]) == null) //判斷是否hash值產(chǎn)生沖突，如果沒有就創(chuàng)建Node賦值
tab[i] = newNode(hash, key, value, null);
else {
HashMap.Node<K,V> e; K k;
//如果p的的位置已經(jīng)有值了蜒秤，而且key相同汁咏，那就覆蓋值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof HashMap.TreeNode)//這里判斷如果當(dāng)前節(jié)點已經(jīng)是紅黑樹，就變轉(zhuǎn)換成紅黑樹的節(jié)點
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //hash值計算出的索引相同（就是已經(jīng)有元素了）作媚，而且key不同的時候 //循環(huán)整個單列表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //遍歷到尾部
p.next = newNode(hash, key, value, null); //創(chuàng)建新節(jié)點
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//遍歷發(fā)現(xiàn)有key的值與要插入的可以相同攘滩，替換value，并停止循環(huán)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//移動指針
p = e;
}
}
//循環(huán)完畢后e不等于空纸泡，就替換e所指的節(jié)點的value
if (e != null) { // existing mapping for key
V oldValue = e.value; //保存原來的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//這個方法在 HashMap 中是空實現(xiàn)漂问，在 LinkedHashMap 中有關(guān)系
return oldValue;
}
}
//增加一次操作數(shù)
++modCount;
//增加一次后如果size大于擴容閾值，就進行擴容,threshold代表擴容閾值
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
1.從這個函數(shù)我們可以發(fā)現(xiàn)女揭，它是放在一個Node數(shù)組里面的蚤假，首先判斷是否table是否為空，如果是空的話今夕resize擴容田绑，
2.然后進行計算要插入的索引位置勤哗，通過i = (n - 1) & hash。
3.接下來判斷是否存在key掩驱，沒有的話就進行插入到數(shù)組當(dāng)中芒划，如果有key，但是要插入的位置發(fā)現(xiàn)也有key且值不相同的話欧穴，就要進行循環(huán)單鏈表民逼，然后查詢是否有相同的節(jié)點，如果沒有涮帘，就在尾部插入新的節(jié)點拼苍。
4.如果插入的單鏈表的長度大于閾值，就要轉(zhuǎn)換成紅黑樹。
5.插入以后疮鲫，再次判斷size有沒有超過閾值吆你，如果有則要再次進行擴容。
HashMap的擴容
final HashMap.Node<K,V>[] resize() {
//先指向到舊的tab上
HashMap.Node<K,V>[] oldTab = table;
//舊tab的長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//舊的擴容閾值
int oldThr = threshold;
//定義一個新的值
int newCap, newThr = 0;
//判斷長度是否大于0俊犯，如果是的話擴容2倍妇多，擴容閾值也是原來的2倍
if (oldCap > 0) {
//如果舊的已經(jīng)到達了2^30，那么就不在擴容燕侠，直接返回者祖，并且長度直接為MAXIMUM_CAPACITY
//設(shè)置后不能安裝新的元素
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//擴容為原來的2倍，閾值也是2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//oldThr 不為空绢彤，代表我們使用帶參數(shù)的構(gòu)造方法指定了加載因子并計算了
//初始初始閾值 會將擴容閾值 賦值給初始容量這里不再是期望容量七问，
//但是 >= 指定的期望容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//如果是空的進行初始化容量，長度和閾值分別是16和12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新的閾值是0茫舶，就計算新的閾值械巡，對應(yīng)的是當(dāng)前 table 為空，但是有閾值的情況
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新新的閾值
//接下來以下注釋來源于網(wǎng)絡(luò)上的簡書大佬作者饶氏，別問我為什么自己不寫注釋坟比，因為后面根本看不懂
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//使用新的容量創(chuàng)建新的哈希表的數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果老的數(shù)組不為空將進行重新插入操作否則直接返回
if (oldTab != null) {
//遍歷老數(shù)組中每個位置的鏈表或者紅黑樹重新計算節(jié)點位置，插入新數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;//用來存儲對應(yīng)數(shù)組位置鏈表頭節(jié)點
//如果當(dāng)前數(shù)組位置存在元素
if ((e = oldTab[j]) != null) {
// 釋放原來數(shù)組中的對應(yīng)的空間
oldTab[j] = null;
// 如果鏈表只有一個節(jié)點嚷往，
//則使用新的數(shù)組長度計算節(jié)點位于新數(shù)組中的角標(biāo)并插入
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//如果當(dāng)前節(jié)點為紅黑樹則需要進一步確定樹中節(jié)點位于新數(shù)組中的位置葛账。
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//因為擴容是容量翻倍，
//原鏈表上的每個節(jié)點 現(xiàn)在可能存放在原來的下標(biāo)皮仁，即low位籍琳，
//或者擴容后的下標(biāo)，即high位
//低位鏈表的頭結(jié)點贷祈、尾節(jié)點
Node<K,V> loHead = null, loTail = null;
//高位鏈表的頭節(jié)點趋急、尾節(jié)點
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;//用來存放原鏈表中的節(jié)點
do {
next = e.next;
// 利用哈希值 & 舊的容量，可以得到哈希值去模后势誊，
//是大于等于 oldCap 還是小于 oldCap呜达，
//等于 0 代表小于 oldCap，應(yīng)該存放在低位粟耻，
//否則存放在高位（稍后有圖片說明）
if ((e.hash & oldCap) == 0) {
//給頭尾節(jié)點指針賦值
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}//高位也是相同的邏輯
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}//循環(huán)直到鏈表結(jié)束
} while ((e = next) != null);
//將低位鏈表存放在原index處查近，
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//將高位鏈表存放在新index處
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
return newTab;
}
}
其實就是找到之前的擴容的數(shù)組大小，然后進行擴容挤忙，一般都是擴容2倍霜威，然后將之前的hash表拷到新的hash表中。
插入的代碼還是可以看得懂的册烈，resize方法第一部分理解下都懂戈泼，第二部分直接懵逼，通過大佬寫的注釋，稍微理解了一下大猛。就是擴容的容量的翻倍扭倾，所以原來的節(jié)點，可能放到了新的位置上挽绩，也有可能放到了oldcap的位置上吆录。
HashMap的查找元素方法get
public V get(Object key) {
//創(chuàng)建一個新的node
HashMap.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是否為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判斷是否是首位是否就是要找的值，如果是就返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//如果對應(yīng)的位置為紅黑樹調(diào)用紅黑樹的方法去尋找節(jié)點
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果不是琼牧，就代表是單鏈表，就遍歷單鏈表找到key和value
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
查找方法就相對與簡單很多了哀卫，通過getNode方法進行查找巨坊，其中key的值要進行hash計算，然后進行返回此改。
在getNode方法里趾撵，也會判斷查找的位置是紅黑樹還是單鏈表，如果是單鏈表就會調(diào)用getTreeNode方法進行查找共啃，不是的就進行循環(huán)查找占调，最后返回要找的值。
HashMap的刪除方法remove
public V remove(Object key) {
HashMap.Node<K,V> e;
//matchValue如果這個值為 true 則表示只有當(dāng) Value 與第三個參數(shù) Value 相同的時候才刪除對一個的節(jié)點
//movable 這個參數(shù)在紅黑樹中先刪除節(jié)點時候使用 true 表示刪除并其他數(shù)中的節(jié)點移剪。
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final HashMap.Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, index;
//判斷tab是否為空究珊，長度是否大于0，而且查找位置上有沒有對應(yīng)的元素纵苛。
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//這里是創(chuàng)建要刪除的node
HashMap.Node<K,V> node = null, e; K k; V v;
//判斷首位hash是不是要刪除的剿涮，如果是就賦值給node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//如果不是
else if ((e = p.next) != null) {
//判斷是不是紅黑樹,如果是就通過紅黑樹來查詢要刪除的節(jié)點
if (p instanceof HashMap.TreeNode)
node = ((HashMap.TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//這里進行遍歷要找到的節(jié)點
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如果不為空，就是代表了找到了要刪除的節(jié)點
// !matchValue 是否不刪除節(jié)點
//這里也進行判斷要刪除的節(jié)點的值是否相同
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//刪除節(jié)點
if (node instanceof HashMap.TreeNode)
((HashMap.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;
}
刪除函數(shù)看著很長攻人，其實細細品味下來也是很好理解取试，判斷tab為空，然后在判斷是否首位是不是要刪除的節(jié)點怀吻，如果不是瞬浓，就往下接著尋找，然后判斷要刪除的節(jié)點的位置是單鏈表還是紅黑樹蓬坡，然后再以它們的方式去查找猿棉，然后在進行刪除，注意的是屑咳，當(dāng)我看到最后的時候發(fā)現(xiàn)了matchValue 這個變量的時候铺根，而且之前的remvove也有出現(xiàn)過，然后百度了一下發(fā)現(xiàn)還有個remove函數(shù)乔宿。
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
看這個實現(xiàn)就知道了位迂，就是可以一起判斷key和value是不是要刪除的那個元素（以前我都不知道還有這個rmove方法，無奈-_-||）。
總結(jié)
HashMap這里只是記錄了最常用的幾個操作掂林，因為能力和實踐有限臣缀，還有一大部分的源代碼沒有去閱讀，而且分析的過程泻帮，發(fā)現(xiàn)能寫出這些的都是大佬中的大佬精置，此篇文章也參考了一些網(wǎng)絡(luò)上大佬的分析，經(jīng)過此次的初探锣杂，也對HashMap有個初步的了解脂倦。
參考
- [搞懂 Java HashMap 源碼] http://www.reibang.com/p/9ea8dd8dd40c
