Java 并发容器(三):基于跳表的 Map 和 Set

  1. Java 并发包中可排序的对应版本工具类是?
    答:

    • HashMap/HashSet 基于哈希,不能对元素排序,对应的可排序的容器类是 TreeMap/TreeSet
    • Java 并发包中可排序的对应版本不是基于树,而是基于 SkipList(跳跃表)
    • Java 并发包中与 TreeMap/TreeSet 对应的并发版本是 ConcurrentSkipListMapConcurrentSkipListSet
    • TreeSet 是基于 TreeMap 实现的,ConcurrentSkipListSet 是基于 ConcurrentSkipListMap 实现的
    • ConcurrentSkipListMap 是基于 SkipList 实现的,SkipList 称为跳跃表或跳表,是一种数据结构
  2. Java 可排序容器的并发版本为什么采用跳表而不是树呢?
    答:因为跳表这种数据结构更易于实现高效的并发算法

  3. ConcurrentSkipListMap 的特点是?
    答:

    • 没有使用锁,所有操作都是无阻塞的,所有操作都可以并行,包括写,多线程可以同时写
    • ConcurrentHashMap 类似,迭代器不会抛出 ConcurrentModificationException 异常,也是弱一致的,迭代可能反映最新修改也可能不反映,一些方法如 putAll()clear() 不是原子的。
    • TreeMap 一样,可排序,默认按键的自然顺序,也可以传递比较器自定义排序,实现了 SortedMapNavigableMap 接口。
    • ConcurrentSkipListMapConcurrentSkipListSet 基于跳表实现,有序、无锁非阻塞、完全并行,主要操作复杂度都是 O(log(N))
  4. 跳表 SkipList 的基本实现原理?
    答:

    • 跳表是基于链表的,在链表的基础上加了多层索引结构
    • 最下面一层就是最基本的单向链表,这个链表是有序的。虽然有序,但与数组不同,链表不能根据索引直接定位,不能进行二分查找。
    • 为了快速查找,跳表有多层索引结构。高层的索引节点一定同时是低层的索引节点。高层的索引节点少,低层的多
    • 统计概率上,第一次索引节点是实际元素数的 1/2,第二层是第一层的 1/2逐层减半,但这不是绝对的,有随机性,只是大致如此
    • 每个索引节点有两个指针:一个向右,指向下一个同层的索引节点;另一个向下,指向下一层的索引节点或基本链表节点
  5. ConcurrentSkipListMap 怎样实现查找?
    答:

    • 有了跳表这个数据结构,就可以实现类似的二分查找了。
    • 查找元素总是从高层开始,将待查值与下一个索引节点的值进行比较,如果大于索引节点,就向右移动,继续比较,如果小于索引节点,则向下移动到下一层进行比较。这个结构是有序的,查找的性能与二叉树类似,复杂度是 O(log(N))
    • 这个结构的构建与二叉树的构建类似,是在更新过程中进行保持的,保存元素的基本思路是:

      • 先保存到基本链表,找到待插入的位置,找到位置后,插入基本链表。
      • 更新索引层。
  6. ConcurrentSkipListMap 怎样更新索引层?
    答:

    • 对于索引更新,随机计算一个数,表示为该元素最高建几层索引,一层的概率为 1/2,二层的概率为 1/4,三层的概率为 1/8,以此类推。
    • 然后从最高层到最低层,在每一层,为该元素建立索引节点,建立索引节点的过程也是先查找位置,再插入。
  7. ConcurrentSkipListMap 怎样删除元素?
    答:对于删除元素,ConcurrentSkipListMap 不是直接进行真正删除,而是为了避免并发冲突,有一个复杂的标记过程,在内部遍历元素的过程中进行真正删除

  8. ConcurrentSkipListMap 的常见操作的时间复杂度是?
    答:

    • 为了实现并发安全、高效、无锁非阻塞,ConcurrentSkipListMap 的实现非常复杂,源码中提到了多篇学术论文,论文中描述了参考的一些算法
    • 对于常见的操作,如 get/put/remove/containsKeyConcurrentSkipListMap 的复杂度都是 O(log(N))
  9. 如果不需要并发,跳表结果可以怎样改进?
    答:

    • SkipList 跳表结构是为了便于并发操作的,如果不需要并发,可以使用另一种更为高效的结构:数据和所有层的索引放到一个节点中
    • 对于一个元素,只有一个节点,只是每个节点的索引个数可能不同。在新建一个节点时,使用随机算法决定它的索引个数、平均而言,1/2 的元素有两个索引,1/4 的元素有三个索引,以此类推。