JDK 8 ConcurrentSkipListMap 源码详解（详细注释版）
1. 类定义和基本属性
public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {
// 序列化版本号
private static final long serialVersionUID = -8627078645895051609L;
/**
* 比较器，用于定义键的排序规则
* 如果为null，则使用键的自然排序
*/
private final Comparator<? super K> comparator;
/**
* 跳表的头节点
* 头节点不存储实际数据，作为跳表的起始点
* 所有层级的头节点都指向同一个Node对象
*/
private transient volatile HeadIndex<K,V> head;
/**
* 跳表的最大层级
* 限制跳表的层级数量，避免过度分层
*/
private static final int MAX_LEVEL = 31;
/**
* 随机数生成器，用于决定新节点的层级
* 通过概率分布来确定节点层级，保证跳表的平衡性
*/
private transient volatile ThreadLocalRandom random;
/**
* 删除操作的阈值
* 当删除的节点数量超过此阈值时，触发清理操作
*/
private transient volatile int baseLevel;
/**
* 节点内部类
* 跳表的基本存储单元
*/
static final class Node<K,V> {
final K key; // 节点的键
volatile Object value; // 节点的值（可能被标记为删除）
volatile Node<K,V> next; // 指向下一个节点的引用
/**
* 构造方法
* @param key 节点键
* @param value 节点值
* @param next 下一个节点
*/
Node(K key, V value, Node<K,V> next) {
this.key = key;
this.value = value;
this.next = next;
}
/**
* 构造方法（用于标记删除的节点）
* @param key 节点键
* @param next 下一个节点
*/
Node(Node<K,V> next) {
this.key = null;
this.value = this; // 特殊标记，表示节点被删除
this.next = next;
}
/**
* 判断节点是否有效（未被删除）
* @return 如果节点有效返回true，否则返回false
*/
boolean isMarker() {
return value == this;
}
/**
* 判断节点是否base-level（最底层）
* @param b 基准节点
* @return 如果是base-level返回true，否则返回false
*/
boolean isBaseHeader() {
return value == BASE_HEADER;
}
/**
* 尝试添加删除标记
* @return 如果成功添加标记返回true，否则返回false
*/
boolean casValue(Object cmp, Object val) {
return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val);
}
/**
* CAS操作更新next指针
* @param cmp 预期的当前值
* @param val 新值
* @return 如果更新成功返回true，否则返回false
*/
boolean casNext(Node<K,V> cmp, Node<K,V> val) {
return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
}
// Unsafe操作相关
private static final sun.misc.Unsafe UNSAFE;
private static final long valueOffset;
private static final long nextOffset;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> k = Node.class;
valueOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("value"));
nextOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("next"));
} catch (Exception e) {
throw new Error(e);
}
}
}
/**
* 索引节点内部类
* 用于构建跳表的多层索引结构
*/
static class Index<K,V> {
final Node<K,V> node; // 关联的数据节点
final Index<K,V> down; // 指向下层索引节点
volatile Index<K,V> right; // 指向右侧索引节点
/**
* 构造方法
* @param node 关联的数据节点
* @param down 下层索引节点
* @param right 右侧索引节点
*/
Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
this.node = node;
this.down = down;
this.right = right;
}
/**
* CAS操作更新right指针
* @param cmp 预期的当前值
* @param val 新值
* @return 如果更新成功返回true，否则返回false
*/
final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);
}
/**
* 判断节点是否有效
* @return 如果节点有效返回true，否则返回false
*/
final boolean indexesDeletedNode() {
return node.value == null;
}
/**
* 链接新的右侧节点
* @param succ 成功的节点
* @param newSucc 新的成功节点
* @return 如果链接成功返回true，否则返回false
*/
final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
Node<K,V> x = node;
newSucc.right = succ;
return x.value != null && casRight(succ, newSucc);
}
/**
* 取消链接右侧节点
* @param succ 成功的节点
* @return 如果取消链接成功返回true，否则返回false
*/
final boolean unlink(Index<K,V> succ) {
return node.value != null && casRight(succ, succ.right);
}
// Unsafe操作相关
private static final sun.misc.Unsafe UNSAFE;
private static final long rightOffset;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> k = Index.class;
rightOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("right"));
} catch (Exception e) {
throw new Error(e);
}
}
}
/**
* 头索引节点内部类
* 跳表各层的头节点
*/
static final class HeadIndex<K,V> extends Index<K,V> {
final int level; // 层级
HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
super(node, down, right);
this.level = level;
}
}
/**
* 基础头节点的特殊标记值
*/
static final Object BASE_HEADER = new Object();
2. 构造方法（详细注释）
/**
* 默认构造方法
* 创建一个使用键自然排序的ConcurrentSkipListMap
*
* 初始化过程：
* 1. 设置比较器为null（使用自然排序）
* 2. 创建初始的跳表结构
* 3. 初始化头节点和随机数生成器
*/
public ConcurrentSkipListMap() {
this.comparator = null; // 使用自然排序
initialize(); // 初始化跳表结构
}
/**
* 使用指定比较器的构造方法
* @param comparator 用于排序的比较器
*
* 比较器说明：
* - 如果comparator为null，使用自然排序
* - 否则使用指定的比较器进行排序
* - 比较器必须保持一致性
*/
public ConcurrentSkipListMap(Comparator<? super K> comparator) {
this.comparator = comparator; // 设置比较器
initialize(); // 初始化跳表结构
}
/**
* 从SortedMap构造ConcurrentSkipListMap
* @param m 包含初始数据的SortedMap
*
* 构造过程：
* 1. 使用m的比较器
* 2. 初始化跳表结构
* 3. 逐个添加m中的元素
*/
public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
this.comparator = m.comparator(); // 使用相同的比较器
initialize(); // 初始化跳表结构
buildFromSorted(m); // 从有序数据构建
}
/**
* 从Map构造ConcurrentSkipListMap
* @param m 包含初始数据的Map
*
* 构造过程：
* 1. 使用自然排序
* 2. 初始化跳表结构
* 3. 逐个添加m中的元素
*/
public ConcurrentSkipListMap(Map<K, ? extends V> m) {
this.comparator = null; // 使用自然排序
initialize(); // 初始化跳表结构
putAll(m); // 添加所有元素
}
/**
* 初始化跳表结构
* 创建初始的头节点和相关组件
*/
private void initialize() {
keySet = null;
entrySet = null;
values = null;
descendingKeySet = null;
random = new ThreadLocalRandom(); // 初始化随机数生成器
baseLevel = 1;
// 创建初始节点和头索引
Node<K,V> baseHead = new Node<K,V>(null, BASE_HEADER, null);
head = new HeadIndex<K,V>(baseHead, null, null, 1);
}
/**
* 从有序数据构建跳表
* @param map 包含有序数据的Map
*/
private void buildFromSorted(SortedMap<K, ? extends V> map) {
// 逐个添加元素
for (Map.Entry<K, ? extends V> e : map.entrySet())
put(e.getKey(), e.getValue());
}
3. 核心查找方法（详细注释）
/**
* 获取指定键对应的值
* @param key 要查找的键
* @return 键对应的值，如果键不存在返回null
*
* 查找过程：
* 1. 从最高层开始，向右查找
* 2. 如果右侧节点的键大于目标键，向下一层
* 3. 如果找到匹配的键，返回对应的值
* 4. 如果到达最底层仍未找到，返回null
*
* 时间复杂度：平均O(log n)，最坏O(n)
*/
public V get(Object key) {
return doGet(key);
}
/**
* 实际的获取操作
* @param key 要查找的键
* @return 键对应的值，如果键不存在返回null
*/
private V doGet(Object key) {
if (key == null)
throw new NullPointerException(); // 不允许null键
Comparator<? super K> cmp = comparator;
outer: for (;;) {
// 从头节点开始查找
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
if (n == null)
break outer; // 到达链表末尾
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
if ((c = cpr(cmp, key, n.key)) == 0) {
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
if (c < 0)
break outer;
b = n;
n = f;
}
}
return null;
}
/**
* 查找指定键的前驱节点
* @param key 要查找的键
* @param cmp 比较器
* @return 前驱节点
*/
private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
if (key == null)
throw new NullPointerException(); // 不允许null键
for (;;) {
// 从最高层开始查找
for (Index<K,V> q = head, r = q.right, d;;) {
if (r != null) {
Node<K,V> n = r.node;
K k = n.key;
if (n.value == null) {
if (!q.unlink(r))
break; // restart
r = q.right; // re-read r
continue;
}
if (cpr(cmp, key, k) > 0) {
q = r;
r = r.right;
continue;
}
}
if ((d = q.down) != null) {
q = d;
r = d.right;
} else
return q.node;
}
}
}
/**
* 比较两个键
* @param c 比较器
* @param x 第一个键
* @param y 第二个键
* @return 比较结果
*/
private static int cpr(Comparator c, Object x, Object y) {
return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);
}
4. 核心插入方法（详细注释）
/**
* 插入键值对
* @param key 键
* @param value 值
* @return 如果是更新操作返回旧值，如果是插入操作返回null
*
* 插入过程：
* 1. 查找插入位置
* 2. 如果键已存在，更新值
* 3. 如果键不存在，创建新节点
* 4. 随机确定新节点的层级
* 5. 更新索引结构
*
* 时间复杂度：平均O(log n)
*/
public V put(K key, V value) {
if (value == null)
throw new NullPointerException(); // 不允许null值
return doPut(key, value, false);
}
/**
* 如果键不存在则插入
* @param key 键
* @param value 值
* @return 如果插入成功返回null，如果键已存在返回旧值
*/
public V putIfAbsent(K key, V value) {
if (value == null)
throw new NullPointerException(); // 不允许null值
return doPut(key, value, true);
}
/**
* 实际的插入操作
* @param key 键
* @param value 值
* @param onlyIfAbsent 是否只在键不存在时插入
* @return 如果是更新操作返回旧值，如果是插入操作返回null
*/
private V doPut(K key, V value, boolean onlyIfAbsent) {
Node<K,V> z; // 新增节点
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
// 查找插入位置
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
if (n != null) {
Object v; int c;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
if ((c = cpr(cmp, key, n.key)) > 0) {
b = n;
n = f;
continue;
}
if (c == 0) {
if (onlyIfAbsent || n.casValue(v, value)) {
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
break; // restart if lost race to replace value
}
// else c < 0; fall through
}
z = new Node<K,V>(key, value, n);
if (!b.casNext(n, z))
break; // restart if lost race to append to b
break outer;
}
}
// 随机确定层级并插入索引
int rnd = random.nextInt();
if ((rnd & 0x80000001) == 0) { // test highest and lowest bits
int level = 1, max;
while (((rnd >>>= 1) & 1) != 0)
++level;
if (level > (max = head.level)) {
if (max >= MAX_LEVEL)
level = MAX_LEVEL;
else {
HeadIndex<K,V> newHead = new HeadIndex<K,V>(z, null, null, level);
for (;;) {
HeadIndex<K,V> oldHead = head;
if (level <= oldHead.level || !casHead(oldHead, newHead))
break;
}
}
}
if (level > 0)
insertIndex(z, level);
}
return null;
}
/**
* 插入索引节点
* @param z 数据节点
* @param level 层级
*/
private void insertIndex(Node<K,V> z, int level) {
HeadIndex<K,V> h = head;
int max = h.level;
if (level <= max) {
Index<K,V> idx = null;
for (int i = 1; i <= level; ++i)
idx = new Index<K,V>(z, idx, null);
addIndex(idx, h, level);
} else { // Add a new level
// 此处省略层级扩展的详细实现
}
}
/**
* 添加索引节点
* @param idx 索引节点
* @param h 头节点
* @param indexLevel 索引层级
*/
private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
// 从指定层级开始，逐层添加索引
int insertionLevel = indexLevel;
Index<K,V> q = h;
Index<K,V> r = h.right;
for (int j = h.level; j >= insertionLevel; --j) {
for (;;) {
Index<K,V> rn = r == null ? null : r.right;
if (j < insertionLevel) {
if (j + 1 < insertionLevel) {
// 插入到下一层
Index<K,V> down = idx.down;
Index<K,V> nd = new Index<K,V>(idx.node, down, null);
idx.right = nd;
idx = nd;
}
break;
}
if (rn != null && rn.node.key != null) {
int c = cpr(comparator, idx.node.key, rn.node.key);
if (c > 0) {
q = r;
r = rn;
continue;
}
}
Index<K,V> rd = r;
idx.right = rd;
if (q.casRight(r, idx))
break;
r = q.right;
}
if (--insertionLevel == 0)
break;
Index<K,V> down = idx.down;
Index<K,V> nd = new Index<K,V>(idx.node, down, null);
idx.right = nd;
idx = nd;
q = q.down;
r = q.right;
}
}
/**
* CAS更新头节点
* @param cmp 预期的当前值
* @param val 新值
* @return 如果更新成功返回true，否则返回false
*/
private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
}
5. 核心删除方法（详细注释）
/**
* 删除指定键的映射关系
* @param key 要删除的键
* @return 被删除的值，如果键不存在返回null
*
* 删除过程：
* 1. 查找要删除的节点
* 2. 标记节点为删除状态
* 3. 物理删除节点
* 4. 更新索引结构
*
* 时间复杂度：平均O(log n)
*/
public V remove(Object key) {
return doRemove(key, null);
}
/**
* 条件删除
* @param key 要删除的键
* @param value 期望的值
* @return 如果删除成功返回true，否则返回false
*/
public boolean remove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
if (value == null)
return false;
return doRemove(key, value) != null;
}
/**
* 实际的删除操作
* @param key 要删除的键
* @param value 期望的值（null表示不检查值）
* @return 被删除的值，如果删除失败返回null
*/
final V doRemove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
// 查找要删除的节点
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
if (n == null)
break outer;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
if ((c = cpr(cmp, key, n.key)) < 0)
break outer;
if (c > 0) {
b = n;
n = f;
continue;
}
if (value != null && !value.equals(v))
break outer;
if (!n.casValue(v, null))
break;
if (!n.appendMarker(f) || !b.casNext(n, f))
findNode(key); // retry via findNode
else {
findPredecessor(key, cmp); // clean index
if (head.right == null)
tryReduceLevel();
}
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
}
return null;
}
/**
* 帮助删除节点
* @param b 前驱节点
* @param f 后继节点
*/
void helpDelete(Node<K,V> b, Node<K,V> f) {
if (f == next && this == b.next) {
if (f == null || f.value != f) // not already marked
casNext(f, new Node<K,V>(f));
else
b.casNext(this, f.next);
}
}
/**
* 追加删除标记
* @param next 后继节点
* @return 如果成功追加标记返回true，否则返回false
*/
boolean appendMarker(Node<K,V> next) {
return casNext(next, new Node<K,V>(next));
}
/**
* 尝试减少层级
* 当头节点的右侧为空时调用
*/
private void tryReduceLevel() {
HeadIndex<K,V> h = head;
HeadIndex<K,V> d;
HeadIndex<K,V> e;
if (h.level > 3 &&
(d = (HeadIndex<K,V>)h.down) != null &&
(e = (HeadIndex<K,V>)d.down) != null &&
e.right == null &&
d.right == null &&
h.right == null &&
casHead(h, d) && // try to set
h.right != null) // recheck
casHead(d, h); // try to backout
}
6. 导航方法（详细注释）
/**
* 返回小于等于指定键的最大键
* @param key 指定键
* @return 小于等于key的最大键，如果不存在返回null
*/
public K floorKey(K key) {
return findNear(key, LT|EQ, comparator);
}
/**
* 返回大于等于指定键的最小键
* @param key 指定键
* @return 大于等于key的最小键，如果不存在返回null
*/
public K ceilingKey(K key) {
return findNear(key, GT|EQ, comparator);
}
/**
* 返回小于指定键的最大键
* @param key 指定键
* @return 小于key的最大键，如果不存在返回null
*/
public K lowerKey(K key) {
return findNear(key, LT, comparator);
}
/**
* 返回大于指定键的最小键
* @param key 指定键
* @return 大于key的最小键，如果不存在返回null
*/
public K higherKey(K key) {
return findNear(key, GT, comparator);
}
/**
* 查找最近的节点
* @param key 目标键
* @param rel 关系标志
* @param cmp 比较器
* @return 找到的键，如果不存在返回null
*/
private K findNear(K key, int rel, Comparator<? super K> cmp) {
if (key == null)
throw new NullPointerException();
for (;;) {
// 从头节点开始查找
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
if (n == null) {
if ((rel & LT) == 0)
break;
for (Node<K,V> p = b; p != null; p = p.prev) {
if (p.value != null && p.value != p) {
@SuppressWarnings("unchecked") K kk = (K)p.key;
return kk;
}
}
break;
}
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
if ((c = cpr(cmp, key, n.key)) == 0) {
if ((rel & EQ) != 0) {
@SuppressWarnings("unchecked") K kk = (K)n.key;
return kk;
}
if ((rel & LT) != 0) {
for (Node<K,V> p = b; p != null; p = p.prev) {
if (p.value != null && p.value != p) {
@SuppressWarnings("unchecked") K kk = (K)p.key;
return kk;
}
}
break;
}
n = f;
continue;
}
if (c < 0) {
if ((rel & LT) == 0)
break;
for (Node<K,V> p = b; p != null; p = p.prev) {
if (p.value != null && p.value != p) {
@SuppressWarnings("unchecked") K kk = (K)p.key;
return kk;
}
}
break;
}
b = n;
n = f;
}
}
return null;
}
// 关系标志常量
private static final int EQ = 1; // 相等
private static final int LT = 2; // 小于
private static final int GT = 4; // 大于
7. 范围操作方法（详细注释）
/**
* 返回此映射的部分视图，键的范围从fromKey到toKey
* @param fromKey 起始键（包含）
* @param fromInclusive 是否包含起始键
* @param toKey 结束键（不包含）
* @param toInclusive 是否包含结束键
* @return 指定范围的子映射
*/
public ConcurrentNavigableMap<K,V> subMap(K fromKey,
boolean fromInclusive,
K toKey,
boolean toInclusive) {
if (fromKey == null || toKey == null)
throw new NullPointerException();
return new SubMap<K,V>
(this, fromKey, fromInclusive, toKey, toInclusive, false);
}
/**
* 返回此映射的部分视图，键小于toKey
* @param toKey 结束键
* @param inclusive 是否包含结束键
* @return 头部映射
*/
public ConcurrentNavigableMap<K,V> headMap(K toKey, boolean inclusive) {
if (toKey == null)
throw new NullPointerException();
return new SubMap<K,V>(this, null, false, toKey, inclusive, false);
}
/**
* 返回此映射的部分视图，键大于等于fromKey
* @param fromKey 起始键
* @param inclusive 是否包含起始键
* @return 尾部映射
*/
public ConcurrentNavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
if (fromKey == null)
throw new NullPointerException();
return new SubMap<K,V>(this, fromKey, inclusive, null, false, false);
}
/**
* SubMap内部类，实现范围映射
*/
static final class SubMap<K,V> extends AbstractMap<K,V>
implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {
// 省略具体实现细节
}
8. 迭代器实现（详细注释）
/**
* 返回键的可导航集合
* @return 键集合
*/
public NavigableSet<K> navigableKeySet() {
KeySet<K> ks = keySet;
return (ks != null) ? ks : (keySet = new KeySet<K>(this));
}
/**
* 键集合内部类
*/
static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
private final ConcurrentNavigableMap<E,?> m;
KeySet(ConcurrentNavigableMap<E,?> map) { m = map; }
public int size() { return m.size(); }
public boolean isEmpty() { return m.isEmpty(); }
public boolean contains(Object o) { return m.containsKey(o); }
public boolean remove(Object o) { return m.remove(o) != null; }
public void clear() { m.clear(); }
/**
* 返回迭代器
* @return 键迭代器
*/
public Iterator<E> iterator() {
if (m instanceof ConcurrentSkipListMap)
return ((ConcurrentSkipListMap<E,?>)m).keyIterator();
else
return ((ConcurrentSkipListMap.SubMap<E,?>)m).keyIterator();
}
/**
* 返回降序迭代器
* @return 降序键迭代器
*/
public Iterator<E> descendingIterator() {
return descendingIterator();
}
}
/**
* 返回键迭代器
* @return 键迭代器
*/
Iterator<K> keyIterator() {
return new KeyIterator();
}
/**
* 键迭代器内部类
*/
final class KeyIterator extends Iter<K> {
public K next() {
Node<K,V> n = next;
if (n == null)
throw new NoSuchElementException();
K x = n.key;
last = n;
advance();
return x;
}
}
/**
* 迭代器基类
*/
abstract class Iter<T> implements Iterator<T> {
/** the last node returned by next() */
Node<K,V> last;
/** the next node to return from next(); */
Node<K,V> next;
/** next node on predecessor's level */
Node<K,V> nextPrec;
/** predecessor of last returned node */
Node<K,V> prev;
/** predecessor of next node */
Node<K,V> prevPrec;
/** estimated number of elements */
long est;
/** true if last() called */
boolean lastRet;
/** true if descending */
boolean descending;
Iter() {
advance();
}
/**
* Advance next to higher entry.
* Precondition: next != null.
*/
final void advance() {
Node<K,V> n = next;
if (n == null) {
next = null;
est = 0;
} else {
Node<K,V> f = n.next;
for (;;) {
if (f == null) {
next = null;
est = 0;
break;
}
Object v = f.value;
if (v != null && v != f) {
next = f;
est--;
break;
}
f = f.next;
}
}
}
public final boolean hasNext() {
return next != null;
}
/** Returns current node, advancing next. */
final Node<K,V> nextNode() {
Node<K,V> n = next;
if (n == null)
throw new NoSuchElementException();
last = n;
advance();
return n;
}
public void remove() {
Node<K,V> l = last;
if (l == null)
throw new IllegalStateException();
m.remove(l.key);
last = null;
}
}
9. ConcurrentSkipListMap 的特点分析
核心设计理念：
/**
* ConcurrentSkipListMap的核心设计思想：
*
* 1. 跳表数据结构：
* - 多层链表结构，提供快速查找
* - 每层都是一个有序链表
* - 上层节点稀疏，下层节点密集
* - 通过随机化保持结构平衡
*
* 2. 无锁并发控制：
* - 使用CAS操作实现无锁化
* - 减少锁竞争，提高并发性能
* - 支持高并发读写操作
*
* 3. 有序性保证：
* - 键按照自然顺序或比较器排序
* - 支持范围查询和导航操作
* - 提供有序的迭代器
*
* 4. 原子性操作：
* - 插入、删除、查找操作都是原子的
* - 保证数据一致性
* - 支持复合操作
*
* 5. 内存管理：
* - 及时清理删除的节点
* - 避免内存泄漏
* - 支持GC友好设计
*
* 适用场景：
* - 需要有序映射的高并发场景
* - 频繁进行范围查询的场景
* - 需要导航操作的场景
* - 要求无锁并发的场景
*/
性能特征分析：
/**
* ConcurrentSkipListMap的性能特征：
*
* 时间复杂度：
* - get(key): O(log n) 平均情况
* - put(key, value): O(log n) 平均情况
* - remove(key): O(log n) 平均情况
* - containsKey(key): O(log n) 平均情况
* - firstKey()/lastKey(): O(log n) 平均情况
* - subMap(): O(log n) 创建视图
*
* 空间复杂度：
* - O(n) 基本存储空间
* - 额外的索引节点开销
* - 平均每个节点约2个指针的额外开销
*
* 并发特性：
* - 无锁设计，减少锁竞争
* - 支持高并发读写
* - 弱一致性：读操作可能看不到最新的写操作
* - 不会抛出ConcurrentModificationException
*
* 内存使用：
* - 动态分配，按需扩展
* - 索引节点占用额外内存
* - 及时GC，避免内存泄漏
*
* 适用性：
* - 读操作频繁：性能优秀
* - 写操作频繁：性能良好
* - 范围查询：性能优秀
* - 有序遍历：性能优秀
*/
10. 使用示例和最佳实践
/**
* 使用示例：
*
* // 基本使用
* ConcurrentSkipListMap<String, Integer> map = new ConcurrentSkipListMap<>();
*
* // 添加元素
* map.put("apple", 1);
* map.put("banana", 2);
* map.put("cherry", 3);
*
* // 查找元素
* Integer value = map.get("apple");
* System.out.println("Value: " + value);
*
* // 范围操作
* ConcurrentNavigableMap<String, Integer> subMap =
* map.subMap("apple", true, "cherry", true);
* System.out.println("SubMap: " + subMap);
*
* // 导航操作
* String firstKey = map.firstKey();
* String lastKey = map.lastKey();
* String lowerKey = map.lowerKey("banana");
* String higherKey = map.higherKey("banana");
*
* // 并发使用示例
* ExecutorService executor = Executors.newFixedThreadPool(10);
*
* // 并发写入
* for (int i = 0; i < 10; i++) {
* final int threadId = i;
* executor.submit(() -> {
* for (int j = 0; j < 1000; j++) {
* map.put("thread" + threadId + "_item" + j, j);
* }
* });
* }
*
* // 并发读取
* for (int i = 0; i < 10; i++) {
* executor.submit(() -> {
* for (int j = 0; j < 1000; j++) {
* Integer value = map.get("someKey");
* // 处理值
* }
* });
* }
*
* 最佳实践：
*
* 1. 合理选择键类型：
* // 键应该实现Comparable接口或提供Comparator
* ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();
*
* // 或者使用自定义比较器
* Comparator<String> comparator = String.CASE_INSENSITIVE_ORDER;
* ConcurrentSkipListMap<String, Integer> map2 =
* new ConcurrentSkipListMap<>(comparator);
*
* 2. 避免频繁的范围操作：
* // 范围操作虽然高效，但仍需谨慎使用
* NavigableMap<String, Integer> range =
* map.headMap("m", false); // 所有小于"m"的键
*
* // 遍历范围
* for (Map.Entry<String, Integer> entry : range.entrySet()) {
* System.out.println(entry.getKey() + ": " + entry.getValue());
* }
*
* 3. 正确处理null值：
* // 不允许null键和null值
* try {
* map.put(null, "value"); // 抛出NullPointerException
* } catch (NullPointerException e) {
* System.out.println("Null keys are not allowed");
* }
*
* try {
* map.put("key", null); // 抛出NullPointerException
* } catch (NullPointerException e) {
* System.out.println("Null values are not allowed");
* }
*
* 4. 使用原子操作：
* // 使用原子操作避免竞态条件
* map.putIfAbsent("key", "value");
* map.replace("key", "oldValue", "newValue");
* map.remove("key", "value");
*
* 5. 监控性能：
* // 监控映射大小
* int size = map.size();
* System.out.println("Map size: " + size);
*
* // 在高并发环境下，size()可能是估算值
*
* 6. 合理使用视图：
* // 创建子映射视图
* ConcurrentNavigableMap<String, Integer> subMap =
* map.subMap("a", true, "z", false);
*
* // 视图操作会反映到原映射中
* subMap.put("newKey", 100);
* System.out.println(map.containsKey("newKey")); // true
*
* 7. 注意内存使用：
* // 大量数据时注意内存使用
* if (map.size() > 100000) {
* System.out.println("Large map size, consider memory usage");
* }
*
* 8. 正确使用迭代器：
* // 迭代器是弱一致性的
* Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
* while (it.hasNext()) {
* Map.Entry<String, Integer> entry = it.next();
* // 处理条目
* // 注意：迭代过程中可能看不到最新的修改
* }
*
* 9. 异常处理：
* // 处理可能的并发异常
* try {
* String value = map.get("key");
* // 处理值
* } catch (Exception e) {
* System.out.println("Error during map operation: " + e.getMessage());
* }
*
* 10. 性能调优：
* // 对于读多写少的场景，性能优秀
* // 对于写多读少的场景，考虑其他数据结构
* // 频繁的范围查询场景，ConcurrentSkipListMap是很好的选择
*/
11. 与其他并发映射的比较
/**
* ConcurrentSkipListMap vs ConcurrentHashMap vs ConcurrentNavigableMap:
*
* ConcurrentSkipListMap:
* - 基于跳表实现
* - 保持键的有序性
* - 支持导航操作
* - 无锁设计，CAS操作
* - 适合有序访问场景
* - 内存开销相对较大
*
* ConcurrentHashMap:
* - 基于哈希表实现
* - 不保持键的有序性
* - 不支持导航操作
* - 分段锁或CAS+synchronized
* - 适合高性能哈希访问
* - 内存开销相对较小
*
* TreeMap (非并发):
* - 基于红黑树实现
* - 保持键的有序性
* - 支持导航操作
* - 需要外部同步
* - 单线程性能优秀
*
* 选择建议：
* - 需要有序映射且高并发：ConcurrentSkipListMap
* - 高性能哈希访问：ConcurrentHashMap
* - 单线程有序访问：TreeMap
* - 需要范围查询：ConcurrentSkipListMap
*
* 性能对比：
* - 读操作：ConcurrentHashMap > ConcurrentSkipListMap > TreeMap
* - 写操作：ConcurrentHashMap ≈ ConcurrentSkipListMap > TreeMap
* - 范围查询：ConcurrentSkipListMap > TreeMap > ConcurrentHashMap
* - 内存使用：TreeMap < ConcurrentHashMap < ConcurrentSkipListMap
* - 并发性：ConcurrentSkipListMap ≈ ConcurrentHashMap > TreeMap
*/
12. 总结
ConcurrentSkipListMap 的核心特性：
-
跳表实现：
- 多层有序链表结构
- 平均O(log n)的查找性能
- 通过随机化保持平衡
-
无锁并发：
- 使用CAS操作实现无锁化
- 减少锁竞争，提高并发性能
- 支持高并发读写操作
-
有序性保证：
- 键按照自然顺序或比较器排序
- 支持范围查询和导航操作
- 提供有序的迭代器
-
原子性操作：
- 插入、删除、查找操作都是原子的
- 保证数据一致性
- 支持复合操作
-
线程安全：
- 所有操作都是线程安全的
- 不需要外部同步
- 支持多个并发访问
适用场景：
- 需要有序映射的高并发场景
- 频繁进行范围查询的场景
- 需要导航操作的场景
- 要求无锁并发的场景
- 需要保持键排序的应用
注意事项：
- 不允许存储null键和null值
- 内存开销比HashMap大
- 迭代器是弱一致性的
- size()方法返回的是估算值
- 比较器必须保持一致性
性能优化建议：
- 合理选择键类型和比较器
- 避免频繁的范围操作
- 正确使用原子操作方法
- 监控内存使用情况
- 根据访问模式选择合适的数据结构
- 在高并发环境下注意性能调优
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
