ConcurrentSkipListMap深入分析

1.前言

　　ConcurrentHashMap与ConcurrentSkipListMap性能测试

　　在4线程1.6万数据的条件下，ConcurrentHashMap 存取速度是ConcurrentSkipListMap 的4倍左右。但ConcurrentSkipListMap有几个ConcurrentHashMap 不能比拟的优点：

  • ConcurrentSkipListMap 的key是有序的。

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

2.使用建议

　　在非多线程的情况下，应当尽量使用TreeMap。此外对于并发性相对较低的并行程序可以使用 Collections.synchronizedSortedMap将TreeMap进行包装，也可以提供较好的效率。对于高并发程序，应当使用 ConcurrentSkipListMap，能够提供更高的并发度。
所以在多线程程序中，如果需要对Map的键值进行排序时，请尽量使用ConcurrentSkipListMap，可能得到更好的并发度。
注意，调用ConcurrentSkipListMap的size时，由于多个线程可以同时对映射表进行操作，所以映射表需要遍历整个链表才能返回元素个数，这个操作是个O(log(n))的操作。

 3.什么是SkipList

　　　　Skiplist(跳表）是一种可以代替平衡树的数据结构，默认是按照Key值升序的。Skiplist让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，通过“空间来换取时间”的一个算法，在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。
从概率上保持数据结构的平衡比显示的保持数据结构平衡要简单的多。对于大多数应用，用Skip list要比用树算法相对简单。由于Skip list比较简单，实现起来会比较容易，虽然和平衡树有着相同的时间复杂度(O(logn)),但是skip list的常数项会相对小很多。Skiplist在空间上也比较节省。一个节点平均只需要1.333个指针（甚至更少）。
                
图1-1 Skip list结构图（以7,14,21,32,37,71,85序列为例）


Skip list的性质

(1) 由很多层结构组成，level是通过一定的概率随机产生的。
(2) 每一层都是一个有序的链表，默认是升序，也可以根据创建映射时所提供的Comparator进行排序，具体取决于使用的构造方法。
(3) 最底层(Level 1)的链表包含所有元素。
(4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现。
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。


三、什么是ConcurrentSkipListMap

 

ConcurrentSkipListMap提供了一种线程安全的并发访问的排序映射表。内部是SkipList（跳表）结构实现，在理论上能够在O(log(n))时间内完成查找、插入、删除操作。
       注意，调用ConcurrentSkipListMap的size时，由于多个线程可以同时对映射表进行操作，所以映射表需要遍历整个链表才能返回元素个数，这个操作是个O(log(n))的操作。


 ConcurrentSkipListMap存储结构



ConcurrentSkipListMap存储结构图

 

跳跃表（SkipList）：（如上图所示）
1.多条链构成，是关键字升序排列的数据结构；
2.包含多个级别，一个head引用指向最高的级别，最低（底部）的级别，包含所有的key；
3.每一个级别都是其更低级别的子集，并且是有序的；
4.如果关键字 key在 级别level=i中出现，则，level<=i的链表中都会包含该关键字key；


------------------------

ConcurrentSkipListMap主要用到了Node和Index两种节点的存储方式，通过volatile关键字实现了并发的操作

  

[java] view plaincopy
 
  1. staticfinalclass final volatile  
  2. volatile  
  3. staticclass final final  
  4. volatile  
  5. }  

 

------------------------

ConcurrentSkipListMap的查找


通过SkipList的方式进行查找操作：（下图以“查找91”进行说明：）

 


红色虚线，表示查找的路径，蓝色向右箭头表示right引用；黑色向下箭头表示down引用；

 

/get方法，通过doGet操作实现

 

[java] view plaincopy
 
  1. public return   
  2. private super null   
  3.   
  4. int for  
  5.   
  6. ifnullnull if) {  
  7. continue elseif) {  
  8.   
  9.   
  10. returnnull else   
  11. ifnull else break   
  12. fornull ifnull if) {  
  13. returnnull elseif)  
  14. break returnnull     }  

 

 

------------------------------------------------

ConcurrentSkipListMap的删除


通过SkipList的方式进行删除操作：（下图以“删除23”进行说明：）

 


红色虚线，表示查找的路径，蓝色向右箭头表示right引用；黑色向下箭头表示down引用；

 

 

[java] view plaincopy
 
  1. //remove操作，通过doRemove实现，把所有level中出现关键字key的地方都delete掉 public returnnull final super for   
  2.   
  3. for  
  4. ifnull//如果next引用为空，直接返回 returnnull if  
  5. break ifnull  
  6. break ifnull  
  7. break int if)  
  8. returnnull if) {  
  9. continue ifnull returnnull ifnull break if  
  10.   
  11. else   
  12. ifnull  
  13. return     }  


 

-------------------------------------

 

ConcurrentSkipListMap的插入

 

 

通过SkipList的方式进行插入操作：（下图以“添加55”的两种情况，进行说明：）


在level=2（该level存在）的情况下添加55的图示:只需在level<=2的合适位置插入55即可

--------


在level=4(该level不存在，图示level4是新建的)的情况下添加55的情况：首先新建level4,然后在level<=4的合适位置插入55

-----------

 

[java] view plaincopy
 
  1. //put操作，通过doPut实现 public ifnull thrownew returnfalse privateboolean super for   
  2.   
  3. for ifnull if  
  4. break ifnull  
  5. break ifnull  
  6. break int if) {  
  7. continue if) {  
  8. if return else break  
  9.   
  10. new if break  
  11. int  
  12. if)  
  13.   
  14. returnnull      * 获得一个随机的level值 
  15.      */ privateint int ;  
  16. ;  
  17. ;  
  18. if) != )   
  19. return;  
  20. int;  
  21. while) & ) != ) ++level;  
  22. return //执行插入操作：如上图所示，有两种可能的情况： //1.当level存在时，对level<=n都执行insert操作 //2.当level不存在（大于目前的最大level）时，首先添加新的level，然后在执行操作1  privatevoidint int if  
  23. null forint; i <= level; ++i)  
  24. newnull   
  25. else  
  26. ;  
  27. new];  
  28. null forint; i <= level; ++i)  
  29. newnull int for int if  
  30. break forint; j <= level; ++j)  
  31. new  
  32. if break /** 
  33.      *在1~indexlevel层中插入数据  
  34.      */ privatevoidint   
  35. int super ifnullthrownew   
  36. for int for ifnull   
  37. int ifnull if break continue if) {  
  38. continue if  
  39.   
  40. if   
  41. return if  
  42. break  
  43. if) {  
  44.   
  45. if return if  
  46.     }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wxgblogs/p/5465218.html