005-多线程-集合-Map-ConcurrentSkipListMap
一、概述
ConcurrentSkipListMap是线程安全的有序的哈希表,适用于高并发的场景。
ConcurrentSkipListMap和TreeMap,它们虽然都是有序的哈希表。但是,第一,它们的线程安全机制不同,TreeMap是非线程安全的,而ConcurrentSkipListMap是线程安全的。第二,ConcurrentSkipListMap是通过跳表实现的,而TreeMap是通过红黑树实现的。
关于跳表(Skip List),它是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。
1.1、原理和数据结构
说明:
先以数据“7,14,21,32,37,71,85”序列为例,来对跳表进行简单说明。
跳表分为许多层(level),每一层都可以看作是数据的索引,这些索引的意义就是加快跳表查找数据速度。每一层的数据都是有序的,上一层数据是下一层数据的子集,并且第一层(level 1)包含了全部的数据;层次越高,跳跃性越大,包含的数据越少。
跳表包含一个表头,它查找数据时,是从上往下,从左往右进行查找。现在“需要找出值为32的节点”为例,来对比说明跳表和普遍的链表。
情况1:链表中查找“32”节点
路径如下图1-02所示:
需要4步(红色部分表示路径)。
情况2:跳表中查找“32”节点
路径如下图1-03所示:
忽略索引垂直线路上路径的情况下,只需要2步(红色部分表示路径)。
下面说说Java中ConcurrentSkipListMap的数据结构。
(01) ConcurrentSkipListMap继承于AbstractMap类,也就意味着它是一个哈希表。
(02) Index是ConcurrentSkipListMap的内部类,它与“跳表中的索引相对应”。HeadIndex继承于Index,ConcurrentSkipListMap中含有一个HeadIndex的对象head,head是“跳表的表头”。
(03) Index是跳表中的索引,它包含“右索引的指针(right)”,“下索引的指针(down)”和“哈希表节点node”。node是Node的对象,Node也是ConcurrentSkipListMap中的内部类。
1.2、示例
/* * ConcurrentSkipListMap是“线程安全”的哈希表,而TreeMap是非线程安全的。 * * 下面是“多个线程同时操作并且遍历map”的示例 * (01) 当map是ConcurrentSkipListMap对象时,程序能正常运行。 * (02) 当map是TreeMap对象时,程序会产生ConcurrentModificationException异常。 */ public class ConcurrentSkipListMapDemo1 { // TODO: map是TreeMap对象时,程序会出错。 //private static Map<String, String> map = new TreeMap<String, String>(); private static Map<String, String> map = new ConcurrentSkipListMap<String, String>(); public static void main(String[] args) { // 同时启动两个线程对map进行操作! new MyThread("a").start(); new MyThread("b").start(); } private static void printAll() { String key, value; Iterator iter = map.entrySet().iterator(); while (iter.hasNext()) { Map.Entry entry = (Map.Entry) iter.next(); key = (String) entry.getKey(); value = (String) entry.getValue(); System.out.print("(" + key + ", " + value + "), "); } System.out.println(); } private static class MyThread extends Thread { MyThread(String name) { super(name); } @Override public void run() { int i = 0; while (i++ < 6) { // “线程名” + "序号" String val = Thread.currentThread().getName() + i; map.put(val, "0"); // 通过“Iterator”遍历map。 printAll(); } } } }
1.3、使用场景
二、源码分析
相关文章
- python deepcopy函数实现_python 多线程
- 面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
- 有序的Map集合_map集合特点
- 支付宝一面:多线程事务怎么回滚?说用 @Transactional 可以回去等通知了!
- php pthreads多线程的安装与使用
- python 多线程优先队列Queue详解编程语言
- Java 文件多线程下载详解编程语言
- 多线程之传统多线程详解编程语言
- Redis实现快速存储Map(redis存map)
- 掌握Linux多线程编程:备战面试之路(linux多线程面试题)
- 深入浅出Redis查看Map(redis查看map)
- 深入浅出理解Redis多线程(怎么理解redis多线程)
- 从Redis中取出Map一步搞定(从redis中取map)
- 如何将Map存储在Redis中(将map存到redis中)
- 解决Redis频繁修改Map难题(redis频繁修改map)
- 警惕Redis Map的频繁变更(redis频繁修改map)
- 基于Redis集群的Map数据结构的删除(redis集群map删除)
- Redis锁在多线程编程中的应用(redis锁场景)
- 在Redis中使用Map存储数据(redis里面加入map)
- 探索Redis中的Map之谜(redis里查map)
- 科学上网如何使用Oracle MAP(oracle map使用)
- 学会调整Redis中Map容量的设置(redis设置map大小)
- Redis解锁Map中蕴藏的绝技(redis获取map的值)
- Python中多线程及程序锁浅析