java7中的hashMap和currentHashMap
hashMap
數(shù)據(jù)結(jié)構(gòu)
數(shù)組加鏈表
尋址方式
將key的哈希值對(duì)數(shù)組長(zhǎng)度進(jìn)行取模，結(jié)果作為該Entry在數(shù)組中的index
擴(kuò)容
- 為什么要擴(kuò)容
- 會(huì)存在多個(gè)Entry對(duì)應(yīng)一個(gè)數(shù)組的情況（哈希沖突），當(dāng)都一個(gè)數(shù)組后面的鏈表特別長(zhǎng)的時(shí)候，進(jìn)行遍歷鏈表順序查找效率很低苦囱。所以為了提高性能榜聂，就會(huì)盡量縮小每個(gè)鏈表的長(zhǎng)度唉俗。
- 擴(kuò)容時(shí)機(jī)
- 當(dāng)map中包含的Entry的數(shù)量大于等于 threshold = loadFactor * capacity
- 且 新建的Entry剛好落在一個(gè)非空的數(shù)組上
- 擴(kuò)容機(jī)制
- 創(chuàng)建一個(gè)新表
- 重新生成hash值
- 頭插法插入新表中
線(xiàn)程不安全闹司？
- ==resize死循環(huán)==
上面知道了擴(kuò)容機(jī)制娱仔，擴(kuò)容時(shí)有個(gè)transfer方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
// 1
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// 2
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
- 假如有兩個(gè)線(xiàn)程同時(shí)執(zhí)行transfer
線(xiàn)程A獲取到e=3，e.next=7,暫停了
-
線(xiàn)程B執(zhí)行完了游桩，即7->3->null牲迫，此時(shí)的狀態(tài)
image 這時(shí)候A執(zhí)行，獲取到7的next是3,造成死循環(huán)
-
最后的結(jié)果
image
- ==fail-fast==
在使用迭代器的過(guò)程中如果hashMap被修改借卧，則會(huì)拋出ConcurrentModificationException異常盹憎，也就是fast-fail策略。
HashIterator() {
// 在iterator的next方法訪(fǎng)問(wèn)下一個(gè)Entry事铐刘，會(huì)做這個(gè)檢查陪每，如果不相等，說(shuō)明被修改镰吵，拋出異常
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
- fail-safe
fail-safe任何對(duì)集合結(jié)構(gòu)的修改都會(huì)在一個(gè)復(fù)制的集合上進(jìn)行修改奶稠，因此不會(huì)拋出ConcurrentModificationException
fail-safe機(jī)制有兩個(gè)問(wèn)題
1需要復(fù)制集合，產(chǎn)生大量的無(wú)效對(duì)象捡遍，開(kāi)銷(xiāo)大
2 無(wú)法保證讀取的數(shù)據(jù)是目前原始數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)
currentHashMap
-
采用分段鎖的結(jié)構(gòu)
image - Segment默認(rèn)是16，理論上竹握，最多同時(shí)支持16個(gè)線(xiàn)程并發(fā)讀寫(xiě)画株，但是是操作不同的Segment
- 初始化時(shí)可以指定Segment數(shù)量
- Segment繼承自ReentrantLock,每一個(gè)Segment都會(huì)有一把鎖，保證線(xiàn)程安全
不同之處
ConcurrentHashMap與HashMap相比啦辐，有以下不同點(diǎn)
- ConcurrentHashMap線(xiàn)程安全谓传，而HashMap非線(xiàn)程安全
- HashMap允許Key和Value為null，而ConcurrentHashMap不允許
- HashMap不允許通過(guò)Iterator遍歷的同時(shí)通過(guò)HashMap修改芹关，而ConcurrentHashMap允許該行為续挟，并且該更新對(duì)后續(xù)的遍歷可見(jiàn)
java8中的hashMap和currentHashMap
hashMap
與1.7不同的是，鏈表的元素超過(guò)8個(gè)以后侥衬，會(huì)講鏈表轉(zhuǎn)換成紅黑樹(shù)诗祸，時(shí)間復(fù)雜度由o(n)變?yōu)閛(logN)
currentHashMap
-
結(jié)構(gòu)
- 和hashMap基本一直,數(shù)組+鏈表+紅黑樹(shù)，通過(guò)CAS+Synchronized保證線(xiàn)程安全轴总。
初始化
擴(kuò)容
數(shù)據(jù)遷移
下面分開(kāi)說(shuō)-
sizeCtl
- 是一個(gè)控制標(biāo)識(shí)符直颅，取值不同，含義不同
- -1代表正在初始化
- -N表示有N-1個(gè)線(xiàn)程正在進(jìn)行擴(kuò)容操作(允許多線(xiàn)程擴(kuò)容)
- 正數(shù)或0代表還沒(méi)有被初始化
private transient volatile int sizeC怀樟；
- 初始化數(shù)組
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// 上面說(shuō)過(guò)<0代表被其他線(xiàn)程正在初始化
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// CAS 一下功偿，將 sizeCtl 設(shè)置為 -1，代表?yè)尩搅随i
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
……
break;
}
}
return tab;
}
- 擴(kuò)容
// 首先要說(shuō)明的是往堡，方法參數(shù) size 傳進(jìn)來(lái)的時(shí)候就已經(jīng)翻了倍了
private final void tryPresize(int size) {
***
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
// 這個(gè) if 分支和之前說(shuō)的初始化數(shù)組的代碼基本上是一樣的械荷，在這里共耍，我們可以不用管這塊代碼
if (tab == null || (n = tab.length) == 0) {
****
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
// 我沒(méi)看懂 rs 的真正含義是什么，不過(guò)也關(guān)系不大
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 2. 用 CAS 將 sizeCtl 加 1吨瞎，然后執(zhí)行 transfer 方法
// 此時(shí) nextTab 不為 null
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// 1. 將 sizeCtl 設(shè)置為 (rs << RESIZE_STAMP_SHIFT) + 2)
// 我是沒(méi)看懂這個(gè)值真正的意義是什么痹兜？不過(guò)可以計(jì)算出來(lái)的是，結(jié)果是一個(gè)比較大的負(fù)數(shù)
// 調(diào)用 transfer 方法关拒，此時(shí) nextTab 參數(shù)為 null
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
數(shù)據(jù)遷移
允許多線(xiàn)程
原理：
假設(shè)數(shù)組長(zhǎng)度為n佃蚜，讓每個(gè)線(xiàn)程負(fù)責(zé)一個(gè)小人物，做完一個(gè)再去做另一個(gè)着绊，使用了一個(gè)stride作為步長(zhǎng)（每次遷移的任務(wù)長(zhǎng)度），然后還需要一個(gè)全局的調(diào)度者安排哪個(gè)線(xiàn)程執(zhí)行哪一段归露，這就是transferIndex屬性的作用第一個(gè)線(xiàn)程會(huì)將ransferIndex執(zhí)行原數(shù)組最后的位置洲脂，然后從后往前stride個(gè)任務(wù)屬于它- 然后ransferIndex指向新位置，分給第二個(gè)線(xiàn)程
什么是紅黑樹(shù)
- 每個(gè)節(jié)點(diǎn)要么是紅要么是黑
- 根節(jié)點(diǎn)是黑
- 每個(gè)葉節(jié)點(diǎn)都是黑（葉節(jié)點(diǎn)指樹(shù)尾端NIL或null節(jié)點(diǎn)）
- 如果一個(gè)節(jié)點(diǎn)是紅的剧包，子節(jié)點(diǎn)就是黑的
- 對(duì)于任意節(jié)點(diǎn)恐锦，其到葉節(jié)點(diǎn)尾端的每條路徑都包含相同數(shù)目的黑節(jié)點(diǎn)。(所以是接近平衡的二叉樹(shù))
