1、HashMap概述
Map 是 Key-Value 對(duì)映射的抽象接口，該映射不包括重復(fù)的鍵，即一個(gè)鍵對(duì)應(yīng)一個(gè)值。HashMap 是 Java Collection Framework 的重要成員，也是Map族(如下圖所示)中我們最為常用的一種。簡(jiǎn)單地說(shuō)，HashMap 是基于哈希表的 Map 接口的實(shí)現(xiàn)，以 Key-Value 的形式存在，即存儲(chǔ)的對(duì)象是 Entry (同時(shí)包含了 Key 和 Value) 。特別地，
此外，HashMap 是 Map 的一個(gè)非同步的實(shí)現(xiàn)。
2、設(shè)計(jì)思想
HashMap采用的是哈希表的數(shù)據(jù)結(jié)構(gòu)。哈希表是一種以
來(lái)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，哈希表的哈希函數(shù)通常有 直接定址法、平方取中法、求余法等。
而hashMap的設(shè)計(jì)者則采取求余法來(lái)對(duì)其進(jìn)行元素的均勻分配。
在源碼中，有這么一句代碼tab[i = (n - 1) & hash],n代表的是數(shù)組的長(zhǎng)度，hash是指的key的hashCode()值，這句話設(shè)計(jì)者的意思是想讓其相當(dāng)于hash%n(位運(yùn)算比%的運(yùn)算要快，源碼中有大量這種位運(yùn)算)，那么你可能會(huì)問(wèn)了，怎養(yǎng)才能使得這兩個(gè)相等呢？這就涉及到位運(yùn)算的知識(shí)了。
首先要知道1&1=1,0&0=0,1&0=0,0&1=0
要使得 (n-1)&hash <==> hash%n,就得使得n為2的n次冪，因?yàn)?的n次冪的二進(jìn)值形式為0000000100000xxxx,因?yàn)閔ashmap的數(shù)組長(zhǎng)度初始化為1<<4,也就是16，那么就以16為例子，二進(jìn)制為0...010000 ,n - 1也就是 0...01111,那么(n - 1)& hash為
hash : 00101010 00011111 00101010 01110100
&
n - 1: 00000000 00000000 00000000 00001111
---------------------------------------------------------
00000000 00000000 00000000 00000100
(可以看出得到的值是在0-15之間(這就保證了==>hash%n)， 而且決定最終值的是hash的后面4位)
這是hash值的計(jì)算方式。
static final int hash(Object key) {
int h;
//將前面的16位和后面的16位進(jìn)行異或，使擾動(dòng)之后的index結(jié)果盡可能的不同
//這么做也能在保證table的length比較小的時(shí)候，也能
//保證到高低位的bit都參與到hash的計(jì)算中來(lái)，同時(shí)也不會(huì)有太大的開(kāi)銷(xiāo)
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
注意，由于hashCode()可以進(jìn)行重寫(xiě)(hashCode和equals()這兩個(gè)方法一定要
一起重寫(xiě)),所以key的hash值有可能重復(fù)(另外字符的hashCode()也有可能重復(fù)，如一些特殊字符)
那么你又會(huì)問(wèn)了HashMap是如何保證長(zhǎng)度是2的n次冪的呢？
這就要看tableSizeFor()了,這個(gè)方法保證了數(shù)組table的長(zhǎng)度是不小于cap的最小2的n次冪
static final int MAXIMUM_CAPACITY = 1 << 30;//超過(guò)這個(gè)，就變成負(fù)數(shù)了
//得到不小于cap的最小整次冪(最高位1后面都變成1，然后再加1)
//eg：1 2 4 8 16 32
//cap:5 15 30 傳入的cap
//n:8 16 32 得到的n
static final int tableSizeFor(int cap) {
int n = cap - 1;//為了避免cap是2的整次冪，從而導(dǎo)致n變成cap的2倍
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;
}
總體思路是：因?yàn)?的冪次都是1000xxxx的形式，所以我們只需把最高位
向右全部變成1，然后再加1變成10000xxxx的形式。就得到了不小于cap
的最近2的次冪.
00000000 00000000 00000000 00000100 n
00000000 00000000 00000000 00000010 n>>>1 n|n:00000000 00000000 00000000 00000110
00000000 00000000 00000000 00000001 n>>>2 n|n:00000000 00000000 00000000 00000111
00000000 00000000 00000000 00000000 n>>>4 n|n:00000000 00000000 00000000 00000111
00000000 00000000 00000000 00000000 n>>>8 n|n:00000000 00000000 00000000 00000111
00000000 00000000 00000000 00000000 n>>>16 n|n:00000000 00000000 00000000 00000111
00000000 00000000 00000000 00001000 n+1
2.1初始化和擴(kuò)容
Q:HashMap是什么時(shí)候進(jìn)行初始化和擴(kuò)容的，擴(kuò)容的長(zhǎng)度是多少，擴(kuò)容是怎么進(jìn)行的。
A:你可能會(huì)說(shuō)，那我判斷size>table.length,不就是可以進(jìn)行擴(kuò)容了嗎？首先table數(shù)組并不是等到裝滿(mǎn)了，再進(jìn)行擴(kuò)容的，因?yàn)檫@樣子會(huì)使得hash的碰撞增多，但是又不能太小就進(jìn)行擴(kuò)容，因?yàn)檫@會(huì)導(dǎo)致table里面的空元素增多，對(duì)table的空間進(jìn)行浪費(fèi),這就使得我們要確定一個(gè)閥值對(duì)table數(shù)組進(jìn)行擴(kuò)容，而確定這個(gè)閥值的因素，我們就叫做 加載因子 。在hashMap中，加載因子loadFactor默認(rèn)為0.75f。為什么是這個(gè)值，我總結(jié)了幾點(diǎn)下面幾點(diǎn)原因：
1、從區(qū)間上來(lái)說(shuō)，0.5太小，會(huì)減少hash碰撞，造成空間的浪費(fèi),定義為1的話，則會(huì)造成hash碰撞增多
2、從數(shù)學(xué)角度上來(lái)說(shuō)，由于長(zhǎng)度是2的整次冪，所以*0.75一般都可以得到一個(gè)整數(shù)的結(jié)果
3、從泊松分布上來(lái)說(shuō)，0.7多可以使得碰撞的元素在8以上的概率極大減小
但是為什么是0.75這個(gè)值,其實(shí)只是個(gè)經(jīng)驗(yàn)值,和泊松分布并沒(méi)有什么關(guān)系,這是java官方自己說(shuō)的.
//初始化和擴(kuò)容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//舊的數(shù)組長(zhǎng)度
int oldThr = threshold;//舊的預(yù)期值
int newCap, newThr = 0;
if (oldCap > 0) {
//已經(jīng)初始化過(guò)，現(xiàn)在要進(jìn)行擴(kuò)容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY){
//對(duì)舊的數(shù)組長(zhǎng)度和舊的預(yù)期值進(jìn)行2倍的擴(kuò)容
newThr = oldThr << 1; // double threshold
}
} else if (oldThr > 0){ // initial capacity was placed in threshold
//進(jìn)行數(shù)組的初始化
newCap = oldThr;
}else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;//默認(rèn)的初始化長(zhǎng)度 1<<4 16
//初始化預(yù)期值
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];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
//對(duì)舊的數(shù)組進(jìn)行一個(gè)數(shù)據(jù)遷移
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//如果oldTab[j] 里面有東西(紅黑樹(shù)或者鏈表)
oldTab[j] = null;//清除舊的格子,對(duì)節(jié)點(diǎn)進(jìn)行重新分布
if (e.next == null){//只有一個(gè)節(jié)點(diǎn)
newTab[e.hash & (newCap - 1)] = e;//用哈希函數(shù)重新計(jì)算index
}else if (e instanceof TreeNode){
//格子里面裝著紅黑樹(shù)，對(duì)其進(jìn)行拆解...
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
}else { // preserve order
//格子里面裝著多個(gè)節(jié)點(diǎn),先初始化4個(gè)節(jié)點(diǎn)
//分別是頭尾高低節(jié)點(diǎn)
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;//下一個(gè)節(jié)點(diǎn)
do {
next = e.next;
//oldCap是2的整次冪 (因此二進(jìn)制是
//10000....)，以16為例子，結(jié)果只可能
//是0或者16
if ((e.hash & oldCap) == 0) {
//代表是在0-16里面
//所以新的數(shù)組還在里面，就不用遷移
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}else {
//節(jié)點(diǎn)的hash是可以在16之外的
//進(jìn)行遷移
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
//hash&16判斷比較小的數(shù)據(jù)
//位置不變
loTail.next = null;
newTab[j] = loHead;//loHead存儲(chǔ)著hash…&16之后比較小
//節(jié)點(diǎn)集合
}
if (hiTail != null) {
//hash&16判斷比較小的數(shù)據(jù)
//位置加上舊的數(shù)組長(zhǎng)度
hiTail.next = null;
newTab[j + oldCap] = hiHead;//hiHead存儲(chǔ)著hash&16之后比較大
//節(jié)點(diǎn)集合
}
}
}
}
}
return newTab;
}
從上面可以看出，hashMap在進(jìn)行擴(kuò)容的時(shí)候，會(huì)對(duì)長(zhǎng)度進(jìn)行原來(lái)2倍的擴(kuò)充，并且對(duì)table[index] 元素上面的鏈表進(jìn)行遷移，這里注意，因?yàn)閠able[index]元素里面的單鏈表，有可能會(huì)有高的hash值(超過(guò)舊的數(shù)組長(zhǎng)度為高)和低位的hash值,那么我們就要把低位和高位分別存在一個(gè)鏈表集合中，這時(shí)候源碼是用(e.hash & oldCap) == 0來(lái)區(qū)分的高低位置的。以16為例，二進(jìn)制為0...01000,所以&它的值要么是0，要么是16，并且用loHead和hiHead存儲(chǔ)起來(lái)。所以，擴(kuò)容之后的index要么是原來(lái)的，要么是加上+舊的長(zhǎng)度length
3、Hashmap結(jié)構(gòu)圖(紅黑樹(shù)后面再講解)
這圖就很好的表現(xiàn)了hashMap的數(shù)據(jù)結(jié)構(gòu)，當(dāng)key的hash的值相等的時(shí)候，它采取尾接法，形成一條單鏈表.
4、put過(guò)程
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
@param evict 如果為false，則表處于創(chuàng)建模式。
如果為true的話，就刪除最久沒(méi)使用的，
這個(gè)是用在LinkedHashMap里面的
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判斷當(dāng)前的table是否為空，為空的話初始化table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//(n-1)&hash 想當(dāng)于hash%n 隨機(jī)分布到0-15
tab[i] = newNode(hash, key, value, null);//當(dāng)前的table[i]里面沒(méi)有鏈表，初始化
else {
//當(dāng)前table[i]存在節(jié)點(diǎn)
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))){
//如果要插入的節(jié)點(diǎn)已經(jīng)存在，且key相等，賦值給e
e = p;
}else if (p instanceof TreeNode){
//如果table[i]里面已經(jīng)有紅黑樹(shù)，則插入紅黑樹(shù)，并進(jìn)行旋轉(zhuǎn)的操作
//如果有相同hash和相同key的話，就返回值
//具體請(qǐng)看下一篇博文紅黑樹(shù)，里面有具體的講解
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
}else {
//單鏈表，往下查找并插入節(jié)點(diǎn) 尾插法
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//找到null的節(jié)點(diǎn)，進(jìn)行插入
p.next = newNode(hash, key, value, null);
//如果這個(gè)大于等于8，則把單鏈表變成紅黑樹(shù)
//這里你可能有個(gè)疑問(wèn)，8-1不是等于7嗎？
//那是因?yàn)?binCount是從下標(biāo)0開(kāi)始的?。。?！)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))){
//往下找，找到相同的key節(jié)點(diǎn),則break結(jié)束循環(huán)
break;
}
p = e;
}
}
if (e != null) { // existing mapping for key
//e不為null，則說(shuō)明有相同的節(jié)點(diǎn)，則修改value的值
V oldValue = e.value;
//由于put操作的時(shí)候，onlyIfAbsent傳的是false
//則舊的值終會(huì)被替換
/**@param onlyIfAbsent 代表著是否保留舊的value
**/
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//afterNodeAccess 是一個(gè)回調(diào)方法，回調(diào)相同key的節(jié)點(diǎn)
/**@link LinkedHashMap有用到這個(gè)**/
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//結(jié)構(gòu)修改的次數(shù)加1 迭代器 failfast
//size 加1之后判斷是否超出預(yù)期的容量值
if (++size > threshold){
//進(jìn)行擴(kuò)容
resize();
}
afterNodeInsertion(evict);//也是LinkedHashMap用到的.
//根據(jù)Lru算法來(lái)刪除最久沒(méi)使用的
//節(jié)點(diǎn)
return null;
}
從put過(guò)程可以看出，判斷table是否為空，若為空，則執(zhí)行resize方法初始化table數(shù)組，如果table[i = (n-1)&hash]的值為空，則初始化一個(gè)鏈表節(jié)點(diǎn),如果不為null，則判斷頭節(jié)點(diǎn)是否和要put的節(jié)點(diǎn)key相等，如果不等，就判斷鏈表是否被紅黑樹(shù)化，需要搜索紅黑樹(shù)查找該key值是否已存在；鏈表未被樹(shù)化，且頭節(jié)點(diǎn)key值與新增key值不同，需要遍歷鏈表查找該key值是否存在。如果不存在，則插入，這里需要注意的是，當(dāng)鏈表>=8的時(shí)候，則轉(zhuǎn)化成紅黑樹(shù)
上面的判斷邏輯中，不管是哪一種，只要key值已存在，則賦值給e，因此在后面判斷e是否為null，若不為空，則表示已存在，根據(jù)策略決定是否覆蓋原值
如果key值不存在，需要將modCount自增1，然后將size自增，判斷大小是否超過(guò)閾值，是，則通過(guò)resize方法double原table數(shù)組的容量。
