Java多线程
Java并发
JUC集合

Java多线程 34——ConcurrentSkipListMap(JDK1.7)详解(三)

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

1. ConcurrentSkipListMap源码解析(二)

上一篇文章中已经对ConcurrentSkipListMap最主要的put相关操作方法介绍完了,接下来的内容中将继续介绍删除、修改、查询等操作的工作流程和原理。

1.1. remove()相关方法

ConcurrentSkipListMap的删除相关的操作是两个重载方法:remove(Object key)remove(Object key, Object value),两个方法内部都调用了doRemove(Object okey, Object value)方法:

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

因此其实我们需要关注的是doRemove(Object okey, Object value)方法,它的源码如下:

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

其实doRemove(Object, Object)方法的文档注释已经阐明了它的删除原理,即:定位Node节点、将其值置为null、添加删除标记节点,将其从前驱节点上断开连接,移除辅助索引节点,还有可能会减少HeadIndex的层级。

根据上面源码中的解释,以我们之前添加了<17, "Tom">之后的ConcurrentSkipListMap为例,演示删除<20, "Jack">键值对的过程。

1.1.1. 定位合适的前驱节点

doRemove(Object, Object)方法首先也将传入的okey转换为了一个Comparable对象,以方便后面的比较操作;接下来同样是两个嵌套的无限for循环,在外层循环中首先通过findPredecessor(key)找到以key为键做参看的符合条件的前驱节点,这个方法在之前添加键值对数据里面已经讲解地很清楚了,这里只贴出对应的查找流程图,读者可以对照源码自行分析:

1.remove操作——定位合适的前驱节点.png

找到的前驱节点被标识为b,然后取b的后继节点为n,接下来会进入内层循环。记住,此时b是找到的符合条件的前驱节点,nb的后继节点。

在内层循环中,当n为null时,则表示此时b是Node链中的最后一个节点,因此以key为键的Node节点并不存在,直接返回null即可;否则取n的后继节点标识为f,此时得到的bnf的顺序是b -> n -> f

1.1.2. 检查并标识待删除节点

接下来是一系列的检查工作,首先会判断n节点的值是否是null,如果为null则表示n节点已经被标识为删除了,因此使用n.helpDelete(b, f)将其清除,然后跳出内层循环,继续向下执行下一次循环。Node类的helpDelete(Node<K, V> b, Node<K, V> f)方法在前面已经讲解过了,它会协助当前Node从bf之前删除(通过添加删除标记节点或直接移除)。

如果n节点的值不为null,就判断n节点的值是否指向n自己,如果是则表示n其实是一个删除标记节点,此时直接跳出跳出内层循环,继续向下执行下一次循环即可;如果n节点的值也不是指向n自己,就判断b的值是否为null,如果是则表示b是被删除的节点,直接跳出跳出内层循环,继续向下执行下一次循环即可,否则的话,检查工作到此为止,可以继续往下执行了。

下面的代码会对比传入的键与n节点的键;这里需要解释一下,因为b是符合条件的前驱节点,而ConcurrentSkipListMap跳表中Node节点的是根据键的顺序从小到大排列的,因此传入的键如果存在,则应该就是b之后的某个Node节点的键。这里的比较分三种情况:

  1. 传入的键比n节点的键小,则表示传入的键在跳表中并不存在,返回null即可;表现代码如下:
  • if (c < 0)
  • /**
  • * 表示没有找到
  • * 注意,此时b是传入key符合条件的前驱,而n是b的后继,
  • * 如果此时传入的key比n的key小,说明key对应的节点在n的前面,
  • * 而此时b和n是连接起来的前后两个节点,这种情况下key所对应的节点是不存在的
  • */
  • return null;
  1. 传入的键比n节点的键大,则表示传入的键可能是n节点后面的某个节点的键,因此需要后移;表现代码如下:
  • if (c > 0) {
  • /**
  • * 要比n的key大,就往后移,跳出进行下一次循环,即往后遍历:
  • * 之前:b -> n -> f
  • * 现在:(old b) -> b(old n) -> n(old f)
  • */
  • b = n;
  • n = f;
  • continue;
  • }
  1. 最后一种情况,自然是传入的键已经找到了,它与n的键是相同的,此时需要判断doRemove(Object okey, Object value)传入的value参数,如果value参数不为null,且value参数与nvalue不同,则表示不符合删除条件,直接返回null;否则会使用CAS方式将n节点的value修改为null;表现代码如下:
  • // 走到这里说明比较结果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;

如果修改n节点的value为null失败就会跳出内层循环进行新的重试,修改成功就会往下执行。单纯的修改value操作体现在示意图中则非常简单:

2.remove操作——修改对应的Node节点的value为null.png

在修改n节点的value为null成功之后,会执行下面的代码:

  • /**
  • * 当前结构为: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();
  • }

这部分代码也比较抽象,首先我们分析if的条件!n.appendMarker(f) || !b.casNext(n, f),这个条件中存在两种操作,其中n.appendMarker(f)用于在n的后面添加一个删除标记节点,而b.casNext(n, f)则是用CAS方式将f修改为b的后继节点;只有在n.appendMarker(f)执行成功后才会执行b.casNext(n, f),这是删除节点的一般操作,即先标记再删除,通过if条件的方式,可以保证两步操作有一步失败就执行findNode(key)重试。我们先分析两步操作都成功的情况,执行示意图如下:

3.remove操作——删除对应的Node节点.png

1.1.3. 清理无效的索引节点

当上面两步操作都成功后,if条件不成立,就会执行else分支;虽然此时对应的Node节点已经从原Node链中断开连接了,但指向该Node节点的索引链还存在,因此else分支的任务就是使用findPredecessor(key)操作清理无用的Index节点,该方法在前面已经讲解过了,可以对照下面本示例清理过程的示意图逐步分析:

4.remove操作——删除失效的索引节点.png

1.1.4. 减少层级

我们注意到,在else分支中,使用findPredecessor(key)清理无效的索引节点后,还有可能会执行tryReduceLevel()操作:

  • if (head.right == null)
  • // 头结点的right为null,表示头节点这一层只有head一个节点,所以需要减少层级
  • tryReduceLevel();

即当head节点的right指针为null时,就会减少层级。以我们上面的示例而言,最后得到的跳表中,head节点这一层确实只有head自己,其他节点都被移除了,因此会调用tryReduceLevel()方法移除无效层级,该方法的源码如下:

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

这个方法的源码执行情况注释已经讲解清楚了,这里就不再赘述。

1.1.5. 另一种情况

下面我们讨论另一种情况,即n.appendMarker(f)b.casNext(n, f)有一个或两个执行失败,此时会调用findNode(key)方法进行重试;这里我们考虑如下两种情况:

  1. n.appendMarker(f)执行成功,而b.casNext(n, f)执行失败。此时代表在n节点后面添加删除标记节点成功,但将bn断开连接失败,得到的结构如下:

5.remove操作——删除对应Node节点失败情况(一).png

此时在findNode(key)方法中,会通过helpDelete(Node<K, V> b, Node<K, V> f)方法将n节点移除;findNode(Comparable<? super K>)方法在之前已经讲解过,在本示例中,该方法处理过程中得到的节点结构也是b -> n -> f,其中f已经是一个删除标记节点了。n.helpDelete(b, f)会协助将nb节点的后继上断开,这个方法以前讲解过,这里回顾一下:

  • void helpDelete(Node<K, V> b, Node<K, V> f) {
  • if (f == next && this == b.next) {
  • if (f == null || f.value != f) // not already marked
  • // f为null或f.value不为自己,说明f不是删除标记节点,需要添加
  • appendMarker(f);
  • else
  • // 上述情况会走这一步,即f是删除标记节点
  • b.casNext(this, f.next);
  • }
  • }

协助删除的步骤如下:

6.remove操作——删除对应Node节点失败情况(一)解决办法.png

  1. n.appendMarker(f)执行失败,b.casNext(n, f)并没有执行,此时相当于删除标记节点都添加失败了。得到的结构如下:

7.remove操作——删除对应Node节点失败情况(二).png

这种情况下,findNode(Comparable<? super K>)方法会通过调用两次n.helpDelete(b, f)来解决,第一次调用会为n节点添加删除标记节点,第二次调用才会真正协助将nb节点的后继上断开,过程示意图如下:

8.remove操作——删除对应Node节点失败情况(二)解决办法.png

同时需要注意的是,在findNode(Comparable<? super K>)方法中还会使用外层循环内的findPredecessor(key)来协助删除失效索引节点。

1.1.6. 其他的remove()方法

remove(Object key)remove(Object key, Object value)两个方法用于移除特定的键值对,其实ConcurrentSkipListMap还提供了两个便捷方法:doRemoveFirstEntry()doRemoveLastEntry(),用于移除并返回第一对键值对和最后一对键值对。有了上面对doRemove(Object okey, Object value)的认识,理解这两个方法都比较简单,先看doRemoveFirstEntry()的源码:

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

doRemoveFirstEntry()方法会直接从head.node,也即是BASE_HEADER节点获取第一个节点n,并验证有效性通过后通过n.appendMarker(f) || b.casNext(n, f)将该节点从Node链中移除,然后清理无效索引,返回由n的键值对构成的SimpleImmutableEntry实例即可。

这里主要说一下用于清理无效索引的clearIndexToFirst()方法,源码如下:

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

从该方法的实现可知,它仅仅作用于删除第一个Node节点的情况下,清理原属于第一个Node节点的失效索引。实现方式是从head节点开始,使指向headq不断下潜,下潜过程中查看q的右节点是否是被删除的索引节点,如果是就进行清理。在清理完失效节点后,还会尝试减少层级。

相比之下,doRemoveLastEntry()的实现稍稍要复杂一点,它的源码如下:

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

doRemoveLastEntry()首先使用findPredecessorOfLast()方法定位到了Node链中比较靠后的节点。findPredecessorOfLast()方法在前面讲到过,当时提到说该方法定位到的Node节点其实并不是最后一个Node节点的前驱;findPredecessorOfLast()方法只在本方法中有使用。

回到doRemoveLastEntry()方法,使用findPredecessorOfLast()方法获取到的Node节点是bnb的后继,当n不为null时,还会使用一个无限循环从n开始往后遍历,直到找到真正的“最后一个Node节点”,对其进行删除操作,并返回以其键和值构造的SimpleImmutableEntry实例即可。相信从这个方法的实现中,大家对findPredecessorOfLast()方法的作用也有更深的理解了。

另外需要提到的一点是,ConcurrentSkipListMap中有两个方法直接使用了doRemoveFirstEntry()doRemoveLastEntry(),这两个方法比较简单,这里只给出源码:

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

1.2. replace()相关方法

添加和删除是ConcurrentSkipListMap中的难点方法,因为涉及到跳表结构的更新,但接下来的更新和查询方法就比较简单了,因为它们只涉及对数据的更新,并不需要维护跳表结构。

ConcurrentSkipListMap提供了两个更新操作:replace(K key, V oldValue, V newValue)replace(K key, V value),这两个方法的不同点在于,前一个方法传入了oldValue参数,删除前会判断节点的值是否与oldValue一致,如果一致才会删除;这两个方法的源码如下:

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

其实这两个更新操作的实现非常简单,就是使用了我们前面讲解过的findNode(Comparable<? super K> key)方法查找对应的Node节点,如果查找到了就使用CAS方式更新值即可;唯一的差别在于前一个更新方法会判断旧值是否与传入的一致。

1.3. get()相关方法

同样的,ConcurrentSkipListMap的get(Object key)方法实现也比较简单,内部调用了doGet(Object key),但doGet(Object key)的实现依旧是使用findNode(Comparable<? super K> key)方法查找对应的Node节点,如果查找到的Node节点值不为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);
  • }
  • /**
  • * 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;
  • }
  • }

1.4. clear()相关方法

ConcurrentSkipListMap的clear()方法用于清空Map,实现异常简单,只需要在内部调用initialize()即可,源码如下:

  • /**
  • * Removes all of the mappings from this map.
  • *
  • * 清空Map
  • */
  • public void clear() {
  • initialize();
  • }

1.5. 遍历相关方法

ConcurrentSkipListMap提供了迭代器进行遍历的同时,还提供了获取键值集合的方法,下面将讨论这部分的内容。

1.5.1. 迭代器相关

ConcurrentSkipListMap提供了迭代器对键值对数据进行遍历操作,其中内部类Iter是一个抽象类,实现了Iterator接口,对其中除next()以为的方法进行了实现,原理比较简单,源码如下:

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

上面源码中的注释已经对Iter类讲解得很清楚了,这里不再赘述。next()方法留给了KeyIterator、ValueIterator和EntryIterator三个内部类进行实现,分别用于提供键迭代器、值迭代器和键值对迭代器,原理也比较简单,因为Iter已经处理了最重要的业务;源码如下:

  • // 值迭代器
  • 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>> {
  • // 实现next方法
  • 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);
  • }
  • }

另外ConcurrentSkipListMap提供了相关的工厂方法用于快速获取三类迭代器:

  • // 迭代器相关的工厂方法
  • Iterator<K> keyIterator() {
  • return new KeyIterator();
  • }
  • Iterator<V> valueIterator() {
  • return new ValueIterator();
  • }
  • Iterator<Map.Entry<K, V>> entryIterator() {
  • return new EntryIterator();
  • }

1.5.2. 集合视图相关

除了常见的对键值进行遍历的迭代器,ConcurrentSkipListMap还提供了大量的集合视图操作方法。我们首先看KetSet、ValueSet和EntrySet这三个类。

1.5.2.1. KeySet类

KeySet类用于包装并返回键集,先关注怎样创建KeySet实例,ConcurrentSkipListMap提供了keySet()方法,源码如下:

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

keySet()方法的注释可知,该方法返回的键集实例是一个NavigableSet类型的KeySet实例,KeySet自带缓存效应,会使用ConcurrentSkipListMap的ks变量对其进行引用,防止多次创建;同时这个实例依赖于ConcurrentSkipListMap,当ConcurrentSkipListMap中的键值对数据发生改变时,KeySet中的数据也会发生改变;这一点从KeySet的源码也有体现:

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

由于KeySet类其实内部是引用了一个ConcurrentNavigableMap类型的对象m,在创建KeySet时将ConcurrentSkipListMap实例(或ConcurrentSkipListMap.SubMap实例,后面会讲)传入赋值给m,大部分操作都是使用m对象的自有方法;前面的方法都比较简单,底层调用m对象的相关方法都已经介绍过了,这里主要讲解SubMap相关类型的实例,观察KeySet类下面的方法:

  • // 逆序迭代器
  • 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());
  • }

可以看到,内部多是调用了m对象的subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)headMap(K toKey, boolean inclusive)tailMap(K fromKey, boolean inclusive)descendingMap()等方法;对于ConcurrentSkipListMap而言,这些方法是一组SortedMap API方法,源码如下:

  • /**
  • * 返回从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);
  • }

从这几个方法的源码可知,最重要的其实是SubMap的构造方法SubMap(ConcurrentSkipListMap<K, V> map, K fromKey, boolean fromInclusive, K toKey, boolean toInclusive, boolean isDescending),因此我们需要关注的是SubMap的实现,但在讲解SubMap之前我们先迅速地将与KeySet同等地位的Values和EntrySet两个类了解一下。

1.5.2.2. Values类和EntrySet类

Values类和EntrySet类与KeySet大同小异,ConcurrentSkipListMap也提供了values()entrySet()方法用于获取二者的实例,源码如下:

  • public Collection<V> values() {
  • Values vs = values;
  • return (vs != null) ? vs : (values = new Values(this));
  • }
  • public Set<Map.Entry<K, V>> entrySet() {
  • EntrySet es = entrySet;
  • return (es != null) ? es : (entrySet = new EntrySet(this));
  • }

同时二者的实现业与KeySet类非常相似,这里只贴出相关源码,大家可以简单地了解一下:

  • // 值集类
  • 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);
  • }
  • }

这里需要另外提一下的是KeySet、Values和EntrySet都用到的toList(Collection<E> c)方法,该方法位于ConcurrentSkipListMap中,实现也比较简单,用于将Collection实例转为一个List实例:

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

1.5.2.3. SubMap类

SubMap是ConcurrentSkipListMap的静态内部类,用于对ConcurrentSkipListMap的元素进行各类子范围操作。我们先查看它的的声明:

  • static final class SubMap<K, V> extends AbstractMap<K, V>
  • implements ConcurrentNavigableMap<K, V>, Cloneable, java.io.Serializable

从声明上看,SubMap继承自AbstractMap,实现了ConcurrentNavigableMap、Cloneable和Serializable三个接口;AbstractMap抽象类实现了一些简单且通用的方法,Cloneable和Serializable则分别是支持克隆和序列化的接口。

1.5.2.3.1. 成员变量和构造方法

先观察SubMap中有用的成员变量,成员变量的含义都比较简单,注释解释得比较详细:

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

SubMap的构造方法是一个使用频率较高的方法,它的定义如下:

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

构造方法虽然接收了多个参数,但它只对这些参数进行了检查和引用,并没有做过多控制。

1.5.2.3.2. 私有工具方法

接下来我们看一下SubMap的私有方法:

  • /* ---------------- 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;
  • }
  • }
  • /**
  • * 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提供了大量的私有方法,但其实这些私有方法的实现很简单,它们主要为后面开放对外的操作服务。

1.5.2.3.3. 公有方法

SubMap中实用的方法主要是提供给外界访问的方法,这些方法分为四类:

  1. 简单API方法;
  2. SortedMap API;
  3. 关系相关API;
  4. SubMap迭代相关的API。

我们先了解简单API方法;简单API方法是指与ConcurrentSkipListMap各类操作相似的API,主要有以下一些:

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

这些简单API方法都比较简单,基本都是使用了SubMap的私有工具方法和ConcurrentSkipListMap的方法来完成具体的操作的;从它们的实现可知,所有的操作都会影响到实际的ConcurrentSkipListMap中的元素。

SortedMap API相关的方法则用于截取ConcurrentSkipListMap某些范围的元素为一个SubMap对象,这些方法的源码如下:

  • // 创建指定范围元素的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);
  • }

其实这些方法底层都调用了上面介绍到的newSubMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)方法,也都比较简单。

而关系判断相关的API方法则更简单了,底层基本就是一些私有方法的组合使用,这里也只是罗列,具体原理可以自行研究:

  • /* ---------------- 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迭代相关的API方法,几个基本方法其实与ConcurrentSkipListMap的迭代方法大同小异:

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

获取键集、值集和键值集的方法与ConcurrentSkipListMap一样,都是使用KeySet、Values和EntrySet来实现的;其中值得关注的是SubMapKeyIterator、SubMapValueIterator和SubMapEntryIterator三个类,这三个类结构与ConcurrentSkipListMap的KeyIterator、ValueIterator和EntryIterator非常像,继承了SubMapIter类,SubMapIter类是一个抽象类,源码如下:

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

SubMapIter的实现与Iter类非常相似,区别在于SubMapIter会根据是否逆序来选择合适的遍历方式,从源码可知,逆序遍历每次都会使用findNear(K, int)查找合适的节点,因此逆序遍历效率会非常低下。SubMapIter也将next()方法留给了SubMap的KeyIterator、ValueIterator和EntryIterator三个内部类进行实现,分别用于提供键迭代器、值迭代器和键值对迭代器,原理也比较简单,因为SubMapIter已经处理了最重要的业务;源码如下:

  • // 值迭代器
  • 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);
  • }
  • }

从源码可以看出,这三个类的实现与ConcurrentSkipListMap的KeyIterator、ValueIterator和EntryIterator除了声明基本一模一样

1.6. clone()方法

ConcurrentSkipListMap的clone()的实现基本是借助之前讲解的buildFromSorted(SortedMap<K, ? extends V>)来实现的:

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

至于调用的父类clone()方法,最后调用的依旧是底层的Native方法:

  • // 来自AbstractMap类
  • protected Object clone() throws CloneNotSupportedException {
  • AbstractMap<?,?> result = (AbstractMap<?,?>)super.clone();
  • result.keySet = null;
  • result.values = null;
  • return result;
  • }
  • // 来自Object类
  • protected native Object clone() throws CloneNotSupportedException;

1.7. 序列化相关方法

ConcurrentSkipListMap重写了序列化相关的方法writeObject(ObjectOutputStream s)readObject(ObjectInputStream s),它们的源码如下:

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

其中从writeObject(ObjectOutputStream s)源码可以得知,写出操作中会先调用默认写出方法将必要的可写数据写出,然后遍历所有的键值对,将键和值一一写出。而readObject(ObjectInputStream s)的实现虽然非常复杂,但它的原理其实就是我们前面讲到过的buildFromSorted(SortedMap<K, ? extends V>),主要代码一模一样,这里也不再赘述。