摘要:簡介是的線程安全版本,內(nèi)部也是使用數(shù)組鏈表紅黑樹的結(jié)構(gòu)來存儲元素。相比于同樣線程安全的來說,效率等各方面都有極大地提高。中的關(guān)鍵字,內(nèi)部實(shí)現(xiàn)為監(jiān)視器鎖,主要是通過對象監(jiān)視器在對象頭中的字段來表明的。
簡介
ConcurrentHashMap是HashMap的線程安全版本,內(nèi)部也是使用(數(shù)組 + 鏈表 + 紅黑樹)的結(jié)構(gòu)來存儲元素。
相比于同樣線程安全的HashTable來說,效率等各方面都有極大地提高。
用到鎖的簡介這里先簡單介紹一下各種鎖,以便下文講到相關(guān)概念時(shí)能有個(gè)印象。
synchronized
java中的關(guān)鍵字,內(nèi)部實(shí)現(xiàn)為監(jiān)視器鎖,主要是通過對象監(jiān)視器在對象頭中的字段來表明的。
synchronized從舊版本到現(xiàn)在已經(jīng)做了很多優(yōu)化了,在運(yùn)行時(shí)會有三種存在方式:偏向鎖,輕量級鎖,重量級鎖。
偏向鎖,是指一段同步代碼一直被一個(gè)線程訪問,那么這個(gè)線程會自動(dòng)獲取鎖,降低獲取鎖的代價(jià)。
輕量級鎖,是指當(dāng)鎖是偏向鎖時(shí),被另一個(gè)線程所訪問,偏向鎖會升級為輕量級鎖,這個(gè)線程會通過自旋的方式嘗試獲取鎖,不會阻塞,提高性能。
重量級鎖,是指當(dāng)鎖是輕量級鎖時(shí),當(dāng)自旋的線程自旋了一定的次數(shù)后,還沒有獲取到鎖,就會進(jìn)入阻塞狀態(tài),該鎖升級為重量級鎖,重量級鎖會使其他線程阻塞,性能降低。
CAS
CAS,Compare And Swap,它是一種樂觀鎖,認(rèn)為對于同一個(gè)數(shù)據(jù)的并發(fā)操作不一定會發(fā)生修改,在更新數(shù)據(jù)的時(shí)候,嘗試去更新數(shù)據(jù),如果失敗就不斷嘗試。
volatile(非鎖)
java中的關(guān)鍵字,當(dāng)多個(gè)線程訪問同一個(gè)變量時(shí),一個(gè)線程修改了這個(gè)變量的值,其他線程能夠立即看得到修改的值。
volatile只保證可見性,不保證原子性,比如 volatile修改的變量 i,針對i++操作,不保證每次結(jié)果都正確,因?yàn)閕++操作是兩步操作,相當(dāng)于 i = i +1,先讀取,再加1,這種情況 volatile是無法保證的。
自旋鎖
自旋鎖,是指嘗試獲取鎖的線程不會阻塞,而是循環(huán)的方式不斷嘗試,這樣的好處是減少線程的上下文切換帶來的開鎖,提高性能,缺點(diǎn)是循環(huán)會消耗CPU。
分段鎖
分段鎖,是一種鎖的設(shè)計(jì)思路,它細(xì)化了鎖的粒度,主要運(yùn)用在ConcurrentHashMap中,實(shí)現(xiàn)高效的并發(fā)操作,當(dāng)操作不需要更新整個(gè)數(shù)組時(shí),就只鎖數(shù)組中的一項(xiàng)就可以了。
ReentrantLock源碼分析 構(gòu)造方法
可重入鎖,是指一個(gè)線程獲取鎖之后再嘗試獲取鎖時(shí)會自動(dòng)獲取鎖,可重入鎖的優(yōu)點(diǎn)是避免死鎖,synchronized也是可重入鎖。
public ConcurrentHashMap() { } public ConcurrentHashMap(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException(); int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); this.sizeCtl = cap; } public ConcurrentHashMap(Map extends K, ? extends V> m) { this.sizeCtl = DEFAULT_CAPACITY; putAll(m); } public ConcurrentHashMap(int initialCapacity, float loadFactor) { this(initialCapacity, loadFactor, 1); } public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); if (initialCapacity < concurrencyLevel) // Use at least as many bins initialCapacity = concurrencyLevel; // as estimated threads long size = (long)(1.0 + (long)initialCapacity / loadFactor); int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size); this.sizeCtl = cap; }
構(gòu)造方法與HashMap對比可以發(fā)現(xiàn),沒有了HashMap中的threshold和loadFactor,而是改用了sizeCtl來控制,而且只存儲了容量在里面,官方給出的解釋如下:
"-1",表示有線程正在進(jìn)行初始化操作
-(1 + nThreads),表示有n個(gè)線程正在一起擴(kuò)容
0,默認(rèn)值,后續(xù)在真正初始化的時(shí)候使用默認(rèn)容量
"> 0",初始化或擴(kuò)容完成后下一次的擴(kuò)容門檻
增加元素public V put(K key, V value) { return putVal(key, value, false); } final V putVal(K key, V value, boolean onlyIfAbsent) { // key和value都不能為null if (key == null || value == null) throw new NullPointerException(); // 計(jì)算hash值 int hash = spread(key.hashCode()); // 要插入的元素所在桶的元素個(gè)數(shù) int binCount = 0; // 死循環(huán),結(jié)合CAS使用(如果CAS失敗,則會重新取整個(gè)桶進(jìn)行下面的流程) for (Node[] tab = table;;) { Node f; int n, i, fh; if (tab == null || (n = tab.length) == 0) // 如果桶未初始化或者桶個(gè)數(shù)為0,則初始化桶 tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 如果要插入的元素所在的桶還沒有元素,則把這個(gè)元素插入到這個(gè)桶中 if (casTabAt(tab, i, null, new Node (hash, key, value, null))) // 如果使用CAS插入元素時(shí),發(fā)現(xiàn)已經(jīng)有元素了,則進(jìn)入下一次循環(huán),重新操作 // 如果使用CAS插入元素成功,則break跳出循環(huán),流程結(jié)束 break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) // 如果要插入的元素所在的桶的第一個(gè)元素的hash是MOVED,則當(dāng)前線程幫忙一起遷移元素 tab = helpTransfer(tab, f); else { // 如果這個(gè)桶不為空且不在遷移元素,則鎖住這個(gè)桶(分段鎖) // 并查找要插入的元素是否在這個(gè)桶中 // 存在,則替換值(onlyIfAbsent=false) // 不存在,則插入到鏈表結(jié)尾或插入樹中 V oldVal = null; synchronized (f) { // 再次檢測第一個(gè)元素是否有變化,如果有變化則進(jìn)入下一次循環(huán),從頭來過 if (tabAt(tab, i) == f) { // 如果第一個(gè)元素的hash值大于等于0(說明不是在遷移,也不是樹) // 那就是桶中的元素使用的是鏈表方式存儲 if (fh >= 0) { // 桶中元素個(gè)數(shù)賦值為1 binCount = 1; // 遍歷整個(gè)桶,每次結(jié)束binCount加1 for (Node e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { // 如果找到了這個(gè)元素,則賦值了新值(onlyIfAbsent=false) // 并退出循環(huán) oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node pred = e; if ((e = e.next) == null) { // 如果到鏈表尾部還沒有找到元素 // 就把它插入到鏈表結(jié)尾并退出循環(huán) pred.next = new Node (hash, key, value, null); break; } } } else if (f instanceof TreeBin) { // 如果第一個(gè)元素是樹節(jié)點(diǎn) Node p; // 桶中元素個(gè)數(shù)賦值為2 binCount = 2; // 調(diào)用紅黑樹的插入方法插入元素 // 如果成功插入則返回null // 否則返回尋找到的節(jié)點(diǎn) if ((p = ((TreeBin )f).putTreeVal(hash, key, value)) != null) { // 如果找到了這個(gè)元素,則賦值了新值(onlyIfAbsent=false) // 并退出循環(huán) oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } // 如果binCount不為0,說明成功插入了元素或者尋找到了元素 if (binCount != 0) { // 如果鏈表元素個(gè)數(shù)達(dá)到了8,則嘗試樹化 // 因?yàn)樯厦姘言夭迦氲綐渲袝r(shí),binCount只賦值了2,并沒有計(jì)算整個(gè)樹中元素的個(gè)數(shù) // 所以不會重復(fù)樹化 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); // 如果要插入的元素已經(jīng)存在,則返回舊值 if (oldVal != null) return oldVal; // 退出外層大循環(huán),流程結(jié)束 break; } } } // 成功插入元素,元素個(gè)數(shù)加1(是否要擴(kuò)容在這個(gè)里面) addCount(1L, binCount); // 成功插入元素返回null return null; }
整體流程跟HashMap比較類似,大致是以下幾步:
如果桶數(shù)組未初始化,則初始化;
如果待插入的元素所在的桶為空,則嘗試把此元素直接插入到桶的第一個(gè)位置;
如果正在擴(kuò)容,則當(dāng)前線程一起加入到擴(kuò)容的過程中;
如果待插入的元素所在的桶不為空且不在遷移元素,則鎖住這個(gè)桶(分段鎖);
如果當(dāng)前桶中元素以鏈表方式存儲,則在鏈表中尋找該元素或者插入元素;
如果當(dāng)前桶中元素以紅黑樹方式存儲,則在紅黑樹中尋找該元素或者插入元素;
如果元素存在,則返回舊值;
如果元素不存在,整個(gè)Map的元素個(gè)數(shù)加1,并檢查是否需要擴(kuò)容;
添加元素操作中使用的鎖主要有(自旋鎖 + CAS + synchronized + 分段鎖)。
為什么使用synchronized而不是ReentrantLock?
因?yàn)閟ynchronized已經(jīng)得到了極大地優(yōu)化,在特定情況下并不比ReentrantLock差。
初始化桶數(shù)組第一次放元素時(shí),初始化桶數(shù)組。
private final Node[] initTable() { Node [] tab; int sc; while ((tab = table) == null || tab.length == 0) { if ((sc = sizeCtl) < 0) // 如果sizeCtl<0說明正在初始化或者擴(kuò)容,讓出CPU Thread.yield(); // lost initialization race; just spin else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 如果把sizeCtl原子更新為-1成功,則當(dāng)前線程進(jìn)入初始化 // 如果原子更新失敗則說明有其它線程先一步進(jìn)入初始化了,則進(jìn)入下一次循環(huán) // 如果下一次循環(huán)時(shí)還沒初始化完畢,則sizeCtl<0進(jìn)入上面if的邏輯讓出CPU // 如果下一次循環(huán)更新完畢了,則table.length!=0,退出循環(huán) try { // 再次檢查table是否為空,防止ABA問題 if ((tab = table) == null || tab.length == 0) { // 如果sc為0則使用默認(rèn)值16 int n = (sc > 0) ? sc : DEFAULT_CAPACITY; // 新建數(shù)組 @SuppressWarnings("unchecked") Node [] nt = (Node [])new Node,?>[n]; // 賦值給table桶數(shù)組 table = tab = nt; // 設(shè)置sc為數(shù)組長度的0.75倍 // n - (n >>> 2) = n - n/4 = 0.75n // 可見這里裝載因子和擴(kuò)容門檻都是寫死了的 // 這也正是沒有threshold和loadFactor屬性的原因 sc = n - (n >>> 2); } } finally { // 把sc賦值給sizeCtl,這時(shí)存儲的是擴(kuò)容門檻 sizeCtl = sc; } break; } } return tab; }
使用CAS鎖控制只有一個(gè)線程初始化桶數(shù)組;
sizeCtl在初始化后存儲的是擴(kuò)容門檻;
擴(kuò)容門檻寫死的是桶數(shù)組大小的0.75倍,桶數(shù)組大小即map的容量,也就是最多存儲多少個(gè)元素。
判斷是否需要擴(kuò)容每次添加元素后,元素?cái)?shù)量加1,并判斷是否達(dá)到擴(kuò)容門檻,達(dá)到了則進(jìn)行擴(kuò)容或協(xié)助擴(kuò)容。
private final void addCount(long x, int check) { CounterCell[] as; long b, s; // 這里使用的思想跟LongAdder類是一模一樣的(后面會講) // 把數(shù)組的大小存儲根據(jù)不同的線程存儲到不同的段上(也是分段鎖的思想) // 并且有一個(gè)baseCount,優(yōu)先更新baseCount,如果失敗了再更新不同線程對應(yīng)的段 // 這樣可以保證盡量小的減少沖突 // 先嘗試把數(shù)量加到baseCount上,如果失敗再加到分段的CounterCell上 if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { CounterCell a; long v; int m; boolean uncontended = true; // 如果as為空 // 或者長度為0 // 或者當(dāng)前線程所在的段為null // 或者在當(dāng)前線程的段上加數(shù)量失敗 if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null || !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { // 強(qiáng)制增加數(shù)量(無論如何數(shù)量是一定要加上的,并不是簡單地自旋) // 不同線程對應(yīng)不同的段都更新失敗了 // 說明已經(jīng)發(fā)生沖突了,那么就對counterCells進(jìn)行擴(kuò)容 // 以減少多個(gè)線程hash到同一個(gè)段的概率 fullAddCount(x, uncontended); return; } if (check <= 1) return; // 計(jì)算元素個(gè)數(shù) s = sumCount(); } if (check >= 0) { Node[] tab, nt; int n, sc; // 如果元素個(gè)數(shù)達(dá)到了擴(kuò)容門檻,則進(jìn)行擴(kuò)容 // 注意,正常情況下sizeCtl存儲的是擴(kuò)容門檻,即容量的0.75倍 while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) { // rs是擴(kuò)容時(shí)的一個(gè)郵戳標(biāo)識 int rs = resizeStamp(n); if (sc < 0) { // sc<0說明正在擴(kuò)容中 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) // 擴(kuò)容已經(jīng)完成了,退出循環(huán) // 正常應(yīng)該只會觸發(fā)nextTable==null這個(gè)條件,其它條件沒看出來何時(shí)觸發(fā) break; // 擴(kuò)容未完成,則當(dāng)前線程加入遷移元素中 // 并把擴(kuò)容線程數(shù)加1 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) // 這里是觸發(fā)擴(kuò)容的那個(gè)線程進(jìn)入的地方 // sizeCtl的高16位存儲著rs這個(gè)擴(kuò)容郵戳 // sizeCtl的低16位存儲著擴(kuò)容線程數(shù)加1,即(1+nThreads) // 所以官方說的擴(kuò)容時(shí)sizeCtl的值為 -(1+nThreads)是錯(cuò)誤的 // 進(jìn)入遷移元素 transfer(tab, null); // 重新計(jì)算元素個(gè)數(shù) s = sumCount(); } } }
元素個(gè)數(shù)的存儲方式類似于LongAdder類,存儲在不同的段上,減少不同線程同時(shí)更新size時(shí)的沖突;
計(jì)算元素個(gè)數(shù)時(shí)把這些段的值及baseCount相加算出總的元素個(gè)數(shù);
正常情況下sizeCtl存儲著擴(kuò)容門檻,擴(kuò)容門檻為容量的0.75倍;
擴(kuò)容時(shí)sizeCtl高位存儲擴(kuò)容郵戳(resizeStamp),低位存儲擴(kuò)容線程數(shù)加1(1+nThreads);
其它線程添加元素后如果發(fā)現(xiàn)存在擴(kuò)容,也會加入的擴(kuò)容行列中來;
協(xié)助擴(kuò)容(遷移元素)線程添加元素時(shí)發(fā)現(xiàn)正在擴(kuò)容且當(dāng)前元素所在的桶元素已經(jīng)遷移完成了,則協(xié)助遷移其它桶的元素。
final Node[] helpTransfer(Node [] tab, Node f) { Node [] nextTab; int sc; // 如果桶數(shù)組不為空,并且當(dāng)前桶第一個(gè)元素為ForwardingNode類型,并且nextTab不為空 // 說明當(dāng)前桶已經(jīng)遷移完畢了,才去幫忙遷移其它桶的元素 // 擴(kuò)容時(shí)會把舊桶的第一個(gè)元素置為ForwardingNode,并讓其nextTab指向新桶數(shù)組 if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode )f).nextTable) != null) { int rs = resizeStamp(tab.length); // sizeCtl<0,說明正在擴(kuò)容 while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || transferIndex <= 0) break; // 擴(kuò)容線程數(shù)加1 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { // 當(dāng)前線程幫忙遷移元素 transfer(tab, nextTab); break; } } return nextTab; } return table; }
當(dāng)前桶元素遷移完成了才去協(xié)助遷移其它桶元素;
遷移元素擴(kuò)容時(shí)容量變?yōu)閮杀叮巡糠衷剡w移到其它桶中。
private final void transfer(Node[] tab, Node [] nextTab) { int n = tab.length, stride; if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // subdivide range if (nextTab == null) { // initiating // 如果nextTab為空,說明還沒開始遷移 // 就新建一個(gè)新桶數(shù)組 try { // 新桶數(shù)組是原桶的兩倍 @SuppressWarnings("unchecked") Node [] nt = (Node [])new Node,?>[n << 1]; nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; transferIndex = n; } // 新桶數(shù)組大小 int nextn = nextTab.length; // 新建一個(gè)ForwardingNode類型的節(jié)點(diǎn),并把新桶數(shù)組存儲在里面 ForwardingNode fwd = new ForwardingNode (nextTab); boolean advance = true; boolean finishing = false; // to ensure sweep before committing nextTab for (int i = 0, bound = 0;;) { Node f; int fh; // 整個(gè)while循環(huán)就是在算i的值,過程太復(fù)雜,不用太關(guān)心 // i的值會從n-1依次遞減,感興趣的可以打下斷點(diǎn)就知道了 // 其中n是舊桶數(shù)組的大小,也就是說i從15開始一直減到1這樣去遷移元素 while (advance) { int nextIndex, nextBound; if (--i >= bound || finishing) advance = false; else if ((nextIndex = transferIndex) <= 0) { i = -1; advance = false; } else if (U.compareAndSwapInt (this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { bound = nextBound; i = nextIndex - 1; advance = false; } } if (i < 0 || i >= n || i + n >= nextn) { // 如果一次遍歷完成了 // 也就是整個(gè)map所有桶中的元素都遷移完成了 int sc; if (finishing) { // 如果全部遷移完成了,則替換舊桶數(shù)組 // 并設(shè)置下一次擴(kuò)容門檻為新桶數(shù)組容量的0.75倍 nextTable = null; table = nextTab; sizeCtl = (n << 1) - (n >>> 1); return; } if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { // 當(dāng)前線程擴(kuò)容完成,把擴(kuò)容線程數(shù)-1 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) // 擴(kuò)容完成兩邊肯定相等 return; // 把finishing設(shè)置為true // finishing為true才會走到上面的if條件 finishing = advance = true; // i重新賦值為n // 這樣會再重新遍歷一次桶數(shù)組,看看是不是都遷移完成了 // 也就是第二次遍歷都會走到下面的(fh = f.hash) == MOVED這個(gè)條件 i = n; // recheck before commit } } else if ((f = tabAt(tab, i)) == null) // 如果桶中無數(shù)據(jù),直接放入ForwardingNode標(biāo)記該桶已遷移 advance = casTabAt(tab, i, null, fwd); else if ((fh = f.hash) == MOVED) // 如果桶中第一個(gè)元素的hash值為MOVED // 說明它是ForwardingNode節(jié)點(diǎn) // 也就是該桶已遷移 advance = true; // already processed else { // 鎖定該桶并遷移元素 synchronized (f) { // 再次判斷當(dāng)前桶第一個(gè)元素是否有修改 // 也就是可能其它線程先一步遷移了元素 if (tabAt(tab, i) == f) { // 把一個(gè)鏈表分化成兩個(gè)鏈表 // 規(guī)則是桶中各元素的hash與桶大小n進(jìn)行與操作 // 等于0的放到低位鏈表(low)中,不等于0的放到高位鏈表(high)中 // 其中低位鏈表遷移到新桶中的位置相對舊桶不變 // 高位鏈表遷移到新桶中位置正好是其在舊桶的位置加n // 這也正是為什么擴(kuò)容時(shí)容量在變成兩倍的原因 Node ln, hn; if (fh >= 0) { // 第一個(gè)元素的hash值大于等于0 // 說明該桶中元素是以鏈表形式存儲的 // 這里與HashMap遷移算法基本類似 // 唯一不同的是多了一步尋找lastRun // 這里的lastRun是提取出鏈表后面不用處理再特殊處理的子鏈表 // 比如所有元素的hash值與桶大小n與操作后的值分別為 0 0 4 4 0 0 0 // 則最后后面三個(gè)0對應(yīng)的元素肯定還是在同一個(gè)桶中 // 這時(shí)lastRun對應(yīng)的就是倒數(shù)第三個(gè)節(jié)點(diǎn) // 至于為啥要這樣處理,我也沒太搞明白 int runBit = fh & n; Node lastRun = f; for (Node p = f.next; p != null; p = p.next) { int b = p.hash & n; if (b != runBit) { runBit = b; lastRun = p; } } // 看看最后這幾個(gè)元素歸屬于低位鏈表還是高位鏈表 if (runBit == 0) { ln = lastRun; hn = null; } else { hn = lastRun; ln = null; } // 遍歷鏈表,把hash&n為0的放在低位鏈表中 // 不為0的放在高位鏈表中 for (Node p = f; p != lastRun; p = p.next) { int ph = p.hash; K pk = p.key; V pv = p.val; if ((ph & n) == 0) ln = new Node (ph, pk, pv, ln); else hn = new Node (ph, pk, pv, hn); } // 低位鏈表的位置不變 setTabAt(nextTab, i, ln); // 高位鏈表的位置是原位置加n setTabAt(nextTab, i + n, hn); // 標(biāo)記當(dāng)前桶已遷移 setTabAt(tab, i, fwd); // advance為true,返回上面進(jìn)行--i操作 advance = true; } else if (f instanceof TreeBin) { // 如果第一個(gè)元素是樹節(jié)點(diǎn) // 也是一樣,分化成兩顆樹 // 也是根據(jù)hash&n為0放在低位樹中 // 不為0放在高位樹中 TreeBin t = (TreeBin )f; TreeNode lo = null, loTail = null; TreeNode hi = null, hiTail = null; int lc = 0, hc = 0; // 遍歷整顆樹,根據(jù)hash&n是否為0分化成兩顆樹 for (Node e = t.first; e != null; e = e.next) { int h = e.hash; TreeNode p = new TreeNode (h, e.key, e.val, null, null); if ((h & n) == 0) { if ((p.prev = loTail) == null) lo = p; else loTail.next = p; loTail = p; ++lc; } else { if ((p.prev = hiTail) == null) hi = p; else hiTail.next = p; hiTail = p; ++hc; } } // 如果分化的樹中元素個(gè)數(shù)小于等于6,則退化成鏈表 ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin (lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin (hi) : t; // 低位樹的位置不變 setTabAt(nextTab, i, ln); // 高位樹的位置是原位置加n setTabAt(nextTab, i + n, hn); // 標(biāo)記該桶已遷移 setTabAt(tab, i, fwd); // advance為true,返回上面進(jìn)行--i操作 advance = true; } } } } } }
新桶數(shù)組大小是舊桶數(shù)組的兩倍;
遷移元素先從靠后的桶開始;
遷移完成的桶在里面放置一ForwardingNode類型的元素,標(biāo)記該桶遷移完成;
遷移時(shí)根據(jù)hash&n是否等于0把桶中元素分化成兩個(gè)鏈表或樹;
低位鏈表(樹)存儲在原來的位置;
高們鏈表(樹)存儲在原來的位置加n的位置;
遷移元素時(shí)會鎖住當(dāng)前桶,也是分段鎖的思想;
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/76242.html
摘要:那么,如果之后不是簡單的操作,而是還有其它業(yè)務(wù)操作,之后才是,比如下面這樣,這該怎么辦呢其它業(yè)務(wù)操作這時(shí)候就沒辦法使用提供的方法了,只能業(yè)務(wù)自己來保證線程安全了,比如下面這樣其它業(yè)務(wù)操作這樣雖然不太友好,但是最起碼能保證業(yè)務(wù)邏輯是正確的。 刪除元素 刪除元素跟添加元素一樣,都是先找到元素所在的桶,然后采用分段鎖的思想鎖住整個(gè)桶,再進(jìn)行操作。 public V remove(Objec...
摘要:是棧,它繼承于。滿二叉樹除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹。沒有鍵值相等的節(jié)點(diǎn)。這是數(shù)據(jù)庫選用樹的最主要原因。 在我們學(xué)習(xí)Java的時(shí)候,很多人會面臨我不知道繼續(xù)學(xué)什么或者面試會問什么的尷尬情況(我本人之前就很迷茫)。所以,我決定通過這個(gè)開源平臺來幫助一些有需要的人,通過下面的內(nèi)容,你會掌握系統(tǒng)的Java學(xué)習(xí)以及面試的相關(guān)知識。本來是想通過Gitbook的...
摘要:基礎(chǔ)問題的的性能及原理之區(qū)別詳解備忘筆記深入理解流水線抽象關(guān)鍵字修飾符知識點(diǎn)總結(jié)必看篇中的關(guān)鍵字解析回調(diào)機(jī)制解讀抽象類與三大特征時(shí)間和時(shí)間戳的相互轉(zhuǎn)換為什么要使用內(nèi)部類對象鎖和類鎖的區(qū)別,,優(yōu)缺點(diǎn)及比較提高篇八詳解內(nèi)部類單例模式和 Java基礎(chǔ)問題 String的+的性能及原理 java之yield(),sleep(),wait()區(qū)別詳解-備忘筆記 深入理解Java Stream流水...
摘要:基礎(chǔ)問題的的性能及原理之區(qū)別詳解備忘筆記深入理解流水線抽象關(guān)鍵字修飾符知識點(diǎn)總結(jié)必看篇中的關(guān)鍵字解析回調(diào)機(jī)制解讀抽象類與三大特征時(shí)間和時(shí)間戳的相互轉(zhuǎn)換為什么要使用內(nèi)部類對象鎖和類鎖的區(qū)別,,優(yōu)缺點(diǎn)及比較提高篇八詳解內(nèi)部類單例模式和 Java基礎(chǔ)問題 String的+的性能及原理 java之yield(),sleep(),wait()區(qū)別詳解-備忘筆記 深入理解Java Stream流水...
閱讀 2941·2023-04-26 01:52
閱讀 3468·2021-09-04 16:40
閱讀 3629·2021-08-31 09:41
閱讀 1764·2021-08-09 13:41
閱讀 556·2019-08-30 15:54
閱讀 2960·2019-08-30 11:22
閱讀 1612·2019-08-30 10:52
閱讀 948·2019-08-29 13:24