【死磕 Java 集合】— ConcurrentSkipListMap源码分析

转自：http://cmsblogs.com/?p=4773
  

作者：彤哥

出处：https://www.cnblogs.com/tong-yuan/

前情提要

点击链接查看“跳表”详细介绍。

拜托，面试别再问我跳表了！

简介

跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。

跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。

跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

存储结构

跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。

源码分析

主要内部类

内部类跟存储结构结合着来看，大概能预测到代码的组织方式。

// 数据节点，典型的单链表结构
static final class Node<K,V> { final K key; // 注意：这里value的类型是Object，而不是V // 在删除元素的时候value会指向当前元素本身 volatile Object value; volatile Node<K,V> next; Node(K key, Object value, Node<K,V> next) { this.key = key; this.value = value; this.next = next; } Node(Node<K,V> next) { this.key = null; this.value = this; // 当前元素本身(marker) this