// 构造一个新的空映射，该映射按照键的自然顺序进行排序
ConcurrentSkipListMap()
// 构造一个新的空映射，该映射按照指定的比较器进行排序
ConcurrentSkipListMap(Comparator<? super K> comparator)
// 构造一个新映射，该映射所包含的映射关系与给定映射包含的映射关系相同，并按照键的自然顺序进行排序
ConcurrentSkipListMap(Map<? extends K, ? extends V> m)
// 构造一个新映射，该映射所包含的映射关系与指定的有序映射包含的映射关系相同，使用的顺序也相同
ConcurrentSkipListMap(SortedMap<K, ? extends V> m)

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

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

public void putAll(Map<? extends K, ? extends V> m) {
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
}

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

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

<15, "Mary">
<20, "Jack">

// 查找第一个数据节点
Node<K, V> findFirst()
// 查找最后一个数据节点
Node<K, V> findLast()
// 根据key查找符合条件的前驱节点
private Node<K, V> findPredecessor(Comparable<? super K> key)
// 具体用处请参考该方法的完整注释的讲解
private Node<K, V> findPredecessorOfLast()
// 根据key查找数据节点
private Node<K, V> findNode(Comparable<? super K> key)
// 根据指定操作查找附近的数据节点
Node<K, V> findNear(K kkey, int rel)

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

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

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

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

// 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；（我一直觉得此处有问题，当传入带有EQ的操作，此时也将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;
        }
    }
}

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

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

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

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

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

/**
 * 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 <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) {
    // 调用doGet()方法获取key对应的值，如果返回不为null则表示存在这个key
    return doGet(key) != null;
}

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

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

/**
 * Main insertion method.  Adds element if not present, or
 * replaces value if present and onlyIfAbsent is false.
 * 主要的插入方法，当键不存在时会添加，当键存在时，如果onlyIfAbsent为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，则直接返回n的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;
        }
    }
}

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

// 比较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;
}

// 比较key和n的key的大小
int c = key.compareTo(n.key);
...
if (c == 0) {
    /**
     * key与n的key相等，则表示键已存在，此时如果onlyIfAbsent为false，
     * 就修改n的value为新value，如果修改成功就返回旧value，
     * 如果onlyIfAbsent为true，则直接返回n的value，不做任何处理，
     * 否则进行下一次尝试
     */
    if (onlyIfAbsent || n.casValue(v, value))
        return (V) v;
    else
        // 否则跳出内层循环
        break; // restart if lost race to replace value
}

/**
 * 走到这里有两种情况：
 * 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;

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

Comparable<? super K> key = comparable(idx.node.key);
Index<K, V> q = h;
// 头节点的后继节点
Index<K, V> r = q.right;
// 取出该后继节点的Node
Node<K, V> n = r.node;
// compare before deletion check avoids needing recheck
// 与传入的待插入Index节点比较Node节点的key
int c = key.compareTo(n.key);
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;

// 插入成功，insertionLevel自减后为0时，就可以返回了
if (--insertionLevel == 0) {
    // need final deletion check before return
    // 返回之前检查t是否被删除了，如果被删除了就调用findNode(key)进行清理
    if (t.indexesDeletedNode())
        // findNode(key)方法的代码会移除已标记为删除的节点
        findNode(key);
    // 返回
    return;
}

if (--j >= insertionLevel && j < indexLevel)
    // 下潜到待插入Index列的下一层级
    t = t.down;

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
        /*
         *
         * 走到这里，说明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);
        ...
        // 会将构建好的一列Index添加到跳表中
        addIndex(idxs[k], oldh, k);
    }
}

/**
 * 走到这里，说明待插入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;