ConcurrentSkipListMap
底层使用的是SkipList结构,也就是跳表
SkipList
SkipList让已排序的数据分布在多层链表中,以0-1随机数决定一个数据的向上攀升与否,通过以时间换空间,在每个节点中增加了向前的指针,在插入、删除、查找时可以忽略一些不可能涉及到的节点,从而提高效率
SkipList具备如下特性:
- 由很多层结构组成,level是通过一定的概率随机产生的
- 每一层都是一个有序的链表,默认是升序,也可以根据创建映射时所提供的Comparator进行排序,具体取决于使用的构造方法
- 最底层(Level 1)的链表包含所有元素
- 如果一个元素出现在Level i 的链表中,则它在Level i 之下的链表也都会出现
- 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素