HashMap概述
HashMap實現(xiàn)了Map接口品山，我們常用HashMap進行put和get操作讀存鍵值對數(shù)據述雾。下面介紹基于jdk1.8深入了解HashMap底層原理街州。
HashMap數(shù)據結構
HashMap實際是一種“數(shù)組+鏈表”數(shù)據結構。在put操作中玻孟，通過內部定義算法尋止找到數(shù)組下標唆缴，將數(shù)據直接放入此數(shù)組元素中，若通過算法得到的該數(shù)組元素已經有了元素（俗稱hash沖突黍翎，鏈表結構出現(xiàn)的實際意義也就是為了解決hash沖突的問題）面徽。將會把這個數(shù)組元素上的鏈表進行遍歷，將新的數(shù)據放到鏈表末尾玩敏。
[圖片上傳失敗...(image-cbd499-1545389166727)]
存儲數(shù)據的對象
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
我們從jdk1.8源代碼看出存儲對象Node實際是實現(xiàn)Map.Entry對象接口斗忌。
hash：通過hash算法的出來的值。hash值的算法我們看下HashMap源代碼的實現(xiàn)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
不同的數(shù)據類型的hashCode計算的方法不一樣旺聚，我們看下String和Integer兩種數(shù)據類型的hashCode算法
String.hashCode()
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
通過將字符串轉換成char數(shù)組织阳，使用公式s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]進行計算得出最后的值。val[i]值是對應字符的ASCII值.在看到這里的時候砰粹，這里為什么使用了一個31作為相乘因子（能為啥唧躲，還不是為了性能考慮，那為什么使用31性能能得到優(yōu)化呢）碱璃，這里可以延伸討論弄痹。
Integer.hashCode()
public static int hashCode(int value) {
return value;
}
直接返回值.
key：存儲數(shù)據的key
value：存儲數(shù)據的value
next：下一個數(shù)據，出現(xiàn)哈希沖突時嵌器，該數(shù)組元素會出現(xiàn)鏈表結構肛真，會使用next指向鏈表中下一個元素對象
鏈表結構導致的問題
通過哈希算法從尋止上能夠高效的找到對應的下標，但是隨著數(shù)據的增長爽航，哈希沖突碰撞過多蚓让。在尋找數(shù)據上乾忱，找到該來鏈表，會通過遍歷在尋找對應數(shù)據历极，如此將會使得get數(shù)據效率越來越低窄瘟。在jdk1.8中，鏈表元素數(shù)量大于等于8將會重組該鏈表結構形成為“紅黑樹結構”趟卸，這種結構使得在hash沖突碰撞過多情況下蹄葱，get效率比鏈表的效率高很多。
HashMap put存儲數(shù)據是如何處理的
HashMap有幾個重要的變量
transient Node<K,V>[] table;
int threshold;
final float loadFactor;
int modCount;
int size;
table：存儲數(shù)組的變量锄列，初始長度為16通過源代碼看出在第一次進行resize擴容（java是靜態(tài)語言图云，在定義數(shù)組初始化時，需要定義數(shù)組的長度右蕊，在map數(shù)據增長后琼稻，內部機制會進行重新定義一個數(shù)組做到擴容的操作）初始化時吮螺，會將默認靜態(tài)變量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;復制代碼
賦給數(shù)組長度進行初始化饶囚。
loadFactor：數(shù)據的增長因子，默認為0.75鸠补。在進行擴容操作會使用到萝风。
threshold：允許的最大的存儲的元素數(shù)量，通過length數(shù)組長度*loadFactor增長因子得出
modCount：記錄內部結構發(fā)生變化的次數(shù)紫岩，put操作（覆蓋值不計算）以及其他...
size：實際存儲的元素數(shù)量
put的流程
直接通過源代碼分析
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ù)組是否為空规惰，長度是否為0，是則進行擴容數(shù)組初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通過hash算法找到數(shù)組下標得到數(shù)組元素泉蝌，為空則新建
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 找到數(shù)組元素歇万，hash相等同時key相等，則直接覆蓋
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 該數(shù)組元素在鏈表長度>8后形成紅黑樹結構的對象
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 該數(shù)組元素hash相等勋陪，key不等贪磺，同時鏈表長度<8.進行遍歷尋找元素，有就覆蓋無則新建
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 新建鏈表中數(shù)據元素
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 鏈表長度>=8 結構轉為 紅黑樹
treeifyBin(tab, hash);
break;
}
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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
便于理解诅愚，花了一下圖寒锚。如下圖示（畫工不是很好，見諒見諒）
下圖是一位大神級別畫的圖违孝，引用一下便于理解
1刹前、首選判斷table是否為空，數(shù)組長度為空雌桑，將會進行第一次初始化喇喉。（在實例化HashMap是，并不會進行初始化數(shù)組）
2校坑、進行第一次resize()擴容之后拣技。開始通過hash算法尋址找到數(shù)組下標衅鹿。若數(shù)組元素為空，則創(chuàng)建新的數(shù)組元素过咬。若數(shù)組元素不為空大渤，同時hash相等，key不相等掸绞，同時不是TreeNode數(shù)據對象泵三，將遍歷該數(shù)組元素下的鏈表元素。若找到對應的元素衔掸，則覆蓋烫幕，如果沒有找到，就新建元素敞映，放入上一個鏈表元素的next中较曼，在放入元素之后，如果條件滿足"鏈表元素長度>8"振愿，則將該鏈表結構轉為"紅黑樹結構"捷犹。
3、找到對應的數(shù)組元素或者鏈表元素冕末，同時創(chuàng)建新的數(shù)據元素或者覆蓋元素之后萍歉。如果條件滿足元素大小size>允許的最大元素數(shù)量threshold，則再一次進行擴容操作档桃。每次擴容操作枪孩，新的數(shù)組大小將是原始的數(shù)組長度的兩倍。
4藻肄、put操作完成蔑舞。
調用put方法示例
下面通過使用例子介紹這個過程
HashMap<Integer, String> hashMap = new HashMap<Integer, String>(4, 0.75f);// 1
int a1 = 1;
int a2 = 2;
int a3 = 5;
System.out.println(String.valueOf(a1&3) + " " + String.valueOf(a2&3)+ " " + String.valueOf(a3&3));// 1 2 1 數(shù)組下標
hashMap.put(a1, "1");// 2
hashMap.put(a2, "2");// 3
hashMap.put(a3, "5");// 4
1、創(chuàng)建了一個HashMap對象嘹屯，初始化initialCapacity為4攻询，增長因子為0.75。threshold初始化為4
2抚垄、進行了第一次put蜕窿，因為table為空，進行了第一次resize()擴容操作呆馁，數(shù)組進行初始化桐经，默認為16. threshold變?yōu)?。同時通過hash算法（數(shù)組長度n-1 & hash）即為1浙滤。
3阴挣、第二次put操作，同時獲取數(shù)組下標為2纺腊，此時數(shù)組下標為2當前沒有數(shù)組元素畔咧，則直接創(chuàng)建數(shù)據元素放入
4茎芭、第三次put操作，得到數(shù)組下標為1已經有了一個數(shù)組元素誓沸。同時我們知道存儲數(shù)據的Node對象中又一個next梅桩，則新的此時的數(shù)據元素放入上一個鏈表中next為空的Node中的next中。
形成了如下圖的數(shù)據結構
結論：通過hash算法進行計算的出來的數(shù)組下標拜隧，有一定概率會導致hash沖突宿百，那在一個數(shù)組元素中，存在hash值一樣的key洪添，key卻不相等垦页。為了解決這一個hash沖突問題，使用了鏈表結構進行處理干奢。
HashMap擴容resize()
java是靜態(tài)方法痊焊，在數(shù)組進行初始化時，必須給一個數(shù)組長度忿峻。HashMap定義默認的數(shù)組長度為16薄啥。條件滿足元素size>允許的最大元素數(shù)量threshold。則進行擴容炭菌。一般來說罪佳，在put操作中逛漫，HashMap至少進行了一次擴容（第一次為初始化）黑低。
我們在原有的示例加入如下
int a4 = 6;
hashMap.put(a4, "6");復制代碼
形成了新的結構，如下圖
放入了2:2的next中酌毡，此時size=4,threshold>3克握，條件滿足size>threshold，進行擴容resize()操作
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超過最大限制枷踏，不進行擴容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 進行原始長度*2擴容
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 第一次初始化
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
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);
}
// 新的最大允許元素數(shù)量值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 新的數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 遍歷老數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 直接按照原始索引放入新數(shù)組中
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 { // preserve order
// 遍歷鏈表
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;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
在put6:6之后菩暗，直接就執(zhí)行了擴容，新數(shù)組長度為8旭蠕，新的結構如下
在新的結構中停团，將原始的數(shù)組下標為1和2鏈表元素均勻分布新數(shù)組的其他數(shù)組元素中。此間擴容的變化的過程如下
老數(shù)組長度為4掏熬，通過算法得出數(shù)據的下標1:1為1,5:5為1,2:2和6:6為2
1(1:1 == > 5:5)
2(2:2 == > 6:6)
在進行擴容操作是佑稠，數(shù)組元素鏈表中的第一個數(shù)組下標不會產生變化，在遍歷鏈表其他元素中通過算法"e.hash & oldCap"!=0則將鏈表元素放入新數(shù)據數(shù)組下標為[原始數(shù)據下標+原始數(shù)據長度]
再次引用大神的圖旗芬，便于理解擴容的數(shù)據移動變化
在擴容操作中舌胶，因無需重新計算hash值，同時均勻將鏈表沖突的元素均勻分布到新的數(shù)組中疮丛。這設計實在是巧妙幔嫂。
get尋找數(shù)據
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
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) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get方法比較簡單辆它，基本流程為通過key的hashCode和尋址算法得到數(shù)組下標，若數(shù)組元素中的key和hash相等履恩，則直接返回锰茉。若不想等，同時存在鏈表元素切心，則遍歷鏈表元素進行匹配洞辣。由于1.8引用了紅黑樹結構，在鏈表元素過多時昙衅，1.8的實現(xiàn)將比1.7在get和put操作上效率高上很多扬霜。
