阅读数:114 评论数:0

跳表是一种采用了空间换时间思想的数据结构。它会随机地将一些节点提升到更高的层次，以创建一种逐层的数据结构，以提高操作的速度。

它实现了SortedMap、NavigableMap、ConcurrentNavigableMap等接口。

跳表分为许多层（level），每一层都可以看作是数据的索引，这些索引的意义就是加快跳表查找数据速度，每一层的数据都是有序的，上一层数据是下一层数据的子集，并且第一层包含了全部的数据，层次越高，跳跃性越大，包含的数据越少。

ConcurrentSkipListMap有几个ConcurrentHashMap不能比拟的优点：

（1）ConcurrentSkipListMap的key是有序的。

（2）ConcurrentSkipListMap支持更高的并发。ConcurrentSkipListMap的存取时间是log(N)，和线程数无关。也就是说在数据量一定的情况下，并的线程越多，CoucurrentSkipListMap越体现出他的优势。