HashMap概述
HashMap實(shí)現(xiàn)了Map接口，我們常用HashMap進(jìn)行put和get操作讀存鍵值對(duì)數(shù)據(jù)。下面介紹基于jdk1.8深入了解HashMap底層原理。
HashMap數(shù)據(jù)結(jié)構(gòu)
HashMap實(shí)際是一種“數(shù)組+鏈表”數(shù)據(jù)結(jié)構(gòu)。在put操作中，通過(guò)內(nèi)部定義算法尋止找到數(shù)組下標(biāo)，將數(shù)據(jù)直接放入此數(shù)組元素中，若通過(guò)算法得到的該數(shù)組元素已經(jīng)有了元素（俗稱hash沖突，鏈表結(jié)構(gòu)出現(xiàn)的實(shí)際意義也就是為了解決hash沖突的問(wèn)題）。將會(huì)把這個(gè)數(shù)組元素上的鏈表進(jìn)行遍歷，將新的數(shù)據(jù)放到鏈表末尾。
[圖片上傳失敗...(image-cbd499-1545389166727)]
存儲(chǔ)數(shù)據(jù)的對(duì)象
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
我們從jdk1.8源代碼看出存儲(chǔ)對(duì)象Node實(shí)際是實(shí)現(xiàn)Map.Entry對(duì)象接口。
hash：通過(guò)hash算法的出來(lái)的值。hash值的算法我們看下HashMap源代碼的實(shí)現(xiàn)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
不同的數(shù)據(jù)類型的hashCode計(jì)算的方法不一樣，我們看下String和Integer兩種數(shù)據(jù)類型的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;
}
通過(guò)將字符串轉(zhuǎn)換成char數(shù)組，使用公式s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]進(jìn)行計(jì)算得出最后的值。val[i]值是對(duì)應(yīng)字符的ASCII值.在看到這里的時(shí)候，這里為什么使用了一個(gè)31作為相乘因子（能為啥，還不是為了性能考慮，那為什么使用31性能能得到優(yōu)化呢），這里可以延伸討論。
Integer.hashCode()
public static int hashCode(int value) {
return value;
}
直接返回值.
key：存儲(chǔ)數(shù)據(jù)的key
value：存儲(chǔ)數(shù)據(jù)的value
next：下一個(gè)數(shù)據(jù)，出現(xiàn)哈希沖突時(shí)，該數(shù)組元素會(huì)出現(xiàn)鏈表結(jié)構(gòu)，會(huì)使用next指向鏈表中下一個(gè)元素對(duì)象
鏈表結(jié)構(gòu)導(dǎo)致的問(wèn)題
通過(guò)哈希算法從尋止上能夠高效的找到對(duì)應(yīng)的下標(biāo)，但是隨著數(shù)據(jù)的增長(zhǎng)，哈希沖突碰撞過(guò)多。在尋找數(shù)據(jù)上，找到該來(lái)鏈表，會(huì)通過(guò)遍歷在尋找對(duì)應(yīng)數(shù)據(jù)，如此將會(huì)使得get數(shù)據(jù)效率越來(lái)越低。在jdk1.8中，鏈表元素?cái)?shù)量大于等于8將會(huì)重組該鏈表結(jié)構(gòu)形成為“紅黑樹結(jié)構(gòu)”，這種結(jié)構(gòu)使得在hash沖突碰撞過(guò)多情況下，get效率比鏈表的效率高很多。
HashMap put存儲(chǔ)數(shù)據(jù)是如何處理的
HashMap有幾個(gè)重要的變量
transient Node<K,V>[] table;
int threshold;
final float loadFactor;
int modCount;
int size;
table：存儲(chǔ)數(shù)組的變量，初始長(zhǎng)度為16通過(guò)源代碼看出在第一次進(jìn)行resize擴(kuò)容（java是靜態(tài)語(yǔ)言，在定義數(shù)組初始化時(shí)，需要定義數(shù)組的長(zhǎng)度，在map數(shù)據(jù)增長(zhǎng)后，內(nèi)部機(jī)制會(huì)進(jìn)行重新定義一個(gè)數(shù)組做到擴(kuò)容的操作）初始化時(shí)，會(huì)將默認(rèn)靜態(tài)變量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;復(fù)制代碼
賦給數(shù)組長(zhǎng)度進(jìn)行初始化。
loadFactor：數(shù)據(jù)的增長(zhǎng)因子，默認(rèn)為0.75。在進(jìn)行擴(kuò)容操作會(huì)使用到。
threshold：允許的最大的存儲(chǔ)的元素?cái)?shù)量，通過(guò)length數(shù)組長(zhǎng)度*loadFactor增長(zhǎng)因子得出
modCount：記錄內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)，put操作（覆蓋值不計(jì)算）以及其他...
size：實(shí)際存儲(chǔ)的元素?cái)?shù)量
put的流程
直接通過(guò)源代碼分析
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ù)組是否為空，長(zhǎng)度是否為0，是則進(jìn)行擴(kuò)容數(shù)組初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通過(guò)hash算法找到數(shù)組下標(biāo)得到數(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相等同時(shí)key相等，則直接覆蓋
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 該數(shù)組元素在鏈表長(zhǎng)度>8后形成紅黑樹結(jié)構(gòu)的對(duì)象
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 該數(shù)組元素hash相等，key不等，同時(shí)鏈表長(zhǎng)度<8.進(jìn)行遍歷尋找元素，有就覆蓋無(wú)則新建
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 新建鏈表中數(shù)據(jù)元素
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 鏈表長(zhǎng)度>=8 結(jié)構(gòu)轉(zhuǎn)為 紅黑樹
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;
}
便于理解，花了一下圖。如下圖示（畫工不是很好，見(jiàn)諒見(jiàn)諒）
下圖是一位大神級(jí)別畫的圖，引用一下便于理解
1、首選判斷table是否為空，數(shù)組長(zhǎng)度為空，將會(huì)進(jìn)行第一次初始化。（在實(shí)例化HashMap是，并不會(huì)進(jìn)行初始化數(shù)組）
2、進(jìn)行第一次resize()擴(kuò)容之后。開始通過(guò)hash算法尋址找到數(shù)組下標(biāo)。若數(shù)組元素為空，則創(chuàng)建新的數(shù)組元素。若數(shù)組元素不為空，同時(shí)hash相等，key不相等，同時(shí)不是TreeNode數(shù)據(jù)對(duì)象，將遍歷該數(shù)組元素下的鏈表元素。若找到對(duì)應(yīng)的元素，則覆蓋，如果沒(méi)有找到，就新建元素，放入上一個(gè)鏈表元素的next中，在放入元素之后，如果條件滿足"鏈表元素長(zhǎng)度>8"，則將該鏈表結(jié)構(gòu)轉(zhuǎn)為"紅黑樹結(jié)構(gòu)"。
3、找到對(duì)應(yīng)的數(shù)組元素或者鏈表元素，同時(shí)創(chuàng)建新的數(shù)據(jù)元素或者覆蓋元素之后。如果條件滿足元素大小size>允許的最大元素?cái)?shù)量threshold，則再一次進(jìn)行擴(kuò)容操作。每次擴(kuò)容操作，新的數(shù)組大小將是原始的數(shù)組長(zhǎng)度的兩倍。
4、put操作完成。
調(diào)用put方法示例
下面通過(guò)使用例子介紹這個(gè)過(guò)程
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ù)組下標(biāo)
hashMap.put(a1, "1");// 2
hashMap.put(a2, "2");// 3
hashMap.put(a3, "5");// 4
1、創(chuàng)建了一個(gè)HashMap對(duì)象，初始化initialCapacity為4，增長(zhǎng)因子為0.75。threshold初始化為4
2、進(jìn)行了第一次put，因?yàn)閠able為空，進(jìn)行了第一次resize()擴(kuò)容操作，數(shù)組進(jìn)行初始化，默認(rèn)為16. threshold變?yōu)?。同時(shí)通過(guò)hash算法（數(shù)組長(zhǎng)度n-1 & hash）即為1。
3、第二次put操作，同時(shí)獲取數(shù)組下標(biāo)為2，此時(shí)數(shù)組下標(biāo)為2當(dāng)前沒(méi)有數(shù)組元素，則直接創(chuàng)建數(shù)據(jù)元素放入
4、第三次put操作，得到數(shù)組下標(biāo)為1已經(jīng)有了一個(gè)數(shù)組元素。同時(shí)我們知道存儲(chǔ)數(shù)據(jù)的Node對(duì)象中又一個(gè)next，則新的此時(shí)的數(shù)據(jù)元素放入上一個(gè)鏈表中next為空的Node中的next中。
形成了如下圖的數(shù)據(jù)結(jié)構(gòu)
結(jié)論：通過(guò)hash算法進(jìn)行計(jì)算的出來(lái)的數(shù)組下標(biāo)，有一定概率會(huì)導(dǎo)致hash沖突，那在一個(gè)數(shù)組元素中，存在hash值一樣的key，key卻不相等。為了解決這一個(gè)hash沖突問(wèn)題，使用了鏈表結(jié)構(gòu)進(jìn)行處理。
HashMap擴(kuò)容resize()
java是靜態(tài)方法，在數(shù)組進(jìn)行初始化時(shí)，必須給一個(gè)數(shù)組長(zhǎng)度。HashMap定義默認(rèn)的數(shù)組長(zhǎng)度為16。條件滿足元素size>允許的最大元素?cái)?shù)量threshold。則進(jìn)行擴(kuò)容。一般來(lái)說(shuō)，在put操作中，HashMap至少進(jìn)行了一次擴(kuò)容（第一次為初始化）。
我們?cè)谠械氖纠尤肴缦?/p>
int a4 = 6;
hashMap.put(a4, "6");復(fù)制代碼
形成了新的結(jié)構(gòu)，如下圖
放入了2:2的next中，此時(shí)size=4,threshold>3，條件滿足size>threshold，進(jìn)行擴(kuò)容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) {
// 超過(guò)最大限制，不進(jìn)行擴(kuò)容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 進(jìn)行原始長(zhǎng)度*2擴(kuò)容
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);
}
// 新的最大允許元素?cái)?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í)行了擴(kuò)容，新數(shù)組長(zhǎng)度為8，新的結(jié)構(gòu)如下
在新的結(jié)構(gòu)中，將原始的數(shù)組下標(biāo)為1和2鏈表元素均勻分布新數(shù)組的其他數(shù)組元素中。此間擴(kuò)容的變化的過(guò)程如下
老數(shù)組長(zhǎng)度為4，通過(guò)算法得出數(shù)據(jù)的下標(biāo)1:1為1,5:5為1,2:2和6:6為2
1(1:1 == > 5:5)
2(2:2 == > 6:6)
在進(jìn)行擴(kuò)容操作是，數(shù)組元素鏈表中的第一個(gè)數(shù)組下標(biāo)不會(huì)產(chǎn)生變化，在遍歷鏈表其他元素中通過(guò)算法"e.hash & oldCap"!=0則將鏈表元素放入新數(shù)據(jù)數(shù)組下標(biāo)為[原始數(shù)據(jù)下標(biāo)+原始數(shù)據(jù)長(zhǎng)度]
再次引用大神的圖，便于理解擴(kuò)容的數(shù)據(jù)移動(dòng)變化
在擴(kuò)容操作中，因無(wú)需重新計(jì)算hash值，同時(shí)均勻?qū)㈡湵頉_突的元素均勻分布到新的數(shù)組中。這設(shè)計(jì)實(shí)在是巧妙。
get尋找數(shù)據(jù)
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方法比較簡(jiǎn)單，基本流程為通過(guò)key的hashCode和尋址算法得到數(shù)組下標(biāo)，若數(shù)組元素中的key和hash相等，則直接返回。若不想等，同時(shí)存在鏈表元素，則遍歷鏈表元素進(jìn)行匹配。由于1.8引用了紅黑樹結(jié)構(gòu)，在鏈表元素過(guò)多時(shí)，1.8的實(shí)現(xiàn)將比1.7在get和put操作上效率高上很多。
