摘要：但是還會(huì)有統(tǒng)計(jì)數(shù)問(wèn)題和數(shù)據(jù)丟失問(wèn)題。中使用了保證線程安全，但是在中又把它優(yōu)化掉了，直接使用
一、開(kāi)篇
HashMap、CurrentHashMap 面試時(shí)都要問(wèn)爛了，用也用爛了。但是網(wǎng)上的解析要不就是不夠全面，要么就是copy來(lái)copy去，連基于JDK版本有的都很混亂。這篇文章帶你解析 基于jdk1.7、jdk1.8不同的hashMap和ConcurrentHashMap簡(jiǎn)略分析（很多代碼和HashMap都是重復(fù)的）。希望看完后有所收獲。
二、提出問(wèn)題
1、我們都知道，HashMap是線程不安全的，那它的不安全體現(xiàn)在哪些方面呢？
2、HashMap在JDK1.8引入了紅黑樹(shù)，引入后有什么好處呢？除了引入紅黑樹(shù)于1.7還有什么不同呢？
3、ConcurrentHashMap怎樣解決的HashMap的并發(fā)問(wèn)題，用synchronized不行嗎？JDK1.8又有什么改變呢？
4、歡迎留言提出各種問(wèn)題...............
三、源碼分析
基于jdk1.7的HashMap
首先來(lái)看1.7的存儲(chǔ)元素類(lèi)Entry類(lèi)
static class Entry implements Map.Entry {
final K key;
V value;
Entry next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
......
}
hash()方法：
如果Key是字符串類(lèi)型，則使用專(zhuān)門(mén)為字符串設(shè)計(jì)的Hash方法，否則使用一連串的異或操作增加hash隨機(jī)性
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
接下來(lái)是put()方法:
public V put(K key, V value) {
if (key == null)
return putForNullKey(value); //專(zhuān)門(mén)放置NullKey
int hash = hash(key);//獲取hash值
int i = indexFor(hash, table.length);//獲取數(shù)組下標(biāo) h & (length-1);
//這個(gè)for循環(huán)進(jìn)行檢測(cè)，如果找到key相同的元素則進(jìn)行覆蓋
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;//修改次數(shù)+1
addEntry(hash, key, value, i);
return null;
}
可以看出addEntry()方法進(jìn)行添加元素，進(jìn)去看一下:
void addEntry(int hash, K key, V value, int bucketIndex) {
//擴(kuò)容檢測(cè)
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//創(chuàng)建entry
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];//獲取原先數(shù)組位置的元素
table[bucketIndex] = new Entry<>(hash, key, value, e);//該數(shù)組位置替換新元素，next為原元素（頭插）
size++;
}
以上put方法就完成了，但是有一個(gè)重點(diǎn)是擴(kuò)容方法，讓我們點(diǎn)進(jìn)去看下resize方法():
void resize(int newCapacity) {
Entry[] oldTable = table//原數(shù)組
int oldCapacity = oldTable.length;
//當(dāng)擴(kuò)容到允許最大擴(kuò)容數(shù)時(shí)不再擴(kuò)容
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//新數(shù)組
Entry[] newTable = new Entry[newCapacity];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;//是否需要再Hash
transfer(newTable, rehash);//進(jìn)行數(shù)組移動(dòng)
table = newTable;//新數(shù)組
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//擴(kuò)大Threshold
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//不斷將原元素放進(jìn)新數(shù)組
for (Entry e : table) {
while(null != e) {
Entry next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
get()方法就相對(duì)簡(jiǎn)單些:
public V get(Object key) {
if (key == null)
return getForNullKey();//get null key
Entry entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);//計(jì)算hash值
//鏈表查詢
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
到這里為止1.7HashMap主要方法就分析完畢，1.7的hashMap實(shí)現(xiàn)還是很容易理解的。但是如果出現(xiàn)并發(fā)，到底在哪里有問(wèn)題呢。
分析put方法：①modCount++;不是原子的，所以修改次數(shù)不準(zhǔn)確，size++不是原子的，所以hashMap的size也不準(zhǔn)確
②在createEntry()方法中，假設(shè)兩個(gè)線程同時(shí)獲取數(shù)組頭結(jié)點(diǎn)，一個(gè)線程修改后另一個(gè)線程還使用原來(lái)的數(shù)組元素頭結(jié)點(diǎn)會(huì)造成數(shù)據(jù)丟失
③擴(kuò)容死循環(huán)問(wèn)題，在transfer方法中，假設(shè)線程1、2同時(shí)擴(kuò)容，則可能出現(xiàn)頭插法互相引用擴(kuò)容死循環(huán)的問(wèn)題
2. 基于jdk1.8的HashMap
讓我們以同樣的招式看一看在jdk1.8中HashMap有什么變化
首先看下1.8存儲(chǔ)元素的Node類(lèi)
和1.7中的Entry類(lèi)似，不過(guò)換了個(gè)名字
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
......
}
當(dāng)晉升為樹(shù)形結(jié)構(gòu)時(shí)，則采用TreeNode
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
......
}
hash方法:
可以看出Hash算法被優(yōu)化了，使得高位參與運(yùn)算，減少了hash沖突
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
接下來(lái)是put方法【方法變長(zhǎng)了o(╥﹏╥)o】：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)//如果tabl未創(chuàng)建或table長(zhǎng)度為0，則初始化（初始化過(guò)程也放入擴(kuò)容方法中）
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//計(jì)算數(shù)組位置，如果該位置沒(méi)有元素直接放入數(shù)組中
tab[i] = newNode(hash, key, value, null);
else { //該位置有元素
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //如果該位置與元素相同key直接覆蓋值
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);//如果該結(jié)構(gòu)為樹(shù)形，則加入TreeNode
else { //如果還是鏈表型結(jié)構(gòu)
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);//將節(jié)點(diǎn)加入鏈表
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//如果鏈表長(zhǎng)度過(guò)長(zhǎng)（8），轉(zhuǎn)換為紅黑樹(shù)
break;
}
//如果鏈表中存在相同Key則直接覆蓋
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);//LinkedHashMap使用，保證順序(HashMap實(shí)現(xiàn)為空)
return oldValue;//返回oldValue
}
}
++modCount;//操作次數(shù)加1
if (++size > threshold)
resize();//如果size>容量則進(jìn)行擴(kuò)容
afterNodeInsertion(evict);//LinkedHashMap使用，用來(lái)回調(diào)移除最早放入Map的對(duì)象（HashMap實(shí)現(xiàn)為空）
return null;
}
OK,put方法分析完后就著重分析下擴(kuò)容方法了resize():【吐槽一下我一直覺(jué)得jdk1.8可讀性變差了，不僅體現(xiàn)在hashMap上，是提高了性能原因嗎？】
final Node[] resize() {
Node[] oldTab = table; //老的數(shù)組
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; //如果已達(dá)到最大容量不在擴(kuò)容
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) //擴(kuò)容到原來(lái)的兩倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0)
newCap = oldThr;
else { // 如果原容量為0，則進(jìn)行初始化
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;// 新可容納元素個(gè)數(shù)終于確定了
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];//新數(shù)組
table = newTab;
if (oldTab != null) { //排出初始化情況
for (int j = 0; j < oldCap; ++j) { //開(kāi)始循環(huán)數(shù)組
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; //如果數(shù)組位置不為null取值
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;//如果該位置元素沒(méi)有next節(jié)點(diǎn)，將該元素放入新數(shù)組
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap); //如果是樹(shù)形節(jié)點(diǎn)
else { // preserve order
//如果是鏈表且有next節(jié)點(diǎn) ,以原位置移動(dòng)到新位置
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
get()方法:
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;// 判斷key為null的情況
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) { //確保數(shù)組被初始化
if (first.hash == hash && // 檢查第一個(gè)元素
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode) //樹(shù)查找
return ((TreeNode)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;
}
1.8的HahMap主要方法也分析完畢了。那么1.8還會(huì)有死循環(huán)問(wèn)題嗎？可以看出保在移入新數(shù)組中保證了鏈表的原順序，所以不會(huì)有這個(gè)問(wèn)題了。但是 ,還會(huì)有統(tǒng)計(jì)數(shù)問(wèn)題和數(shù)據(jù)丟失問(wèn)題。
基于jdk1.7的currentHashMap
concurrentHashMap介紹就不能像hashmap一樣直接進(jìn)入方法了，有些同學(xué)不了解它的屬性，讓我們先看一下
HashEntry :用來(lái)存儲(chǔ)元素
static final class HashEntry {
final int hash;
final K key;
volatile V value;
volatile HashEntry next;
HashEntry(int hash, K key, V value, HashEntry next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
Segment桶 實(shí)現(xiàn)線程的關(guān)鍵類(lèi)（部分屬性為列出，太長(zhǎng)了。。）
static final class Segment extends ReentrantLock implements Serializable {
//可以看出Segment繼承自ReentrantLock，是一個(gè)天然的鎖
transient volatile HashEntry[] table;
···
transient int count;
transient int modCount;
transient int threshold;
final float loadFactor; transient volatile HashEntry[] table;
transient int count;
transient int modCount;
transient int threshold;
final float loadFactor;
···
}
put()方法：
public V put(K key, V value) {
Segment s;
if (value == null)
throw new NullPointerException(); //不予許null value
int hash = hash(key); //或許hash
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j); //根據(jù)hash獲取對(duì)應(yīng)的桶
return s.put(key, hash, value, false); //put
}
//可以看出put方法和hashMap非常像，只不過(guò)多了一個(gè)加解鎖的過(guò)程
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry node = tryLock() ? null :
scanAndLockForPut(key, hash, value);//tryLock失敗會(huì)重復(fù)執(zhí)行tryLock則進(jìn)行l(wèi)ock【阻塞】，等待鎖的釋放
V oldValue;
try {
HashEntry[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry first = entryAt(tab, index);
for (HashEntry e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
get()方法：
//get方法是不加鎖的，所有共享變量都是通過(guò)volatile修飾的，確保或許最新值
public V get(Object key) {
Segment s;
HashEntry[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment)UNSAFE.getObjectVolatile(segments, u)) != null && //獲取volatile
(tab = s.table) != null) {
for (HashEntry e = (HashEntry) UNSAFE.getObjectVolatile //獲取volatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
基于jdk1.8的ConcurrentHashMap
存儲(chǔ)節(jié)點(diǎn):
static class Node implements Map.Entry {
final int hash;
final K key;
volatile V val;
volatile Node next;
put()方法:
可以看出jdk1.8中取消了桶的設(shè)計(jì)，使用了Node + CAS + Synchronized來(lái)保證并發(fā)安全進(jìn)行實(shí)現(xiàn)
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[] tab = table;;) {
Node f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); //初始化
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //如果該位置無(wú)元素則使用cas插入
if (casTabAt(tab, i, null,
new Node(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) { //如果有元素或cas插入失敗 則使用synchronized 鎖
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node 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 pred = e;
if ((e = e.next) == null) {
pred.next = new Node(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
get()方法
// 也是不加鎖的，直接獲取volatile
public V get(Object key) {
Node[] tab; Node e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
三、總結(jié)
JDK1.7中HashMap采用了數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)，有線程安全問(wèn)題（統(tǒng)計(jì)不準(zhǔn)確，丟失數(shù)據(jù)，死循環(huán)cpu100%），1.8中采用了數(shù)組+鏈表+紅黑樹(shù)的結(jié)構(gòu)，有線程安全問(wèn)題（統(tǒng)計(jì)不準(zhǔn)確，丟失數(shù)據(jù)）。1.8中優(yōu)化了hash算法，并且每次擴(kuò)容不需要重新計(jì)算hash值。
JDK1.7中concurentHashMap使用了segment保證線程安全，但是在1.8中又把它優(yōu)化掉了，直接使用cas+synchronized
