// 构造一个新的空映射，该映射按照键的自然顺序进行排序
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()

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--;
            }
        }
    }
}

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

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);
        }
    }
}

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);
        }
    }
}

/**
 * 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;
    }
}

// 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);
    }
}

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

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;

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);
        }
    }
}