Java多线程 32 - ConcurrentSkipListMap详解(1)
发布于 / 2018-08-26
简介:ConcurrentSkipListMap是线程安全的有序的哈希表,适用于高并发的场景。
1. ConcurrentSkipListMap简介
注:本文讲解的ConcurrentSkipListMap基于JDK 1.7.0_07。
ConcurrentSkipListMap是线程安全的有序的哈希表,适用于高并发的场景。ConcurrentSkipListMap和TreeMap虽然都是有序的哈希表,但有以下区别:
- 它们的线程安全机制不同,TreeMap是非线程安全的,而ConcurrentSkipListMap是线程安全的。
- ConcurrentSkipListMap是通过跳表实现的,而TreeMap是通过红黑树实现的。
跳表(Skip List)是平衡树的一种替代的数据结构,和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。
ConcurrentSkipListMap的相关类图结构如下:
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. 跳表结构和原理
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链的节点类,它除了拥有key
和value
两个分别表示键和值的成员属性外,还拥有一个成员变量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类为value
和next
变量分别提供了CAS修改方法,保证在并发情景下对其修改过程的一致性。getValidValue()
方法则用于获取有效节点的值,规避基础头节点和标记节点这两类无效节点。
总体来说,Node类的设计相对复杂,尤其是标记节点的相关操作,这里大家只需要对标记节点有一个印象,在后面的内容中会结合实际操作详细介绍标记节点的用处。
4.2. Index类的设计
Index类是构成跳表框架的主要类,它包括一个Node节点的引用,用于存储键值对数据,另外还包括两个指向引用:right
和down
,用于跳表框架的构建,源码如下:
- 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_HEADER
和head
的意义。
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);
- }
- }
- }
推荐阅读
Java多线程 46 - ScheduledThreadPoolExecutor详解(2)
ScheduledThreadPoolExecutor用于执行周期性或延时性的定时任务,它是在ThreadPoolExe...