HashMap源碼分析——JDK1.8
轉(zhuǎn)載：http://blog.csdn.net/u010498696/article/details/45888613
在JDK1.6中，HashMap采用位桶+鏈表實現(xiàn)：即使用鏈表處理沖突，同一hash值的鏈表都存儲在一個鏈表里。但是當(dāng)位于一個桶中的元素較多蚣抗，即hash值相等的元素較多時，通過key值依次查找的效率較低鱼鼓。
而JDK1.8中帮寻，HashMap采用位桶+鏈表+紅黑樹實現(xiàn)：當(dāng)鏈表長度超過閾值（8）時悍赢，將鏈表轉(zhuǎn)換為紅黑樹援制，這樣大大減少了查找時間戏挡。
1、涉及到的數(shù)據(jù)結(jié)構(gòu)
1.1 處理hash沖突的鏈表
//Node是單向鏈表中的節(jié)點晨仑，它實現(xiàn)了Map.Entry接口增拥，代表一個鍵值對
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //hash值
final K key; //鍵
V value; //值
Node<K,V> next; //鏈表中下一個節(jié)點
//Node的構(gòu)造函數(shù)
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; }
//計算該Node節(jié)點對象的hash值
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//判斷兩個Node是否相等,若key和value都相等，返回true寻歧。可以與自身比較, 返回true秩仆。
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;
}
}
1.2 紅黑樹
//紅黑樹
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left; //左節(jié)點
TreeNode<K,V> right; //右節(jié)點
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; //節(jié)點顏色（紅码泛、黑）
//構(gòu)造函數(shù)
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
//返回紅黑樹的根節(jié)點
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
1.3 位桶（hash數(shù)組）
transient Node<K,V>[] table;
HashMap的大致實現(xiàn)思路：
首先有一個存儲Node<K, V>節(jié)點引用的數(shù)組，當(dāng)添加一個元素（Node<K, V>代表一個鍵值對）時澄耍，就首先計算元素key的hash值噪珊，以此確定插入數(shù)組中的位置晌缘，但是可能存在同一個hash值的元素已經(jīng)被放在數(shù)組同一位置了，這時就添加到同一hash值的元素的后面痢站，他們在數(shù)組的同一位置磷箕，但是形成了鏈表，所以說數(shù)組存放的是鏈表的頭結(jié)點阵难。而當(dāng)鏈表長度太長時岳枷，鏈表就轉(zhuǎn)換為紅黑樹，這樣大大提高了查找的效率呜叫。
2空繁、HashMap的主要屬性
填充比，默認值為0.75朱庆，如果實際元素所占容量占分配容量的75%時就要擴容了盛泡。如果填充比很大，說明利用的空間很多娱颊，但是查找的效率很低傲诵，因為鏈表的長度很大（當(dāng)然最新版本使用了紅黑樹后會改進很多），HashMap本來是以空間換時間箱硕，所以填充比沒必要太大拴竹。但是填充比太小又會導(dǎo)致空間浪費。如果關(guān)注內(nèi)存颅痊，填充比可以稍大殖熟，如果主要關(guān)注查找性能，填充比可以稍小斑响。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 默認初始化容量
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默認填充比(裝載因子)
//當(dāng)add一個元素到某個位桶菱属，其鏈表長度達到8時將鏈表轉(zhuǎn)換為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<K,V>[] table; //存儲元素的數(shù)組
transient Set<Map.Entry<K,V>> entrySet; //鍵值對集合
transient int size; //存放的元素的個數(shù)
transient int modCount; //被修改的次數(shù)fast-fail機制
int threshold; //臨界值 當(dāng)實際大小(容量*填充比)超過臨界值時，會進行擴容
final float loadFactor;//填充比（......后面略）
3舰罚、構(gòu)造方法
HashMap的構(gòu)造方法有4種纽门，主要涉及到的參數(shù)有，指定初始容量营罢，指定填充比和用來初始化的Map赏陵。
//構(gòu)造函數(shù)1
public HashMap(int initialCapacity, float loadFactor) {
//指定的初始容量非負
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果指定的初始容量大于最大容量, 則設(shè)置為最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//填充比大于0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity); //新的擴容臨界值
}
//構(gòu)造函數(shù)2
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//構(gòu)造函數(shù)3
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//構(gòu)造函數(shù)4：用 m 的元素初始化 hashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
4、擴容機制（★★★）
構(gòu)造hash表時饲漾，如果不指明初始大小蝙搔，默認大小為16（即Node數(shù)組大小16），如果Node[]數(shù)組中的元素達到閾值---即當(dāng)前數(shù)組的長度乘以加載因子的值（Node.length * 填充比）的時候考传，就要自動擴容吃型。
下面我們講解下JDK1.8做了哪些優(yōu)化。經(jīng)過觀測可以發(fā)現(xiàn)僚楞，我們使用的是2次冪的擴展(指長度擴為原來2倍)勤晚，所以枉层，經(jīng)過rehash（重新計算hash值）之后，元素的位置要么是在原位置赐写，要么是在原位置再移動2次冪的位置鸟蜡。
看下圖可以明白這句話的意思，n為table的長度挺邀，圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例揉忘，圖（b）表示擴容后key1和key2兩種key確定索引位置的示例，其中hash1是key1對應(yīng)的哈希與高位運算結(jié)果悠夯。
元素在重新計算hash之后癌淮，因為n變?yōu)?倍，那么n-1的mask范圍在高位多1bit(紅色)沦补，因此新的index就會發(fā)生這樣的變化：
因此乳蓄，我們在擴充HashMap的時候，不需要像JDK1.7的實現(xiàn)那樣重新計算hash夕膀，只需要看看原來的hash值新增的那個bit是1還是0就好了虚倒，是0的話“索引不變”，是1的話索引變成“原索引+oldCap”产舞，可以看看下圖為16擴充為32的resize示意圖：
這個設(shè)計確實非常的巧妙魂奥，既省去了重新計算hash值的時間，而且同時易猫，由于新增的1bit是0還是1可以認為是隨機的耻煤，因此resize的過程，均勻的把之前的沖突的節(jié)點分散到新的bucket了准颓。這一塊就是JDK1.8新增的優(yōu)化點哈蝇。
下面是jdk1.8中HashMap的擴容函數(shù)resize源碼：
//擴容函數(shù)
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //oldTab引用指向舊數(shù)組
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//超過1>>30大小,如果超過最大容量，無法擴容只能改變 擴容的閾值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//新的容量設(shè)定為舊的容量的2倍攘已，最小值為16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//下一次擴容的閾值同樣加倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0)
newCap = oldThr; //oldCap=0, oldThr>0, 此時newThr=0
else {
//oldCap=0, oldThr=0, 相當(dāng)于使用默認填充比和初始容量 初始化
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //創(chuàng)建一個新數(shù)組
table = newTab; //table引用指向新數(shù)組
////數(shù)組元素復(fù)制到新的數(shù)組中炮赦，分紅黑樹和鏈表討論
if (oldTab != null) {
//取舊數(shù)組中的每一個Node的引用（因為數(shù)組中存的是引用，不是對象）
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//先將該Node在舊數(shù)組中的引用清空
oldTab[j] = null;
//如果只有這一個節(jié)點Node样勃，計算新的index位置吠勘，放入新數(shù)組中的對應(yīng)位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果該節(jié)點是TreeNode類型，說明原來這里是一個紅黑樹
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //如果是鏈表峡眶，優(yōu)化相同hash的節(jié)點
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + 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;
}
//原索引 + oldCap 放入數(shù)組中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//移動完畢剧防，返回新的hash表
return newTab;
}
顯然：元素從舊數(shù)組移動到新數(shù)組中非常耗時，因此擴容非常耗時辫樱。
大概思路就是峭拘，分XXX種情況： （1）如果舊數(shù)組i號位置下只有一個節(jié)點，那么直接通過e.hash & (newCap -
1)計算index，放入新數(shù)組的對應(yīng)位置中棚唆。
（2）如果判斷第一個節(jié)點是TreeNode紅黑樹節(jié)點的類型，那么采用紅黑樹的插入方式將節(jié)點插入到新數(shù)組中心例。
（3）如果是鏈表節(jié)點宵凌，那么將鏈表中的節(jié)點移到新數(shù)組中（有優(yōu)化）。
5止后、確定元素put/get操作時在Node[]數(shù)組中的位置
//計算key的hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//Object類中的hashCode()函數(shù)
public native int hashCode();
在HashMap中瞎惫，首先由key值通過hash(key)獲取hash值h，再通過 h &（length-1）得到所在數(shù)組位置译株。
hash = hash(key)
tab[i = (n - 1) & hash]
一般對于哈希表的散列常用的方法有直接定址法瓜喇，除留余數(shù)法等，既要便于計算歉糜，又能減少沖突乘寒。
在Hashtable中就是通過除留余數(shù)法散列分布的，具體如下：
int index = (hash & 0x7FFFFFFF) % tab.length;
但是取模中的除法運算效率很低匪补，HashMap則通過（length-1）& h 替代取模伞辛，得到所在數(shù)組位置，這樣效率會高很多夯缺。
在HashMap實現(xiàn)中還可以看到如下代碼取代了以前版本JDK1.6的while循環(huán)來保證哈希表的容量一直是2的整數(shù)倍數(shù)蚤氏，用移位操作取代了循環(huán)移位。
//這段代碼保證HashMap的容量總是2的n次方
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;
}
可以從源碼看出踊兜，在HashMap的構(gòu)造函數(shù)中竿滨，都直接或間接的調(diào)用了tableSizeFor函數(shù)。
下面分析原因：length為2的整數(shù)冪保證了length-1最后一位（當(dāng)然是二進制表示）為1捏境，從而保證了取索引操作 h&（length-1）的最后一位同時有為0和為1的可能性于游，保證了散列的均勻性。反過來講典蝌，當(dāng)length為奇數(shù)時曙砂，length-1最后一位為0，這樣與h按位與的最后一位肯定為0骏掀，即索引位置肯定是偶數(shù)鸠澈，這樣數(shù)組的奇數(shù)位置全部沒有放置元素，浪費了大量空間截驮。
簡重點內(nèi)容而言之：length為2的冪保證了按位與最后一位的有效性笑陈，使哈希表散列更均勻。
6葵袭、下面分析HashMap的最常用操作put和get
注意HashMap中key和value都容許為null涵妥。
6.1 put操作
//put元素的時候，調(diào)用的是putVal函數(shù)
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;
//如果tab為空或長度為0坡锡，則分配空間resize()
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通過(n - 1) & hash計算找到put位置蓬网，如果為空,則直接put
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//與第一節(jié)點hash值相同窒所，且key值與插入key相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//發(fā)生沖突，插入的位置下面是一顆紅黑樹帆锋，處理沖突
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//未達到生成紅黑樹的臨界值吵取，因此還是鏈式結(jié)構(gòu)
//向鏈表中插入新節(jié)點(插入鏈表的尾部)
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//新節(jié)點插入到鏈表的尾部（尾插法）
p.next = newNode(hash, key, value, null);
//新插入節(jié)點后，需要做判斷锯厢，如果節(jié)點個數(shù)到達閾值皮官，則將鏈表轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//驗證一下：如果在這個鏈表中已經(jīng)存在了某個節(jié)點的key和要插入的節(jié)點的key相等，
//說明曾經(jīng)已經(jīng)插入過实辑，不要再新建節(jié)點了捺氢，
//注意：此時該節(jié)點的值不一定是最新的值，更新為最新的值的操作在下面進行
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //更新p指向下一個節(jié)點
}
}
//更新新插入的節(jié)點的value的最新值（不管是新建的還是原來就有這個節(jié)點）
//因為onlyIfAbsent直接賦值為了false剪撬，所以,e.value = value一定會執(zhí)行摄乒。
//所以，如果曾經(jīng)插入過這個節(jié)點婿奔，新插入相同節(jié)點缺狠，直接采用“覆蓋”的策略
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果超過了閾值，進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
put(key,value)過程：
判斷保存鍵值對的數(shù)組tab[]是否為空（沒有元素）或為null萍摊，否則resize()挤茄。
根據(jù)鍵key的值計算hash值得到插入數(shù)組的索引i，如果tab[i]==null冰木，直接新建節(jié)點插入進去穷劈，否則轉(zhuǎn)入步驟3。
判斷當(dāng)前數(shù)組中處理hash沖突的方式為鏈表還是紅黑樹(check第一個節(jié)點類型即可)踊沸，分別采用相應(yīng)的策略處理沖突歇终。
6.2 get操作
//get元素的時候，調(diào)用的是getNode函數(shù)
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;
//通過計算(n - 1) & hash 找到元素的位置
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) {
//如果第一個節(jié)點是TreeNode類型, 說明采用的是數(shù)組+紅黑樹結(jié)構(gòu)處理沖突
//遍歷紅黑樹逼龟，得到節(jié)點值
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//否則就是鏈式結(jié)構(gòu), 在鏈表中找到該節(jié)點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get(key)過程：
通過計算得到鍵值為key的元素在數(shù)組中的索引位置评凝。
判斷該索引下數(shù)組中的元素（該元素也是鏈表的頭結(jié)點或者紅黑樹的根節(jié)點），是那種類型腺律。
根據(jù)類型判定解決沖突的方式是鏈式還是紅黑樹奕短，根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，搜索目標節(jié)點匀钧，并返回該節(jié)點翎碑。
