構(gòu)造方法
HashMap提供了三個構(gòu)造函數(shù)
HashMap()：構(gòu)造一個具有默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75) 的空 HashMap岭洲。
HashMap(int initialCapacity)：構(gòu)造一個帶指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap相恃。
HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個帶指定初始容量和加載因子的空 HashMap务甥。
下面是所有的屬性
/**
* 默認(rèn)的初始容量：16
* 必須為2的冪
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量為2的 30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認(rèn)加載因子0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
*一個桶中bin（箱子）的存儲方式由鏈表轉(zhuǎn)換成樹的閾值
*當(dāng)桶上的結(jié)點數(shù)量大于等于TREEIFY_THRESHOLD時底層結(jié)構(gòu)由鏈表變?yōu)榧t黑樹而晒。默認(rèn)是8
*/
static final int TREEIFY_THRESHOLD = 8;
/**
*當(dāng)桶上的結(jié)點數(shù)量小于等于6時等層結(jié)構(gòu)由紅黑樹變?yōu)殒湵怼ＤJ(rèn)是6
*當(dāng)執(zhí)行resize操作時珍语，當(dāng)桶中bin的數(shù)量少于6時使用鏈表來代替樹
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
*當(dāng)桶中的bin被樹化時最小的hash表容量测垛。（如果沒有達(dá)到這個閾值罚渐，即hash表容量小于MIN_TREEIFY_CAPACITY却汉，當(dāng)桶中bin的數(shù)量太多時
*會執(zhí)行resize擴(kuò)容操作）這個MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD(鏈表轉(zhuǎn)化為紅黑樹的閥值)的4倍。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* Entry數(shù)組荷并，哈希表，長度必須為2的冪
*/
transient Entry<K,V>[] table;
/**
* 已存元素的個數(shù)
*/
transient int size;
/**
* 下次擴(kuò)容的臨界值青扔，size >= threshold就會擴(kuò)容
*/
int threshold;
/**
* 加載因子
*/
final float loadFactor;
數(shù)據(jù)結(jié)構(gòu)
HashMap的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表源织。當(dāng)鏈表長度達(dá)到8時（binCount >= TREEIFY_THRESHOLD - 1），就轉(zhuǎn)化為紅黑樹（JDK1.8增加了紅黑樹部分）
哈希桶數(shù)組
里面有個屬性next微猖，是個節(jié)點類型谈息，根據(jù)構(gòu)造函數(shù)傳進(jìn)來的。他對上面那個鏈表的形成很重要凛剥。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用來定位數(shù)組索引位置
final K key;
V value;
Node<K,V> next; //鏈表的下一個node
Node(int hash, K key, V value, Node<K,V> next) {.....} //初始化四個屬性
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() { //返回hashcode
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) { //更改value值侠仇，并返回oldvalue
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;
}
}
HashMap就是使用哈希表來存儲的。哈希表為解決沖突犁珠，可以采用開放地址法和鏈地址法等來解決問題逻炊，Java中HashMap采用了鏈地址法。鏈地址法犁享，簡單來說余素，就是數(shù)組加鏈表的結(jié)合。在每個數(shù)組元素上都一個鏈表結(jié)構(gòu)炊昆，當(dāng)數(shù)據(jù)被Hash后桨吊，得到數(shù)組下標(biāo)，把數(shù)據(jù)放在對應(yīng)下標(biāo)元素的鏈表上凤巨。
功能實現(xiàn)
確定哈希桶數(shù)組索引
步驟1：獲取key的hashcode值
步驟2：高位運算视乐，通過hashcode值的高十六位異或低十六位得到hash值
public class Hash_IndexFor {
/**
* HashMap的hash算法
*/
private int hash(Object key){
/*if (key == null) return 0;
// 獲得key的hashcode值
int hashcode = key.hashCode();
// 高位運算
int hash = hashcode ^(hashcode >>> 16); // 高16位與低十六位做異或運算
return hash;*/
int h;
return key == null ? 0: (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 計算索引
* JDK1.8把它去掉了，但是在put方法中直接使用了敢茁，沒有單獨作為方法佑淀。
*
*/
private int indexFor(int hash, int length){
return hash & (length - 1);
}
}
分析put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步驟1：判斷數(shù)組是否為null或者為空，否則進(jìn)行擴(kuò)容resize()操作卷要，新建一個渣聚。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步驟2：通過key的hash值得到插入數(shù)組的索引i; 如果tab[i]處還沒有元素，直接新建一個節(jié)點放入數(shù)組
if ((p = tab[i = (n - 1) & hash]) == null) // 這里注意：table[i]已經(jīng)賦給引用p了僧叉，后續(xù)操作會多次用到p
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步驟3：節(jié)點key存在奕枝，則直接覆蓋value。這里還有疑問瓶堕，為什么要比較兩次隘道，兩次操作作用有什么不同嗎？
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步驟4：判斷table[i]的處鏈表是否為紅黑樹。
else if (p instanceof TreeNode) // 這里注意：TreeNode繼承自LinkedList的內(nèi)部類Entry谭梗，而Entry又繼承自HashMap的內(nèi)部類Node忘晤，即TreeNode是Node的子類，故能進(jìn)行（p instanceof TreeNode）這樣的判斷激捏。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步驟5：該鏈為鏈表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 鏈表長度 大于8 則轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 遍歷過程中设塔，如果發(fā)現(xiàn)節(jié)點key存在，則直接覆蓋value远舅。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步驟6：超過最大容量就擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
擴(kuò)容機(jī)制
先分析JDK1.7的擴(kuò)容機(jī)制闰蛔，會更容易理解JDK1.8的擴(kuò)容
什么時候擴(kuò)容
當(dāng)向容器添加元素的時候，會判斷當(dāng)前容器的元素個數(shù)图柏，如果大于等于閾值的時候序六，就要自動擴(kuò)容啦。
擴(kuò)容是怎么實現(xiàn)
就是重新計算容量蚤吹，向HashMap對象里不停的添加元素例诀，而當(dāng)HashMap對象內(nèi)部的數(shù)組無法裝載更多的元素時，對象就需要擴(kuò)大數(shù)組的長度裁着，以便能裝入更多的元素繁涂。當(dāng)然Java里的數(shù)組是無法自動擴(kuò)容的，方法是使用一個新的數(shù)組代替已有的容量小的數(shù)組跨算，就像我們用一個小桶裝水爆土，如果想裝更多的水，就得換大水桶诸蚕，再將小水桶中的水倒進(jìn)大水桶步势。
幾個重要的屬性
- loadFactor：負(fù)載因子
- Node<K,V>：鏈表節(jié)點，包含了key背犯、value坏瘩、hash、next指針?biāo)膫€元素
- table：Node<K,V>類型的數(shù)組漠魏，里面的元素是鏈表倔矾，用于存放元素的鍵和值
- threshold：閾值。決定了HashMap何時擴(kuò)容（達(dá)到閥值的3/4時就擴(kuò)）柱锹，以及擴(kuò)容后的大小哪自，一般等于table的大小乘以負(fù)載因子（0.75）
JDK1.7中的擴(kuò)容的具體實現(xiàn)方法（resize）
void resize(int newCapacity) { //傳入新的容量，原容量的兩倍
Entry[] oldTable = table; //引用擴(kuò)容前的Entry數(shù)組
int oldCapacity = oldTable.length;//原容量
if (oldCapacity == MAXIMUM_CAPACITY) { //擴(kuò)容前的數(shù)組大小如果已經(jīng)達(dá)到最大容量了
threshold = Integer.MAX_VALUE; //修改閾值為（最大容量-1）禁熏，這樣以后就不會擴(kuò)容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一個新的Entry數(shù)組
transfer(newTable); //注意Ｈ老铩：將數(shù)據(jù)拷貝到新的數(shù)組里
table = newTable; //HashMap的table屬性引用指向新的Entry數(shù)組
threshold = (int) (newCapacity * loadFactor);//修改閾值
}
transfer()方法：
將原有Entry數(shù)組的元素拷貝到新的Entry數(shù)組里
/*上面的resize方法中，調(diào)用了transfer(newTable)方法瞧毙，將數(shù)據(jù)拷貝到一個更大的數(shù)組中*/
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了舊的Entry數(shù)組
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍歷舊的Entry數(shù)組
Entry<K, V> e = src[j]; //取得舊Entry數(shù)組的每個元素
if (e != null) {
src[j] = null;//釋放舊Entry數(shù)組的對象引用（for循環(huán)后胧华，舊的Entry數(shù)組不再引用任何對象）
do {
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity); //注意＜闹ⅰ：重新計算每個元素在數(shù)組中的位置
e.next = newTable[i];
newTable[i] = e; //頭插法，將新元素放到單鏈表的頭部矩动。因為newTable是數(shù)組加鏈表的形式有巧，newTable[i]存放的是鏈表首節(jié)點的地址
e = next; //訪問下一個Entry鏈上的元素
} while (e != null);
}
}
}
JDK1.8的擴(kuò)容機(jī)制
resize()方法的注釋：
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize()
初始化或者翻倍表的大小。如果表為null悲没，則根據(jù)存放在threshold變量中的初始化capacity的值來分配table內(nèi)存（這個注釋說的很清楚篮迎，在實例化HashMap時，capacity其實是存放在了成員變量threshold中檀训，注意柑潦，HashMap中沒有capacity這個成員變量）。如果表不為null峻凫，由于我們使用2的冪來擴(kuò)容，則每個bin（箱子）元素要么還是在原來的bucket（桶）中览露，要么在2的冪中荧琼。
下面是resize()方法對于newCap 和newThr的計算：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
/* 如果原容量 > 0 */
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { //擴(kuò)容前的數(shù)組大小如果已經(jīng)達(dá)到最大容量了
threshold = Integer.MAX_VALUE; //修改閾值為（最大容量-1），這樣以后就不會擴(kuò)容了
return oldTab;
}
//先對newCap進(jìn)行翻倍差牛。如果newCap達(dá)還小于最大值命锄，且原容量oldCap大于等于默認(rèn)的容量。則newThr賦值為原容量的兩倍偏化，即此時newCap
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
/*如果原容量 == 0 */
else if (oldThr > 0) // 表示在實例化HashMap時脐恩，調(diào)用了HashMap的帶參構(gòu)造方法，初始化了threshold侦讨，這時將閾值賦值給newCap驶冒，因為在
newCap = oldThr; //構(gòu)造方法 中是將capacity賦值給了threshold。
/*如果原容量 == 0韵卤， 而且oldThr == 0骗污。即調(diào)用了HashMap的默認(rèn)構(gòu)造方法，這時沈条，將newCap賦值默認(rèn)初始容量16需忿，然后newThr等于加載因子與默認(rèn)容量的乘積*/
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
/*如果newThr == 0。這里是上面當(dāng)oldThr > 0遺留下來的,要重新計算newThr的值*/
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
//加載因子可以大于1蜡歹，所以要同時判斷newCap或newThr是否達(dá)到了整數(shù)最大值
}
threshold = newThr;
重點屋厘，將原HashMap中的元素拷貝到新HashMap中：
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//把每個桶的水都移動到新的桶中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 這部分是鏈表優(yōu)化rehash的代碼塊
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);
// 新索引 == 原索引放到桶里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//新索引 == 原索引 + oldCap放到桶里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
相比于JDK1.7 ， JDK1.8采用2次冪的擴(kuò)展(指長度擴(kuò)為原來2倍)月而，所以
經(jīng)過rehash之后汗洒，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置景鼠。
jdk1.8擴(kuò)容機(jī)制的優(yōu)化
- 省去了重新計算hash值的時間
- 由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的仲翎，因此resize的過程痹扇，均勻的把之前的沖突的節(jié)點分散到新的bucket了。這一塊就是JDK1.8新增的優(yōu)化點溯香。
- 有一點注意區(qū)別鲫构，JDK1.7中rehash的時候，舊鏈表遷移新鏈表的時候玫坛，如果在新表的數(shù)組索引位置相同结笨，則鏈表元素會倒置，但是JDK1.8不會倒置湿镀。
