TreeMap作用
- 元素可以按key保持顺序。
- 因为有序，提供了很多范围查询的方法，非常方便。
TreeMap的实现
TreeMap实现了NavigableMap接口，该接口又继承SortedMap接口，两个提供了很多范围查询的方法，非常方便。
用红黑树实现，插入、删除、查询的平均时间复杂度都是log(n)。
TreeMap也是非线程安全的，为什么不提供ConcurrentTreeMap?
- 因为红黑树的结构调整可能涉及整个树的结点，这样并发下就要锁住很多结点，使用跳表会更局部一点，只锁住局部的几个结点，并发性能更高。
- 红黑树加锁实现起来比较复杂，跳表是链表加锁比较容易实现
可以用过Collections.synchronizedSortedMap()保证线程安全，也可以改用ConcurrentSkipListMap并发性能更好。
TreeMap为什么用红黑树不用AVL树？
跟HashMap中的问题一样。
红黑树的3结点可以吸收变化，在多次使用中可以减少调整数据结构的次数，从而提升性能。
ConcurrentSkipListMap是什么？
跳表：链表+多级索引（多层链表）。
- 给有序链表再增加若干层额外的指针索引，用空间换时间。
- 每一层都是一个有序链表。
- 实际效果类似于平衡二叉搜索树。
- 插入、删除、查询的平均时间复杂度都是log(n)。
- 支持按key排序所有元素，也支持快速查找。
跳表的数据结构存在什么问题？
按照理想的生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到O(log n)。
但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。
skiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。比如，一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中。
跳表与红黑树区别？
- 红黑树为了保持平衡有可能会调整很多结点甚至整个树，而跳表只要修改相邻结点更加的局部，跳表调整次数少性能也就高，同时并发加锁时，锁住的结点更少，可以减少竞争
- 跳表的区间查询更高效，因为找到链表头结点顺序遍历就行了，红黑树需要中序遍历相对比较复杂
- 跳表占用空间更少，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。
ConcurrentSkipListMap存在什么问题？
size方法求得链表长度要遍历整个链表，并且没有加锁，多线程高并发下这个方法返回值并不准确，高并发下使用size的意义不大。