一、HashMap的關(guān)鍵參數(shù)及部分源碼解析
1.1 HashMap的幾個(gè)關(guān)鍵參數(shù)
HashMap的源碼中存下以下幾個(gè)常量
//默認(rèn)容量氮采，默認(rèn)為16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量逊桦，最大為2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//負(fù)載因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//變?yōu)榧t黑樹的閾值悟耘，jdk1.8的參數(shù)，當(dāng)鏈的長(zhǎng)度大于8時(shí)，則從鏈表變?yōu)榧t黑樹
static final int TREEIFY_THRESHOLD = 8;
//jdk1.8的參數(shù)似踱，當(dāng)紅黑樹的節(jié)點(diǎn)小于6時(shí)盾舌，則從紅黑樹轉(zhuǎn)變?yōu)殒湵? static final int UNTREEIFY_THRESHOLD = 6;
//jdk1.8的參數(shù)墓臭，最小樹形化容量閾值，當(dāng)整個(gè)hash表容量大于64時(shí)則從鏈表轉(zhuǎn)變?yōu)榧t黑樹
static final int MIN_TREEIFY_CAPACITY = 64;
1.2HashMap的部分源碼解析
幾個(gè)構(gòu)造方法
1.2.1無(wú)參構(gòu)造
默認(rèn)給初始容量（16）和負(fù)載因子（0.75）
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
1.2.2按容量初始化
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
1.2.3按容量和負(fù)載因子初始化
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//得到比給定initialCapacity大的最接近的2的冪
this.threshold = tableSizeFor(initialCapacity);
}
需要注意的是妖谴，這里最終初始化的HashMap的容量不一定是傳進(jìn)來(lái)的initialCapacity窿锉，而是比該值大的最接近的一個(gè)2的冪，這里關(guān)鍵要看下tableSizeFor方法
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;
}
這里解釋下為什么會(huì)出現(xiàn)5次無(wú)符號(hào)右移膝舅，
假設(shè)cap=1嗡载，那int n = cap - 1就是0，無(wú)論經(jīng)過多少次右移都是0仍稀，最終返回n+1=1也就是2的0次冪洼滚；
假設(shè)cap>1，那int n = cap - 1后技潘，n>0遥巴，在二進(jìn)制表示中，最高為一定是1享幽，例如00010000铲掐，當(dāng)經(jīng)過第一次無(wú)符號(hào)右移一位，并進(jìn)行或運(yùn)算后就成了00011000值桩，第二次右移兩位或運(yùn)算摆霉，00011110，第三次右移思維或運(yùn)算奔坟，00011111携栋，此后無(wú)論怎么右移再進(jìn)行或運(yùn)算都會(huì)變成00011111，可以看出蛀蜜，每次進(jìn)行右移或運(yùn)算刻两，其實(shí)就相當(dāng)于在把最高位后的每一位變成1，這樣當(dāng)最終返回n+1時(shí)滴某，就自然而然比最高位還高一位變?yōu)?磅摹，后面都是0滋迈，也就是一個(gè)恰好比原給定數(shù)大的2的冪次方數(shù)。
那為什么最多右移16位呢户誓，因?yàn)橛乙?6位并進(jìn)行或運(yùn)算饼灿，相當(dāng)于是容量到了2的32次方了，而HashMap的最大容量MAXIMUM_CAPACITY 是2的30次方帝美。
1.2.4按照指定Map初始化一個(gè)HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
可以看到真正核心的方法就是最后這個(gè)putVal碍彭，這個(gè)方法其實(shí)就涉及到了HashMap的實(shí)現(xiàn)原理，我們接下來(lái)詳細(xì)看
二悼潭、HashMap實(shí)現(xiàn)原理簡(jiǎn)述
2.1 數(shù)組+鏈表+紅黑樹
HashMap的底層實(shí)際是一張HashTable庇忌，也就是會(huì)先根據(jù)key值來(lái)hash，并根據(jù)不同的hash結(jié)果將原來(lái)的key,value鍵值對(duì)放到hashTable這個(gè)數(shù)組的不同區(qū)域舰褪，對(duì)于相同hash值的key皆疹，則使用鏈表來(lái)解決，在jdk1.8后如果鏈表的長(zhǎng)度超過8占拍，則會(huì)轉(zhuǎn)化為紅黑樹略就。
回到前文1.2.4按照指定Map初始化一個(gè)HashMap源碼中，這里有兩個(gè)方法令人在意晃酒，一個(gè)是 resize();另一個(gè)是 putVal(hash(key), key, value, false, evict);
先來(lái)看 resize();
2.2 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) {
//如果舊容量已經(jīng)達(dá)到貨超過最大容量表牢，那新的無(wú)論多少，其實(shí)都不需要再擴(kuò)容贝次，直接返回最大容量
threshold = Integer.MAX_VALUE;
return oldTab;
}
//這里在判斷條件中容量也翻倍了
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
//oldCap為0崔兴，但閾值不為0時(shí)，此時(shí)將容量設(shè)置為閾值大小即可
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//舊閾值和容量均小于等于0時(shí)浊闪，此時(shí)將容量設(shè)置為默認(rèn)容量恼布，閾值設(shè)置為默認(rèn)容量*默認(rèn)容量因子0.75
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;
//用新的容量創(chuàng)建新的hashTable數(shù)組螺戳，并將其賦值給Map中的table
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//如果舊的數(shù)組不為空搁宾，則遍歷舊的數(shù)組賦值到新數(shù)組上
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//如果節(jié)點(diǎn)是單個(gè)節(jié)點(diǎn)，則直接將節(jié)點(diǎn)定位到新的table上即可
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果節(jié)點(diǎn)是紅黑樹倔幼，則需要對(duì)紅黑樹進(jìn)行rehash操作盖腿，紅黑樹的rehash其實(shí)原理上和鏈表的rehash類似，這里就只以鏈表為例损同，在下一個(gè)else分支中詳解
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//如果節(jié)點(diǎn)是鏈表翩腐，則需要對(duì)鏈表進(jìn)行rehash
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//根據(jù)(e.hash & oldCap) 是否為0將鏈表分為兩個(gè)部分
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//因?yàn)閿U(kuò)容是左移擴(kuò)容的2倍，所以膏燃，新的節(jié)點(diǎn)要么還在原位置茂卦，要么就是在原位置+原容量的位置上,是否在原位置，取決于(e.hash & oldCap)组哩，如果為0等龙，則表示最高位沒有發(fā)生變化处渣，還在原位置，否則最高位為1隨著左移也擴(kuò)容了蛛砰，則在原位置+原容量的位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
2.3 putVal(hash(key), key, value, false, evict)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//如果插入的位置是空的罐栈，則直接在該位置插入新的節(jié)點(diǎn)即可
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果該位置是單節(jié)點(diǎn)，且目前的節(jié)點(diǎn)的key就是要插入的鍵值對(duì)的key泥畅，則直接將該節(jié)點(diǎn)更新
e = p;
else if (p instanceof TreeNode)
//如果該位置是紅黑樹荠诬，則按紅黑樹的插入邏輯，因?yàn)榧t黑樹并非本文討論的重點(diǎn)位仁，故不贅述
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//該位置為鏈表柑贞，則遍歷該位置的元素先
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//直到鏈表的末尾也沒找到相同key的節(jié)點(diǎn)，則為新的節(jié)點(diǎn)聂抢，添加一個(gè)node
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//如果長(zhǎng)度已經(jīng)到了需要轉(zhuǎn)變?yōu)榧t黑樹的長(zhǎng)度-1了凌外，那此時(shí)需要轉(zhuǎn)變?yōu)榧t黑樹
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//如果找到了相同key的節(jié)點(diǎn)，則不需要再遍歷了
break;
p = e;
}
}
if (e != null) { // existing mapping for key
//e不為空涛浙，說(shuō)明以前map中存在同樣的key康辑，將舊值替換
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
//如果size增加后已經(jīng)超過閾值，則擴(kuò)容
resize();
afterNodeInsertion(evict);
return null;
}
2.4其他需要說(shuō)明的
通過上述源碼及標(biāo)注在源碼中的注釋可以看出來(lái)轿亮，hashMap的底層其實(shí)是數(shù)組+鏈表+紅黑樹的形式疮薇，這里需要說(shuō)明的是，紅黑樹是jdk1.8以后才引入到hashMap中的我注，1.8以前只是單純的數(shù)組+鏈表的形式按咒。
另外也正是因?yàn)檫@一點(diǎn)變化，jdk1.8后在插入節(jié)點(diǎn)時(shí)但骨，是采用的尾端插入励七，而在1.8以前其實(shí)是頭插入。
三奔缠、為什么HashMap是線程不安全的
3.1 putVal時(shí)存在數(shù)據(jù)不一致的可能
通過剛剛的源碼可以看出來(lái)掠抬，hashMap在put值時(shí)，是先找到原來(lái)的hashtable校哎，取到原來(lái)的hash(key)所在位置的鏈表or紅黑樹两波，并遍歷找到原來(lái)key的數(shù)據(jù)進(jìn)行修改或在末尾插入，如果此時(shí)兩個(gè)線程A和B同時(shí)進(jìn)來(lái)闷哆，并同時(shí)取到了hash(key)所在位置的鏈表or紅黑樹(此時(shí)還沒有任何一個(gè)線程修改map成功)腰奋，假設(shè)A和B操作的是同一個(gè)key，則會(huì)出現(xiàn)ABA問題抱怔，如果A和B操作的是不同key且最終都是在隊(duì)尾新增劣坊，則A剛剛在隊(duì)尾新增的記錄，會(huì)被B在同樣位置新增的數(shù)據(jù)覆蓋屈留，導(dǎo)致A的數(shù)據(jù)丟失局冰。
3.2 resize()可能導(dǎo)致的死循環(huán)
如果兩個(gè)線程同時(shí)發(fā)現(xiàn)需要擴(kuò)容括儒，同時(shí)操作某一鏈表時(shí)，可能會(huì)導(dǎo)致該鏈表變成循環(huán)鏈表锐想，此時(shí)再去get時(shí)就會(huì)發(fā)生死循環(huán)
四帮寻、ConcurrentHashMap原理
為了解決HashMap的線程不安全問題，java提供了線程安全的HashMap——ConcurrentHashMap赠摇。
ConcurrentHashMap在jdk1.8以前和1.8以后原理上有一定的區(qū)別固逗，jdk1.8以前采用的是分段加鎖的方式實(shí)現(xiàn)，1.8以后則采用CAS寫入數(shù)據(jù)+同步代碼塊來(lái)實(shí)現(xiàn)藕帜，這里只貼上1.8及1.8以后put值的代碼
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//找到的位置為空烫罩，則CAS寫入數(shù)據(jù)，確保寫入的時(shí)候table沒有發(fā)生變更
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
//需要擴(kuò)容,底層也是CAS操作+synchronized 洽故，這里不贅述
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
//利用 synchronized 鎖寫入數(shù)據(jù)
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
//如果超過閾值贝攒，則需要轉(zhuǎn)變?yōu)榧t黑樹，這里和HashMap有一點(diǎn)小區(qū)別时甚，HashMap是在循環(huán)體內(nèi)部進(jìn)行的判斷隘弊，而這里實(shí)在循環(huán)體外，所以并沒有-1
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
