1. Java 并发包中可排序的对应版本工具类是
HashMap/HashSet基于哈希，不能对元素排序，对应的可排序的容器类是TreeMap/TreeSetJava 并发包中可排序的对应版本不是基于树，而是基于
SkipList（跳跃表）- Java 并发包中与
TreeMap/TreeSet对应的并发版本是ConcurrentSkipListMap和ConcurrentSkipListSet TreeSet是基于TreeMap实现的，ConcurrentSkipListSet是基于ConcurrentSkipListMap实现的
- Java 并发包中与
ConcurrentSkipListMap是基于SkipList实现的，SkipList称为跳跃表或跳表，是一种数据结构
2. Java 可排序容器的并发版本为什么采用跳表而不是树呢
- 因为跳表这种数据结构更易于实现高效的并发算法
3. ConcurrentSkipListMap 的特点是
- 没有使用锁，所有操作都是无阻塞的；所有操作都可以并行，包括写，多线程可以同时写
- 与
ConcurrentHashMap类似，迭代器不会抛出ConcurrentModificationException异常，也是弱一致的，迭代可能反映最新修改也可能不反映。一些方法如putAll()、clear()不是原子的 - 与
TreeMap一样，可排序，默认按键的自然顺序，也可以传递比较器自定义排序，实现了SortedMap和NavigableMap接口 ConcurrentSkipListMap和ConcurrentSkipListSet基于跳表实现，有序、无锁非阻塞、完全并行，主要操作复杂度都是O(logN)
4. 跳表 SkipList 的基本实现原理
跳表是基于链表的，在链表的基础上加了多层索引结构
最下面一层就是最基本的单向链表，这个链表是有序的。虽然有序，但与数组不同，链表不能根据索引直接定位，不能进行二分查找
- 为了快速查找，跳表有多层索引结构。高层的索引节点一定同时是低层的索引节点。高层的索引节点少，低层的多
- 统计概率上，第一次索引节点是实际元素数的 1/2，第二层是第一层的 1/2，逐层减半，但这不是绝对的，有随机性，只是大致如此
每个索引节点有两个指针：一个向右，指向下一个同层的索引节点；另一个向下，指向下一层的索引节点或基本链表节点
5. ConcurrentSkipListMap 怎样实现查找
- 有了跳表这个数据结构，就可以实现类似的二分查找了
- 查找元素总是从高层开始，将待查值与下一个索引节点的值进行比较，如果大于索引节点，就向右移动，继续比较；如果小于索引节点，则向下移动到下一层进行比较。这个结构是有序的，查找的性能与二叉树类似，复杂度是
O(logN) - 这个结构的构建与二叉树的构建类似，是在更新过程中进行保持的，保存元素的基本思路是
- 先保存到基本链表，找到待插入的位置，找到位置后，插入基本链表
- 更新索引层
6. ConcurrentSkipListMap 怎样更新索引层
- 对于索引更新，随机计算一个数，表示为该元素最高建几层索引，一层的概率为 1/2，二层的概率为 1/4，三层的概率为 1/8，以此类推
- 然后从最高层到最低层，在每一层，为该元素建立索引节点，建立索引节点的过程也是先查找位置，再插入
7. ConcurrentSkipListMap 怎样删除元素
- 对于删除元素，
ConcurrentSkipListMap不是直接进行真正删除 - 而是为了避免并发冲突，有一个复杂的标记过程，在内部遍历元素的过程中进行真正删除
8. ConcurrentSkipListMap 的常见操作的时间复杂度是
- 为了实现并发安全、高效、无锁非阻塞，
ConcurrentSkipListMap的实现非常复杂，源码中提到了多篇学术论文，论文中描述了参考的一些算法 - 对于常见的操作，如
get()/put()/remove()/containsKey()，ConcurrentSkipListMap的复杂度都是O(logN)
9. 如果不需要并发，跳表结果可以怎样改进
SkipList跳表结构是为了便于并发操作的，如果不需要并发，可以使用另一种更为高效的结构：数据和所有层的索引放到一个节点中- 对于一个元素，只有一个节点，只是每个节点的索引个数可能不同。在新建一个节点时，使用随机算法决定它的索引个数、平均而言，1/2 的元素有两个索引，1/4 的元素有三个索引，以此类推