ConcurrentNavigableMap，支持 firstKey()、floorEntry()、subMap() 等範圍操作。O(log n)，迭代器弱一致性，無 ConcurrentModificationException。適用場景：高併發緩存、路由表、限流計數器、時序數據索引、分布式鎖元數據存儲。
Node —— 底層有序單鏈表static final class Node {
final K key;
volatile Object value; // Object 區分普通值 / 刪除標記 / 頭節點
volatile Node next;
// 普通節點
Node(K key, Object value, Node next) { ... }
// 刪除標記節點：value 指向自己，key=null
Node(Node next) { this.key=null; this.value=this; this.next=next; }
// CAS 輔助
boolean casValue(Object cmp, Object val) { ... }
boolean casNext(Node cmp, Node val) { ... }
boolean isMarker() { return value == this; }
boolean isBaseHeader() { return value == BASE_HEADER; }
} 關鍵設計：value 為 Object 而非 V，利用特殊引用標識節點狀態：
this (Marker)BASE_HEADER 單例Index —— 多層索引縮小查找範圍static class Index {
final Node node; // 指向底層 Node
final Index down; // 下一層索引（final，簡化並發）
volatile Index right; // 同層下一個索引
// CAS 鏈接/解鏈接 right
final boolean casRight(Index cmp, Index val) { ... }
// 索引節點是否指向已刪除 Node
final boolean indexesDeletedNode() { return node.value == null; }
// 鏈接新索引節點
final boolean link(Index succ, Index newSucc) { ... }
// 解鏈接索引節點
final boolean unlink(Index succ) { ... }
} 索引層邏輯上形成「下沉式」雙向鏈表：down 指向下層，right 指向同層後繼。
HeadIndex —— 跟蹤最高層級static final class HeadIndex extends Index {
final int level; // 索引層數，從 1 開始，底層 Node 層為 0
HeadIndex(Node node, Index down, Index right, int level) { ... }
} 
（參考 Wikipedia 跳表圖示：多層索引逐層下沉，最終定位到底層有序鏈表）
// 無參：自然順序
public ConcurrentSkipListMap() { this.comparator = null; initialize(); }
// 指定 Comparator
public ConcurrentSkipListMap(Comparator comparator) { ... }
// 從 Map 複製（自然順序）
public ConcurrentSkipListMap(Map m) { ... putAll(m); }
// 從 SortedMap 複製（保留其 Comparator）
public ConcurrentSkipListMap(SortedMap m) { ... buildFromSorted(m); }
private void initialize() {
keySet = entrySet = values = descendingMap = null;
randomSeed = seedGenerator.nextInt() | 0x0100; // 非零種子
head = new HeadIndex<>(new Node<>(null, BASE_HEADER, null), null, null, 1);
} findPredecessor(key)從最高層 HeadIndex 開始：
right，直到 node.key >= key 或 right == nullnode.value == null) → unlink() 刪除該索引down 進入下一層q.node 作為前驅作用：查找插入/刪除位置 + 順便清理失效索引。
doPut(key, value, onlyIfAbsent)b = findPredecessor(key) 獲取前驅helpDelete() 推進刪除CAS value 更新或 onlyIfAbsent 返回舊值b.key < key < n.key）CAS b.next 將新 Node 鏈入randomLevel() 隨機生成索引層數（幂次分佈，p=0.5，最大 31）level > 0 → insertIndex(z, level) 為新節點建立索引塔insertIndex(z, level)level <= head.level：在現有層數內，自底向上創建 Index 鏈，調用 addIndex() 逐層 CAS right 鏈入level > head.level：需增加新層 → 創建新 HeadIndex 鏈，CAS head 指針原子切換doRemove(key, value)findPredecessor() + 底層遍歷定位目標 Node n、前驅 b、後繼 fCAS n.value → null 標記為待刪除n.appendMarker(f) 在 n 後插入 Marker 節點，阻止新節點插入其間CAS b.next → f 將 n + Marker 從鏈表摘除findNode() 重試（其他線程可能已幫助完成）findPredecessor() 清理索引塔，tryReduceLevel() 嘗試降低最高層四步刪除協議：value=null → appendMarker → CAS next → cleanup indexes，解決並發插入/刪除/讀取的所有競態。
doGet(key)findNode(key) 定位 Node（含清理 Marker）value，非 null 直接返回abstract class Iter implements Iterator {
Node lastReturned, next; V nextValue;
Iter() { next = findFirst(); ... } // 跳過頭節點與 Marker
void advance() {
next = next.next;
while (next != null) {
Object x = next.value;
if (x != null && x != next) { nextValue = (V)x; break; }
next = next.next;
}
}
// ... hasNext, next, remove ...
} ConcurrentModificationException| 技術點 | 實現方式 | 效果 |
|---|---|---|
| 無鎖並發 | CAS (Unsafe) + volatile + final | 無阻塞、可線性化 |
| 節點狀態編碼 | value 引用特殊值 | 無額外標記字段，原子讀取 |
| 刪除協議 | value=null → Marker → CAS next | 防止 ABA、並發插入安全 |
| 索引維護 | 懶刪除 + 遍歷時清理 + 最高層收縮 | 索引不準確不影響正確性，僅影響查找速度 |
| 隨機層數 | Xorshift RNG，p=0.5 | 期望高度 O(log n)，空間 O(n) |
| 弱一致性迭代器 | 遍歷底層 Node 鏈表 | 無鎖、無異常、可並發修改 |
size() 需全遍歷（非 O(1)）、範圍查詢需遍歷底層鏈表、降序迭代慢ConcurrentHashMap：無序、吞吐更高、size() O(1)Collections.synchronizedSortedMap(TreeMap)：粗粒度鎖、擴展性差TreeMap：非線程安全最佳實踐：需要「高併發 + 有序 + 範圍查詢」時首選；純緩存/計數用 ConcurrentHashMap；單線程/低併發用 TreeMap。
