ConcrrentSkipListMap介绍和原理分析

Java

2016-09-14

153

73

一、前言:

JDK为我们提供了很多Map接口的实现,使得我们可以方便地处理Key-Value的数据结构。

当我们希望快速存取<Key, Value>键值对时我们可以使用HashMap。

当我们希望在多线程并发存取<Key, Value>键值对时,我们会选择ConcurrentHashMap。

TreeMap则会帮助我们保证数据是按照Key的自然顺序或者compareTo方法指定的排序规则进行排序。

OK,那么当我们需要多线程并发存取<Key, Value>数据并且希望保证数据有序时,我们需要怎么做呢?

。。。。。。

也许,我们可以选择ConcurrentTreeMap。不好意思,JDK没有提供这么好的数据结构给我们。

当然,我们可以自己添加lock来实现ConcurrentTreeMap,但是随着并发量的提升,lock带来的性能开销也随之增大。

Don't cry......,JDK6里面引入的ConcurrentSkipListMap也许可以满足我们的需求。

JDK Documentation对ConcurrentSkipListMap的介绍

通过上面的介绍我们可以对ConcurrentSkipListMap中基本操作的时间复杂度有个基本的了解:

Operation Time Complexity
Insertion O(log N)
Removal O(log N)
Check if contains O(log N)
Enumerate in order O(N)

 

二、ConcurrentSkipListMap实例:

import java.util.Iterator;
import java.util.NavigableSet;
import java.util.concurrent.ConcurrentNavigableMap;
import java.util.concurrent.ConcurrentSkipListMap;

public class ConcurrentSkipListMapExample {
public static void main(String[] args) {
ConcurrentNavigableMap<String, String> concurrentSkipListMap = new ConcurrentSkipListMap<String, String>();
concurrentSkipListMap.put("3", "Wednesday");
concurrentSkipListMap.put("2", "Tuesday");
concurrentSkipListMap.put("1", "Monday");
concurrentSkipListMap.put("5", "Friday");
concurrentSkipListMap.put("4", "Thursday");

NavigableSet navigableSet = concurrentSkipListMap.descendingKeySet();
System.out.println("descendingKeySet: ");
Iterator itr = navigableSet.iterator();
while (itr.hasNext()) {
String s = itr.next();
System.out.println(s);
}
System.out.println("ceilingEntry-2: " + concurrentSkipListMap.ceilingEntry("2"));
System.out.println("firstEntry: " + concurrentSkipListMap.firstEntry());
System.out.println("lastEntry: " + concurrentSkipListMap.lastEntry());
System.out.println("pollFirstEntry: " + concurrentSkipListMap.pollFirstEntry());
System.out.println("now firstEntry: " + concurrentSkipListMap.firstEntry());
System.out.println("pollLastEntry: " + concurrentSkipListMap.pollLastEntry());
System.out.println("now lastEntry: " + concurrentSkipListMap.lastEntry());
System.out.println("Entry-2: " + concurrentSkipListMap.get("2"));
}

}

 

三、ConcurrentSkipListMap性能测试:

下面,我们来比较一下ConcurrentSkipListMap与TreeMap在并发情况下查询的性能状况。

我们会启动n个线程随机读取Map中的记录,每个线程会读取106次。

从测试结果,我们可以看出随着并发度的不断提高,ConcurrentSkipListMap相对于TreeMap的优势也越来越明显。

四、ConcurrentSkipListMap实现原理

skiplist数据结构介绍:

http://kenby.iteye.com/blog/1187303

concurrentskiplistmap实现并发的原理:

concurrentskiplistmap并没有使用lock来保证线程的并发访问和修改,而是使用了非阻塞算法来保证并发访问(Michael-Scott 算法)

也可以参考下面的博客(http://blog.csdn.net/jy3161286/article/details/22809913)

打赏一个呗~~

关注我
长按二维码可识别关注
微信号:xwintop
微信号xwintop


追风

爱一个人就像执着于一种梦想,没有值不值得,只有愿不愿意···

关注我
长按二维码可识别关注
微信号:xwintop
微信号xwintop


推荐文章

湄公河行动

2016-10-29 18:39:48
关注我
长按二维码可识别关注
微信号:xwintop
微信号xwintop