當(dāng)前位置：首頁 > news >正文

托管型網(wǎng)站專業(yè)網(wǎng)絡(luò)推廣公司排名

news 2025/7/7 12:02:51

托管型網(wǎng)站,專業(yè)網(wǎng)絡(luò)推廣公司排名,招商網(wǎng)站建設(shè)需要什么,免費(fèi)申請?jiān)囉镁W(wǎng)站ConcurrentSkipListMap的源碼很復(fù)雜，但它的核心思想和實(shí)現(xiàn)方式非常值得深入學(xué)習(xí)。下面會提煉出它的關(guān)鍵結(jié)構(gòu)，并重點(diǎn)解釋最復(fù)雜、最值得學(xué)習(xí)的方法，以及它在并發(fā)和跳表結(jié)合上的獨(dú)特用法。 1. 關(guān)鍵結(jié)構(gòu) 跳表（Skip List）…

ConcurrentSkipListMap的源碼很復(fù)雜，但它的核心思想和實(shí)現(xiàn)方式非常值得深入學(xué)習(xí)。下面會提煉出它的關(guān)鍵結(jié)構(gòu)，并重點(diǎn)解釋最復(fù)雜、最值得學(xué)習(xí)的方法，以及它在并發(fā)和跳表結(jié)合上的獨(dú)特用法。

1. 關(guān)鍵結(jié)構(gòu)

跳表（Skip List）基本結(jié)構(gòu)

Node<K,V>：跳表的基礎(chǔ)節(jié)點(diǎn)，存儲key、value和指向下一個節(jié)點(diǎn)的指針（next）。
Index<K,V>：跳表多級索引節(jié)點(diǎn)，存儲指向下方索引（down）和右側(cè)索引（right）的指針，每個Index節(jié)點(diǎn)關(guān)聯(lián)一個Node節(jié)點(diǎn)。
head：頂層索引節(jié)點(diǎn)（Index類型），通過down可以訪問到底層。

static final class Node<K,V> {final K key;V val;Node<K,V> next;...
}
static final class Index<K,V> {final Node<K,V> node;final Index<K,V> down;Index<K,V> right;...
}

其他核心成員

comparator：可選的比較器，決定排序規(guī)則。
LongAdder adder：高效計(jì)數(shù)器，記錄元素數(shù)量。
VarHandle機(jī)制：用來做原子操作，支持無鎖CAS（Compare and Swap）修改指針和數(shù)據(jù)。

2. 并發(fā)跳表的獨(dú)特實(shí)現(xiàn)

跳表的多層索引

跳表結(jié)構(gòu)使得查找、插入、刪除的平均復(fù)雜度為O(log n)，而且天然適合并發(fā)遍歷。
索引節(jié)點(diǎn)(Index)和底層節(jié)點(diǎn)(Node)分離，每次變更都只需CAS原子操作，避免全局鎖。

無鎖設(shè)計(jì)（Lock-Free）

主要依賴CAS原子操作（比如 NEXT.compareAndSet、VAL.compareAndSet），避免傳統(tǒng)鎖帶來的性能瓶頸。
節(jié)點(diǎn)刪除采用“懶惰刪除”+“幫助刪除”，即遇到被標(biāo)記為刪除的節(jié)點(diǎn)時，順便幫忙物理移除，所有線程協(xié)作完成清理。

doPut（插入/更新元素）

這是插入和更新的核心方法，難點(diǎn)在于：

多線程場景下，如何安全地插入節(jié)點(diǎn)和建立索引；
如何在概率意義下決定新節(jié)點(diǎn)的高度（索引層數(shù)）；
如何處理并發(fā)插入沖突和失敗的重試。

簡化流程：

找到插入位置的前驅(qū)節(jié)點(diǎn)（findPredecessor）。
通過CAS原子操作插入新節(jié)點(diǎn)；
按概率（1/4）決定是否生成索引節(jié)點(diǎn)，并逐層向上插入索引（addIndices）；
若有必要，增加跳表高度。

doPut?方法是?ConcurrentSkipListMap?的核心插入方法，實(shí)現(xiàn)了線程安全的鍵值對插入操作。以下是該方法的詳細(xì)分析：

1. 方法簽名與參數(shù)說明

private V doPut(K key, V value, boolean onlyIfAbsent)

key: 要插入的鍵
value: 要插入的值
onlyIfAbsent: 如果為?true，僅在鍵不存在時插入；如果為?false，則替換已存在的值
返回值: 如果是新插入返回?null，如果是替換則返回舊值

整體執(zhí)行流程

第一階段：初始化檢查與跳表遍歷

if (key == null)throw new NullPointerException();
Comparator<? super K> cmp = comparator;
for (;;) {  // 無限循環(huán)，直到操作成功Index<K,V> h; Node<K,V> b;VarHandle.acquireFence(); // 內(nèi)存屏障，確?？梢娦?

關(guān)鍵知識點(diǎn)：

使用?無限循環(huán)?實(shí)現(xiàn)?樂觀鎖?機(jī)制
VarHandle.acquireFence()?提供?內(nèi)存可見性保證，類似于 volatile 讀操作

第二階段：跳表初始化

if ((h = head) == null) {          // 跳表未初始化Node<K,V> base = new Node<K,V>(null, null, null);  // 創(chuàng)建哨兵節(jié)點(diǎn)h = new Index<K,V>(base, null, null);               // 創(chuàng)建頂層索引b = (HEAD.compareAndSet(this, null, h)) ? base : null; // CAS 操作
}

設(shè)計(jì)要點(diǎn)：

使用?哨兵節(jié)點(diǎn)?簡化邊界處理
通過?CAS 操作?保證線程安全的初始化
如果 CAS 失敗，說明其他線程已完成初始化，重新開始循環(huán)

第三階段：跳表索引層遍歷

for (Index<K,V> q = h, r, d;;) { // 從頂層開始遍歷while ((r = q.right) != null) {  // 水平向右遍歷Node<K,V> p; K k;if ((p = r.node) == null || (k = p.key) == null || p.val == null)RIGHT.compareAndSet(q, r, r.right); // 清理已刪除節(jié)點(diǎn)else if (cpr(cmp, key, k) > 0)q = r; // 繼續(xù)向右elsebreak; // 找到插入位置}if ((d = q.down) != null) {++levels; // 記錄下降層數(shù)q = d;    // 向下一層}else {b = q.node; // 找到基礎(chǔ)層的前驅(qū)節(jié)點(diǎn)break;}
}

跳表遍歷原理：

水平遍歷：在當(dāng)前層級向右查找，直到找到大于等于目標(biāo)鍵的位置
垂直下降：當(dāng)無法繼續(xù)右移時，下降到下一層級
清理機(jī)制：遍歷過程中清理已標(biāo)記刪除的節(jié)點(diǎn)，維護(hù)數(shù)據(jù)結(jié)構(gòu)完整性

基礎(chǔ)層節(jié)點(diǎn)插入

尋找精確插入位置

for (;;) {  // 在基礎(chǔ)層尋找插入點(diǎn)Node<K,V> n, p; K k; V v; int c;if ((n = b.next) == null) {if (b.key == null)  // 空跳表，進(jìn)行類型檢查cpr(cmp, key, key);c = -1;}else if ((k = n.key) == null)break;  // 遇到標(biāo)記節(jié)點(diǎn)，重新開始else if ((v = n.val) == null) {unlinkNode(b, n);  // 清理已刪除節(jié)點(diǎn)c = 1;}else if ((c = cpr(cmp, key, k)) > 0)b = n;  // 繼續(xù)向右查找else if (c == 0 && (onlyIfAbsent || VAL.compareAndSet(n, v, value)))return v;  // 找到相同鍵，根據(jù) onlyIfAbsent 決定是否更新

執(zhí)行 CAS 插入

if (c < 0 && NEXT.compareAndSet(b, n, p = new Node<K,V>(key, value, n))) {z = p;  // 記錄新插入的節(jié)點(diǎn)break;
}

CAS 插入機(jī)制：

原子性地將新節(jié)點(diǎn)插入到?b?和?n?之間
如果 CAS 失敗，說明其他線程修改了鏈表結(jié)構(gòu)，需要重新查找

來詳細(xì)解釋這段看似復(fù)雜的 null 處理邏輯。這些設(shè)計(jì)都與?ConcurrentSkipListMap 的并發(fā)刪除機(jī)制?密切相關(guān)。

1. 類型檢查邏輯分析

if (b.key == null)       // if empty, type check key nowcpr(cmp, key, key);

為什么需要這個檢查？

這個看似奇怪的?cpr(cmp, key, key)?調(diào)用實(shí)際上是一個?提前類型檢查：

觸發(fā)時機(jī)：當(dāng)跳表為空時（b.key == null?表示?b?是哨兵節(jié)點(diǎn)）
目的：提前驗(yàn)證?key?的類型是否與比較器兼容
機(jī)制：通過自比較觸發(fā)潛在的?ClassCastException

// cpr 方法的實(shí)現(xiàn)邏輯
static int cpr(Comparator c, Object x, Object y) {return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);
}

如果?key?類型不兼容，這里會立即拋出異常，避免在后續(xù)操作中出現(xiàn)問題。

2. 并發(fā)刪除機(jī)制的核心區(qū)別

key == null?vs?val == null?的本質(zhì)區(qū)別

在 ConcurrentSkipListMap 中，這兩種 null 狀態(tài)代表?刪除過程的不同階段：

狀態(tài)	含義	處理方式	原因
`key == null`	標(biāo)記節(jié)點(diǎn)，表示前一個節(jié)點(diǎn)正在被刪除	`break`?重新開始	結(jié)構(gòu)不穩(wěn)定，無法安全插入
`val == null`	邏輯刪除，節(jié)點(diǎn)已被標(biāo)記刪除但仍在鏈表中	`unlinkNode()`?物理刪除	可以安全地完成物理刪除

3. 并發(fā)刪除的三階段過程

根據(jù)代碼注釋，ConcurrentSkipListMap 采用三階段刪除：

階段 1：邏輯刪除

// 將節(jié)點(diǎn)值設(shè)為 null，標(biāo)記為已刪除
VAL.compareAndSet(n, v, null)

階段 2：插入標(biāo)記節(jié)點(diǎn)

// 插入一個 key=null 的標(biāo)記節(jié)點(diǎn)
NEXT.compareAndSet(n, f, new Node<K,V>(null, null, f))

階段 3：物理刪除

// 將前驅(qū)節(jié)點(diǎn)直接指向后繼節(jié)點(diǎn)
NEXT.compareAndSet(b, n, p)

代碼邏輯的并發(fā)安全考慮

else if ((k = n.key) == null)break;                   // can't append; restart
else if ((v = n.val) == null) {unlinkNode(b, n);c = 1;
}

為什么?key == null?需要重啟？

結(jié)構(gòu)不穩(wěn)定：遇到標(biāo)記節(jié)點(diǎn)說明正在進(jìn)行刪除操作
無法預(yù)測：不知道刪除何時完成，鏈表結(jié)構(gòu)可能隨時改變
安全策略：重新開始遍歷，等待刪除操作完成

為什么?val == null?可以繼續(xù)？

狀態(tài)確定：節(jié)點(diǎn)已被邏輯刪除，不會再被修改
助人為樂：當(dāng)前線程可以幫助完成物理刪除
性能優(yōu)化：避免其他線程重復(fù)遇到已刪除節(jié)點(diǎn)

實(shí)際執(zhí)行流程示例

假設(shè)有鏈表：A -> B -> C，要刪除節(jié)點(diǎn) B：

// 初始狀態(tài)
A.next -> B(key=b, val=v) -> C// 步驟1：邏輯刪除 B
A.next -> B(key=b, val=null) -> C
// 此時遇到 val==null，執(zhí)行 unlinkNode// 步驟2：插入標(biāo)記節(jié)點(diǎn)
A.next -> B(key=b, val=null) -> marker(key=null, val=null) -> C
// 此時遇到 key==null，執(zhí)行 break 重啟// 步驟3：物理刪除完成
A.next -> C

這種設(shè)計(jì)的巧妙在于：

漸進(jìn)式刪除：避免一次性操作導(dǎo)致的競爭
協(xié)作式清理：多個線程共同維護(hù)數(shù)據(jù)結(jié)構(gòu)完整性
無鎖設(shè)計(jì)：通過 CAS 操作保證原子性
異常安全：提前進(jìn)行類型檢查，避免后續(xù)錯誤

這就是為什么同樣是 null，但處理方式完全不同的根本原因——它們代表了并發(fā)刪除過程中的不同狀態(tài)，需要采用不同的應(yīng)對策略來保證線程安全。

索引層構(gòu)建（概率性）

隨機(jī)決定是否添加索引

int lr = ThreadLocalRandom.nextSecondarySeed();
if ((lr & 0x3) == 0) {  // 1/4 概率添加索引int hr = ThreadLocalRandom.nextSecondarySeed();long rnd = ((long)hr << 32) | ((long)lr & 0xffffffffL);int skips = levels;  // 從當(dāng)前層級開始構(gòu)建索引

構(gòu)建索引鏈

Index<K,V> x = null;
for (;;) {  // 構(gòu)建垂直索引鏈x = new Index<K,V>(z, x, null);  // 創(chuàng)建新索引節(jié)點(diǎn)if (rnd >= 0L || --skips < 0)break;elsernd <<= 1;  // 左移判斷下一層
}

跳表索引構(gòu)建原理：

概率性構(gòu)建：每層索引節(jié)點(diǎn)數(shù)量約為下層的 1/2
幾何分布：通過位運(yùn)算實(shí)現(xiàn)高效的概率計(jì)算
最大層數(shù)限制：最多構(gòu)建 62 層索引

添加索引到跳表

if (addIndices(h, skips, x, cmp) && skips < 0 && head == h) {// 需要增加新的頂層Index<K,V> hx = new Index<K,V>(z, x, null);Index<K,V> nh = new Index<K,V>(h.node, h, hx);HEAD.compareAndSet(this, h, nh);
}

關(guān)鍵技術(shù)特性

并發(fā)安全機(jī)制

Lock-Free 設(shè)計(jì)：全程無鎖，使用 CAS 操作保證原子性
內(nèi)存屏障：使用?VarHandle.acquireFence()?確保內(nèi)存可見性
重試機(jī)制：失敗時重新開始，保證最終一致性

性能優(yōu)化策略

惰性刪除：標(biāo)記刪除而非立即物理刪除
清理機(jī)制：遍歷過程中順便清理已刪除節(jié)點(diǎn)
概率性索引：平衡查找效率和空間開銷

數(shù)據(jù)結(jié)構(gòu)維護(hù)

動態(tài)層級調(diào)整：根據(jù)需要增加新的索引層
索引一致性：確保索引層與基礎(chǔ)層數(shù)據(jù)一致
并發(fā)清理：在操作過程中維護(hù)結(jié)構(gòu)完整性

為什么需要標(biāo)記節(jié)點(diǎn)？并發(fā)鏈表刪除的根本問題

詳細(xì)解釋為什么ConcurrentSkipListMap不能"直接CAS刪除"，而必須使用標(biāo)記節(jié)點(diǎn)的分步刪除策略。

如果我們嘗試"直接刪除"：

// 危險的直接刪除方式
NEXT.compareAndSet(A, B, C);  // 直接讓A指向C

這會導(dǎo)致嚴(yán)重的并發(fā)競態(tài)條件：

// 初始狀態(tài)
A -> B -> C -> D// 線程T1想刪除B，讀取了B.next = C
// 線程T2在B和C之間插入了新節(jié)點(diǎn)X
A -> B -> X -> C -> D// T1執(zhí)行CAS：A.next從B改為C
A -> C -> D  // X節(jié)點(diǎn)永遠(yuǎn)丟失！

unlinkNode的三步刪除策略

查看unlinkNode的實(shí)現(xiàn)：

static <K,V> void unlinkNode(Node<K,V> b, Node<K,V> n) {if (b != null && n != null) {Node<K,V> f, p;for (;;) {if ((f = n.next) != null && f.key == null) {p = f.next;               // 步驟1：發(fā)現(xiàn)已有標(biāo)記節(jié)點(diǎn)break;}else if (NEXT.compareAndSet(n, f,new Node<K,V>(null, null, f))) {p = f;                    // 步驟2：插入標(biāo)記節(jié)點(diǎn)break;}}NEXT.compareAndSet(b, n, p);      // 步驟3：繞過被刪節(jié)點(diǎn)}
}

為什么分步刪除是必需的？

無鎖并發(fā)的本質(zhì)需求

原子性保證：每個CAS操作都是原子的，但組合操作不是
順序依賴：必須先"鎖定"被刪節(jié)點(diǎn)的next指針，再修改前驅(qū)節(jié)點(diǎn)
狀態(tài)可見性：中間狀態(tài)必須對所有線程可見和可處理

對比有鎖方案

// 如果用鎖（但ConcurrentSkipListMap是無鎖的）
synchronized(lock) {A.next = B.next;  // 可以原子完成
}

但無鎖環(huán)境下，我們只能依賴CAS的原子性，因此必須分解為原子步驟。

實(shí)際運(yùn)行示例

// 時刻T1：初始狀態(tài)
A.next -> B(key=5, val="hello") -> C(key=10)// 時刻T2：線程1開始刪除B，執(zhí)行邏輯刪除
A.next -> B(key=5, val=null) -> C(key=10)// 時刻T3：線程2試圖在B后插入節(jié)點(diǎn)失敗
// 因?yàn)榘l(fā)現(xiàn)B.val==null，執(zhí)行unlinkNode幫助刪除// 時刻T4：插入標(biāo)記節(jié)點(diǎn)
A.next -> B(key=5, val=null) -> marker(key=null, val=null) -> C(key=10)// 時刻T5：物理刪除完成
A.next -> C(key=10)

findPredecessor（查找前驅(qū)節(jié)點(diǎn)）

負(fù)責(zé)自頂向下查找，過程中順便幫忙清理已刪除節(jié)點(diǎn)的索引，保證跳表結(jié)構(gòu)整潔。
支持并發(fā)刪除時的“協(xié)作清理”。

核心邏輯：

    private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {Index<K,V> q;VarHandle.acquireFence();if ((q = head) == null || key == null)return null;else {for (Index<K,V> r, d;;) {while ((r = q.right) != null) {Node<K,V> p; K k;if ((p = r.node) == null || (k = p.key) == null ||p.val == null)  // unlink index to deleted nodeRIGHT.compareAndSet(q, r, r.right);else if (cpr(cmp, key, k) > 0)q = r;elsebreak;}if ((d = q.down) != null)q = d;elsereturn q.node;}}}

VarHandle.acquireFence() 的作用

VarHandle.acquireFence()?在此處的作用是：

保證可見性：確保讀取到其他線程對?head?字段的最新修改
防止重排序：確保后續(xù)的讀操作基于一致的內(nèi)存狀態(tài)
性能優(yōu)化：避免使用過多 volatile 字段的開銷
維護(hù)弱一致性：為無鎖數(shù)據(jù)結(jié)構(gòu)提供必要的內(nèi)存語義保證

這是 ConcurrentSkipListMap 實(shí)現(xiàn)高性能并發(fā)訪問的關(guān)鍵技術(shù)之一。

acquireFence()確保在屏障之后的所有讀操作不會被重排序到屏障之前，主要用于確保讀取操作能看到最新的寫入值，是構(gòu)建更高級并發(fā)原語的基礎(chǔ)工具。
releaseFence(): 確保屏障之前的所有寫操作對其他線程可見（類似于 StoreStore + LoadStore）
fullFence(): 同時提供獲取和釋放語義（類似于 volatile 變量的讀寫）

內(nèi)存屏障的核心作用

1. 確保?head?字段的最新值可見

VarHandle.acquireFence();
if ((q = head) == null || key == null)return null;

關(guān)鍵問題：head?字段可能被其他線程修改（如在?doPut、tryReduceLevel?等方法中），需要確保當(dāng)前線程能看到最新的值。

解決方案：acquireFence()?提供了類似?volatile 讀?的語義，確保：

讀取到?head?的最新值
防止編譯器和處理器的指令重排序

2. 建立 happens-before 關(guān)系

根據(jù)代碼注釋中的設(shè)計(jì)說明：

This form of fence-hoisting is similar to RCU and related techniques... It minimizes overhead that may otherwise occur when using so many volatile-mode reads.

設(shè)計(jì)思路：

避免將每個字段都聲明為?volatile
通過在關(guān)鍵方法入口處放置內(nèi)存屏障，建立全局的內(nèi)存可見性保證

為什么選擇 acquireFence 而非其他屏障

acquireFence 的特性

// acquireFence 等價于：
// 確保屏障之前的讀操作不會被重排序到屏障之后
// 提供 "acquire" 語義，類似于 volatile 讀或 synchronized 進(jìn)入

與 ConcurrentSkipListMap 的無鎖設(shè)計(jì)契合

無鎖遍歷：findPredecessor?是純讀操作，不需要修改數(shù)據(jù)
弱一致性：允許看到稍微過時的數(shù)據(jù)，但必須是一致的快照
性能優(yōu)化：比使用多個 volatile 字段開銷更小

場景分析

場景 1：讀取跳表頭節(jié)點(diǎn)

// 其他線程可能正在執(zhí)行：
HEAD.compareAndSet(this, h, nh);  // 在 doPut 中更新頭節(jié)點(diǎn)// 當(dāng)前線程需要確?？吹阶钚碌?head 值
VarHandle.acquireFence();
if ((q = head) == null || key == null)  // 必須是最新值

場景 2：確保索引結(jié)構(gòu)一致性

// 確保讀取的索引鏈?zhǔn)且恢碌臓顟B(tài)
while ((r = q.right) != null) {Node<K,V> p; K k;// 這些字段的讀取都受到屏障保護(hù)if ((p = r.node) == null || (k = p.key) == null || p.val == null)

對比其他方法中的類似用法

可以看到相同的模式：

doGet?方法：

VarHandle.acquireFence();
if (key == null)throw new NullPointerException();

findLast?方法：

VarHandle.acquireFence();
if ((q = head) == null)break;

doRemove（刪除元素）

先邏輯刪除（將val設(shè)為null），再插入一個“marker”節(jié)點(diǎn)做物理刪除，最后CAS更新前驅(qū)的next指針。
刪除后會考慮是否需要降低跳表高度（tryReduceLevel）。

    /*** Main deletion method. Locates node, nulls value, appends a* deletion marker, unlinks predecessor, removes associated index* nodes, and possibly reduces head index level.** @param key the key* @param value if non-null, the value that must be* associated with key* @return the node, or null if not found*/final V doRemove(Object key, Object value) {if (key == null)throw new NullPointerException();Comparator<? super K> cmp = comparator;V result = null;Node<K,V> b;outer: while ((b = findPredecessor(key, cmp)) != null &&result == null) {for (;;) {Node<K,V> n; K k; V v; int c;if ((n = b.next) == null)break outer;else if ((k = n.key) == null)break;else if ((v = n.val) == null)unlinkNode(b, n);else if ((c = cpr(cmp, key, k)) > 0)b = n;else if (c < 0)break outer;else if (value != null && !value.equals(v))break outer;else if (VAL.compareAndSet(n, v, null)) {result = v;unlinkNode(b, n);break; // loop to clean up}}}if (result != null) {tryReduceLevel();addCount(-1L);}return result;}

doRemove?方法是 ConcurrentSkipListMap 中的核心刪除實(shí)現(xiàn)，它完美體現(xiàn)了之前提到的三階段刪除策略。

這個方法實(shí)現(xiàn)了無鎖并發(fā)刪除，支持兩種刪除模式：

精確刪除：value != null?時，只有當(dāng)節(jié)點(diǎn)值完全匹配時才刪除
鍵刪除：value == null?時，刪除指定鍵的節(jié)點(diǎn)（不關(guān)心值）

核心執(zhí)行流程

外層循環(huán)：定位目標(biāo)節(jié)點(diǎn)

outer: while ((b = findPredecessor(key, cmp)) != null && result == null) {

關(guān)鍵設(shè)計(jì)：

使用?findPredecessor?找到目標(biāo)鍵的前驅(qū)節(jié)點(diǎn)
外層循環(huán)處理并發(fā)沖突重試
result == null?確保刪除成功后不再重試

內(nèi)層循環(huán)：執(zhí)行刪除操作

內(nèi)層循環(huán)處理多種并發(fā)場景，每個分支對應(yīng)不同的節(jié)點(diǎn)狀態(tài)：

場景1：鏈表結(jié)束

if ((n = b.next) == null)break outer;

前驅(qū)節(jié)點(diǎn)后沒有節(jié)點(diǎn)，目標(biāo)不存在

場景2：遇到標(biāo)記節(jié)點(diǎn)

else if ((k = n.key) == null)  break;

遇到?key == null?的標(biāo)記節(jié)點(diǎn)
表示鏈表結(jié)構(gòu)正在變化，需要重新開始

場景3：遇到已刪除節(jié)點(diǎn)

else if ((v = n.val) == null)unlinkNode(b, n);

遇到?val == null?的邏輯刪除節(jié)點(diǎn)
助人為樂：幫助完成物理刪除

場景4：繼續(xù)搜索

else if ((c = cpr(cmp, key, k)) > 0)b = n;

目標(biāo)鍵更大，向后移動搜索

場景5：目標(biāo)不存在

else if (c < 0)break outer;

目標(biāo)鍵更小，說明不存在該鍵

場景6：值不匹配（精確刪除）

else if (value != null && !value.equals(v))break outer;

鍵匹配但值不匹配，刪除失敗

場景7：執(zhí)行刪除（核心邏輯）

else if (VAL.compareAndSet(n, v, null)) {result = v;unlinkNode(b, n);break;
}

三階段刪除的具體實(shí)現(xiàn)

階段1：邏輯刪除

VAL.compareAndSet(n, v, null)

原子操作：將節(jié)點(diǎn)值設(shè)為 null
標(biāo)記刪除：其他線程看到?val == null?知道節(jié)點(diǎn)已刪除
CAS失敗重試：如果失敗說明有并發(fā)修改，繼續(xù)循環(huán)

階段2+3：物理刪除

unlinkNode(b, n);

調(diào)用?unlinkNode?完成后續(xù)的標(biāo)記節(jié)點(diǎn)插入和鏈表斷開。

刪除后的清理工作

if (result != null) {tryReduceLevel();     // 嘗試減少跳表層級addCount(-1L);        // 更新元素計(jì)數(shù)
}

雖然?doRemove?沒有直接清理索引，但通過以下機(jī)制保證索引一致性：

遍歷時清理：其他方法（如?findPredecessor、doGet）遍歷時會清理指向已刪除節(jié)點(diǎn)的索引
層級縮減：tryReduceLevel()?在頂層索引為空時減少跳表高度

`unlinkNode`?方法詳解

unlinkNode?方法是 ConcurrentSkipListMap 實(shí)現(xiàn)中用于物理刪除節(jié)點(diǎn)的關(guān)鍵方法。

unlinkNode?方法的主要任務(wù)是將已邏輯刪除的節(jié)點(diǎn)（val == null）從鏈表中完全移除。它通過以下步驟實(shí)現(xiàn)：

插入標(biāo)記節(jié)點(diǎn)：在刪除節(jié)點(diǎn)的?next?指針上插入一個標(biāo)記節(jié)點(diǎn)，防止其他線程向該節(jié)點(diǎn)追加新節(jié)點(diǎn)。
斷開前驅(qū)節(jié)點(diǎn)：將前驅(qū)節(jié)點(diǎn)的?next?指針直接指向刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)，完成物理刪除。

    /*** Tries to unlink deleted node n from predecessor b (if both* exist), by first splicing in a marker if not already present.* Upon return, node n is sure to be unlinked from b, possibly* via the actions of some other thread.** @param b if nonnull, predecessor* @param n if nonnull, node known to be deleted*/static <K,V> void unlinkNode(Node<K,V> b, Node<K,V> n) {if (b != null && n != null) {Node<K,V> f, p;for (;;) {if ((f = n.next) != null && f.key == null) {p = f.next;               // already markedbreak;}else if (NEXT.compareAndSet(n, f,new Node<K,V>(null, null, f))) {p = f;                    // add markerbreak;}}NEXT.compareAndSet(b, n, p);}}

核心執(zhí)行流程

1. 檢查參數(shù)

if (b != null && n != null) {

確保?b（前驅(qū)節(jié)點(diǎn)）和?n（要刪除的節(jié)點(diǎn)）不為空。

2. 插入標(biāo)記節(jié)點(diǎn)

Node<K,V> f, p;
for (;;) {if ((f = n.next) != null && f.key == null) {p = f.next;               // already markedbreak;}else if (NEXT.compareAndSet(n, f, new Node<K,V>(null, null, f))) {p = f;                    // add markerbreak;}
}

檢查是否已標(biāo)記：如果刪除節(jié)點(diǎn)的?next?指針指向的節(jié)點(diǎn)?key?為?null，說明已經(jīng)有一個標(biāo)記節(jié)點(diǎn)存在。
插入新標(biāo)記節(jié)點(diǎn)：如果?next?指針沒有標(biāo)記節(jié)點(diǎn)，則使用?NEXT.compareAndSet?原子操作插入一個新的標(biāo)記節(jié)點(diǎn)。

3. 斷開前驅(qū)節(jié)點(diǎn)

NEXT.compareAndSet(b, n, p);

將前驅(qū)節(jié)點(diǎn)?b?的?next?指針指向刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)?p，完成物理刪除。

總結(jié)

結(jié)合并發(fā)與跳表的獨(dú)特之處

極致的無鎖化設(shè)計(jì)：所有節(jié)點(diǎn)和索引的增刪都用CAS而非鎖，實(shí)現(xiàn)高并發(fā)下的線程安全。
懶惰刪除和協(xié)作清理：任何線程遇到“已刪除節(jié)點(diǎn)”時都會順手幫忙清理，避免“懸掛節(jié)點(diǎn)”影響性能。
跳表高度動態(tài)調(diào)整：插入時隨機(jī)決定高度，刪除時嘗試降低高度，避免高度失控。
弱一致性遍歷：迭代器弱一致，允許并發(fā)修改時遍歷不會拋異常，適合高并發(fā)場景。

查看全文

http://www.risenshineclean.com/news/23294.html

中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

托管型網(wǎng)站專業(yè)網(wǎng)絡(luò)推廣公司排名

1. 關(guān)鍵結(jié)構(gòu)

2. 并發(fā)跳表的獨(dú)特實(shí)現(xiàn)

doPut（插入/更新元素）

整體執(zhí)行流程

基礎(chǔ)層節(jié)點(diǎn)插入

1. 類型檢查邏輯分析

2. 并發(fā)刪除機(jī)制的核心區(qū)別

3. 并發(fā)刪除的三階段過程

代碼邏輯的并發(fā)安全考慮

實(shí)際執(zhí)行流程示例

索引層構(gòu)建（概率性）

關(guān)鍵技術(shù)特性

為什么需要標(biāo)記節(jié)點(diǎn)？并發(fā)鏈表刪除的根本問題

unlinkNode的三步刪除策略

為什么分步刪除是必需的？

實(shí)際運(yùn)行示例

findPredecessor（查找前驅(qū)節(jié)點(diǎn)）

VarHandle.acquireFence() 的作用

為什么選擇 acquireFence 而非其他屏障

場景分析

對比其他方法中的類似用法

doRemove（刪除元素）

內(nèi)層循環(huán)：執(zhí)行刪除操作

三階段刪除的具體實(shí)現(xiàn)

刪除后的清理工作

`unlinkNode`?方法詳解

核心執(zhí)行流程

總結(jié)

相關(guān)文章：

中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

1. 關(guān)鍵結(jié)構(gòu)

2. 并發(fā)跳表的獨(dú)特實(shí)現(xiàn)

doPut（插入/更新元素）

整體執(zhí)行流程

基礎(chǔ)層節(jié)點(diǎn)插入

1. 類型檢查邏輯分析

2. 并發(fā)刪除機(jī)制的核心區(qū)別

3. 并發(fā)刪除的三階段過程

代碼邏輯的并發(fā)安全考慮

實(shí)際執(zhí)行流程示例

索引層構(gòu)建（概率性）

關(guān)鍵技術(shù)特性

為什么需要標(biāo)記節(jié)點(diǎn)？并發(fā)鏈表刪除的根本問題

unlinkNode的三步刪除策略

為什么分步刪除是必需的？

實(shí)際運(yùn)行示例

findPredecessor（查找前驅(qū)節(jié)點(diǎn)）

VarHandle.acquireFence() 的作用

為什么選擇 acquireFence 而非其他屏障

場景分析

對比其他方法中的類似用法

doRemove（刪除元素）

內(nèi)層循環(huán)：執(zhí)行刪除操作

三階段刪除的具體實(shí)現(xiàn)

刪除后的清理工作

unlinkNode?方法詳解

核心執(zhí)行流程

總結(jié)

相關(guān)文章：

`unlinkNode`?方法詳解