Java多线程
Java并发
JUC集合

Java多线程 32 - ConcurrentSkipListMap详解(1)

简介:ConcurrentSkipListMap是线程安全的有序的哈希表,适用于高并发的场景。

1. ConcurrentSkipListMap简介

注:本文讲解的ConcurrentSkipListMap基于JDK 1.7.0_07。

ConcurrentSkipListMap是线程安全的有序的哈希表,适用于高并发的场景。ConcurrentSkipListMap和TreeMap虽然都是有序的哈希表,但有以下区别:

  1. 它们的线程安全机制不同,TreeMap是非线程安全的,而ConcurrentSkipListMap是线程安全的。
  2. ConcurrentSkipListMap是通过跳表实现的,而TreeMap是通过红黑树实现的。

跳表(Skip List)是平衡树的一种替代的数据结构,和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。

ConcurrentSkipListMap的相关类图结构如下:

1.ConcurrentSkipListMap类图结构.png

ConcurrentSkipListMap方法列表如下:

  • // 构造一个新的空映射,该映射按照键的自然顺序进行排序
  • ConcurrentSkipListMap()
  • // 构造一个新的空映射,该映射按照指定的比较器进行排序
  • ConcurrentSkipListMap(Comparator<? super K> comparator)
  • // 构造一个新映射,该映射所包含的映射关系与给定映射包含的映射关系相同,并按照键的自然顺序进行排序
  • ConcurrentSkipListMap(Map<? extends K, ? extends V> m)
  • // 构造一个新映射,该映射所包含的映射关系与指定的有序映射包含的映射关系相同,使用的顺序也相同
  • ConcurrentSkipListMap(SortedMap<K, ? extends V> m)
  • // 返回与大于等于给定键的最小键关联的键-值映射关系;如果不存在这样的条目,则返回null
  • Map.Entry<K, V> ceilingEntry(K key)
  • // 返回大于等于给定键的最小键;如果不存在这样的键,则返回null
  • K ceilingKey(K key)
  • // 从此映射中移除所有映射关系
  • void clear()
  • // 返回此ConcurrentSkipListMap实例的浅表副本
  • ConcurrentSkipListMap<K, V> clone()
  • // 返回对此映射中的键进行排序的比较器;如果此映射使用键的自然顺序,则返回null
  • Comparator<? super K> comparator()
  • // 如果此映射包含指定键的映射关系,则返回true
  • boolean containsKey(Object key)
  • // 如果此映射为指定值映射一个或多个键,则返回true
  • boolean containsValue(Object value)
  • // 返回此映射中所包含键的逆序NavigableSet视图
  • NavigableSet<K> descendingKeySet()
  • // 返回此映射中所包含映射关系的逆序视图
  • ConcurrentNavigableMap<K, V> descendingMap()
  • // 返回此映射中所包含的映射关系的 Set 视图
  • Set<Map.Entry<K, V>> entrySet()
  • // 比较指定对象与此映射的相等性
  • boolean equals(Object o)
  • // 返回与此映射中的最小键关联的键-值映射关系;如果该映射为空,则返回null
  • Map.Entry<K, V> firstEntry()
  • // 返回此映射中当前第一个(最低)键
  • K firstKey()
  • // 返回与小于等于给定键的最大键关联的键-值映射关系;如果不存在这样的键,则返回null
  • Map.Entry<K, V> floorEntry(K key)
  • // 返回小于等于给定键的最大键;如果不存在这样的键,则返回null
  • K floorKey(K key)
  • // 返回指定键所映射到的值;如果此映射不包含该键的映射关系,则返回null
  • V get(Object key)
  • // 返回此映射的部分视图,其键值严格小于 toKey
  • ConcurrentNavigableMap<K, V> headMap(K toKey)
  • // 返回此映射的部分视图,其键小于(或等于,如果inclusive为true)toKey
  • ConcurrentNavigableMap<K, V> headMap(K toKey, boolean inclusive)
  • // 返回与严格大于给定键的最小键关联的键-值映射关系;如果不存在这样的键,则返回null
  • Map.Entry<K, V> higherEntry(K key)
  • // 返回严格大于给定键的最小键;如果不存在这样的键,则返回null
  • K higherKey(K key)
  • // 如果此映射未包含键-值映射关系,则返回true
  • boolean isEmpty()
  • // 返回此映射中所包含键的NavigableSet视图
  • NavigableSet<K> keySet()
  • // 返回与此映射中的最大键关联的键-值映射关系;如果该映射为空,则返回null
  • Map.Entry<K, V> lastEntry()
  • // 返回映射中当前最后一个(最高)键
  • K lastKey()
  • // 返回与严格小于给定键的最大键关联的键-值映射关系;如果不存在这样的键,则返回null
  • Map.Entry<K, V> lowerEntry(K key)
  • // 返回严格小于给定键的最大键;如果不存在这样的键,则返回null
  • K lowerKey(K key)
  • // 返回此映射中所包含键的NavigableSet视图
  • NavigableSet<K> navigableKeySet()
  • // 移除并返回与此映射中的最小键关联的键-值映射关系;如果该映射为空,则返回null
  • Map.Entry<K, V> pollFirstEntry()
  • // 移除并返回与此映射中的最大键关联的键-值映射关系;如果该映射为空,则返回null
  • Map.Entry<K, V> pollLastEntry()
  • // 将指定值与此映射中的指定键关联
  • V put(K key, V value)
  • // 如果指定键已经不再与某个值相关联,则将它与给定值关联
  • V putIfAbsent(K key, V value)
  • // 从此映射中移除指定键的映射关系(如果存在)
  • V remove(Object key)
  • // 只有目前将键的条目映射到给定值时,才移除该键的条目
  • boolean remove(Object key, Object value)
  • // 只有目前将键的条目映射到某一值时,才替换该键的条目
  • V replace(K key, V value)
  • // 只有目前将键的条目映射到给定值时,才替换该键的条目
  • boolean replace(K key, V oldValue, V newValue)
  • // 返回此映射中的键值映射关系数
  • int size()
  • // 返回此映射的部分视图,其键的范围从fromKey到toKey
  • ConcurrentNavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
  • // 返回此映射的部分视图,其键值的范围从 fromKey(包括)到 toKey(不包括)
  • ConcurrentNavigableMap<K, V> subMap(K fromKey, K toKey)
  • // 返回此映射的部分视图,其键大于等于 fromKey
  • ConcurrentNavigableMap<K, V> tailMap(K fromKey)
  • // 返回此映射的部分视图,其键大于(或等于,如果inclusive为true)fromKey
  • ConcurrentNavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
  • // 返回此映射中所包含值的Collection视图
  • Collection<V> values()

2. 跳表结构和原理

2.跳表结构.png

3. ConcurrentSkipListMap示例

我们首先通过一个示例来了解ConcurrentSkipListMap的使用方法,代码如下:

  • package com.coderap.collection;
  • import java.util.HashMap;
  • import java.util.Map;
  • import java.util.concurrent.ConcurrentSkipListMap;
  • public class ConcurrentSkipListMapTest {
  • // 循环次数
  • private final static int loopCount = 5;
  • // 操作的HashMap和ConcurrentSkipListMap
  • private final static Map<String, String> hashMap = new HashMap<>();
  • private final static ConcurrentSkipListMap<String, String> concurrentSkipListMap = new ConcurrentSkipListMap();
  • public static void main(String[] args) {
  • // 开启两个线程同时操作
  • new Thread(new ConcurrentSkipListMapTest.OperateThread(concurrentSkipListMap, loopCount), "T-1").start();
  • new Thread(new ConcurrentSkipListMapTest.OperateThread(concurrentSkipListMap, loopCount), "T-2").start();
  • //new Thread(new ConcurrentSkipListMapTest.OperateThread(hashMap, loopCount), "T-3").start();
  • //new Thread(new ConcurrentSkipListMapTest.OperateThread(hashMap, loopCount), "T-4").start();
  • }
  • // 遍历方法
  • private static void iterate(Map<String, String> map) {
  • StringBuilder stringBuilder = new StringBuilder();
  • for (Map.Entry<String, String> entry : map.entrySet()) {
  • stringBuilder.append(entry.getKey() + " => " + entry.getValue());
  • stringBuilder.append(", ");
  • }
  • // 删除最后多余的字符
  • stringBuilder.delete(stringBuilder.length() - 2, stringBuilder.length() - 1);
  • // 打印
  • System.out.println(Thread.currentThread().getName() + " iterate: " + stringBuilder.toString());
  • }
  • private static class OperateThread implements Runnable {
  • private Map map;
  • private int loopCount;
  • public OperateThread(Map map, int loopCount) {
  • this.map = map;
  • this.loopCount = loopCount;
  • }
  • @Override
  • public void run() {
  • // 循环添加并遍历打印
  • while (loopCount >= 0) {
  • map.put(Thread.currentThread().getName() + " - " + loopCount, "" + loopCount);
  • iterate(map);
  • loopCount--;
  • }
  • }
  • }
  • }

示例代码非常简单,其实与之前的ConcurrentHashMap示例比较类似,都是使用使用两个线程同时操作;某一次运行结果如下:

  • T-2 iterate: T-1 - 5 => 5, T-2 - 5 => 5
  • T-1 iterate: T-1 - 5 => 5, T-2 - 5 => 5
  • T-2 iterate: T-1 - 5 => 5, T-2 - 4 => 4, T-2 - 5 => 5
  • T-1 iterate: T-1 - 4 => 4, T-1 - 5 => 5, T-2 - 4 => 4, T-2 - 5 => 5
  • T-2 iterate: T-1 - 4 => 4, T-1 - 5 => 5, T-2 - 3 => 3, T-2 - 4 => 4, T-2 - 5 => 5
  • T-1 iterate: T-1 - 3 => 3, T-1 - 4 => 4, T-1 - 5 => 5, T-2 - 3 => 3, T-2 - 4 => 4, T-2 - 5 => 5
  • T-2 iterate: T-1 - 3 => 3, T-1 - 4 => 4, T-1 - 5 => 5, T-2 - 2 => 2, T-2 - 3 => 3, T-2 - 4 => 4, T-2 - 5 => 5
  • T-1 iterate: T-1 - 2 => 2, T-1 - 3 => 3, T-1 - 4 => 4, T-1 - 5 => 5, T-2 - 2 => 2, T-2 - 3 => 3, T-2 - 4 => 4, T-2 - 5 => 5
  • T-2 iterate: T-1 - 2 => 2, T-1 - 3 => 3, T-1 - 4 => 4, T-1 - 5 => 5, T-2 - 1 => 1, T-2 - 2 => 2, T-2 - 3 => 3, T-2 - 4 => 4, T-2 - 5 => 5
  • T-1 iterate: T-1 - 1 => 1, T-1 - 2 => 2, T-1 - 3 => 3, T-1 - 4 => 4, T-1 - 5 => 5, T-2 - 0 => 0, T-2 - 1 => 1, T-2 - 2 => 2, T-2 - 3 => 3, T-2 - 4 => 4, T-2 - 5 => 5
  • T-2 iterate: T-1 - 1 => 1, T-1 - 2 => 2, T-1 - 3 => 3, T-1 - 4 => 4, T-1 - 5 => 5, T-2 - 0 => 0, T-2 - 1 => 1, T-2 - 2 => 2, T-2 - 3 => 3, T-2 - 4 => 4, T-2 - 5 => 5
  • T-1 iterate: T-1 - 0 => 0, T-1 - 1 => 1, T-1 - 2 => 2, T-1 - 3 => 3, T-1 - 4 => 4, T-1 - 5 => 5, T-2 - 0 => 0, T-2 - 1 => 1, T-2 - 2 => 2, T-2 - 3 => 3, T-2 - 4 => 4, T-2 - 5 => 5

同样的,如果将源码中的ConcurrentSkipListMap类型Map改成HashMap类型Map时,程序可能会产生ConcurrentModificationException异常。

4. ConcurrentSkipListMap的基础设计

ConcurrentSkipListMap底层是使用跳表来实现数据的存储的,跳表的结构比较复杂,ConcurrentSkipListMap使用了三个内部类来支撑跳表结构的构建,接下来我们先了解这三个内部类的设计。

4.1. Node类的设计

Node类是装载键值对数据的类,也是构成Node链的节点类,它除了拥有keyvalue两个分别表示键和值的成员属性外,还拥有一个成员变量next用于指向自己的后继节点;源码如下:

  • static final class Node<K, V> {
  • // 键
  • final K key;
  • // 值
  • volatile Object value;
  • // 后继节点
  • volatile Node<K, V> next;
  • /**
  • * Creates a new regular node.
  • * 根据键值对、后继节点构造一个节点
  • */
  • Node(K key, Object value, Node<K, V> next) {
  • this.key = key;
  • this.value = value;
  • this.next = next;
  • }
  • /**
  • * Creates a new marker node. A marker is distinguished by
  • * having its value field point to itself. Marker nodes also
  • * have null keys, a fact that is exploited in a few places,
  • * but this doesn't distinguish markers from the base-level
  • * header node (head.node), which also has a null key.
  • * <p>
  • * 标记节点,特征是它的key为null,value指向了自己
  • */
  • Node(Node<K, V> next) {
  • this.key = null;
  • this.value = this;
  • this.next = next;
  • }
  • /**
  • * compareAndSet value field
  • * CAS修改value为val
  • */
  • boolean casValue(Object cmp, Object val) {
  • return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val);
  • }
  • /**
  • * compareAndSet next field
  • * CAS修改后继节点
  • */
  • boolean casNext(Node<K, V> cmp, Node<K, V> val) {
  • return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
  • }
  • /**
  • * Returns true if this node is a marker. This method isn't
  • * actually called in any current code checking for markers
  • * because callers will have already read value field and need
  • * to use that read (not another done here) and so directly
  • * test if value points to node.
  • * <p>
  • * 判断是否是标记节点,根据value值是否是自己来判断
  • *
  • * @return true if this node is a marker node
  • */
  • boolean isMarker() {
  • return value == this;
  • }
  • /**
  • * Returns true if this node is the header of base-level list.
  • * 判断是否是基础头节点
  • *
  • * @return true if this node is header node
  • */
  • boolean isBaseHeader() {
  • return value == BASE_HEADER;
  • }
  • /**
  • * Tries to append a deletion marker to this node.
  • * 尝试添加一个删除标记到当前节点的下一个节点
  • *
  • * @param f the assumed current successor of this node
  • * @return true if successful
  • */
  • boolean appendMarker(Node<K, V> f) {
  • return casNext(f, new Node<K, V>(f));
  • }
  • /**
  • * Helps out a deletion by appending marker or unlinking from
  • * predecessor. This is called during traversals when value
  • * field seen to be null.
  • * <p>
  • * 通过添加标记节点或与前驱节点断开连接以协助删除
  • *
  • * @param b predecessor
  • * @param f successor
  • */
  • void helpDelete(Node<K, V> b, Node<K, V> f) {
  • /*
  • * Rechecking links and then doing only one of the
  • * help-out stages per call tends to minimize CAS
  • * interference among helping threads.
  • */
  • // 条件:f是当前节点的后继节点,且b是当前节点的前驱节点
  • if (f == next && this == b.next) {
  • if (f == null || f.value != f) // not already marked
  • /**
  • * 走到这里,有两种情况:
  • * 1. f为null;
  • * 2. f不为null,但f的value值不是自己,即f不是标记节点
  • *
  • * 这一步会构建一个标记节点,后继是f,然后把当前节点指向该标记节点,即:
  • * 原来是这样的:b -> current -> f
  • * 现在是这样的:b -> current -> marker -> f
  • */
  • appendMarker(f);
  • else
  • /**
  • * 走到这里,且f不为null,但f是标记节点
  • * 这一步会将b的后继设置为f的后继,即:
  • * 原来是这样的:b -> current -> f(marker) -> f.next
  • * 修改后是这样的:b -> f.next
  • * 即将current和f都删除了
  • */
  • b.casNext(this, f.next);
  • }
  • }
  • /**
  • * Returns value if this node contains a valid key-value pair,
  • * else null.
  • * <p>
  • * 获取校验后的值,防止取到头节点或标记节点
  • *
  • * @return this node's value if it isn't a marker or header or
  • * is deleted, else null.
  • */
  • V getValidValue() {
  • Object v = value;
  • if (v == this || v == BASE_HEADER)
  • /**
  • * 当节点value为自己,或节点value为BASE_HEADER时
  • * 表示节点是标记节点或头节点,此时直接返回null
  • */
  • return null;
  • // 否则返回value
  • return (V) v;
  • }
  • /**
  • * Creates and returns a new SimpleImmutableEntry holding current
  • * mapping if this node holds a valid value, else null.
  • * <p>
  • * 返回一个SimpleImmutableEntry对象
  • *
  • * @return new entry or null
  • */
  • AbstractMap.SimpleImmutableEntry<K, V> createSnapshot() {
  • V v = getValidValue();
  • if (v == null)
  • return null;
  • return new AbstractMap.SimpleImmutableEntry<K, V>(key, v);
  • }
  • // UNSAFE mechanics
  • 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;
  • // value成员变量的偏移量
  • valueOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("value"));
  • // next成员变量的偏移量
  • nextOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("next"));
  • } catch (Exception e) {
  • throw new Error(e);
  • }
  • }
  • }

Node类的构造方法Node(Node<K, V> next)用于构建一个标记节点,这种节点使用this.value = this;value的值指向了自己,同时还提供了isMarker()方法用于判断节点是否是标记节点。appendMarker(Node<K, V>)方法则会将当前节点的后继节点修改为一个标记节点,标识当前节点是一个被删除的节点;helpDelete(Node<K, V>, Node<K, V>)方法的作用则是辅助删除被标记为已删除的节点。appendMarker(Node<K, V>)helpDelete(Node<K, V>, Node<K, V>)这两个方法虽然代码简单,但逻辑比较,大家可以仔细阅读源码和注释进行理解。

另外,在ConcurrentSkipListMap中还定义了一个基础头节点,它也是一个Node实例,但其value被固定为常量BASE_HEADER,即一个Object对象。Node类提供了isBaseHeader()来判断节点是否是基础头节点。

需要注意的是,Node类为valuenext变量分别提供了CAS修改方法,保证在并发情景下对其修改过程的一致性。getValidValue()方法则用于获取有效节点的值,规避基础头节点和标记节点这两类无效节点。

总体来说,Node类的设计相对复杂,尤其是标记节点的相关操作,这里大家只需要对标记节点有一个印象,在后面的内容中会结合实际操作详细介绍标记节点的用处。

4.2. Index类的设计

Index类是构成跳表框架的主要类,它包括一个Node节点的引用,用于存储键值对数据,另外还包括两个指向引用:rightdown,用于跳表框架的构建,源码如下:

  • static class Index<K, V> {
  • // 对节点的引用
  • final Node<K, V> node;
  • // 下指针
  • final Index<K, V> down;
  • // 右指针
  • volatile Index<K, V> right;
  • /**
  • * Creates index node with given values.
  • */
  • Index(Node<K, V> node, Index<K, V> down, Index<K, V> right) {
  • this.node = node;
  • this.down = down;
  • this.right = right;
  • }
  • /**
  • * compareAndSet right field
  • * CAS方式修改右指针的指向,将其由指向cmp改为指向val
  • */
  • final boolean casRight(Index<K, V> cmp, Index<K, V> val) {
  • return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);
  • }
  • /**
  • * Returns true if the node this indexes has been deleted.
  • * 当前index的node被删除时返回true
  • * 即当node.value为null时返回true
  • *
  • * @return true if indexed node is known to be deleted
  • */
  • final boolean indexesDeletedNode() {
  • return node.value == null;
  • }
  • /**
  • * Tries to CAS newSucc as successor. To minimize races with
  • * unlink that may lose this index node, if the node being
  • * indexed is known to be deleted, it doesn't try to link in.
  • * <p>
  • * CAS方式将newSucc指定为后继(右指针)
  • * 即在当前Index的后面插入newSucc节点
  • *
  • * @param succ the expected current successor
  • * @param newSucc the new successor
  • * @return true if successful
  • */
  • final boolean link(Index<K, V> succ, Index<K, V> newSucc) {
  • // node引用
  • Node<K, V> n = node;
  • // 将之前的succ作为newSucc的后继
  • newSucc.right = succ;
  • // 然后将newSucc作为当前Index的后继
  • return n.value != null && casRight(succ, newSucc);
  • }
  • /**
  • * Tries to CAS right field to skip over apparent successor
  • * succ. Fails (forcing a retraversal by caller) if this node
  • * is known to be deleted.
  • * <p>
  • * CAS方式跳过当前后继(右指针指向)
  • *
  • * @param succ the expected current successor
  • * @return true if successful
  • */
  • final boolean unlink(Index<K, V> succ) {
  • return !indexesDeletedNode() && casRight(succ, succ.right);
  • }
  • // Unsafe mechanics
  • private static final sun.misc.Unsafe UNSAFE;
  • private static final long rightOffset;
  • static {
  • try {
  • UNSAFE = sun.misc.Unsafe.getUnsafe();
  • Class k = Index.class;
  • // right指针的偏移量
  • rightOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("right"));
  • } catch (Exception e) {
  • throw new Error(e);
  • }
  • }
  • }

Index的结构是比较简单的,提供了casRight(Index<K, V>, Index<K, V>)方法来CAS方式修改right右指针的值;另外link(Index<K, V>, Index<K, V>)unlink(Index<K, V>)分别用于插入及删除Index节点。

4.3. HeadIndex类的设计

HeadIndex继承自Index类,在其基础上扩展了属于自己的level成员变量:

  • /**
  • * Nodes heading each level keep track of their level.
  • * 继承自Index
  • */
  • 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;
  • }
  • }

level成员变量用于标识HeadIndex的级别,关于级别的内容会在后面讲解。

4.4. ConcurrentSkipListMap类的设计

我们再来看看ConcurrentSkipListMap类的设计;ConcurrentSkipListMap的整体设计非常复杂,这里先关注基础设计,具体的各类操作将在后面的内容中讲解。

4.4.1. 静态代码块相关

先关注其静态代码块的部分,代码如下:

  • // Unsafe mechanics
  • private static final sun.misc.Unsafe UNSAFE;
  • // head字段的偏移量
  • private static final long headOffset;
  • static {
  • try {
  • UNSAFE = sun.misc.Unsafe.getUnsafe();
  • Class k = ConcurrentSkipListMap.class;
  • // Unsafe取head字段的偏移量
  • headOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("head"));
  • } catch (Exception e) {
  • throw new Error(e);
  • }
  • }

ConcurrentSkipListMap在静态代码块中仅仅使用Unsafe方法获取了head字段的偏移量;head字段是一个HeadIndex对象,代表最顶层头节点,定义如下:

  • /**
  • * The topmost head index of the skiplist.
  • * 最顶层头节点
  • */
  • private transient volatile HeadIndex<K, V> head;

head字段使用transient和volatile,保证了其内存可见性,但放弃了对它序列化。

4.4.2. 各类变量和常量

ConcurrentSkipListMap中用到的变量和常量如下:

  • private static final long serialVersionUID = -8627078645895051609L;
  • /**
  • * Generates the initial random seed for the cheaper per-instance
  • * random number generators used in randomLevel.
  • * 生成随机种子
  • */
  • private static final Random seedGenerator = new Random();
  • /**
  • * Special value used to identify base-level header
  • * 基础级别的头节点
  • */
  • private static final Object BASE_HEADER = new Object();
  • /**
  • * The topmost head index of the skiplist.
  • * 最顶层头节点
  • */
  • private transient volatile HeadIndex<K, V> head;
  • /**
  • * The comparator used to maintain order in this map, or null
  • * if using natural ordering.
  • * <p>
  • * 用于排序的比较器,当为null时则使用自然排序
  • *
  • * @serial
  • */
  • private final Comparator<? super K> comparator;
  • /**
  • * Seed for simple random number generator. Not volatile since it
  • * doesn't matter too much if different threads don't see updates.
  • * <p>
  • * 随机数种子
  • */
  • private transient int randomSeed;
  • /**
  • * Lazily initialized key set
  • * 键集
  • */
  • private transient KeySet keySet;
  • /**
  • * Lazily initialized entry set
  • * 键值对集
  • */
  • private transient EntrySet entrySet;
  • /**
  • * Lazily initialized values collection
  • * 值集
  • */
  • private transient Values values;
  • /**
  • * Lazily initialized descending key set
  • * 降序键集
  • */
  • private transient ConcurrentNavigableMap<K, V> descendingMap;

这些字段都比较简单,大家只需要脑海中有个印象即可,可以特别关注BASE_HEADERhead的意义。

5. ConcurrentSkipListMap源码完整注释

下面先给出ConcurrentSkipListMap源码的完整注释版本,关于源码的讲解将在后面的文章中详细剖析。

  • package java.util.concurrent;
  • import java.util.*;
  • import java.util.concurrent.atomic.*;
  • public class ConcurrentSkipListMap<K, V> extends AbstractMap<K, V>
  • implements ConcurrentNavigableMap<K, V>,
  • Cloneable,
  • java.io.Serializable {
  • private static final long serialVersionUID = -8627078645895051609L;
  • /**
  • * Generates the initial random seed for the cheaper per-instance
  • * random number generators used in randomLevel.
  • * 生成随机种子
  • */
  • private static final Random seedGenerator = new Random();
  • /**
  • * Special value used to identify base-level header
  • * 基础级别的头节点
  • */
  • private static final Object BASE_HEADER = new Object();
  • /**
  • * The topmost head index of the skiplist.
  • * 最顶层头节点
  • */
  • private transient volatile HeadIndex<K, V> head;
  • /**
  • * The comparator used to maintain order in this map, or null
  • * if using natural ordering.
  • * <p>
  • * 用于排序的比较器,当为null时则使用自然排序
  • *
  • * @serial
  • */
  • private final Comparator<? super K> comparator;
  • /**
  • * Seed for simple random number generator. Not volatile since it
  • * doesn't matter too much if different threads don't see updates.
  • * <p>
  • * 随机数种子
  • */
  • private transient int randomSeed;
  • /**
  • * Lazily initialized key set
  • * 键集
  • */
  • private transient KeySet keySet;
  • /**
  • * Lazily initialized entry set
  • * 键值对集
  • */
  • private transient EntrySet entrySet;
  • /**
  • * Lazily initialized values collection
  • * 值集
  • */
  • private transient Values values;
  • /**
  • * Lazily initialized descending key set
  • * 降序键集
  • */
  • private transient ConcurrentNavigableMap<K, V> descendingMap;
  • /**
  • * Initializes or resets state. Needed by constructors, clone,
  • * clear, readObject. and ConcurrentSkipListSet.clone.
  • * (Note that comparator must be separately initialized.)
  • */
  • final void initialize() {
  • keySet = null;
  • entrySet = null;
  • values = null;
  • descendingMap = null;
  • // 最小为4
  • randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
  • head = new HeadIndex<K, V>(new Node<K, V>(null, BASE_HEADER, null), null, null, 1);
  • }
  • /**
  • * compareAndSet head node
  • */
  • private boolean casHead(HeadIndex<K, V> cmp, HeadIndex<K, V> val) {
  • return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
  • }
  • /* ---------------- Nodes -------------- */
  • /**
  • * Nodes hold keys and values, and are singly linked in sorted
  • * order, possibly with some intervening marker nodes. The list is
  • * headed by a dummy node accessible as head.node. The value field
  • * is declared only as Object because it takes special non-V
  • * values for marker and header nodes.
  • */
  • static final class Node<K, V> {
  • // 键
  • final K key;
  • // 值
  • volatile Object value;
  • // 后继节点
  • volatile Node<K, V> next;
  • /**
  • * Creates a new regular node.
  • * 根据键值对、后继节点构造一个节点
  • */
  • Node(K key, Object value, Node<K, V> next) {
  • this.key = key;
  • this.value = value;
  • this.next = next;
  • }
  • /**
  • * Creates a new marker node. A marker is distinguished by
  • * having its value field point to itself. Marker nodes also
  • * have null keys, a fact that is exploited in a few places,
  • * but this doesn't distinguish markers from the base-level
  • * header node (head.node), which also has a null key.
  • * <p>
  • * 标记节点,特征是它的key为null,value指向了自己
  • */
  • Node(Node<K, V> next) {
  • this.key = null;
  • this.value = this;
  • this.next = next;
  • }
  • /**
  • * compareAndSet value field
  • * CAS修改value为val
  • */
  • boolean casValue(Object cmp, Object val) {
  • return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val);
  • }
  • /**
  • * compareAndSet next field
  • * CAS修改后继节点
  • */
  • boolean casNext(Node<K, V> cmp, Node<K, V> val) {
  • return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
  • }
  • /**
  • * Returns true if this node is a marker. This method isn't
  • * actually called in any current code checking for markers
  • * because callers will have already read value field and need
  • * to use that read (not another done here) and so directly
  • * test if value points to node.
  • * <p>
  • * 判断是否是标记节点,根据value值是否是自己来判断
  • *
  • * @return true if this node is a marker node
  • */
  • boolean isMarker() {
  • return value == this;
  • }
  • /**
  • * Returns true if this node is the header of base-level list.
  • * 判断是否是基础头节点
  • *
  • * @return true if this node is header node
  • */
  • boolean isBaseHeader() {
  • return value == BASE_HEADER;
  • }
  • /**
  • * Tries to append a deletion marker to this node.
  • * 尝试添加一个删除标记到当前节点的后继节点
  • *
  • * 新建一个标记节点,将传入的f作为该标记节点的后继节点,
  • * 然后将该标记节点设置为当前节点的后继节点
  • *
  • * @param f the assumed current successor of this node
  • * @return true if successful
  • */
  • boolean appendMarker(Node<K, V> f) {
  • return casNext(f, new Node<K, V>(f));
  • }
  • /**
  • * Helps out a deletion by appending marker or unlinking from
  • * predecessor. This is called during traversals when value
  • * field seen to be null.
  • * <p>
  • * 通过添加标记节点或与前驱节点断开连接以协助删除
  • *
  • * @param b predecessor
  • * @param f successor
  • */
  • void helpDelete(Node<K, V> b, Node<K, V> f) {
  • /*
  • * Rechecking links and then doing only one of the
  • * help-out stages per call tends to minimize CAS
  • * interference among helping threads.
  • */
  • // 条件:f是当前节点的后继节点,且b是当前节点的前驱节点
  • if (f == next && this == b.next) {
  • if (f == null || f.value != f) // not already marked
  • /**
  • * 走到这里,有两种情况:
  • * 1. f为null;
  • * 2. f不为null,但f的value值不是自己,即f不是标记节点
  • *
  • * 这一步会构建一个标记节点,后继是f,然后把当前节点指向该标记节点,即:
  • * 原来是这样的:b -> current -> f
  • * 现在是这样的:b -> current -> marker -> f
  • */
  • appendMarker(f);
  • else
  • /**
  • * 走到这里,且f不为null,但f是标记节点
  • * 这一步会将b的后继设置为f的后继,即:
  • * 原来是这样的:b -> current -> f(marker) -> f.next
  • * 修改后是这样的:b -> f.next
  • * 即将current和f都删除了
  • */
  • b.casNext(this, f.next);
  • }
  • }
  • /**
  • * Returns value if this node contains a valid key-value pair,
  • * else null.
  • * <p>
  • * 获取校验后的值,防止取到头节点或标记节点
  • *
  • * @return this node's value if it isn't a marker or header or
  • * is deleted, else null.
  • */
  • V getValidValue() {
  • Object v = value;
  • if (v == this || v == BASE_HEADER)
  • /**
  • * 当节点value为自己,或节点value为BASE_HEADER时
  • * 表示节点是标记节点或头节点,此时直接返回null
  • */
  • return null;
  • // 否则返回value
  • return (V) v;
  • }
  • /**
  • * Creates and returns a new SimpleImmutableEntry holding current
  • * mapping if this node holds a valid value, else null.
  • * <p>
  • * 返回一个SimpleImmutableEntry对象
  • *
  • * @return new entry or null
  • */
  • AbstractMap.SimpleImmutableEntry<K, V> createSnapshot() {
  • V v = getValidValue();
  • if (v == null)
  • return null;
  • return new AbstractMap.SimpleImmutableEntry<K, V>(key, v);
  • }
  • // UNSAFE mechanics
  • 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;
  • // value成员变量的偏移量
  • valueOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("value"));
  • // next成员变量的偏移量
  • nextOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("next"));
  • } catch (Exception e) {
  • throw new Error(e);
  • }
  • }
  • }
  • /* ---------------- Indexing -------------- */
  • /**
  • * Index nodes represent the levels of the skip list. Note that
  • * even though both Nodes and Indexes have forward-pointing
  • * fields, they have different types and are handled in different
  • * ways, that can't nicely be captured by placing field in a
  • * shared abstract class.
  • */
  • static class Index<K, V> {
  • // 对节点的引用
  • final Node<K, V> node;
  • // 下指针
  • final Index<K, V> down;
  • // 右指针
  • volatile Index<K, V> right;
  • /**
  • * Creates index node with given values.
  • */
  • Index(Node<K, V> node, Index<K, V> down, Index<K, V> right) {
  • this.node = node;
  • this.down = down;
  • this.right = right;
  • }
  • /**
  • * compareAndSet right field
  • * CAS方式修改右指针的指向,将其由指向cmp改为指向val
  • */
  • final boolean casRight(Index<K, V> cmp, Index<K, V> val) {
  • return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);
  • }
  • /**
  • * Returns true if the node this indexes has been deleted.
  • * 当前index的node被删除时返回true
  • * 即当node.value为null时返回true
  • *
  • * @return true if indexed node is known to be deleted
  • */
  • final boolean indexesDeletedNode() {
  • return node.value == null;
  • }
  • /**
  • * Tries to CAS newSucc as successor. To minimize races with
  • * unlink that may lose this index node, if the node being
  • * indexed is known to be deleted, it doesn't try to link in.
  • * <p>
  • * CAS方式将newSucc指定为后继(右指针)
  • * 即在当前Index的后面插入newSucc节点
  • *
  • * @param succ the expected current successor
  • * @param newSucc the new successor
  • * @return true if successful
  • */
  • final boolean link(Index<K, V> succ, Index<K, V> newSucc) {
  • // node引用
  • Node<K, V> n = node;
  • // 将之前的succ作为newSucc的后继
  • newSucc.right = succ;
  • // 然后将newSucc作为当前Index的后继
  • return n.value != null && casRight(succ, newSucc);
  • }
  • /**
  • * Tries to CAS right field to skip over apparent successor
  • * succ. Fails (forcing a retraversal by caller) if this node
  • * is known to be deleted.
  • * <p>
  • * CAS方式跳过当前后继(右指针指向)
  • *
  • * @param succ the expected current successor
  • * @return true if successful
  • */
  • final boolean unlink(Index<K, V> succ) {
  • return !indexesDeletedNode() && casRight(succ, succ.right);
  • }
  • // Unsafe mechanics
  • private static final sun.misc.Unsafe UNSAFE;
  • private static final long rightOffset;
  • static {
  • try {
  • UNSAFE = sun.misc.Unsafe.getUnsafe();
  • Class k = Index.class;
  • // right指针的偏移量
  • rightOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("right"));
  • } catch (Exception e) {
  • throw new Error(e);
  • }
  • }
  • }
  • /* ---------------- Head nodes -------------- */
  • /**
  • * Nodes heading each level keep track of their level.
  • * 继承自Index
  • */
  • 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;
  • }
  • }
  • /* ---------------- Comparison utilities -------------- */
  • /**
  • * Represents a key with a comparator as a Comparable.
  • * <p>
  • * Because most sorted collections seem to use natural ordering on
  • * Comparables (Strings, Integers, etc), most internal methods are
  • * geared to use them. This is generally faster than checking
  • * per-comparison whether to use comparator or comparable because
  • * it doesn't require a (Comparable) cast for each comparison.
  • * (Optimizers can only sometimes remove such redundant checks
  • * themselves.) When Comparators are used,
  • * ComparableUsingComparators are created so that they act in the
  • * same way as natural orderings. This penalizes use of
  • * Comparators vs Comparables, which seems like the right
  • * tradeoff.
  • */
  • static final class ComparableUsingComparator<K> implements Comparable<K> {
  • final K actualKey;
  • final Comparator<? super K> cmp;
  • ComparableUsingComparator(K key, Comparator<? super K> cmp) {
  • this.actualKey = key;
  • this.cmp = cmp;
  • }
  • public int compareTo(K k2) {
  • return cmp.compare(actualKey, k2);
  • }
  • }
  • /**
  • * If using comparator, return a ComparableUsingComparator, else
  • * cast key as Comparable, which may cause ClassCastException,
  • * which is propagated back to caller.
  • *
  • * 如果使用比较器,将返回一个ComparableUsingComparator
  • * 否则将key转换为Comparable对象,可能会抛出ClassCastException异常
  • */
  • private Comparable<? super K> comparable(Object key)
  • throws ClassCastException {
  • if (key == null)
  • throw new NullPointerException();
  • if (comparator != null)
  • // 使用构造器,构造一个ComparableUsingComparator实例,并返回
  • return new ComparableUsingComparator<K>((K) key, comparator);
  • else
  • // 不使用构造器,将key转换为Comparable对象
  • return (Comparable<? super K>) key;
  • }
  • /**
  • * Compares using comparator or natural ordering. Used when the
  • * ComparableUsingComparator approach doesn't apply.
  • */
  • int compare(K k1, K k2) throws ClassCastException {
  • Comparator<? super K> cmp = comparator;
  • if (cmp != null)
  • return cmp.compare(k1, k2);
  • else
  • return ((Comparable<? super K>) k1).compareTo(k2);
  • }
  • /**
  • * Returns true if given key greater than or equal to least and
  • * strictly less than fence, bypassing either test if least or
  • * fence are null. Needed mainly in submap operations.
  • */
  • boolean inHalfOpenRange(K key, K least, K fence) {
  • if (key == null)
  • throw new NullPointerException();
  • return ((least == null || compare(key, least) >= 0) &&
  • (fence == null || compare(key, fence) < 0));
  • }
  • /**
  • * Returns true if given key greater than or equal to least and less
  • * or equal to fence. Needed mainly in submap operations.
  • */
  • boolean inOpenRange(K key, K least, K fence) {
  • if (key == null)
  • throw new NullPointerException();
  • return ((least == null || compare(key, least) >= 0) &&
  • (fence == null || compare(key, fence) <= 0));
  • }
  • /* ---------------- Traversal -------------- */
  • /**
  • * Returns a base-level node with key strictly less than given key,
  • * or the base-level header if there is no such node. Also
  • * unlinks indexes to deleted nodes found along the way. Callers
  • * rely on this side-effect of clearing indices to deleted nodes.
  • *
  • * 根据传入的key,查找符合条件的前驱节点
  • *
  • * @param key the key
  • * @return a predecessor of key
  • */
  • private Node<K, V> findPredecessor(Comparable<? super K> key) {
  • if (key == null)
  • throw new NullPointerException(); // don't postpone errors
  • for (; ; ) {
  • // 头节点
  • Index<K, V> q = head;
  • Index<K, V> r = q.right;
  • for (; ; ) {
  • if (r != null) { // 头节点的右Index节点不为null
  • // 查看当前Index包装的Node节点
  • Node<K, V> n = r.node;
  • K k = n.key;
  • // 这一步if会尝试将失效的Index节点移除
  • if (n.value == null) {
  • /**
  • * value为空,表示这个Node节点已经被删除了
  • * 就调用unlink()将其从链表中移除,unlink()操作会将q的右节点换成r的右节点
  • * 移除成功会跳出内层循环;否则继续往下执行
  • */
  • if (!q.unlink(r))
  • // 跳出内层循环
  • break; // restart
  • // 走到这里说明unlink()操作失败,这一步会将r指向q新的右节点
  • r = q.right; // reread r
  • // 继续
  • continue;
  • }
  • /**
  • * 走到这里说明value不为null,对比key
  • * 当传入的key比遍历到的节点的k大,就继续往后移
  • * 即将q指向r,将r指向r的右节点(即后继)
  • * 然后继续下一个循环
  • */
  • if (key.compareTo(k) > 0) {
  • q = r;
  • r = r.right;
  • continue;
  • }
  • }
  • /**
  • * 走到这里有两种情况:
  • * 1. r为null;此时表示head节点没有右节点,所以需要查找下一层(也即是这一层已经找到末尾了)
  • * 2. r不为null,但key小于或等于k
  • * 注:r为q的后继节点
  • */
  • // 获取head的下节点
  • Index<K, V> d = q.down;
  • if (d != null) {
  • /**
  • * 下节点不为null,将q指向该下节点,将r指向下节点的右节点
  • * 这个操作相当于往下移了一层,因为当前层已经没有可找的了
  • */
  • q = d;
  • r = d.right;
  • } else
  • /**
  • * 走到这里,说明d为null,即只有一层,因此直接将当前q的Node返回
  • * 此时应该有两种情况:
  • * 1. q的右节点r(即后继节点)不为null时,但r的key比传入的key大;
  • * 2. q的右节点r为null;
  • * 这两种情况下,q的Node就应该是要找的前驱节点
  • */
  • return q.node;
  • }
  • }
  • }
  • /**
  • * Returns node holding key or null if no such, clearing out any
  • * deleted nodes seen along the way. Repeatedly traverses at
  • * base-level looking for key starting at predecessor returned
  • * from findPredecessor, processing base-level deletions as
  • * encountered. Some callers rely on this side-effect of clearing
  • * deleted nodes.
  • * <p>
  • * Restarts occur, at traversal step centered on node n, if:
  • * <p>
  • * (1) After reading n's next field, n is no longer assumed
  • * predecessor b's current successor, which means that
  • * we don't have a consistent 3-node snapshot and so cannot
  • * unlink any subsequent deleted nodes encountered.
  • * <p>
  • * (2) n's value field is null, indicating n is deleted, in
  • * which case we help out an ongoing structural deletion
  • * before retrying. Even though there are cases where such
  • * unlinking doesn't require restart, they aren't sorted out
  • * here because doing so would not usually outweigh cost of
  • * restarting.
  • * <p>
  • * (3) n is a marker or n's predecessor's value field is null,
  • * indicating (among other possibilities) that
  • * findPredecessor returned a deleted node. We can't unlink
  • * the node because we don't know its predecessor, so rely
  • * on another call to findPredecessor to notice and return
  • * some earlier predecessor, which it will do. This check is
  • * only strictly needed at beginning of loop, (and the
  • * b.value check isn't strictly needed at all) but is done
  • * each iteration to help avoid contention with other
  • * threads by callers that will fail to be able to change
  • * links, and so will retry anyway.
  • * <p>
  • * The traversal loops in doPut, doRemove, and findNear all
  • * include the same three kinds of checks. And specialized
  • * versions appear in findFirst, and findLast and their
  • * variants. They can't easily share code because each uses the
  • * reads of fields held in locals occurring in the orders they
  • * were performed.
  • *
  • * @param key the key
  • * @return node holding key, or null if no such
  • */
  • private Node<K, V> findNode(Comparable<? super K> key) {
  • // 无限循环
  • for (; ; ) {
  • // 尝试找到符合条件的key的前驱节点
  • Node<K, V> b = findPredecessor(key);
  • // 获取b的后继节点
  • Node<K, V> n = b.next;
  • for (; ; ) {
  • // n为null,表示没找到,直接返回null
  • if (n == null)
  • return null;
  • // 得到n的后继节点
  • Node<K, V> f = n.next;
  • // 检查b的后继是否被改变,如果改变就跳出内层循环
  • if (n != b.next) // inconsistent read
  • break;
  • // 获取n的value
  • Object v = n.value;
  • // n的value为null表示n已经被删掉了
  • if (v == null) { // n is deleted
  • // 调用helpDelete()方法将其删除,并跳出内层循环
  • n.helpDelete(b, f);
  • break;
  • }
  • // 走到这里说明n的value不为null
  • if (v == n || b.value == null) // b is deleted
  • /**
  • * 两种情况:
  • * 1. v == n说明n是标记节点
  • * 2. v != n,但b.value为null,说明b是被删除的节点
  • * 跳出内层循环
  • */
  • break;
  • // 比较key和n的key的大小
  • int c = key.compareTo(n.key);
  • // key和n的key相同,表示找到
  • if (c == 0)
  • return n;
  • // 表示没有找到
  • if (c < 0)
  • return null;
  • // 往后移,跳出进行下一次循环,即往后遍历
  • b = n;
  • n = f;
  • }
  • }
  • }
  • /**
  • * Gets value for key using findNode.
  • *
  • * @param okey the key
  • * @return the value, or null if absent
  • */
  • private V doGet(Object okey) {
  • // 包装传入的key为Comparable类型实例
  • Comparable<? super K> key = comparable(okey);
  • /*
  • * Loop needed here and elsewhere in case value field goes
  • * null just as it is about to be returned, in which case we
  • * lost a race with a deletion, so must retry.
  • */
  • // 无限循环
  • for (; ; ) {
  • // 找到对应的节点
  • Node<K, V> n = findNode(key);
  • if (n == null)
  • // 没找到,直接返回null
  • return null;
  • // 找到节点了,检查value
  • Object v = n.value;
  • if (v != null)
  • // value不为null,直接返回value
  • return (V) v;
  • }
  • }
  • /* ---------------- Insertion -------------- */
  • /**
  • * Main insertion method. Adds element if not present, or
  • * replaces value if present and onlyIfAbsent is false.
  • *
  • * @param kkey the key
  • * @param value the value that must be associated with key
  • * @param onlyIfAbsent if should not insert if already present 是否只在不存在时添加
  • * @return the old value, or null if newly inserted 旧值(当覆盖、或onlyIfAbsent为true但key已存在时),或者null(新添加)
  • */
  • private V doPut(K kkey, V value, boolean onlyIfAbsent) {
  • /**
  • * 在comparable()方法中,key为null会抛出NullPointerException。
  • * 这个地方得到的key其实就是一个Comparable类型实例,可能是ComparableUsingComparator对象
  • * ComparableUsingComparator将key和Comparator封装了一下
  • */
  • Comparable<? super K> key = comparable(kkey);
  • // 无限循环
  • for (; ; ) {
  • /**
  • * 在跳表中尝试找到符合条件的key的前驱节点
  • * 查找的规则在于:跳表中底层Node的key比上层的key要大,Node链中后面Node的key比前面的key要大
  • * 因此查找时是从上往下,从前往后找
  • */
  • Node<K, V> b = findPredecessor(key);
  • // 获取b的后继节点
  • Node<K, V> n = b.next;
  • // 无限循环
  • for (; ; ) {
  • if (n != null) {
  • // b的后继节点n不为null,得到n的后继节点
  • Node<K, V> f = n.next;
  • // 检查b的后继是否被改变,如果改变就跳出内层循环
  • if (n != b.next) // inconsistent read
  • break;
  • // 获取n的value
  • Object v = n.value;
  • // n的value为null表示n已经被删掉了
  • if (v == null) { // n is deleted
  • /**
  • * 调用helpDelete()方法将其删除,并跳出内层循环
  • * 此时可能返回的情况可能有两种:
  • * 修改前:b -> n -> f -> f.next(f.next可能有,也可能没有)
  • * 修改后:
  • * 1. b -> n -> marker -> f
  • * 2. b -> f.next
  • * 然后跳出内层循环
  • */
  • n.helpDelete(b, f);
  • break;
  • }
  • // 走到这里说明n的value不为null
  • if (v == n || b.value == null) // b is deleted
  • /**
  • * 两种情况:
  • * 1. v == n说明n是标记节点
  • * 2. v != n,但b.value为null,说明b是被删除的节点
  • * 跳出内层循环
  • */
  • break;
  • // 比较key和n的key的大小
  • int c = key.compareTo(n.key);
  • if (c > 0) {
  • /**
  • * 要比n的key大,就往后移,跳出进行下一次循环,即往后遍历:
  • * 之前:b -> n -> f
  • * 现在:(old b) -> b(old n) -> n(old f)
  • */
  • b = n;
  • n = f;
  • continue;
  • }
  • if (c == 0) {
  • /**
  • * key与n的key相等,则表示键已存在,此时如果onlyIfAbsent为false,
  • * 就修改n的value为新value,如果修改成功就返回旧value,
  • * 如果onlyIfAbsent为true,则直接返回value,不做任何处理,
  • * 否则进行下一次尝试
  • */
  • if (onlyIfAbsent || n.casValue(v, value))
  • return (V) v;
  • else
  • // 否则跳出内层循环
  • break; // restart if lost race to replace value
  • }
  • // else c < 0; fall through
  • }
  • /**
  • * 走到这里有两种情况:
  • * 1. n为null;此时b就是新节点的前驱
  • * 2. n不为null,且已经确认传入的key小于等于n的key,因此n就是新节点的后继,b就是新节点的前驱
  • */
  • // 构建一个新节点z,将n作为该节点的后继
  • Node<K, V> z = new Node<K, V>(kkey, value, n);
  • // CAS修改b的后继为新节点z,如果修改不成功就跳出内层循环
  • if (!b.casNext(n, z))
  • break; // restart if lost race to append to b
  • // 随机一个级别,这个方法后面讲解
  • int level = randomLevel();
  • if (level > 0)
  • // 插入一个级别
  • insertIndex(z, level);
  • return null;
  • }
  • }
  • }
  • /**
  • * Returns a random level for inserting a new node.
  • * Hardwired to k=1, p=0.5, max 31 (see above and
  • * Pugh's "Skip List Cookbook", sec 3.4).
  • * <p>
  • * This uses the simplest of the generators described in George
  • * Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
  • * generator but is acceptable here.
  • *
  • * 为即将插入的新的Index节点生成一个随机级别,
  • * 这里使用的算法是Pugh's的论文《Skip List Cookbook》中3.4节提到的内容,
  • * 保持level级别在1 ~ 31之间。
  • * 这使用了George Marsaglia的《Xorshift RNGs》论文中描述的最简单的生成器。
  • * 这个生成器并不完美,但在这里是可以接受的。
  • */
  • private int randomLevel() {
  • int x = randomSeed;
  • x ^= x << 13;
  • x ^= x >>> 17;
  • randomSeed = x ^= x << 5;
  • if ((x & 0x80000001) != 0) // test highest and lowest bits
  • return 0;
  • int level = 1;
  • while (((x >>>= 1) & 1) != 0) ++level;
  • return level;
  • }
  • /**
  • * Creates and adds index nodes for the given node.
  • *
  • * 根据Node节点和随机级别添加对应的Index节点
  • *
  • * @param z the node Node数据节点
  • * @param level the level of the index 随机级别
  • */
  • private void insertIndex(Node<K, V> z, int level) {
  • HeadIndex<K, V> h = head;
  • // 当前head节点的level
  • int max = h.level;
  • /**
  • * 如果插入的level小于等于max,则不用创建新层级,
  • * 只需要构建相应层级的Index列,添加到跳表中即可
  • */
  • if (level <= max) {
  • Index<K, V> idx = null;
  • /**
  • * 循环创建Index节点,
  • * 这种循环方式可以构建一列Index节点,
  • * 最终idx指向最顶层的那个Index节点,这一列Index节点的node都指向z
  • * 即假设level为2,则最终会有这样的结构:
  • * Index(idx)
  • * |
  • * Index
  • * |
  • * Node(z)
  • */
  • for (int i = 1; i <= level; ++i)
  • idx = new Index<K, V>(z, idx, null);
  • // 使用addIndex()方法将idx添加到跳表中,后面分析
  • addIndex(idx, h, level);
  • } else { // Add a new level
  • /*
  • * To reduce interference by other threads checking for
  • * empty levels in tryReduceLevel, new levels are added
  • * with initialized right pointers. Which in turn requires
  • * keeping levels in an array to access them while
  • * creating new head index nodes from the opposite
  • * direction.
  • *
  • * 走到这里,说明level比head的level还要大,
  • * 因此需要添加一个新的层级,即需要构建新的HeadIndex
  • */
  • // 指定新层级只比当前层级大1
  • level = max + 1;
  • // 将要创建的Index放在一个数组中
  • Index<K, V>[] idxs = (Index<K, V>[]) new Index[level + 1];
  • Index<K, V> idx = null;
  • // 循环创建Index节点,效果与上面的一样;并把创建的Index节点放在idxs数组中
  • for (int i = 1; i <= level; ++i)
  • idxs[i] = idx = new Index<K, V>(z, idx, null);
  • HeadIndex<K, V> oldh;
  • int k;
  • for (; ; ) {
  • // 旧的head
  • oldh = head;
  • // 旧的head的级别
  • int oldLevel = oldh.level;
  • if (level <= oldLevel) { // lost race to add level
  • /**
  • * 执行到这里,说明存在并发情况,
  • * 其他线程由于维护了级别,导致head节点的级别出现了增加,
  • * 因此直接记录level,跳出for循环,由addIndex()完成添加Index操作
  • */
  • k = level;
  • break;
  • }
  • //
  • HeadIndex<K, V> newh = oldh;
  • // 旧的HeadIndex指向的Node节点
  • Node<K, V> oldbase = oldh.node;
  • // 从旧的HeadIndex节点层级加1开始,一直到level级别,创建新的HeadIndex
  • for (int j = oldLevel + 1; j <= level; ++j)
  • /**
  • * 所有新的HeadIndex的层级为j,node都指向oldbase
  • * right指向对应层级的Index(从idxs中获取),down指向当前顶层的HeadIndex
  • * 具体效果如下:
  • * HeadIndex(level) -> Index(idxs[level])
  • * | |
  • * ...... ......
  • * | |
  • * HeadIndex(oldLevel + 1) -> Index(idxs[oldLevel + 1])
  • * | |
  • * HeadIndex(oldLevel) -> Index(idxs[level])
  • */
  • newh = new HeadIndex<K, V>(oldbase, newh, idxs[j], j);
  • // 修改head
  • if (casHead(oldh, newh)) {
  • // 如果修改成功,就记录旧的层级,并跳出for循环,由addIndex()完成添加Index操作
  • k = oldLevel;
  • break;
  • }
  • }
  • // 会将构建好的一列Index添加到跳表中
  • addIndex(idxs[k], oldh, k);
  • }
  • }
  • /**
  • * Adds given index nodes from given level down to 1.
  • * 添加Index节点
  • *
  • * @param idx the topmost index node being inserted 最高层的将被插入的节点
  • * @param h the value of head to use to insert. This must be
  • * snapshotted by callers to provide correct insertion level
  • * @param indexLevel the level of the index 插入的级别
  • */
  • private void addIndex(Index<K, V> idx, HeadIndex<K, V> h, int indexLevel) {
  • // Track next level to insert in case of retries
  • // 跟踪下一个待插入的级别,用于重试
  • int insertionLevel = indexLevel;
  • // 包装idx中node节点的key
  • Comparable<? super K> key = comparable(idx.node.key);
  • // 检查key
  • if (key == null) throw new NullPointerException();
  • // Similar to findPredecessor, but adding index nodes along path to key.
  • // 与findPredecessor()类似,但会根据遍历到相应key的路径添加Index节点
  • for (; ; ) {
  • // 头节点的级别
  • int j = h.level;
  • // 记录头节点
  • Index<K, V> q = h;
  • // 头节点的后继节点
  • Index<K, V> r = q.right;
  • // 待插入的Index节点
  • Index<K, V> t = idx;
  • for (; ; ) {
  • if (r != null) { // 头节点的后继节点不为null
  • // 取出该后继节点的Node
  • Node<K, V> n = r.node;
  • // compare before deletion check avoids needing recheck
  • // 与传入的待插入Index节点比较Node节点的key
  • int c = key.compareTo(n.key);
  • // 如果头节点的后继节点r中node的value为null,表明该节点被删除了
  • if (n.value == null) {
  • /**
  • * 调用unlink()将其从链中移除
  • * 移除之前:q -> r -> r.right
  • * 移除之后:q -> r.right
  • */
  • if (!q.unlink(r))
  • // 移除不成功就跳出内层循环重试
  • break;
  • // 此时表示移除r成功,将q新的后继节点赋值给r,进行下一次内层循环
  • r = q.right;
  • continue;
  • }
  • // 走到这里表示r不是被删除的节点
  • if (c > 0) {
  • // 如果传入的节点idx的key比r所代表节点的key大,则往后移,并继续查找
  • q = r;
  • r = r.right;
  • continue;
  • }
  • }
  • /**
  • * 走到这里,说明待插入Index节点的node的key小于或等于r节点的node的key
  • * 即已经找到了Index节点正确的待插入位置
  • * 需要判断当前待插入Index节点的级别与q与r的级别是否相同,
  • * 如果相同则可以插入,如果不同,应该在当前层的下面层进行尝试插入,
  • * 以保持插入节点后Index列的高度与HeadIndex列的高度保持低部对齐
  • */
  • if (j == insertionLevel) { // 待插入Index节点的级别等于头节点的级别
  • // Don't insert index if node already deleted
  • // 检查待插入的Index节点的Node节点是否是被删除的节点
  • if (t.indexesDeletedNode()) {
  • // 待插入的Index节点中的Node节点是一个被删除的节点
  • // findNode(key)方法的代码会移除已标记为删除的节点
  • findNode(key); // cleans up
  • // 返回,结束这次Index节点的插入
  • return;
  • }
  • /**
  • * 可以插入,将r作为t的后继,然后将t作为q的后继,即将t插在r的前面,q的后面
  • * 插入前:q -> r -> r.right
  • * 插入后:q -> t -> r -> r.right
  • */
  • if (!q.link(r, t))
  • // 插入不成功,跳出内层循环重试
  • break; // restart
  • // 插入成功,insertionLevel自减后为0时,就可以返回了
  • if (--insertionLevel == 0) {
  • // need final deletion check before return
  • // 返回之前检查t是否被删除了,如果被删除了就调用findNode(key)进行清理
  • if (t.indexesDeletedNode())
  • // findNode(key)方法的代码会移除已标记为删除的节点
  • findNode(key);
  • // 返回
  • return;
  • }
  • }
  • /**
  • * 走到这里,有两种情况:
  • * 1. 尝试插入Index时,发现需要连接的前驱Index和后继Index与待插入的Index不在一个层级,因此需要下潜一层再尝试插入
  • * 2. Index插入成功了,但insertionLevel自减后还不为0,即表示插入的Index其实是一个多层的列,还剩余有层级没有进行连接处理
  • */
  • if (--j >= insertionLevel && j < indexLevel)
  • // 下潜到待插入Index列的下一层级
  • t = t.down;
  • // 前驱节点也下潜,然后进行下一次内层循环,处理该层级待插入的Index节点的连接
  • q = q.down;
  • r = q.right;
  • }
  • }
  • }
  • /* ---------------- Deletion -------------- */
  • /**
  • * Main deletion method. Locates node, nulls value, appends a
  • * deletion marker, unlinks predecessor, removes associated index
  • * nodes, and possibly reduces head index level.
  • * <p>
  • * Index nodes are cleared out simply by calling findPredecessor.
  • * which unlinks indexes to deleted nodes found along path to key,
  • * which will include the indexes to this node. This is done
  • * unconditionally. We can't check beforehand whether there are
  • * index nodes because it might be the case that some or all
  • * indexes hadn't been inserted yet for this node during initial
  • * search for it, and we'd like to ensure lack of garbage
  • * retention, so must call to be sure.
  • *
  • * 主要的删除方法。
  • * 定位Node节点,将其值置为null,添加删除标记节点,与前驱节点断开连接,删除辅助索引节点,
  • * 还有可能会减少头节点的层级。
  • *
  • * 索引节点的清理是由findPredecessor()方法完成的
  • *
  • * @param okey 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 okey, Object value) {
  • // 包装传入的key为Comparable类型实例
  • Comparable<? super K> key = comparable(okey);
  • for (; ; ) {
  • // 找到符合条件的key的前驱节点
  • Node<K, V> b = findPredecessor(key);
  • // 获取b的后继节点
  • Node<K, V> n = b.next;
  • // 无限循环
  • for (; ; ) {
  • if (n == null)
  • // n为null,表示要删除的节点不存在,直接返回null
  • return null;
  • // f为n的后继节点
  • Node<K, V> f = n.next;
  • // 检查b的后继是否被改变,如果改变就跳出内层循环
  • if (n != b.next) // inconsistent read
  • break;
  • // 获取n的value
  • Object v = n.value;
  • // n的value为null表示n已经被删掉了
  • if (v == null) { // n is deleted
  • // 调用helpDelete()方法将其删除,并跳出内层循环
  • n.helpDelete(b, f);
  • break;
  • }
  • // 走到这里说明n的value不为null
  • if (v == n || b.value == null) // b is deleted
  • /**
  • * 两种情况:
  • * 1. v == n说明n是标记节点
  • * 2. v != n,但b.value为null,说明b是被删除的节点
  • * 跳出内层循环
  • */
  • break;
  • // 比较key和n的key的大小
  • int c = key.compareTo(n.key);
  • if (c < 0)
  • /**
  • * 表示没有找到
  • * 注意,此时b是key符合条件的前驱,而n是b的后继,
  • * 如果此时传入的key比n的key小,说明key对应的节点在n的前面,
  • * 而此时b和n是连接起来的前后两个节点,这种情况下key所对应的节点是不存在的
  • */
  • return null;
  • if (c > 0) {
  • /**
  • * 要比n的key大,就往后移,跳出进行下一次循环,即往后遍历:
  • * 之前:b -> n -> f
  • * 现在:(old b) -> b(old n) -> n(old f)
  • */
  • b = n;
  • n = f;
  • continue;
  • }
  • // 走到这里说明比较结果c等于0,即找到了key对应的节点
  • /**
  • * 这里的检查是针对传入了value参数的情况
  • * 只有传入的value和找到的节点的value相同才会继续往下走
  • * 否则视为不符合条件,返回null
  • */
  • if (value != null && !value.equals(v))
  • // value不等于传入的value,不符合条件,返回null
  • return null;
  • // CAS方式修改n的value为null,修改不成功就跳出内层循环,进行下一次尝试
  • if (!n.casValue(v, null))
  • break;
  • /**
  • * 当前结构为:b -> n -> f
  • * 跳过n节点,即:
  • * n.appendMarker(f)的作用后:b -> n -> marker -> f
  • * 即新建一个标记节点,f作为该标记节点的后继节点,然后将该标记节点作为n的后继节点
  • * b.casNext(n, f)的作用后:b -> f
  • * 即把f作为b的后继节点,跳过n
  • *
  • * n.appendMarker(f)成功后才会执行b.casNext(n, f)
  • * 如果两步有一步失败,就会执行findNode(key)进行重试
  • */
  • if (!n.appendMarker(f) || !b.casNext(n, f))
  • // findNode(key)方法的代码会移除已标记为删除的节点
  • findNode(key); // Retry via findNode
  • else {
  • // 走到这里说明两步都成功了
  • // 利用findPredecessor函数的副作用,删除n结点对应的Index结点
  • findPredecessor(key); // Clean index
  • if (head.right == null)
  • // 头结点的right为null,表示头节点这一层只有head一个节点,所以需要减少层级
  • tryReduceLevel();
  • }
  • // 返回删除的旧值
  • return (V) v;
  • }
  • }
  • }
  • /**
  • * Possibly reduce head level if it has no nodes. This method can
  • * (rarely) make mistakes, in which case levels can disappear even
  • * though they are about to contain index nodes. This impacts
  • * performance, not correctness. To minimize mistakes as well as
  • * to reduce hysteresis, the level is reduced by one only if the
  • * topmost three levels look empty. Also, if the removed level
  • * looks non-empty after CAS, we try to change it back quick
  • * before anyone notices our mistake! (This trick works pretty
  • * well because this method will practically never make mistakes
  • * unless current thread stalls immediately before first CAS, in
  • * which case it is very unlikely to stall again immediately
  • * afterwards, so will recover.)
  • * <p>
  • * We put up with all this rather than just let levels grow
  • * because otherwise, even a small map that has undergone a large
  • * number of insertions and removals will have a lot of levels,
  • * slowing down access more than would an occasional unwanted
  • * reduction.
  • */
  • private void tryReduceLevel() {
  • /**
  • * h为头节点,d为h的下节点,e为d的下节点
  • * 只有在h.level > 3,d和e都不为空,h、d、e的右节点都为null时,
  • * 才尝试将d设置为h
  • * 设置之后检查新的h的右节点是否为null,不为null则修改成功,否则修改回去
  • */
  • 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
  • }
  • /* ---------------- Finding and removing first element -------------- */
  • /**
  • * Specialized variant of findNode to get first valid node.
  • * 找到第一个有效的节点
  • *
  • * @return first node or null if empty
  • */
  • Node<K, V> findFirst() {
  • // 无限循环
  • for (; ; ) {
  • // head头索引的Node
  • Node<K, V> b = head.node;
  • // 头节点的后继节点n
  • Node<K, V> n = b.next;
  • if (n == null)
  • // n为null则返回null
  • return null;
  • if (n.value != null)
  • // n的value不为null则返回该后继节点
  • return n;
  • // n的value为null,删除n节点
  • n.helpDelete(b, n.next);
  • }
  • }
  • /**
  • * Removes first entry; returns its snapshot.
  • *
  • * @return null if empty, else snapshot of first entry
  • */
  • Map.Entry<K, V> doRemoveFirstEntry() {
  • for (; ; ) {
  • // 获取head节点的node,即BASE_HEADER
  • Node<K, V> b = head.node;
  • // 获取BASE_HEADER的后继
  • Node<K, V> n = b.next;
  • // 如果n为null,表示跳表中只有BASE_HEADER一个节点,返回null即可
  • if (n == null)
  • return null;
  • // 否则获取n的后继
  • Node<K, V> f = n.next;
  • // 重新检查
  • if (n != b.next)
  • continue;
  • // 获取n的value
  • Object v = n.value;
  • /**
  • * 如果n的value是null,表示n是被删除的节点,
  • * 则使用helpDelete协助删除,然后进行新的循环
  • */
  • if (v == null) {
  • n.helpDelete(b, f);
  • continue;
  • }
  • // 否则将n的value置为null,如果失败直接进行新的循环
  • if (!n.casValue(v, null))
  • continue;
  • /**
  • * 走到这里说明n的value已被置为null
  • * 尝试将n与Node链断开,如果失败就使用findFirst()重试
  • */
  • if (!n.appendMarker(f) || !b.casNext(n, f))
  • findFirst(); // retry
  • // 走到这里说明n已与Node链断开,开始清理失效的索引
  • clearIndexToFirst();
  • // 返回删除的n节点的键值对,构造为一个SimpleImmutableEntry实例
  • return new AbstractMap.SimpleImmutableEntry<K, V>(n.key, (V) v);
  • }
  • }
  • /**
  • * Clears out index nodes associated with deleted first entry.
  • * 在删除第一个Node节点时协助清理失效Index
  • */
  • private void clearIndexToFirst() {
  • // 无限循环
  • for (; ; ) {
  • // 头节点
  • Index<K, V> q = head;
  • // 无限循环
  • for (; ; ) {
  • // 头节点的右节点r
  • Index<K, V> r = q.right;
  • // 判断r是否为被删除的节点,如果是就将其从索引链中断开;操作失败的话,就跳出内层循环重试
  • if (r != null && r.indexesDeletedNode() && !q.unlink(r))
  • break;
  • /**
  • * 走到这里表示r不是被删除的节点,q尝试下潜,
  • * 下潜成功,进行下一次循环
  • * 如果q的down为null,下潜失败,表示q已处于最底层,
  • * 此时查看head层是否只有head节点,如果是就尝试减少层级,
  • * 否则直接结束方法
  • */
  • if ((q = q.down) == null) {
  • // 查看head层是否只有head节点,如果是就尝试减少层级
  • if (head.right == null)
  • // 尝试减少层级
  • tryReduceLevel();
  • return;
  • }
  • }
  • }
  • }
  • /* ---------------- Finding and removing last element -------------- */
  • /**
  • * Specialized version of find to get last valid node.
  • *
  • * 查找最后一个有效的数据节点
  • *
  • * @return last node or null if empty
  • */
  • Node<K, V> findLast() {
  • /*
  • * findPredecessor can't be used to traverse index level
  • * because this doesn't use comparisons. So traversals of
  • * both levels are folded together.
  • */
  • // 头节点
  • Index<K, V> q = head;
  • // 无限循环
  • for (; ; ) {
  • Index<K, V> d, r;
  • // 头节点的right节点
  • if ((r = q.right) != null) {
  • // 如果r为被删除的节点,将其从索引链中断开
  • if (r.indexesDeletedNode()) {
  • q.unlink(r);
  • // 重新赋值q,然后进行下一次循环
  • q = head; // restart
  • } else
  • // 否则q进行右移操作,即指向r,然后进行下一次循环
  • q = r;
  • } else if ((d = q.down) != null) { // 如果q的right节点为null,则尝试下潜
  • // 走到这里表示q的down节点不为null,下潜成功,将进行下一次循环
  • q = d;
  • } else {
  • // 走到这里,表示q的right点为null,down点也为null,即q无法右移也无法下潜
  • // 获取q指向的Node节点b
  • Node<K, V> b = q.node;
  • // 获取b的后继
  • Node<K, V> n = b.next;
  • for (; ; ) {
  • if (n == null)
  • /**
  • * n为null的话,表示b已经是Node链中最后一个节点
  • * 如果此时b不是BASE_HEADER,那么b就是要找的最后一个节点
  • */
  • return b.isBaseHeader() ? null : b;
  • // 走到这里表示n不为null,获取n的后继为f
  • Node<K, V> f = n.next; // inconsistent read
  • // 检查n是否改变,如果改变的话跳出本次循环,重新进行外层循环重试
  • if (n != b.next)
  • break;
  • /**
  • * 检查n是否是被删除的节点
  • * 如果是,调用helpDelete将其从Node链中断开,
  • * 然后跳出本次循环,重新进行外层循环重试
  • */
  • Object v = n.value;
  • if (v == null) { // n is deleted
  • n.helpDelete(b, f);
  • break;
  • }
  • /**
  • * 走到这里说明n是有效的
  • * 这里用于判断b是否是被删除的节点
  • * 当v(n.value)== n时,表示n是删除标记节点
  • * 此时如果b的value也为null,则b也是被删除的节点
  • * 如果是,就跳出本次循环,重新进行外层循环重试
  • */
  • if (v == n || b.value == null) // b is deleted
  • break;
  • // 走到这里说明b和n都有效,后移,再次进行循环判断
  • b = n;
  • n = f;
  • }
  • q = head; // restart
  • }
  • }
  • }
  • /**
  • * Specialized variant of findPredecessor to get predecessor of last
  • * valid node. Needed when removing the last entry. It is possible
  • * that all successors of returned node will have been deleted upon
  • * return, in which case this method can be retried.
  • *
  • * 这个方法的字面意思是查找最后一个Node节点的前驱节点
  • * 其实分析这个方法的内容以及对它的使用,可以发现它并不是返回最后一个Node节点的前驱节点
  • * 它会遍历到跳表底层靠后的位置,然后返回特定的Index对应的Node节点
  • * 这时这个Node节点可能还有后继节点
  • *
  • * @return likely predecessor of last node
  • */
  • private Node<K, V> findPredecessorOfLast() {
  • // 无限循环
  • for (; ; ) {
  • // 获取head节点
  • Index<K, V> q = head;
  • // 无限循环
  • for (; ; ) {
  • Index<K, V> d, r;
  • // 头节点的right节点
  • if ((r = q.right) != null) {
  • // 如果r为被删除的节点,将其从索引链中断开
  • if (r.indexesDeletedNode()) {
  • // 重新赋值q,然后进行下一次循环
  • q.unlink(r);
  • break; // must restart
  • }
  • // proceed as far across as possible without overshooting
  • /**
  • * 否则查看r对应的Node节点的后继是否为null
  • * 如果不为null,则将q往后移动
  • */
  • if (r.node.next != null) {
  • // q往后移动
  • q = r;
  • continue;
  • }
  • }
  • /**
  • * 走到这里有两种情况:
  • * 1. q的right节点r为null
  • * 2. q的right节点r不为null,但r对应的Node节点的后继为null
  • * 尝试下潜操作
  • */
  • if ((d = q.down) != null)
  • // 走到这里表示q的down节点不为null,下潜成功,将进行下一次循环
  • q = d;
  • /**
  • * 走到这里表示q节点的down节点也为null,下潜失败
  • */
  • else
  • return q.node;
  • }
  • }
  • }
  • /**
  • * Removes last entry; returns its snapshot.
  • * Specialized variant of doRemove.
  • *
  • * 删除最后一个Node节点,并返回
  • *
  • * @return null if empty, else snapshot of last entry
  • */
  • Map.Entry<K, V> doRemoveLastEntry() {
  • for (; ; ) {
  • // 该方法用处请参见该方法的注释
  • Node<K, V> b = findPredecessorOfLast();
  • // 获取b的后继为n
  • Node<K, V> n = b.next;
  • /**
  • * 如果n为null,判断b是否是BASE_HEADER,
  • * 如果是表示此时跳表是空的,就返回null
  • * 否则说明b的后继被删了,直接进行下一次循环
  • */
  • if (n == null) {
  • if (b.isBaseHeader()) // empty
  • return null;
  • else
  • continue; // all b's successors are deleted; retry
  • }
  • // 走到这里说明n不为null,开启一个无限循环
  • for (; ; ) {
  • // 获取n的后继为f
  • Node<K, V> f = n.next;
  • // 检查n是否被改变
  • if (n != b.next) // inconsistent read
  • break;
  • // 判断n是否是被删除的节点,如果是就使用helpDelete协助删除
  • Object v = n.value;
  • if (v == null) { // n is deleted
  • n.helpDelete(b, f);
  • break;
  • }
  • // 判断b是否是被删除的节点,如果是就跳出内层循环,进行下一次外层循环的尝试
  • if (v == n || b.value == null) // b is deleted
  • break;
  • // 如果f不为null,则表示n后面还有节点,继续后移
  • if (f != null) {
  • b = n;
  • n = f;
  • continue;
  • }
  • /**
  • * 走到这里说明f为null,因此n已经是最后一个节点了
  • * 尝试CAS方式修改n的value为null
  • * 如果修改失败,跳出内层循环进行重试
  • */
  • if (!n.casValue(v, null))
  • break;
  • // 走到这里表示n的value已经被置为null了
  • // 获取n的key
  • K key = n.key;
  • Comparable<? super K> ck = comparable(key);
  • /**
  • * 这部分代码与doRemove()一样
  • * 当前结构为:b -> n -> f
  • * 跳过n节点,即:
  • * n.appendMarker(f)的作用后:b -> n -> marker -> f
  • * 即新建一个标记节点,f作为该标记节点的后继节点,然后将该标记节点作为n的后继节点
  • * b.casNext(n, f)的作用后:b -> f
  • * 即把f作为b的后继节点,跳过n
  • *
  • * n.appendMarker(f)成功后才会执行b.casNext(n, f)
  • * 如果两步有一步失败,就会执行findNode(key)进行重试
  • */
  • if (!n.appendMarker(f) || !b.casNext(n, f))
  • // findNode(key)方法的代码会移除已标记为删除的节点
  • findNode(ck); // Retry via findNode
  • else {
  • // 走到这里说明两步都成功了
  • // 利用findPredecessor函数的副作用,删除n结点对应的Index结点
  • findPredecessor(ck); // Clean index
  • if (head.right == null)
  • // 头结点的right为null,表示头节点这一层只有head一个节点,所以需要减少层级
  • tryReduceLevel();
  • }
  • // 返回有n节点的key和value构成的SimpleImmutableEntry对象
  • return new AbstractMap.SimpleImmutableEntry<K, V>(key, (V) v);
  • }
  • }
  • }
  • /* ---------------- Relational operations -------------- */
  • // Control values OR'ed as arguments to findNear
  • private static final int EQ = 1;
  • private static final int LT = 2;
  • private static final int GT = 0; // Actually checked as !LT
  • /**
  • * Utility for ceiling, floor, lower, higher methods.
  • *
  • * @param kkey the key
  • * @param rel the relation -- OR'ed combination of EQ, LT, GT;查找关系,值为EQ, LT, GT其中一个
  • * @return nearest node fitting relation, or null if no such
  • */
  • Node<K, V> findNear(K kkey, int rel) {
  • // 包装key
  • Comparable<? super K> key = comparable(kkey);
  • // 无限循环
  • for (; ; ) {
  • // 获取符合条件的前驱节点,标识为b
  • Node<K, V> b = findPredecessor(key);
  • // 获取b的后继为n
  • Node<K, V> n = b.next;
  • // 无限循环
  • for (; ; ) {
  • if (n == null)
  • /**
  • * n为null时,说明b已经是Node链中最后一个节点了
  • * rel & LT为0时,表示rel不为LT
  • * 此时表示,要查找的Node并不是小于传入的key的Node,即要查找的是键大于或等于key的Node
  • * 由于跳表中节点时按键从小到大的顺序排列的,因此b就是要查找的Node节点
  • */
  • return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
  • // 走到这里说明b不为null,获取n的后继为f,此时有关系b -> n -> f
  • Node<K, V> f = n.next;
  • // 检查n是否被改变
  • if (n != b.next) // inconsistent read
  • break;
  • /**
  • * 如果n的value为null表示n是被删除的节点,使用helpDelete()协助将其从Node链移除
  • * 然后进行直接跳出内层循环
  • */
  • Object v = n.value;
  • if (v == null) { // n is deleted
  • n.helpDelete(b, f);
  • break;
  • }
  • /**
  • * 检查n是否是标记删除节点,
  • * 如果n是标记删除节点,则检查b是否是被删除节点,如果b是被删除的节点,
  • * 就跳出内层循环,重新在外层循环中使用findPredecessor(key)查找
  • */
  • if (v == n || b.value == null) // b is deleted
  • break;
  • // 走到这里表示b和n都是正常的Node节点,因此比较传入key与n的key
  • int c = key.compareTo(n.key);
  • /**
  • * 首先关注其中两个条件的意思:
  • * 1. (rel & EQ) != 0表示指定比较操作存在EQ操作,即可能是EQ(等于)、LT | EQ(小于等于)或GT | EQ(大于等于)
  • * 2. (rel & LT) == 0表示指定操作不存在LT操作,即可能是EQ(等于)、GT(大于)或GT | EQ(大于等于)
  • * 再来看if的判断过程
  • * 1. 如果传入key与n的key相等,且比较操作存在EQ操作(即查找等于、小于等于或大于等于key的节点),就返回n;
  • * 2. 如果传入key与n的key相等,但比较操作不存在EQ操作(即查找不等于key的节点),n不符合条件,什么都不做;
  • * 3. 如果传入key小于n的key,且不存在LT操作(即查找等于、大于或大于等于key的节点),就返回n;
  • * 4. 如果传入key小于n的key,但存在LT操作(即查找小于、小于等于key的节点),n不符合条件,什么都不做。
  • */
  • if ((c == 0 && (rel & EQ) != 0) || (c < 0 && (rel & LT) == 0))
  • return n;
  • /**
  • * 如果传入key小于等于n的key,且比较操作存在LT操作(即可能是小于、小于等于)
  • * 判断b是否是BASE_HEADER,如果不是就返回b
  • */
  • if (c <= 0 && (rel & LT) != 0)
  • return b.isBaseHeader() ? null : b;
  • // 走到这里说明传入的key大于n的key,因此需要进行后移操作
  • b = n;
  • n = f;
  • }
  • }
  • }
  • /**
  • * Returns SimpleImmutableEntry for results of findNear.
  • *
  • * 根据指定操作查找附近的数据节点,包装为SimpleImmutableEntry实例返回
  • *
  • * @param key the key
  • * @param rel the relation -- OR'ed combination of EQ, LT, GT
  • * @return Entry fitting relation, or null if no such
  • */
  • AbstractMap.SimpleImmutableEntry<K, V> getNear(K key, int rel) {
  • for (; ; ) {
  • Node<K, V> n = findNear(key, rel);
  • if (n == null)
  • return null;
  • AbstractMap.SimpleImmutableEntry<K, V> e = n.createSnapshot();
  • if (e != null)
  • return e;
  • }
  • }
  • /* ---------------- Constructors -------------- */
  • /**
  • * Constructs a new, empty map, sorted according to the
  • * {@linkplain Comparable natural ordering} of the keys.
  • * 构造一个新的ConcurrentSkipListMap实例
  • */
  • public ConcurrentSkipListMap() {
  • this.comparator = null;
  • // 初始化方法
  • initialize();
  • }
  • /**
  • * Constructs a new, empty map, sorted according to the specified
  • * comparator.
  • * <p>
  • * 指定比较器,构造一个新的ConcurrentSkipListMap实例
  • *
  • * @param comparator the comparator that will be used to order this map.
  • * If <tt>null</tt>, the {@linkplain Comparable natural
  • * ordering} of the keys will be used.
  • */
  • public ConcurrentSkipListMap(Comparator<? super K> comparator) {
  • this.comparator = comparator;
  • // 初始化方法
  • initialize();
  • }
  • /**
  • * Constructs a new map containing the same mappings as the given map,
  • * sorted according to the {@linkplain Comparable natural ordering} of
  • * the keys.
  • * <p>
  • * 构造一个新的ConcurrentSkipListMap实例,并将传入的Map中的元素添加到实例中
  • *
  • * @param m the map whose mappings are to be placed in this map
  • * @throws ClassCastException if the keys in <tt>m</tt> are not
  • * {@link Comparable}, or are not mutually comparable
  • * @throws NullPointerException if the specified map or any of its keys
  • * or values are null
  • */
  • public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
  • this.comparator = null;
  • initialize();
  • // 调用putAll()方法添加元素
  • putAll(m);
  • }
  • /**
  • * Constructs a new map containing the same mappings and using the
  • * same ordering as the specified sorted map.
  • * <p>
  • * 构造一个新的ConcurrentSkipListMap实例,并将传入的SortedMap中的元素添加到实例中
  • *
  • * @param m the sorted map whose mappings are to be placed in this
  • * map, and whose comparator is to be used to sort this map
  • * @throws NullPointerException if the specified sorted map or any of
  • * its keys or values are null
  • */
  • public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
  • // 将传入Map的比较器作为ConcurrentSkipListMap的比较器
  • this.comparator = m.comparator();
  • initialize();
  • // 调用buildFromSorted()方法添加元素
  • buildFromSorted(m);
  • }
  • /**
  • * Returns a shallow copy of this <tt>ConcurrentSkipListMap</tt>
  • * instance. (The keys and values themselves are not cloned.)
  • *
  • * 返回ConcurrentSkipListMap的浅拷贝,键和值并没有被拷贝
  • *
  • * @return a shallow copy of this map
  • */
  • public ConcurrentSkipListMap<K, V> clone() {
  • // 先通过父类的clone方法返回一个空的Map
  • ConcurrentSkipListMap<K, V> clone = null;
  • try {
  • clone = (ConcurrentSkipListMap<K, V>) super.clone();
  • } catch (CloneNotSupportedException e) {
  • throw new InternalError();
  • }
  • // 对其调用initialize()
  • clone.initialize();
  • // 将现有ConcurrentSkipListMap中的元素添加到该Map中
  • clone.buildFromSorted(this);
  • return clone;
  • }
  • /**
  • * Streamlined bulk insertion to initialize from elements of
  • * given sorted map. Call only from constructor or clone
  • * method.
  • *
  • * 批量将有序集合中依次添加到新创建的ConcurrentSkipListMap中
  • * 该方法只会在构造方法和clone()方法中被调用
  • */
  • private void buildFromSorted(SortedMap<K, ? extends V> map) {
  • // 参数检查
  • if (map == null)
  • throw new NullPointerException();
  • // 头节点
  • HeadIndex<K, V> h = head;
  • // 头节点的node
  • Node<K, V> basepred = h.node;
  • // Track the current rightmost node at each level. Uses an
  • // ArrayList to avoid committing to initial or maximum level.
  • // 跟踪当前层最右边的节点
  • ArrayList<Index<K, V>> preds = new ArrayList<Index<K, V>>();
  • // initialize
  • /**
  • * 这一步的操作大致效果是这样的,假设当前跳表的结构如下:
  • * head -> n1 -> n2
  • * |
  • * index1 -> n3 -> n4 -> n5
  • * |
  • * index2 -> n6 -> n7
  • * 则会将head、index1、index2添加到preds中,顺序如下:
  • * (index2, index1, head)
  • */
  • // 根据头节点层级向preds添加null占位
  • for (int i = 0; i <= h.level; ++i)
  • preds.add(null);
  • // 反向往preds中添加头节点这一列的节点
  • Index<K, V> q = h;
  • for (int i = h.level; i > 0; --i) {
  • preds.set(i, q);
  • q = q.down;
  • }
  • // 迭代传入的map,将元素添加到新创建的ConcurrentSkipListMap中
  • Iterator<? extends Map.Entry<? extends K, ? extends V>> it = map.entrySet().iterator();
  • while (it.hasNext()) {
  • // 取出元素
  • Map.Entry<? extends K, ? extends V> e = it.next();
  • // 随机一个级别j
  • int j = randomLevel();
  • // j与head级别进行比较,如果大于,就置j为只比head级别大1
  • if (j > h.level) j = h.level + 1;
  • // 取出并检查键值对
  • K k = e.getKey();
  • V v = e.getValue();
  • if (k == null || v == null)
  • throw new NullPointerException();
  • // 根据键值对构造一个节点,后继节点为null
  • Node<K, V> z = new Node<K, V>(k, v, null);
  • // 将z作为head的node的后继节点
  • basepred.next = z;
  • // basepred后移,指向新添加的节点z
  • basepred = z;
  • if (j > 0) {
  • Index<K, V> idx = null;
  • // 从1遍历到j
  • for (int i = 1; i <= j; ++i) {
  • // 构建一个新的Index节点,其node指向上面新创建的节点z,后继节点为null
  • idx = new Index<K, V>(z, idx, null);
  • if (i > h.level)
  • /**
  • * 如果i比head节点的层级大,应该新构建一个head节点,补在idx前面
  • * 这一步的操作大致是这样的,假设当前跳表的结构如下:
  • * head(1)
  • * 此时head级别为1,此时插入一个级别为2的Index,级别比head大,因此需要新构建一个head,级别也为2
  • * 修改后结构如下:
  • * head(new, 2) -> idx(2)
  • * |
  • * head(old, 1)
  • */
  • h = new HeadIndex<K, V>(h.node, h, idx, i);
  • // 更新preds数组
  • if (i < preds.size()) {
  • preds.get(i).right = idx;
  • preds.set(i, idx);
  • } else
  • preds.add(idx);
  • }
  • }
  • }
  • // 更新head
  • head = h;
  • }
  • /* ---------------- Serialization -------------- */
  • /**
  • * Save the state of this map to a stream.
  • *
  • * 序列化写出ConcurrentSkipListMap
  • *
  • * @serialData The key (Object) and value (Object) for each
  • * key-value mapping represented by the map, followed by
  • * <tt>null</tt>. The key-value mappings are emitted in key-order
  • * (as determined by the Comparator, or by the keys' natural
  • * ordering if no Comparator).
  • */
  • private void writeObject(java.io.ObjectOutputStream s)
  • throws java.io.IOException {
  • // Write out the Comparator and any hidden stuff
  • // 调用默认的序列化写方法
  • s.defaultWriteObject();
  • // Write out keys and values (alternating)
  • // 遍历所有的Node节点
  • for (Node<K, V> n = findFirst(); n != null; n = n.next) {
  • // 如果值有效,依次写出键和值
  • V v = n.getValidValue();
  • if (v != null) {
  • s.writeObject(n.key);
  • s.writeObject(v);
  • }
  • }
  • // 写出一个null
  • s.writeObject(null);
  • }
  • /**
  • * Reconstitute the map from a stream.
  • * 序列化读ConcurrentSkipListMap
  • *
  • * 该方法主要代码的实现与buildFromSorted(SortedMap<K, ? extends V>)非常相似
  • */
  • private void readObject(final java.io.ObjectInputStream s)
  • throws java.io.IOException, ClassNotFoundException {
  • // Read in the Comparator and any hidden stuff
  • // 调用默认的序列化读方法
  • s.defaultReadObject();
  • // Reset transients
  • // 初始化transients变量
  • initialize();
  • /*
  • * This is nearly identical to buildFromSorted, but is
  • * distinct because readObject calls can't be nicely adapted
  • * as the kind of iterator needed by buildFromSorted. (They
  • * can be, but doing so requires type cheats and/or creation
  • * of adaptor classes.) It is simpler to just adapt the code.
  • */
  • // 构建第一列索引结构,实现与buildFromSorted(SortedMap<K, ? extends V>)一模一样
  • HeadIndex<K, V> h = head;
  • Node<K, V> basepred = h.node;
  • ArrayList<Index<K, V>> preds = new ArrayList<Index<K, V>>();
  • for (int i = 0; i <= h.level; ++i)
  • preds.add(null);
  • Index<K, V> q = h;
  • for (int i = h.level; i > 0; --i) {
  • preds.set(i, q);
  • q = q.down;
  • }
  • for (; ; ) {
  • // 读取并检查键值对
  • Object k = s.readObject();
  • if (k == null)
  • break;
  • Object v = s.readObject();
  • if (v == null)
  • throw new NullPointerException();
  • // 接下来的实现与buildFromSorted(SortedMap<K, ? extends V>)一模一样
  • K key = (K) k;
  • V val = (V) v;
  • int j = randomLevel();
  • if (j > h.level) j = h.level + 1;
  • Node<K, V> z = new Node<K, V>(key, val, null);
  • basepred.next = z;
  • basepred = z;
  • if (j > 0) {
  • Index<K, V> idx = null;
  • for (int i = 1; i <= j; ++i) {
  • idx = new Index<K, V>(z, idx, null);
  • if (i > h.level)
  • h = new HeadIndex<K, V>(h.node, h, idx, i);
  • if (i < preds.size()) {
  • preds.get(i).right = idx;
  • preds.set(i, idx);
  • } else
  • preds.add(idx);
  • }
  • }
  • }
  • head = h;
  • }
  • /* ------ Map API methods ------ */
  • /**
  • * Returns <tt>true</tt> if this map contains a mapping for the specified
  • * key.
  • *
  • * 判断是否存在某个键
  • *
  • * @param key key whose presence in this map is to be tested
  • * @return <tt>true</tt> if this map contains a mapping for the specified key
  • * @throws ClassCastException if the specified key cannot be compared
  • * with the keys currently in the map
  • * @throws NullPointerException if the specified key is null
  • */
  • public boolean containsKey(Object key) {
  • return doGet(key) != null;
  • }
  • /**
  • * Returns the value to which the specified key is mapped,
  • * or {@code null} if this map contains no mapping for the key.
  • *
  • * 获取指定key对应的值,如果没有找到的话就返回null
  • *
  • * <p>More formally, if this map contains a mapping from a key
  • * {@code k} to a value {@code v} such that {@code key} compares
  • * equal to {@code k} according to the map's ordering, then this
  • * method returns {@code v}; otherwise it returns {@code null}.
  • * (There can be at most one such mapping.)
  • *
  • * @throws ClassCastException if the specified key cannot be compared
  • * with the keys currently in the map
  • * @throws NullPointerException if the specified key is null
  • */
  • public V get(Object key) {
  • // 调用doGet()方法
  • return doGet(key);
  • }
  • /**
  • * Associates the specified value with the specified key in this map.
  • * If the map previously contained a mapping for the key, the old
  • * value is replaced.
  • * <p>
  • * 添加键值对到Map中,键存在时会覆盖原来的值
  • *
  • * @param key key with which the specified value is to be associated
  • * @param value value to be associated with the specified key
  • * @return the previous value associated with the specified key, or
  • * <tt>null</tt> if there was no mapping for the key 当覆盖时会返回旧值,否则返回null
  • * @throws ClassCastException if the specified key cannot be compared
  • * with the keys currently in the map
  • * @throws NullPointerException if the specified key or value is null 键或值为空都会抛出异常
  • */
  • public V put(K key, V value) {
  • // value不能为null
  • if (value == null)
  • throw new NullPointerException();
  • // 调用doPut()方法添加元素,onlyIfAbsent传入false
  • return doPut(key, value, false);
  • }
  • /**
  • * Removes the mapping for the specified key from this map if present.
  • * 从Map中移除key对应的键值对,返回值为旧值(如果key不存在则返回null)
  • *
  • * @param key key for which mapping should be removed
  • * @return the previous value associated with the specified key, or
  • * <tt>null</tt> if there was no mapping for the key
  • * @throws ClassCastException if the specified key cannot be compared
  • * with the keys currently in the map
  • * @throws NullPointerException if the specified key is null
  • */
  • public V remove(Object key) {
  • // 调用doRemove()方法,会返回旧值(如果存在)
  • return doRemove(key, null);
  • }
  • /**
  • * Returns <tt>true</tt> if this map maps one or more keys to the
  • * specified value. This operation requires time linear in the
  • * map size. Additionally, it is possible for the map to change
  • * during execution of this method, in which case the returned
  • * result may be inaccurate.
  • *
  • * 判断是否包含某个值,需要遍历Node节点
  • * 返回的值可能不准确,因为存在其他线程并发修改的情况
  • *
  • * @param value value whose presence in this map is to be tested
  • * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
  • * <tt>false</tt> otherwise
  • * @throws NullPointerException if the specified value is null
  • */
  • public boolean containsValue(Object value) {
  • // 参数检查
  • if (value == null)
  • throw new NullPointerException();
  • // 遍历Node链
  • for (Node<K, V> n = findFirst(); n != null; n = n.next) {
  • V v = n.getValidValue();
  • // 判断值是否相等
  • if (v != null && value.equals(v))
  • return true;
  • }
  • return false;
  • }
  • /**
  • * Returns the number of key-value mappings in this map. If this map
  • * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
  • * returns <tt>Integer.MAX_VALUE</tt>.
  • *
  • * <p>Beware that, unlike in most collections, this method is
  • * <em>NOT</em> a constant-time operation. Because of the
  • * asynchronous nature of these maps, determining the current
  • * number of elements requires traversing them all to count them.
  • * Additionally, it is possible for the size to change during
  • * execution of this method, in which case the returned result
  • * will be inaccurate. Thus, this method is typically not very
  • * useful in concurrent applications.
  • *
  • * @return the number of elements in this map
  • */
  • public int size() {
  • long count = 0;
  • // 遍历计算
  • for (Node<K, V> n = findFirst(); n != null; n = n.next) {
  • if (n.getValidValue() != null)
  • ++count;
  • }
  • // 最大只能为Integer.MAX_VALUE
  • return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count;
  • }
  • /**
  • * Returns <tt>true</tt> if this map contains no key-value mappings.
  • *
  • * @return <tt>true</tt> if this map contains no key-value mappings
  • */
  • public boolean isEmpty() {
  • // 如果找到的第一个有效节点为null则表示Map为空
  • return findFirst() == null;
  • }
  • /**
  • * Removes all of the mappings from this map.
  • *
  • * 清空Map
  • */
  • public void clear() {
  • initialize();
  • }
  • /* ---------------- View methods -------------- */
  • /*
  • * Note: Lazy initialization works for views because view classes
  • * are stateless/immutable so it doesn't matter wrt correctness if
  • * more than one is created (which will only rarely happen). Even
  • * so, the following idiom conservatively ensures that the method
  • * returns the one it created if it does so, not one created by
  • * another racing thread.
  • */
  • /**
  • * Returns a {@link NavigableSet} view of the keys contained in this map.
  • * The set's iterator returns the keys in ascending order.
  • * The set is backed by the map, so changes to the map are
  • * reflected in the set, and vice-versa. The set supports element
  • * removal, which removes the corresponding mapping from the map,
  • * via the {@code Iterator.remove}, {@code Set.remove},
  • * {@code removeAll}, {@code retainAll}, and {@code clear}
  • * operations. It does not support the {@code add} or {@code addAll}
  • * operations.
  • *
  • * <p>The view's {@code iterator} is a "weakly consistent" iterator
  • * that will never throw {@link ConcurrentModificationException},
  • * and guarantees to traverse elements as they existed upon
  • * construction of the iterator, and may (but is not guaranteed to)
  • * reflect any modifications subsequent to construction.
  • *
  • * <p>This method is equivalent to method {@code navigableKeySet}.
  • *
  • * 获取键集实例;键集中的键是按照ConcurrentSkipListMap中键值对升序的顺序组织的;
  • * 同时需要注意的是,KeySet依赖于ConcurrentSkipListMap,
  • * 因此ConcurrentSkipListMap中的键值对数据发生改变时,KeySet中的数据也会发生改变;
  • * KeySet支持元素移除操作,会通过Iterator.remove,Set.remove,removeAll,retainAll,clear等方法与ConcurrentSkipListMap关联
  • * KeySet不支持add、addAll等方法。
  • *
  • * 视图的迭代器是一个“弱一致”的迭代器,它永远不会抛出ConcurrentModificationException,
  • * 并保证能够遍历在构造迭代器时ConcurrentSkipListMap中存在的元素,并且能够(但不保证)反映构造之后的任何修改。
  • *
  • * @return a navigable set view of the keys in this map
  • */
  • public NavigableSet<K> keySet() {
  • KeySet ks = keySet;
  • return (ks != null) ? ks : (keySet = new KeySet(this));
  • }
  • public NavigableSet<K> navigableKeySet() {
  • KeySet ks = keySet;
  • return (ks != null) ? ks : (keySet = new KeySet(this));
  • }
  • /**
  • * Returns a {@link Collection} view of the values contained in this map.
  • * The collection's iterator returns the values in ascending order
  • * of the corresponding keys.
  • * The collection is backed by the map, so changes to the map are
  • * reflected in the collection, and vice-versa. The collection
  • * supports element removal, which removes the corresponding
  • * mapping from the map, via the <tt>Iterator.remove</tt>,
  • * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
  • * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
  • * support the <tt>add</tt> or <tt>addAll</tt> operations.
  • *
  • * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
  • * that will never throw {@link ConcurrentModificationException},
  • * and guarantees to traverse elements as they existed upon
  • * construction of the iterator, and may (but is not guaranteed to)
  • * reflect any modifications subsequent to construction.
  • */
  • public Collection<V> values() {
  • Values vs = values;
  • return (vs != null) ? vs : (values = new Values(this));
  • }
  • /**
  • * Returns a {@link Set} view of the mappings contained in this map.
  • * The set's iterator returns the entries in ascending key order.
  • * The set is backed by the map, so changes to the map are
  • * reflected in the set, and vice-versa. The set supports element
  • * removal, which removes the corresponding mapping from the map,
  • * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
  • * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
  • * operations. It does not support the <tt>add</tt> or
  • * <tt>addAll</tt> operations.
  • *
  • * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
  • * that will never throw {@link ConcurrentModificationException},
  • * and guarantees to traverse elements as they existed upon
  • * construction of the iterator, and may (but is not guaranteed to)
  • * reflect any modifications subsequent to construction.
  • *
  • * <p>The <tt>Map.Entry</tt> elements returned by
  • * <tt>iterator.next()</tt> do <em>not</em> support the
  • * <tt>setValue</tt> operation.
  • *
  • * @return a set view of the mappings contained in this map,
  • * sorted in ascending key order
  • */
  • public Set<Map.Entry<K, V>> entrySet() {
  • EntrySet es = entrySet;
  • return (es != null) ? es : (entrySet = new EntrySet(this));
  • }
  • public ConcurrentNavigableMap<K, V> descendingMap() {
  • ConcurrentNavigableMap<K, V> dm = descendingMap;
  • return (dm != null) ? dm : (descendingMap = new SubMap<K, V>
  • (this, null, false, null, false, true));
  • }
  • public NavigableSet<K> descendingKeySet() {
  • return descendingMap().navigableKeySet();
  • }
  • /* ---------------- AbstractMap Overrides -------------- */
  • /**
  • * Compares the specified object with this map for equality.
  • * Returns <tt>true</tt> if the given object is also a map and the
  • * two maps represent the same mappings. More formally, two maps
  • * <tt>m1</tt> and <tt>m2</tt> represent the same mappings if
  • * <tt>m1.entrySet().equals(m2.entrySet())</tt>. This
  • * operation may return misleading results if either map is
  • * concurrently modified during execution of this method.
  • *
  • * @param o object to be compared for equality with this map
  • * @return <tt>true</tt> if the specified object is equal to this map
  • */
  • public boolean equals(Object o) {
  • if (o == this)
  • return true;
  • if (!(o instanceof Map))
  • return false;
  • Map<?, ?> m = (Map<?, ?>) o;
  • try {
  • for (Map.Entry<K, V> e : this.entrySet())
  • if (!e.getValue().equals(m.get(e.getKey())))
  • return false;
  • for (Map.Entry<?, ?> e : m.entrySet()) {
  • Object k = e.getKey();
  • Object v = e.getValue();
  • if (k == null || v == null || !v.equals(get(k)))
  • return false;
  • }
  • return true;
  • } catch (ClassCastException unused) {
  • return false;
  • } catch (NullPointerException unused) {
  • return false;
  • }
  • }
  • /* ------ ConcurrentMap API methods ------ */
  • /**
  • * {@inheritDoc}
  • *
  • * 添加键值对到Map中,只有在键不存在时才会添加
  • *
  • * @return the previous value associated with the specified key,
  • * or <tt>null</tt> if there was no mapping for the key
  • * @throws ClassCastException if the specified key cannot be compared
  • * with the keys currently in the map
  • * @throws NullPointerException if the specified key or value is null
  • */
  • public V putIfAbsent(K key, V value) {
  • // value不能为null
  • if (value == null)
  • throw new NullPointerException();
  • // 调用doPut()方法添加元素,onlyIfAbsent传入true
  • return doPut(key, value, true);
  • }
  • /**
  • * {@inheritDoc}
  • * 根据key和value删除键值对
  • *
  • * @throws ClassCastException if the specified key cannot be compared
  • * with the keys currently in the map
  • * @throws NullPointerException if the specified key is null
  • */
  • public boolean remove(Object key, Object value) {
  • // 检查传入的参数
  • if (key == null)
  • throw new NullPointerException();
  • if (value == null)
  • return false;
  • // 使用doRemove方法来删除,如果发生删除将会返回true,否则返回false
  • return doRemove(key, value) != null;
  • }
  • /**
  • * {@inheritDoc}
  • *
  • * 修改指定键对应的节点的值,需要传入旧值进行比对,如果一致就修改为新值
  • * 修改成功返回true,否则返回false
  • *
  • * @throws ClassCastException if the specified key cannot be compared
  • * with the keys currently in the map
  • * @throws NullPointerException if any of the arguments are null
  • */
  • public boolean replace(K key, V oldValue, V newValue) {
  • // 参数检查
  • if (oldValue == null || newValue == null)
  • throw new NullPointerException();
  • // 包装key为Comparable类型实例
  • Comparable<? super K> k = comparable(key);
  • // 无限循环
  • for (; ; ) {
  • // 找到对应的节点
  • Node<K, V> n = findNode(k);
  • if (n == null)
  • // 没找到,直接返回false
  • return false;
  • // 找到节点了,检查value
  • Object v = n.value;
  • if (v != null) {
  • if (!oldValue.equals(v))
  • // 传入的oldValue与n的value不同,直接返回false
  • return false;
  • // 否则CAS方式修改n的value为newValue
  • if (n.casValue(v, newValue))
  • // 修改成功返回true
  • return true;
  • }
  • }
  • }
  • /**
  • * {@inheritDoc}
  • *
  • * 直接修改指定键对应的节点的值,修改成功返回旧值,否则返回null
  • *
  • * @return the previous value associated with the specified key,
  • * or <tt>null</tt> if there was no mapping for the key
  • * @throws ClassCastException if the specified key cannot be compared
  • * with the keys currently in the map
  • * @throws NullPointerException if the specified key or value is null
  • */
  • public V replace(K key, V value) {
  • // 参数检查
  • if (value == null)
  • throw new NullPointerException();
  • // 包装key为Comparable类型实例
  • Comparable<? super K> k = comparable(key);
  • // 无限循环
  • for (; ; ) {
  • // 找到对应的节点
  • Node<K, V> n = findNode(k);
  • if (n == null)
  • // 没找到,直接返回null
  • return null;
  • // 找到节点了,检查value
  • Object v = n.value;
  • // n的value不为null,CAS方式修改n的value为value
  • if (v != null && n.casValue(v, value))
  • // 修改成功返回旧value
  • return (V) v;
  • }
  • }
  • /* ------ SortedMap API methods ------ */
  • public Comparator<? super K> comparator() {
  • return comparator;
  • }
  • /**
  • * @throws NoSuchElementException {@inheritDoc}
  • * 获取第一个数据节点的键
  • */
  • public K firstKey() {
  • Node<K, V> n = findFirst();
  • if (n == null)
  • throw new NoSuchElementException();
  • return n.key;
  • }
  • /**
  • * @throws NoSuchElementException {@inheritDoc}
  • * 获取最后一个数据节点的键
  • */
  • public K lastKey() {
  • Node<K, V> n = findLast();
  • if (n == null)
  • throw new NoSuchElementException();
  • return n.key;
  • }
  • /**
  • * 返回从fromKey到toKey的子Map,fromInclusive和toInclusive决定是否包含fromKey和toKey
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
  • * @throws IllegalArgumentException {@inheritDoc}
  • */
  • public ConcurrentNavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
  • // 检查参数
  • if (fromKey == null || toKey == null)
  • throw new NullPointerException();
  • // 返回SubMap对象
  • return new SubMap<K, V>(this, fromKey, fromInclusive, toKey, toInclusive, false);
  • }
  • /**
  • * 返回从头到toKey的子Map,inclusive决定是否包含toKey
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if {@code toKey} is null
  • * @throws IllegalArgumentException {@inheritDoc}
  • */
  • public ConcurrentNavigableMap<K, V> headMap(K toKey, boolean inclusive) {
  • // 检查参数
  • if (toKey == null)
  • throw new NullPointerException();
  • // 返回SubMap对象
  • return new SubMap<K, V>(this, null, false, toKey, inclusive, false);
  • }
  • /**
  • * 返回从fromKey到尾的子Map,inclusive决定是否包含fromKey
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if {@code fromKey} is null
  • * @throws IllegalArgumentException {@inheritDoc}
  • */
  • public ConcurrentNavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
  • // 检查参数
  • if (fromKey == null)
  • throw new NullPointerException();
  • // 返回SubMap对象
  • return new SubMap<K, V>(this, fromKey, inclusive, null, false, false);
  • }
  • /**
  • * 返回[fromKey, toKey)范围的子Map
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
  • * @throws IllegalArgumentException {@inheritDoc}
  • */
  • public ConcurrentNavigableMap<K, V> subMap(K fromKey, K toKey) {
  • return subMap(fromKey, true, toKey, false);
  • }
  • /**
  • * 返回从头到toKey的子Map,不包含toKey
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if {@code toKey} is null
  • * @throws IllegalArgumentException {@inheritDoc}
  • */
  • public ConcurrentNavigableMap<K, V> headMap(K toKey) {
  • return headMap(toKey, false);
  • }
  • /**
  • * 返回fromKey到尾的子Map,包含fromKey
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if {@code fromKey} is null
  • * @throws IllegalArgumentException {@inheritDoc}
  • */
  • public ConcurrentNavigableMap<K, V> tailMap(K fromKey) {
  • return tailMap(fromKey, true);
  • }
  • /* ---------------- Relational operations -------------- */
  • /**
  • * Returns a key-value mapping associated with the greatest key
  • * strictly less than the given key, or <tt>null</tt> if there is
  • * no such key. The returned entry does <em>not</em> support the
  • * <tt>Entry.setValue</tt> method.
  • *
  • * 获取比给定key小的最大键对应的键值对
  • *
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if the specified key is null
  • */
  • public Map.Entry<K, V> lowerEntry(K key) {
  • return getNear(key, LT);
  • }
  • /**
  • * 获取比给定key小的最大键对应的键值对的键
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if the specified key is null
  • */
  • public K lowerKey(K key) {
  • Node<K, V> n = findNear(key, LT);
  • return (n == null) ? null : n.key;
  • }
  • /**
  • * Returns a key-value mapping associated with the greatest key
  • * less than or equal to the given key, or <tt>null</tt> if there
  • * is no such key. The returned entry does <em>not</em> support
  • * the <tt>Entry.setValue</tt> method.
  • *
  • * 获取键小于或等于给定key的最大键值对
  • *
  • * @param key the key
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if the specified key is null
  • */
  • public Map.Entry<K, V> floorEntry(K key) {
  • return getNear(key, LT | EQ);
  • }
  • /**
  • * 获取键小于或等于给定key的最大键值对对应的键
  • * @param key the key
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if the specified key is null
  • */
  • public K floorKey(K key) {
  • Node<K, V> n = findNear(key, LT | EQ);
  • return (n == null) ? null : n.key;
  • }
  • /**
  • * Returns a key-value mapping associated with the least key
  • * greater than or equal to the given key, or <tt>null</tt> if
  • * there is no such entry. The returned entry does <em>not</em>
  • * support the <tt>Entry.setValue</tt> method.
  • *
  • * 获取键大于或等于给定key的最大键值对
  • *
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if the specified key is null
  • */
  • public Map.Entry<K, V> ceilingEntry(K key) {
  • return getNear(key, GT | EQ);
  • }
  • /**
  • * 获取键大于或等于给定key的最大键
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if the specified key is null
  • */
  • public K ceilingKey(K key) {
  • Node<K, V> n = findNear(key, GT | EQ);
  • return (n == null) ? null : n.key;
  • }
  • /**
  • * Returns a key-value mapping associated with the least key
  • * strictly greater than the given key, or <tt>null</tt> if there
  • * is no such key. The returned entry does <em>not</em> support
  • * the <tt>Entry.setValue</tt> method.
  • *
  • * 获取键大于给定key的最大键值对
  • *
  • * @param key the key
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if the specified key is null
  • */
  • public Map.Entry<K, V> higherEntry(K key) {
  • return getNear(key, GT);
  • }
  • /**
  • * 获取键大于给定key的最大键
  • * @param key the key
  • * @throws ClassCastException {@inheritDoc}
  • * @throws NullPointerException if the specified key is null
  • */
  • public K higherKey(K key) {
  • Node<K, V> n = findNear(key, GT);
  • return (n == null) ? null : n.key;
  • }
  • /**
  • * Returns a key-value mapping associated with the least
  • * key in this map, or <tt>null</tt> if the map is empty.
  • * The returned entry does <em>not</em> support
  • * the <tt>Entry.setValue</tt> method.
  • * 获取第一个数据节点的键值对,包装为SimpleImmutableEntry实例返回
  • */
  • public Map.Entry<K, V> firstEntry() {
  • for (; ; ) {
  • Node<K, V> n = findFirst();
  • if (n == null)
  • return null;
  • AbstractMap.SimpleImmutableEntry<K, V> e = n.createSnapshot();
  • if (e != null)
  • return e;
  • }
  • }
  • /**
  • * Returns a key-value mapping associated with the greatest
  • * key in this map, or <tt>null</tt> if the map is empty.
  • * The returned entry does <em>not</em> support
  • * the <tt>Entry.setValue</tt> method.
  • * 获取最后一个数据节点的键值对,包装为SimpleImmutableEntry实例返回
  • */
  • public Map.Entry<K, V> lastEntry() {
  • for (; ; ) {
  • Node<K, V> n = findLast();
  • if (n == null)
  • return null;
  • AbstractMap.SimpleImmutableEntry<K, V> e = n.createSnapshot();
  • if (e != null)
  • return e;
  • }
  • }
  • /**
  • * Removes and returns a key-value mapping associated with
  • * the least key in this map, or <tt>null</tt> if the map is empty.
  • * The returned entry does <em>not</em> support
  • * the <tt>Entry.setValue</tt> method.
  • *
  • * 移除并返回第一个数据节点
  • */
  • public Map.Entry<K, V> pollFirstEntry() {
  • return doRemoveFirstEntry();
  • }
  • /**
  • * Removes and returns a key-value mapping associated with
  • * the greatest key in this map, or <tt>null</tt> if the map is empty.
  • * The returned entry does <em>not</em> support
  • * the <tt>Entry.setValue</tt> method.
  • *
  • * 移除并返回最后一个数据节点
  • */
  • public Map.Entry<K, V> pollLastEntry() {
  • return doRemoveLastEntry();
  • }
  • /* ---------------- Iterators -------------- */
  • /**
  • * Base of iterator classes:
  • *
  • * 迭代器基类,没有实现next()
  • */
  • abstract class Iter<T> implements Iterator<T> {
  • /**
  • * the last node returned by next()
  • * 这个节点为记录上一次返回的数据节点
  • */
  • Node<K, V> lastReturned;
  • /**
  • * the next node to return from next();
  • * 这个节点会记录当次应该返回的数据节点
  • */
  • Node<K, V> next;
  • /**
  • * Cache of next value field to maintain weak consistency
  • * 缓存当次应该返回的数据节点的值
  • */
  • V nextValue;
  • /**
  • * Initializes ascending iterator for entire range.
  • */
  • Iter() {
  • for (; ; ) {
  • // 初始化时,将next指向第一个Node节点
  • next = findFirst();
  • // 如果next为null,直接结束循环
  • if (next == null)
  • break;
  • // 检查next的有效性,如果有效,将next的value赋值给nextValue记录
  • Object x = next.value;
  • if (x != null && x != next) {
  • nextValue = (V) x;
  • break;
  • }
  • }
  • }
  • // 判断是否有下一个元素
  • public final boolean hasNext() {
  • return next != null;
  • }
  • /**
  • * Advances next to higher entry.
  • * 后移
  • */
  • final void advance() {
  • // 检查next,如果next为null,抛出错误
  • if (next == null)
  • throw new NoSuchElementException();
  • // 记录next为lastReturned
  • lastReturned = next;
  • for (; ; ) {
  • // 将next后移
  • next = next.next;
  • // 如果新的next为null,代表迭代到末尾了,直接跳出
  • if (next == null)
  • break;
  • // 检查next是否有效,如果有效用nextValue记录next的value
  • Object x = next.value;
  • if (x != null && x != next) {
  • nextValue = (V) x;
  • break;
  • }
  • }
  • }
  • // 移除元素
  • public void remove() {
  • // 检查元素是否有效,即不能从空的ConcurrentSkipListMap中移除元素
  • Node<K, V> l = lastReturned;
  • if (l == null)
  • throw new IllegalStateException();
  • // It would not be worth all of the overhead to directly
  • // unlink from here. Using remove is fast enough.
  • // 根据lastReturned的key移除元素
  • ConcurrentSkipListMap.this.remove(l.key);
  • // 将lastReturned置为null
  • lastReturned = null;
  • }
  • }
  • // 值迭代器
  • final class ValueIterator extends Iter<V> {
  • // 实现next方法
  • public V next() {
  • // 获取nextValue,这个变量记录了next的值
  • V v = nextValue;
  • // 使next后移
  • advance();
  • // 返回值
  • return v;
  • }
  • }
  • // 键迭代器
  • final class KeyIterator extends Iter<K> {
  • // 实现next方法
  • public K next() {
  • // 将next赋值给n
  • Node<K, V> n = next;
  • // 使next后移
  • advance();
  • // 返回n的key值
  • return n.key;
  • }
  • }
  • // 键值对迭代器
  • final class EntryIterator extends Iter<Map.Entry<K, V>> {
  • public Map.Entry<K, V> next() {
  • // 将next赋值给n
  • Node<K, V> n = next;
  • // 获取nextValue,这个变量记录了next的值
  • V v = nextValue;
  • // 使next后移
  • advance();
  • // 返回以SimpleImmutableEntry包装的键值对实例
  • return new AbstractMap.SimpleImmutableEntry<K, V>(n.key, v);
  • }
  • }
  • // ConcurrentSkipListSet迭代器相关的工厂方法
  • Iterator<K> keyIterator() {
  • return new KeyIterator();
  • }
  • Iterator<V> valueIterator() {
  • return new ValueIterator();
  • }
  • Iterator<Map.Entry<K, V>> entryIterator() {
  • return new EntryIterator();
  • }
  • /* ---------------- View Classes -------------- */
  • /*
  • * View classes are static, delegating to a ConcurrentNavigableMap
  • * to allow use by SubMaps, which outweighs the ugliness of
  • * needing type-tests for Iterator methods.
  • */
  • static final <E> List<E> toList(Collection<E> c) {
  • // Using size() here would be a pessimization.
  • List<E> list = new ArrayList<E>();
  • for (E e : c)
  • list.add(e);
  • return list;
  • }
  • static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
  • // 用于引用ConcurrentSkipListMap实例,ConcurrentSkipListMap继承自ConcurrentNavigableMap
  • private final ConcurrentNavigableMap<E, Object> m;
  • // 构造方法对传入的map进行引用
  • KeySet(ConcurrentNavigableMap<E, Object> map) {
  • m = map;
  • }
  • public int size() {
  • // 返回ConcurrentSkipListMap的size()
  • return m.size();
  • }
  • public boolean isEmpty() {
  • // 返回ConcurrentSkipListMap的isEmpty()
  • return m.isEmpty();
  • }
  • public boolean contains(Object o) {
  • // 返回ConcurrentSkipListMap的containsKey(o)
  • return m.containsKey(o);
  • }
  • public boolean remove(Object o) {
  • // 返回ConcurrentSkipListMap的remove(o)的返回值
  • return m.remove(o) != null;
  • }
  • public void clear() {
  • // 调用ConcurrentSkipListMap的clear()
  • m.clear();
  • }
  • public E lower(E e) {
  • // 返回ConcurrentSkipListMap的lowerKey(e)的返回值
  • return m.lowerKey(e);
  • }
  • public E floor(E e) {
  • // 返回ConcurrentSkipListMap的floorKey(e)的返回值
  • return m.floorKey(e);
  • }
  • public E ceiling(E e) {
  • // 返回ConcurrentSkipListMap的ceilingKey(e)的返回值
  • return m.ceilingKey(e);
  • }
  • public E higher(E e) {
  • // 返回ConcurrentSkipListMap的higherKey(e)的返回值
  • return m.higherKey(e);
  • }
  • public Comparator<? super E> comparator() {
  • // 返回ConcurrentSkipListMap的comparator()的返回值
  • return m.comparator();
  • }
  • public E first() {
  • // 返回ConcurrentSkipListMap的firstKey()的返回值
  • return m.firstKey();
  • }
  • public E last() {
  • // 返回ConcurrentSkipListMap的lastKey()的返回值
  • return m.lastKey();
  • }
  • public E pollFirst() {
  • // 使用ConcurrentSkipListMap的pollFirstEntry()获得第一个键值对的键
  • Map.Entry<E, Object> e = m.pollFirstEntry();
  • return (e == null) ? null : e.getKey();
  • }
  • public E pollLast() {
  • // 使用ConcurrentSkipListMap的pollLastEntry()获得最后一个键值对的键
  • Map.Entry<E, Object> e = m.pollLastEntry();
  • return (e == null) ? null : e.getKey();
  • }
  • public Iterator<E> iterator() {
  • // 通过判断m的类型决定是返回ConcurrentSkipListMap的键迭代器还是ConcurrentSkipListMap.SubMap的键迭代器
  • if (m instanceof ConcurrentSkipListMap)
  • return ((ConcurrentSkipListMap<E, Object>) m).keyIterator();
  • else
  • return ((ConcurrentSkipListMap.SubMap<E, Object>) m).keyIterator();
  • }
  • public boolean equals(Object o) {
  • // 判断传入实例是否相同
  • if (o == this)
  • return true;
  • // 判断传入实例类型是否是Set
  • if (!(o instanceof Set))
  • return false;
  • Collection<?> c = (Collection<?>) o;
  • try {
  • // 通过父类AbstractCollection的containsAll()方法来判断是否相同
  • return containsAll(c) && c.containsAll(this);
  • } catch (ClassCastException unused) {
  • return false;
  • } catch (NullPointerException unused) {
  • return false;
  • }
  • }
  • // 转换为Array
  • public Object[] toArray() {
  • return toList(this).toArray();
  • }
  • // 转换为Array
  • public <T> T[] toArray(T[] a) {
  • return toList(this).toArray(a);
  • }
  • // 逆序迭代器
  • public Iterator<E> descendingIterator() {
  • return descendingSet().iterator();
  • }
  • // 获取键集中从fromElement到toElement的子集,fromInclusive和toInclusive分别决定是否包含fromElement到toElement
  • public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
  • return new KeySet<E>(m.subMap(fromElement, fromInclusive,
  • toElement, toInclusive));
  • }
  • // 返回从头到toElement的子集,inclusive用于决定是否包括toElement
  • public NavigableSet<E> headSet(E toElement, boolean inclusive) {
  • return new KeySet<E>(m.headMap(toElement, inclusive));
  • }
  • // 返回从fromElement到尾的子集,inclusive用于决定是否包括fromElement
  • public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
  • return new KeySet<E>(m.tailMap(fromElement, inclusive));
  • }
  • // 返回从[fromElementm toElement)到尾的子集
  • public NavigableSet<E> subSet(E fromElement, E toElement) {
  • return subSet(fromElement, true, toElement, false);
  • }
  • // 返回从头到toElement的子集,不包括toElement
  • public NavigableSet<E> headSet(E toElement) {
  • return headSet(toElement, false);
  • }
  • // 返回从fromElement到尾的子集,包括fromElement
  • public NavigableSet<E> tailSet(E fromElement) {
  • return tailSet(fromElement, true);
  • }
  • // 逆序键集
  • public NavigableSet<E> descendingSet() {
  • return new KeySet(m.descendingMap());
  • }
  • }
  • // 值集类
  • static final class Values<E> extends AbstractCollection<E> {
  • // 用于引用ConcurrentSkipListMap实例,ConcurrentSkipListMap继承自ConcurrentNavigableMap
  • private final ConcurrentNavigableMap<Object, E> m;
  • // 构造方法对传入的map进行引用
  • Values(ConcurrentNavigableMap<Object, E> map) {
  • m = map;
  • }
  • public Iterator<E> iterator() {
  • // 通过判断m的类型决定是返回ConcurrentSkipListMap的值迭代器还是ConcurrentSkipListMap.SubMap的值迭代器
  • if (m instanceof ConcurrentSkipListMap)
  • return ((ConcurrentSkipListMap<Object, E>) m).valueIterator();
  • else
  • return ((SubMap<Object, E>) m).valueIterator();
  • }
  • public boolean isEmpty() {
  • // 返回ConcurrentSkipListMap的isEmpty()
  • return m.isEmpty();
  • }
  • public int size() {
  • // 返回ConcurrentSkipListMap的size()
  • return m.size();
  • }
  • public boolean contains(Object o) {
  • // 返回ConcurrentSkipListMap的containsValue(o)
  • return m.containsValue(o);
  • }
  • public void clear() {
  • // 调用ConcurrentSkipListMap的clear()
  • m.clear();
  • }
  • // 转换为Array
  • public Object[] toArray() {
  • return toList(this).toArray();
  • }
  • // 转换为Array
  • public <T> T[] toArray(T[] a) {
  • return toList(this).toArray(a);
  • }
  • }
  • // 键值集
  • static final class EntrySet<K1, V1> extends AbstractSet<Map.Entry<K1, V1>> {
  • // 用于引用ConcurrentSkipListMap实例,ConcurrentSkipListMap继承自ConcurrentNavigableMap
  • private final ConcurrentNavigableMap<K1, V1> m;
  • // 构造方法对传入的map进行引用
  • EntrySet(ConcurrentNavigableMap<K1, V1> map) {
  • m = map;
  • }
  • public Iterator<Map.Entry<K1, V1>> iterator() {
  • // 通过判断m的类型决定是返回ConcurrentSkipListMap的键值迭代器还是ConcurrentSkipListMap.SubMap的键值迭代器
  • if (m instanceof ConcurrentSkipListMap)
  • return ((ConcurrentSkipListMap<K1, V1>) m).entryIterator();
  • else
  • return ((SubMap<K1, V1>) m).entryIterator();
  • }
  • public boolean contains(Object o) {
  • // 检查o的类型
  • if (!(o instanceof Map.Entry))
  • return false;
  • // 强转类型
  • Map.Entry<K1, V1> e = (Map.Entry<K1, V1>) o;
  • // 从ConcurrentSkipListMap中以o的key取值
  • V1 v = m.get(e.getKey());
  • // 根据判断取到的值是否与o的值相等来决定返回结果
  • return v != null && v.equals(e.getValue());
  • }
  • public boolean remove(Object o) {
  • // 检查o的类型
  • if (!(o instanceof Map.Entry))
  • return false;
  • // 强转类型
  • Map.Entry<K1, V1> e = (Map.Entry<K1, V1>) o;
  • // 使用ConcurrentSkipListMap的remove(K, V)方法来移除
  • return m.remove(e.getKey(), e.getValue());
  • }
  • public boolean isEmpty() {
  • // 返回ConcurrentSkipListMap的isEmpty()
  • return m.isEmpty();
  • }
  • public int size() {
  • // 返回ConcurrentSkipListMap的size()
  • return m.size();
  • }
  • public void clear() {
  • // 调用ConcurrentSkipListMap的clear()
  • m.clear();
  • }
  • public boolean equals(Object o) {
  • // 判断传入实例是否相同
  • if (o == this)
  • return true;
  • // 判断传入实例类型是否是Set
  • if (!(o instanceof Set))
  • return false;
  • Collection<?> c = (Collection<?>) o;
  • try {
  • // 通过父类AbstractCollection的containsAll()方法来判断是否相同
  • return containsAll(c) && c.containsAll(this);
  • } catch (ClassCastException unused) {
  • return false;
  • } catch (NullPointerException unused) {
  • return false;
  • }
  • }
  • // 转换为Array
  • public Object[] toArray() {
  • return toList(this).toArray();
  • }
  • // 转换为Array
  • public <T> T[] toArray(T[] a) {
  • return toList(this).toArray(a);
  • }
  • }
  • /**
  • * Submaps returned by {@link ConcurrentSkipListMap} submap operations
  • * represent a subrange of mappings of their underlying
  • * maps. Instances of this class support all methods of their
  • * underlying maps, differing in that mappings outside their range are
  • * ignored, and attempts to add mappings outside their ranges result
  • * in {@link IllegalArgumentException}. Instances of this class are
  • * constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and
  • * <tt>tailMap</tt> methods of their underlying maps.
  • *
  • * @serial include
  • */
  • static final class SubMap<K, V> extends AbstractMap<K, V>
  • implements ConcurrentNavigableMap<K, V>, Cloneable,
  • java.io.Serializable {
  • private static final long serialVersionUID = -7647078645895051609L;
  • /**
  • * Underlying map
  • * 底层的ConcurrentSkipListMap
  • */
  • private final ConcurrentSkipListMap<K, V> m;
  • /**
  • * lower bound key, or null if from start
  • * 下限键,为null时表示从头开始
  • */
  • private final K lo;
  • /**
  • * upper bound key, or null if to end
  • * 上限键,为null时表示一直到末尾
  • */
  • private final K hi;
  • /**
  • * inclusion flag for lo
  • * 是否包含下限键lo
  • */
  • private final boolean loInclusive;
  • /**
  • * inclusion flag for hi
  • * 是否包含上限键hi
  • */
  • private final boolean hiInclusive;
  • /**
  • * direction
  • * 是否逆序
  • */
  • private final boolean isDescending;
  • // Lazily initialized view holders
  • // 键集、值集、键值集对象,会延迟初始化;均不支持序列化
  • private transient KeySet<K> keySetView;
  • private transient Set<Map.Entry<K, V>> entrySetView;
  • private transient Collection<V> valuesView;
  • /**
  • * Creates a new submap, initializing all fields
  • * 创建一个新的SubMap,初始化各类变量
  • */
  • SubMap(ConcurrentSkipListMap<K, V> map, K fromKey, boolean fromInclusive, K toKey, boolean toInclusive, boolean isDescending) {
  • // 检查fromKey和toKey,同时通过map的compare方法保证fromKey比toKey大
  • if (fromKey != null && toKey != null && map.compare(fromKey, toKey) > 0)
  • throw new IllegalArgumentException("inconsistent range");
  • // 各类变量的引用赋值
  • this.m = map;
  • this.lo = fromKey;
  • this.hi = toKey;
  • this.loInclusive = fromInclusive;
  • this.hiInclusive = toInclusive;
  • this.isDescending = isDescending;
  • }
  • /* ---------------- Utilities -------------- */
  • // 检查键是否太小
  • private boolean tooLow(K key) {
  • if (lo != null) {
  • // 与lo比较
  • int c = m.compare(key, lo);
  • // 兼顾包含lo的情况
  • if (c < 0 || (c == 0 && !loInclusive))
  • return true;
  • }
  • return false;
  • }
  • // 检查键是否太大
  • private boolean tooHigh(K key) {
  • if (hi != null) {
  • // 与hi比较
  • int c = m.compare(key, hi);
  • // 兼顾包含hi的情况
  • if (c > 0 || (c == 0 && !hiInclusive))
  • return true;
  • }
  • return false;
  • }
  • // 检查键是否在范围内
  • private boolean inBounds(K key) {
  • return !tooLow(key) && !tooHigh(key);
  • }
  • // 检查键是否符合条件
  • private void checkKeyBounds(K key) throws IllegalArgumentException {
  • // 键不能为null
  • if (key == null)
  • throw new NullPointerException();
  • // 使用inBounds检查
  • if (!inBounds(key))
  • throw new IllegalArgumentException("key out of range");
  • }
  • /**
  • * Returns true if node key is less than upper bound of range
  • * 判断节点n的键是否小于hi
  • */
  • private boolean isBeforeEnd(ConcurrentSkipListMap.Node<K, V> n) {
  • // 各类检查
  • if (n == null)
  • return false;
  • if (hi == null)
  • return true;
  • K k = n.key;
  • if (k == null) // pass by markers and headers
  • return true;
  • // 进行比较
  • int c = m.compare(k, hi);
  • if (c > 0 || (c == 0 && !hiInclusive))
  • return false;
  • return true;
  • }
  • /**
  • * Returns lowest node. This node might not be in range, so
  • * most usages need to check bounds
  • * 获取最小的节点,但节点的键需要在范围内
  • */
  • private ConcurrentSkipListMap.Node<K, V> loNode() {
  • // 如果lo为null,则直接获取第一个节点
  • if (lo == null)
  • return m.findFirst();
  • // 否则根据loInclusive是否为true判断是否包含起始节点
  • else if (loInclusive)
  • // 如果包含就传入EQ操作
  • return m.findNear(lo, m.GT | m.EQ);
  • else
  • // 否则没有EQ操作
  • return m.findNear(lo, m.GT);
  • }
  • /**
  • * Returns highest node. This node might not be in range, so
  • * most usages need to check bounds
  • * 获取最大的节点,但节点的键需要在范围内
  • */
  • private ConcurrentSkipListMap.Node<K, V> hiNode() {
  • // 如果hi为null,则直接获取最后一个节点
  • if (hi == null)
  • return m.findLast();
  • // 否则根据hiInclusive是否为true判断是否包含结尾节点
  • else if (hiInclusive)
  • // 如果包含就传入EQ操作
  • return m.findNear(hi, m.LT | m.EQ);
  • else
  • // 否则没有EQ操作
  • return m.findNear(hi, m.LT);
  • }
  • /**
  • * Returns lowest absolute key (ignoring directonality)
  • * 获取最小的键,忽略是否逆序
  • */
  • private K lowestKey() {
  • ConcurrentSkipListMap.Node<K, V> n = loNode();
  • if (isBeforeEnd(n))
  • return n.key;
  • else
  • throw new NoSuchElementException();
  • }
  • /**
  • * Returns highest absolute key (ignoring directonality)
  • * 获取最大的键,忽略是否逆序
  • */
  • private K highestKey() {
  • ConcurrentSkipListMap.Node<K, V> n = hiNode();
  • if (n != null) {
  • K last = n.key;
  • if (inBounds(last))
  • return last;
  • }
  • throw new NoSuchElementException();
  • }
  • // 获取最小的键值对,包装为Map.Entry返回
  • private Map.Entry<K, V> lowestEntry() {
  • for (; ; ) {
  • ConcurrentSkipListMap.Node<K, V> n = loNode();
  • if (!isBeforeEnd(n))
  • return null;
  • Map.Entry<K, V> e = n.createSnapshot();
  • if (e != null)
  • return e;
  • }
  • }
  • // 获取最大的键值对,包装为Map.Entry返回
  • private Map.Entry<K, V> highestEntry() {
  • for (; ; ) {
  • ConcurrentSkipListMap.Node<K, V> n = hiNode();
  • if (n == null || !inBounds(n.key))
  • return null;
  • Map.Entry<K, V> e = n.createSnapshot();
  • if (e != null)
  • return e;
  • }
  • }
  • // 移除并返回最小的键值对,包装为Map.Entry返回
  • private Map.Entry<K, V> removeLowest() {
  • for (; ; ) {
  • Node<K, V> n = loNode();
  • if (n == null)
  • return null;
  • K k = n.key;
  • if (!inBounds(k))
  • return null;
  • // 移除操作
  • V v = m.doRemove(k, null);
  • if (v != null)
  • return new AbstractMap.SimpleImmutableEntry<K, V>(k, v);
  • }
  • }
  • // 移除并返回最大的键值对,包装为Map.Entry返回
  • private Map.Entry<K, V> removeHighest() {
  • for (; ; ) {
  • Node<K, V> n = hiNode();
  • if (n == null)
  • return null;
  • K k = n.key;
  • if (!inBounds(k))
  • return null;
  • // 移除操作
  • V v = m.doRemove(k, null);
  • if (v != null)
  • return new AbstractMap.SimpleImmutableEntry<K, V>(k, v);
  • }
  • }
  • /**
  • * Submap version of ConcurrentSkipListMap.getNearEntry
  • * 根据指定的key和比较关系查找并返回键值对
  • */
  • private Map.Entry<K, V> getNearEntry(K key, int rel) {
  • // 根据是否逆序调整比较关系
  • if (isDescending) { // adjust relation for direction
  • if ((rel & m.LT) == 0)
  • rel |= m.LT;
  • else
  • rel &= ~m.LT;
  • }
  • // 上下界控制
  • if (tooLow(key))
  • return ((rel & m.LT) != 0) ? null : lowestEntry();
  • if (tooHigh(key))
  • return ((rel & m.LT) != 0) ? highestEntry() : null;
  • // 上下界没超,正常查找
  • for (; ; ) {
  • Node<K, V> n = m.findNear(key, rel);
  • if (n == null || !inBounds(n.key))
  • return null;
  • K k = n.key;
  • V v = n.getValidValue();
  • if (v != null)
  • return new AbstractMap.SimpleImmutableEntry<K, V>(k, v);
  • }
  • }
  • /**
  • * Almost the same as getNearEntry, except for keys
  • * 根据指定的key和比较关系查找并返回键,
  • * 与getNearEntry()基本类似,仅仅增加了取键操作
  • * 不多做赘述
  • */
  • private K getNearKey(K key, int rel) {
  • if (isDescending) { // adjust relation for direction
  • if ((rel & m.LT) == 0)
  • rel |= m.LT;
  • else
  • rel &= ~m.LT;
  • }
  • if (tooLow(key)) {
  • if ((rel & m.LT) == 0) {
  • ConcurrentSkipListMap.Node<K, V> n = loNode();
  • if (isBeforeEnd(n))
  • return n.key;
  • }
  • return null;
  • }
  • if (tooHigh(key)) {
  • if ((rel & m.LT) != 0) {
  • ConcurrentSkipListMap.Node<K, V> n = hiNode();
  • if (n != null) {
  • K last = n.key;
  • if (inBounds(last))
  • return last;
  • }
  • }
  • return null;
  • }
  • for (; ; ) {
  • Node<K, V> n = m.findNear(key, rel);
  • if (n == null || !inBounds(n.key))
  • return null;
  • K k = n.key;
  • V v = n.getValidValue();
  • if (v != null)
  • return k;
  • }
  • }
  • /* ---------------- Map API methods -------------- */
  • // 大小
  • public int size() {
  • // 计数count
  • long count = 0;
  • // 从最小的节点开始往后进行遍历,到最后一个节点停止
  • for (ConcurrentSkipListMap.Node<K, V> n = loNode(); isBeforeEnd(n); n = n.next) {
  • // 如果遍历到的节点的值是有效的,则计数器自增
  • if (n.getValidValue() != null)
  • ++count;
  • }
  • // 最大不超过Integer.MAX_VALUE
  • return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) count;
  • }
  • // 是否为空
  • public boolean isEmpty() {
  • // 检查最小节点是否超过hi,以此判断是否为空
  • return !isBeforeEnd(loNode());
  • }
  • // 是否包含键
  • public boolean containsKey(Object key) {
  • // 参数检查
  • if (key == null) throw new NullPointerException();
  • K k = (K) key;
  • // 先检查键是否在范围内,然后通过ConcurrentSkipListMap的containsKey()方法判断
  • return inBounds(k) && m.containsKey(k);
  • }
  • // 是否包含值
  • public boolean containsValue(Object value) {
  • // 参数检查
  • if (value == null) throw new NullPointerException();
  • // 从最小的节点开始往后进行遍历,到最后一个节点停止
  • for (ConcurrentSkipListMap.Node<K, V> n = loNode(); isBeforeEnd(n); n = n.next) {
  • // 获取遍历到的节点的值,与传入参数value进行比较
  • V v = n.getValidValue();
  • if (v != null && value.equals(v))
  • return true;
  • }
  • return false;
  • }
  • // 添加键值对
  • public V put(K key, V value) {
  • // 检查范围
  • checkKeyBounds(key);
  • // 通过ConcurrentSkipListMap的put()方法添加
  • return m.put(key, value);
  • }
  • // 移除键所对应的键值对
  • public V remove(Object key) {
  • K k = (K) key;
  • // 检查范围,通过ConcurrentSkipListMap的remove()方法移除
  • return (!inBounds(k)) ? null : m.remove(k);
  • }
  • // 根据键获取对应的键值对
  • public V get(Object key) {
  • // 检查参数
  • if (key == null) throw new NullPointerException();
  • K k = (K) key;
  • // 检查范围,通过ConcurrentSkipListMap的get()方法获取
  • return ((!inBounds(k)) ? null : m.get(k));
  • }
  • // 清除Map
  • public void clear() {
  • // 从最小的节点开始往后进行遍历,到最后一个节点停止
  • for (ConcurrentSkipListMap.Node<K, V> n = loNode(); isBeforeEnd(n); n = n.next) {
  • // 对有效的节点通过ConcurrentSkipListMap的remove()方法移除
  • if (n.getValidValue() != null)
  • m.remove(n.key);
  • }
  • }
  • /* ---------------- ConcurrentMap API methods -------------- */
  • // 添加键值对
  • public V putIfAbsent(K key, V value) {
  • // 检查范围
  • checkKeyBounds(key);
  • // 通过ConcurrentSkipListMap的put()方法添加
  • return m.putIfAbsent(key, value);
  • }
  • // 移除键值对
  • public boolean remove(Object key, Object value) {
  • K k = (K) key;
  • // 检查范围,通过ConcurrentSkipListMap的remove()方法移除
  • return inBounds(k) && m.remove(k, value);
  • }
  • // 更新键值对
  • public boolean replace(K key, V oldValue, V newValue) {
  • // 检查范围
  • checkKeyBounds(key);
  • // 通过ConcurrentSkipListMap的replace()方法更新
  • return m.replace(key, oldValue, newValue);
  • }
  • // 更新键值对
  • public V replace(K key, V value) {
  • // 检查范围
  • checkKeyBounds(key);
  • // 通过ConcurrentSkipListMap的replace()方法更新
  • return m.replace(key, value);
  • }
  • /* ---------------- SortedMap API methods -------------- */
  • // 获取比较器
  • public Comparator<? super K> comparator() {
  • // 先获取ConcurrentSkipListMap的比较器
  • Comparator<? super K> cmp = m.comparator();
  • // 根据是否逆序选择返回对应的比较器
  • if (isDescending)
  • return Collections.reverseOrder(cmp);
  • else
  • return cmp;
  • }
  • /**
  • * Utility to create submaps, where given bounds override
  • * unbounded(null) ones and/or are checked against bounded ones.
  • * 用于创建子Map的方法
  • */
  • private SubMap<K, V> newSubMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
  • // 如果是逆序,则要进行特殊处理
  • if (isDescending) { // flip senses
  • // 将fromKey和toKey对调
  • K tk = fromKey;
  • fromKey = toKey;
  • toKey = tk;
  • // 将fromInclusive和toInclusive对调
  • boolean ti = fromInclusive;
  • fromInclusive = toInclusive;
  • toInclusive = ti;
  • }
  • if (lo != null) {
  • if (fromKey == null) {
  • /**
  • * 如果fromKey为null则将fromKey置为lo,并将fromInclusive置为loInclusive
  • * 这里表示传入的fromKey为null时,则直接从lo开始截取
  • */
  • fromKey = lo;
  • fromInclusive = loInclusive;
  • } else {
  • // 否则将fromKey与lo进行比较,确保fromKey在范围内
  • int c = m.compare(fromKey, lo);
  • if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
  • throw new IllegalArgumentException("key out of range");
  • }
  • }
  • if (hi != null) {
  • if (toKey == null) {
  • /**
  • * 如果toKey为null则将toKey置为hi,并将toInclusive置为hiInclusive
  • * 这里表示传入的toKey为null时,则直接截取到hi
  • */
  • toKey = hi;
  • toInclusive = hiInclusive;
  • } else {
  • // 否则将toKey与hi进行比较,确保toKey在范围内
  • int c = m.compare(toKey, hi);
  • if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
  • throw new IllegalArgumentException("key out of range");
  • }
  • }
  • // 创建对应的SubMap,使用SubMap的构造方法
  • return new SubMap<K, V>(m, fromKey, fromInclusive, toKey, toInclusive, isDescending);
  • }
  • // 创建指定范围元素的SubMap
  • public SubMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
  • // 检查参数
  • if (fromKey == null || toKey == null) throw new NullPointerException();
  • // 使用newSubMap()方法处理
  • return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
  • }
  • // 创建从头到toKey范围元素的SubMap,inclusive用于决定是否包含toKey
  • public SubMap<K, V> headMap(K toKey, boolean inclusive) {
  • // 检查参数
  • if (toKey == null) throw new NullPointerException();
  • // 使用newSubMap()方法处理
  • return newSubMap(null, false, toKey, inclusive);
  • }
  • // 创建从fromKey到尾范围元素的SubMap,inclusive用于决定是否包含fromKey
  • public SubMap<K, V> tailMap(K fromKey, boolean inclusive) {
  • // 检查参数
  • if (fromKey == null) throw new NullPointerException();
  • // 使用newSubMap()方法处理
  • return newSubMap(fromKey, inclusive, null, false);
  • }
  • // 创建[fromKey, toKey)范围元素的SubMap
  • public SubMap<K, V> subMap(K fromKey, K toKey) {
  • // 使用newSubMap()方法处理
  • return subMap(fromKey, true, toKey, false);
  • }
  • // 创建从头到toKey范围元素的SubMap,不包含toKey
  • public SubMap<K, V> headMap(K toKey) {
  • // 使用headMap()方法处理
  • return headMap(toKey, false);
  • }
  • // 创建从fromKey到尾范围元素的SubMap,包含fromKey
  • public SubMap<K, V> tailMap(K fromKey) {
  • // 使用tailMap()方法处理
  • return tailMap(fromKey, true);
  • }
  • // 创建逆序SubMap
  • public SubMap<K, V> descendingMap() {
  • // 将!isDescending传入SubMap的构造方法创建一个逆序的SubMap返回
  • return new SubMap<K, V>(m, lo, loInclusive, hi, hiInclusive, !isDescending);
  • }
  • /* ---------------- Relational methods -------------- */
  • public Map.Entry<K, V> ceilingEntry(K key) {
  • return getNearEntry(key, (m.GT | m.EQ));
  • }
  • public K ceilingKey(K key) {
  • return getNearKey(key, (m.GT | m.EQ));
  • }
  • public Map.Entry<K, V> lowerEntry(K key) {
  • return getNearEntry(key, (m.LT));
  • }
  • public K lowerKey(K key) {
  • return getNearKey(key, (m.LT));
  • }
  • public Map.Entry<K, V> floorEntry(K key) {
  • return getNearEntry(key, (m.LT | m.EQ));
  • }
  • public K floorKey(K key) {
  • return getNearKey(key, (m.LT | m.EQ));
  • }
  • public Map.Entry<K, V> higherEntry(K key) {
  • return getNearEntry(key, (m.GT));
  • }
  • public K higherKey(K key) {
  • return getNearKey(key, (m.GT));
  • }
  • public K firstKey() {
  • return isDescending ? highestKey() : lowestKey();
  • }
  • public K lastKey() {
  • return isDescending ? lowestKey() : highestKey();
  • }
  • public Map.Entry<K, V> firstEntry() {
  • return isDescending ? highestEntry() : lowestEntry();
  • }
  • public Map.Entry<K, V> lastEntry() {
  • return isDescending ? lowestEntry() : highestEntry();
  • }
  • public Map.Entry<K, V> pollFirstEntry() {
  • return isDescending ? removeHighest() : removeLowest();
  • }
  • public Map.Entry<K, V> pollLastEntry() {
  • return isDescending ? removeLowest() : removeHighest();
  • }
  • /* ---------------- Submap Views -------------- */
  • public NavigableSet<K> keySet() {
  • KeySet<K> ks = keySetView;
  • return (ks != null) ? ks : (keySetView = new KeySet(this));
  • }
  • public NavigableSet<K> navigableKeySet() {
  • KeySet<K> ks = keySetView;
  • return (ks != null) ? ks : (keySetView = new KeySet(this));
  • }
  • public Collection<V> values() {
  • Collection<V> vs = valuesView;
  • return (vs != null) ? vs : (valuesView = new Values(this));
  • }
  • public Set<Map.Entry<K, V>> entrySet() {
  • Set<Map.Entry<K, V>> es = entrySetView;
  • return (es != null) ? es : (entrySetView = new EntrySet(this));
  • }
  • public NavigableSet<K> descendingKeySet() {
  • return descendingMap().navigableKeySet();
  • }
  • Iterator<K> keyIterator() {
  • return new SubMapKeyIterator();
  • }
  • Iterator<V> valueIterator() {
  • return new SubMapValueIterator();
  • }
  • Iterator<Map.Entry<K, V>> entryIterator() {
  • return new SubMapEntryIterator();
  • }
  • /**
  • * Variant of main Iter class to traverse through submaps.
  • * 迭代器基类,没有实现next()
  • */
  • abstract class SubMapIter<T> implements Iterator<T> {
  • /**
  • * the last node returned by next()
  • * 这个节点为记录上一次返回的数据节点
  • */
  • Node<K, V> lastReturned;
  • /**
  • * the next node to return from next();
  • * 这个节点会记录当次应该返回的数据节点
  • */
  • Node<K, V> next;
  • /**
  • * Cache of next value field to maintain weak consistency
  • * 缓存当次应该返回的数据节点的值
  • */
  • V nextValue;
  • SubMapIter() {
  • for (; ; ) {
  • /**
  • * 初始化时,将next指向SubMap中的第一个Node节点
  • * 需要根据是否逆序来决定指向头还是尾
  • */
  • next = isDescending ? hiNode() : loNode();
  • // 如果next为null,直接结束循环
  • if (next == null)
  • break;
  • Object x = next.value;
  • // 检查next的有效性
  • if (x != null && x != next) {
  • // 检查next的key是否在范围内,如果不在就将next置为null
  • if (!inBounds(next.key))
  • next = null;
  • else
  • // 如果有效用nextValue记录next的value
  • nextValue = (V) x;
  • break;
  • }
  • }
  • }
  • // 判断是否有下一个元素
  • public final boolean hasNext() {
  • return next != null;
  • }
  • final void advance() {
  • // 检查next,如果next为null,抛出错误
  • if (next == null)
  • throw new NoSuchElementException();
  • // 记录next为lastReturned
  • lastReturned = next;
  • if (isDescending)
  • // 如果是逆序,调用descend()
  • descend();
  • else
  • // 如果是顺序,调用ascend()
  • ascend();
  • }
  • // 顺序遍历方法
  • private void ascend() {
  • for (; ; ) {
  • // 将next后移
  • next = next.next;
  • // 如果新的next为null,代表迭代到末尾了,直接跳出
  • if (next == null)
  • break;
  • // 检查next是否有效
  • Object x = next.value;
  • if (x != null && x != next) {
  • // 检查next的key是否在范围内,如果不在就将next置为null
  • if (tooHigh(next.key))
  • next = null;
  • else
  • // 如果有效用nextValue记录next的value
  • nextValue = (V) x;
  • break;
  • }
  • }
  • }
  • // 逆序遍历方法
  • private void descend() {
  • for (; ; ) {
  • // 找到比上一次返回的节点的键小的节点作为next
  • next = m.findNear(lastReturned.key, LT);
  • // 如果新的next为null,代表没有合适的节点,直接跳出
  • if (next == null)
  • break;
  • // 检查next是否有效
  • Object x = next.value;
  • if (x != null && x != next) {
  • // 检查next的key是否在范围内,如果不在就将next置为null
  • if (tooLow(next.key))
  • next = null;
  • else
  • // 如果有效用nextValue记录next的value
  • nextValue = (V) x;
  • break;
  • }
  • }
  • }
  • public void remove() {
  • // 检查元素是否有效,即不能从空的ConcurrentSkipListMap中移除元素
  • Node<K, V> l = lastReturned;
  • if (l == null)
  • throw new IllegalStateException();
  • // 根据lastReturned的key移除元素
  • m.remove(l.key);
  • // 将lastReturned置为null
  • lastReturned = null;
  • }
  • }
  • // 值迭代器
  • final class SubMapValueIterator extends SubMapIter<V> {
  • public V next() {
  • // 获取nextValue,这个变量记录了next的值
  • V v = nextValue;
  • // 使next后移
  • advance();
  • // 返回值
  • return v;
  • }
  • }
  • // 键迭代器
  • final class SubMapKeyIterator extends SubMapIter<K> {
  • public K next() {
  • // 将next赋值给n
  • Node<K, V> n = next;
  • // 使next后移
  • advance();
  • // 返回n的key值
  • return n.key;
  • }
  • }
  • // 键值对迭代器
  • final class SubMapEntryIterator extends SubMapIter<Map.Entry<K, V>> {
  • public Map.Entry<K, V> next() {
  • // 将next赋值给n
  • Node<K, V> n = next;
  • // 获取nextValue,这个变量记录了next的值
  • V v = nextValue;
  • // 使next后移
  • advance();
  • // 返回以SimpleImmutableEntry包装的键值对实例
  • return new AbstractMap.SimpleImmutableEntry<K, V>(n.key, v);
  • }
  • }
  • }
  • // Unsafe mechanics
  • private static final sun.misc.Unsafe UNSAFE;
  • // head字段的偏移量
  • private static final long headOffset;
  • static {
  • try {
  • UNSAFE = sun.misc.Unsafe.getUnsafe();
  • Class k = ConcurrentSkipListMap.class;
  • // Unsafe取head字段的偏移量
  • headOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("head"));
  • } catch (Exception e) {
  • throw new Error(e);
  • }
  • }
  • }