- 浏览: 144426 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
EclipseEye:
fair_jm 写道不错 蛮详细的 谢谢分享
SWT/JFace专题 --- SWT中Display和多线程 -
fair_jm:
不错 蛮详细的 谢谢分享
SWT/JFace专题 --- SWT中Display和多线程
Map
------
1.HashMap
2.LinkedHashMap
3.IdentityHashMap
4.WeakHashMap
5.TreeMap
6.EnumMap
7.ConcurrentHashMap
8.ConcurrentSkipListMap
--------------------------------------
------------------ConcurrentSkipListMap-----------------
ConcurrentSkipListMap提供了一种线程安全的并发访问的排序映射表。内部是SkipList(跳表)结构实现,在理论上能够在O(log(n))时间内完成查找、插入、删除操作。
SkipList是一种红黑树的替代方案,由于SkipList与红黑树相比无论从理论和实现都简单许多,所以得到了很好的推广。SkipList是基于一种统计学原理实现的,有可能出现最坏情况,即查找和更新操作都是O(n)时间复杂度,但从统计学角度分析这种概率极小。
使用SkipList类型的数据结构更容易控制多线程对集合访问的处理,因为链表的局部处理性比较好,当多个线程对SkipList进行更新操作(指插入和删除)时,SkipList具有较好的局部性,每个单独的操作,对整体数据结构影响较小。而如果使用红黑树,很可能一个更新操作,将会波及整个树的结构,其局部性较差。因此使用SkipList更适合实现多个线程的并发处理。
在非多线程的情况下,应当尽量使用TreeMap。此外对于并发性相对较低的并行程序可以使用Collections.synchronizedSortedMap将TreeMap进行包装,也可以提供较好的效率。对于高并发程序,应当使用ConcurrentSkipListMap,能够提供更高的并发度。
所以在多线程程序中,如果需要对Map的键值进行排序时,请尽量使用ConcurrentSkipListMap,可能得到更好的并发度。
注意,调用ConcurrentSkipListMap的size时,由于多个线程可以同时对映射表进行操作,所以映射表需要遍历整个链表才能返回元素个数,这个操作是个O(log(n))的操作。
ConcurrentSkipListMap存储结构
ConcurrentSkipListMap存储结构图
跳跃表(SkipList):(如上图所示)
1.多条链构成,是关键字升序排列的数据结构;
2.包含多个级别,一个head引用指向最高的级别,最低(底部)的级别,包含所有的key;
3.每一个级别都是其更低级别的子集,并且是有序的;
4.如果关键字 key在 级别level=i中出现,则,level<=i的链表中都会包含该关键字key;
------------------------
ConcurrentSkipListMap主要用到了Node和Index两种节点的存储方式,通过volatile关键字实现了并发的操作
------------------------
ConcurrentSkipListMap的查找
通过SkipList的方式进行查找操作:(下图以“查找91”进行说明:)
红色虚线,表示查找的路径,蓝色向右箭头表示right引用;黑色向下箭头表示down引用;
ConcurrentSkipListMap的删除
通过SkipList的方式进行删除操作:(下图以“删除23”进行说明:)
红色虚线,表示查找的路径,蓝色向右箭头表示right引用;黑色向下箭头表示down引用;
ConcurrentSkipListMap的插入
通过SkipList的方式进行插入操作:(下图以“添加55”的两种情况,进行说明:)
在level=2(该level存在)的情况下添加55的图示:只需在level<=2的合适位置插入55即可
--------
在level=4(该level不存在,图示level4是新建的)的情况下添加55的情况:首先新建level4,然后在level<=4的合适位置插入55
-----------
------
1.HashMap
2.LinkedHashMap
3.IdentityHashMap
4.WeakHashMap
5.TreeMap
6.EnumMap
7.ConcurrentHashMap
8.ConcurrentSkipListMap
--------------------------------------
------------------ConcurrentSkipListMap-----------------
ConcurrentSkipListMap提供了一种线程安全的并发访问的排序映射表。内部是SkipList(跳表)结构实现,在理论上能够在O(log(n))时间内完成查找、插入、删除操作。
SkipList是一种红黑树的替代方案,由于SkipList与红黑树相比无论从理论和实现都简单许多,所以得到了很好的推广。SkipList是基于一种统计学原理实现的,有可能出现最坏情况,即查找和更新操作都是O(n)时间复杂度,但从统计学角度分析这种概率极小。
使用SkipList类型的数据结构更容易控制多线程对集合访问的处理,因为链表的局部处理性比较好,当多个线程对SkipList进行更新操作(指插入和删除)时,SkipList具有较好的局部性,每个单独的操作,对整体数据结构影响较小。而如果使用红黑树,很可能一个更新操作,将会波及整个树的结构,其局部性较差。因此使用SkipList更适合实现多个线程的并发处理。
在非多线程的情况下,应当尽量使用TreeMap。此外对于并发性相对较低的并行程序可以使用Collections.synchronizedSortedMap将TreeMap进行包装,也可以提供较好的效率。对于高并发程序,应当使用ConcurrentSkipListMap,能够提供更高的并发度。
所以在多线程程序中,如果需要对Map的键值进行排序时,请尽量使用ConcurrentSkipListMap,可能得到更好的并发度。
注意,调用ConcurrentSkipListMap的size时,由于多个线程可以同时对映射表进行操作,所以映射表需要遍历整个链表才能返回元素个数,这个操作是个O(log(n))的操作。
ConcurrentSkipListMap存储结构
ConcurrentSkipListMap存储结构图
跳跃表(SkipList):(如上图所示)
1.多条链构成,是关键字升序排列的数据结构;
2.包含多个级别,一个head引用指向最高的级别,最低(底部)的级别,包含所有的key;
3.每一个级别都是其更低级别的子集,并且是有序的;
4.如果关键字 key在 级别level=i中出现,则,level<=i的链表中都会包含该关键字key;
------------------------
ConcurrentSkipListMap主要用到了Node和Index两种节点的存储方式,通过volatile关键字实现了并发的操作
static final class Node<K,V> { final K key; volatile Object value;//value值 volatile Node<K,V> next;//next引用 …… } static class Index<K,V> { final Node<K,V> node; final Index<K,V> down;//downy引用 volatile Index<K,V> right;//右边引用 …… }
------------------------
ConcurrentSkipListMap的查找
通过SkipList的方式进行查找操作:(下图以“查找91”进行说明:)
红色虚线,表示查找的路径,蓝色向右箭头表示right引用;黑色向下箭头表示down引用;
/get方法,通过doGet操作实现 public V get(Object key) { return doGet(key); } //doGet的实现 private V doGet(Object okey) { Comparable<? super K> key = comparable(okey); Node<K,V> bound = null; Index<K,V> q = head;//把头结点作为当前节点的前驱节点 Index<K,V> r = q.right;//前驱节点的右节点作为当前节点 Node<K,V> n; K k; int c; for (;;) {//遍历 Index<K,V> d; // 依次遍历right节点 if (r != null && (n = r.node) != bound && (k = n.key) != null) { if ((c = key.compareTo(k)) > 0) {//由于key都是升序排列的,所有当前关键字大于所要查找的key时继续向右遍历 q = r; r = r.right; continue; } else if (c == 0) { //如果找到了相等的key节点,则返回该Node的value如果value为空可能是其他并发delete导致的,于是通过另一种 //遍历findNode的方式再查找 Object v = n.value; return (v != null)? (V)v : getUsingFindNode(key); } else bound = n; } //如果一个链表中right没能找到key对应的value,则调整到其down的引用处继续查找 if ((d = q.down) != null) { q = d; r = d.right; } else break; } // 如果通过上面的遍历方式,还没能找到key对应的value,再通过Node.next的方式进行查找 for (n = q.node.next; n != null; n = n.next) { if ((k = n.key) != null) { if ((c = key.compareTo(k)) == 0) { Object v = n.value; return (v != null)? (V)v : getUsingFindNode(key); } else if (c < 0) break; } } return null; }------------------------------------------------
ConcurrentSkipListMap的删除
通过SkipList的方式进行删除操作:(下图以“删除23”进行说明:)
红色虚线,表示查找的路径,蓝色向右箭头表示right引用;黑色向下箭头表示down引用;
//remove操作,通过doRemove实现,把所有level中出现关键字key的地方都delete掉 public V remove(Object key) { return doRemove(key, null); } final V doRemove(Object okey, Object value) { Comparable<? super K> key = comparable(okey); for (;;) { Node<K,V> b = findPredecessor(key);//得到key的前驱(就是比key小的最大节点) Node<K,V> n = b.next;//前驱节点的next引用 for (;;) {//遍历 if (n == null)//如果next引用为空,直接返回 return null; Node<K,V> f = n.next; if (n != b.next) // 如果两次获得的b.next不是相同的Node,就跳转到第一层循环重新获得b和n break; Object v = n.value; if (v == null) { // 当n被其他线程delete的时候,其value==null,此时做辅助处理,并重新获取b和n n.helpDelete(b, f); break; } if (v == n || b.value == null) // 当其前驱被delet的时候直接跳出,重新获取b和n break; int c = key.compareTo(n.key); if (c < 0) return null; if (c > 0) {//当key较大时就继续遍历 b = n; n = f; continue; } if (value != null && !value.equals(v)) return null; if (!n.casValue(v, null)) break; if (!n.appendMarker(f) || !b.casNext(n, f))//casNext方法就是通过比较和设置b(前驱)的next节点的方式来实现删除操作 findNode(key); // 通过尝试findNode的方式继续find else { findPredecessor(key); // Clean index if (head.right == null) //如果head的right引用为空,则表示不存在该level tryReduceLevel(); } return (V)v; } } }-------------------------------------
ConcurrentSkipListMap的插入
通过SkipList的方式进行插入操作:(下图以“添加55”的两种情况,进行说明:)
在level=2(该level存在)的情况下添加55的图示:只需在level<=2的合适位置插入55即可
--------
在level=4(该level不存在,图示level4是新建的)的情况下添加55的情况:首先新建level4,然后在level<=4的合适位置插入55
-----------
//put操作,通过doPut实现 public V put(K key, V value) { if (value == null) throw new NullPointerException(); return doPut(key, value, false); } private V doPut(K kkey, V value, boolean onlyIfAbsent) { Comparable<? super K> key = comparable(kkey); for (;;) { Node<K,V> b = findPredecessor(key);//前驱 Node<K,V> n = b.next; //定位的过程就是和get操作相似 for (;;) { if (n != null) { Node<K,V> f = n.next; if (n != b.next) // 前后值不一致的情况下,跳转到第一层循环重新获得b和n break;; Object v = n.value; if (v == null) { // n被delete的情况下 n.helpDelete(b, f); break; } if (v == n || b.value == null) // b 被delete的情况,重新获取b和n break; int c = key.compareTo(n.key); if (c > 0) { b = n; n = f; continue; } if (c == 0) { if (onlyIfAbsent || n.casValue(v, value)) return (V)v; else break; // restart if lost race to replace value } // else c < 0; fall through } Node<K,V> z = new Node<K,V>(kkey, value, n); if (!b.casNext(n, z)) break; // restart if lost race to append to b int level = randomLevel();//得到一个随机的level作为该key-value插入的最高level if (level > 0) insertIndex(z, level);//进行插入操作 return null; } } } /** * 获得一个随机的level值 */ private int randomLevel() { int x = randomSeed; x ^= x << 13; x ^= x >>> 17; randomSeed = x ^= x << 5; if ((x & 0x8001) != 0) // test highest and lowest bits return 0; int level = 1; while (((x >>>= 1) & 1) != 0) ++level; return level; } //执行插入操作:如上图所示,有两种可能的情况: //1.当level存在时,对level<=n都执行insert操作 //2.当level不存在(大于目前的最大level)时,首先添加新的level,然后在执行操作1 private void insertIndex(Node<K,V> z, int level) { HeadIndex<K,V> h = head; int max = h.level; if (level <= max) {//情况1 Index<K,V> idx = null; for (int i = 1; i <= level; ++i)//首先得到一个包含1~level个级别的down关系的链表,最后的inx为最高level idx = new Index<K,V>(z, idx, null); addIndex(idx, h, level);//把最高level的idx传给addIndex方法 } else { // 情况2 增加一个新的级别 level = max + 1; Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1]; Index<K,V> idx = null; for (int i = 1; i <= level; ++i)//该步骤和情况1类似 idxs[i] = idx = new Index<K,V>(z, idx, null); HeadIndex<K,V> oldh; int k; for (;;) { oldh = head; int oldLevel = oldh.level; if (level <= oldLevel) { // lost race to add level k = level; break; } HeadIndex<K,V> newh = oldh; Node<K,V> oldbase = oldh.node; for (int j = oldLevel+1; j <= level; ++j) newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);//创建新的 if (casHead(oldh, newh)) { k = oldLevel; break; } } addIndex(idxs[k], oldh, k); } } /** *在1~indexlevel层中插入数据 */ private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) { // insertionLevel 代表要插入的level,该值会在indexLevel~1间遍历一遍 int insertionLevel = indexLevel; Comparable<? super K> key = comparable(idx.node.key); if (key == null) throw new NullPointerException(); // 和get操作类似,不同的就是查找的同时在各个level上加入了对应的key for (;;) { int j = h.level; Index<K,V> q = h; Index<K,V> r = q.right; Index<K,V> t = idx; for (;;) { if (r != null) { Node<K,V> n = r.node; // compare before deletion check avoids needing recheck int c = key.compareTo(n.key); if (n.value == null) { if (!q.unlink(r)) break; r = q.right; continue; } if (c > 0) { q = r; r = r.right; continue; } } if (j == insertionLevel) {//在该层level中执行插入操作 // Don't insert index if node already deleted if (t.indexesDeletedNode()) { findNode(key); // cleans up return; } if (!q.link(r, t))//执行link操作,其实就是inset的实现部分 break; // restart if (--insertionLevel == 0) { // need final deletion check before return if (t.indexesDeletedNode()) findNode(key); return; } } if (--j >= insertionLevel && j < indexLevel)//key移动到下一层level t = t.down; q = q.down; r = q.right; } } }
发表评论
-
Nio Socket
2013-05-16 05:53 0asfda -
结合jdk源码解读,Error Exception
2013-05-10 04:00 0/* * @(#)Error.java 1.17 05/11 ... -
从不同的角度,重新审视class和interface
2013-05-07 03:40 0java开发中,对应class和interface的基本区别都 ... -
java.lang.Object
2013-05-07 03:35 0/* * @(#)Object.java 1.73 06/0 ... -
反射机制+类加载机制
2013-02-18 01:30 0反射机制+类加载机制 -
并发专题----使用开源软件Amino构建并发应用程序/多线程运行时分析工具MTRAT
2013-02-14 00:50 1342使用开源软件构建并发 ... -
并发专题 ---- 线程安全
2013-02-14 00:50 718线程安全 ================== ... -
并发专题 --- 锁
2013-02-14 00:50 778相比于synchronized,ReentrantLock 提 ... -
并发专题 ----(JMM)java内存模型
2013-02-14 00:50 507Java 内存模型 ------------ ... -
并发专题 ---java.util.concurrent 包
2013-02-13 02:26 1797java.util.concurrent 包 原 ... -
集合框架 Queue篇(8)---PriorityBlockingQueue、SynchronousQueue
2013-02-07 12:40 1270Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(7)---LinkedBlockingDeque
2013-02-07 12:40 829Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(6)---LinkedBlockingQueue
2013-02-07 12:39 801Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(5)---ArrayBlockingQueue
2013-02-06 10:39 674Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(4)---阻塞队列和生产者-消费者模式、DelayQueue
2013-02-06 10:39 965Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(3)---ConcurrentLinkedQueue
2013-02-06 10:38 1007Queue ------------ 1.ArrayDequ ... -
集合框架 Queue篇(2)---PriorityQueue
2013-02-06 10:38 800Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(1)---ArrayDeque
2013-02-06 10:38 898Queue ------------ 1.ArrayDeq ... -
集合框架 Set篇---HashSet、LinkedHashSet、TreeSet、CopyOnWriteArraySet、ConcurrentSkipList
2013-02-05 08:43 1447Set --------- 1.HashSet 2.Link ... -
集合框架 List篇(2)---CopyOnWriteArrayList
2013-02-05 08:43 818List ----------- 1.ArrayList(jd ...
相关推荐
比较Java原生的 3种Map的效率。 1. TreeMap 2. HashMap 3. ConcurrentSkipListMap 本测试查找方法使用Map的get方法,循环、离散获取。对于ConcurrentSkipListMap,获得顺序片段,可用subMap()方法,提取50w的子序列...
Java concurrency集合之ConcurrentSkipListMap_动力节点Java学院整理,动力节点口口相传的Java黄埔军校
NULL 博文链接:https://maoyidao.iteye.com/blog/1559420
java集合 线程不安全的集合 HashMap的特点 HashMap的长度(容量)为什么要设计成2的幂? HashTable的特点 TreeMap ArrayList的特点 Vector的特点 LinkedList的特点 Set ConcurrentModificationException异常 线程...
简介跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,
Java 常见并发容器总结 JDK 提供的这些容器大部分在 `java.util.concurrent` 包中。 - **`ConcurrentHashMap`** : ...- **`ConcurrentSkipListMap`** : 跳表的实现。这是一个 Map,使用跳表的数据结构进行快速查找。
5、Fork/Join框架的异常处理 26 6、Fork/Join框架的实现原理 26 二、闭锁CountDownLatch 28 1、应用场景 28 2、CyclicBarrier 28 3、Semaphore 29 4、Callable、Future和FutureTask 30 5、原子操作CAS (compare ...
高并发编程第三阶段34讲 ForkJoin框架之RecursiveAction_.mp4 高并发编程第三阶段35讲 Phaser工具的实战案例使用第一部分_.mp4 高并发编程第三阶段36讲 Phaser工具的实战案例使用第二部分_.mp4 高并发编程第...
高并发编程第三阶段34讲 ForkJoin框架之RecursiveAction_.mp4 高并发编程第三阶段35讲 Phaser工具的实战案例使用第一部分_.mp4 高并发编程第三阶段36讲 Phaser工具的实战案例使用第二部分_.mp4 高并发编程第...
ConcurrentSkipListMap等类的概念、原理、数据结构、使用场景描述。
基于SpringBoot的应用程序在启动应用程序时通过RestTemplate从外部链接恢复数据,并加载到ConcurrentSkipListMap中,以通过get和put rest api管理并发。 我已经集成了openAPI来描述其余的API。 基本身份验证是通过...
用于替代同步且基于散列的Map CopyOnWriteArrayList 用于在遍历操作为主要操作的情况下替代同步的List Queue ConcurrentLinkedQueue *BlockingQueue 提供了可阻塞的put和take方法...