ConcurrentHashMap的设计实现
为什么还需要ConcurrentHashMap,不是有了Hashtable吗。如果所有的事情都用Synchronized去解决,那么这个世界会变得很糟糕。
ConcurrentHashMap最绝妙的地方是采用了锁分段技术,一种分而治之的策略,一个HashMap被分为了几个Segment,在每个Segment里面实行同步控制。
对ConcurrentHashMap的操作首先找到相应的Segment,然后在Segment里面进行操作
public V put(K key, V value) { if (value == null) throw new NullPointerException(); int hash = hash(key.hashCode()); return segmentFor(hash).put(key, hash, value, false); } final Segment<K,V> segmentFor(int hash) { return segments[(hash >>> segmentShift) & segmentMask]; } 这种所分段方法本身有利于多线程操作。 但是ConcurrentHashMap所做的还不止这些,源代码中对Segment中Entry的读取操作并未加锁! V get(Object key, int hash) { if (count != 0) { // read-volatile HashEntry<K,V> e = getFirst(hash); while (e != null) { if (e.hash == hash && key.equals(e.key)) { V v = e.value; if (v != null) return v; return readValueUnderLock(e); // recheck } e = e.next; } } return null; }
首先找到对应的项,如果不为null就直接返回,否则调用readValueUnderLock方法。需要注意的就是那个readValueUnderLock(e)方法
/** * Reads value field of an entry under lock. Called if value * field ever appears to be null. This is possible only if a * compiler happens to reorder a HashEntry initialization with * its table assignment, which is legal under memory model * but is not known to ever occur. */ V readValueUnderLock(HashEntry<K,V> e) { lock(); try { return e.value; } finally { unlock(); } }
源码注释的解释是编译器可能会对HashEntry进行重排序,这对JMM来说是允许的。我的理解还是此时会有其他线程会对value进行更新,所以需要加锁,等待其他线程更新之后获取value。
CopyOnWriteArrayList设计实现
所有可变操作(add、set 等等)都是通过对底层数组进行一次新的复制来实现的。
BlockingQueue设计实现
天生的生产者消费者型的数据结构。
BlockingQueue的实现,两把锁takeLock和putLock,两个信号量(条件变量)notEmpty和notFull,基于PV原理实现。Await操作支持延迟,所以相应的put和take也支持延迟操作。
ConcurrentLinkedQueue的设计实现
一个基于非阻塞算法的链表队列。非阻塞算法比较难理解的一个地方是多个指针或者引用如何运用CAS操作。此处只涉及两个指针,一offer操作为例:
public boolean offer(E e) { if (e == null) throw new NullPointerException(); Node<E> n = new Node<E>(e); retry: for (;;) { Node<E> t = tail; Node<E> p = t; for (int hops = 0; ; hops++) { Node<E> next = succ(p); if (next != null) { if (hops > HOPS && t != tail) continue retry; p = next; } else if (p.casNext(null, n)) { if (hops >= HOPS) casTail(t, n); // Failure is OK. return true; } else { p = succ(p); } } } }
对于多个指针的修改可能会使数据结构状态不一致,例如第一个引用的指向修改成功了,但是第二个修改失败的情形,这中间如果有其它线程对数据结构进行操作就有可能产生不可预知的问题。一般采用多线程协助操作的策略进行非阻塞处理,如果第一个线程有未完成的操作,后续线程能够判断出并可以帮助它继续完成。对于offer操作,如果其他线程在更新是发现尾节点一致,但是尾节点的后继节点不为空,那么表示上一线程操作未完成,则在此线程会继续在循环里设置尾节点为当前尾节点的后继。
相关推荐
第二部分 结构化并发应用程序 第6章 任务执行 6.1 在线程中执行任务 6.1.1 串行地执行任务 6.1.2 显式地为任务创建线程 6.1.3 无限制创建线程的不足 6.2 Executor框架 6.2.1 示例:基于Executor的Web服务器 ...
第二部分 结构化并发应用程序 第6章 任务执行 6.1 在线程中执行任务 6.1.1 串行地执行任务 6.1.2 显式地为任务创建线程 6.1.3 无限制创建线程的不足 6.2 Executor框架 6.2.1 示例:基于Executor的Web服务器 ...
│ Java并发编程.png │ ppt+源码.rar │ 高并发编程第二阶段01讲、课程大纲及主要内容介绍.wmv │ 高并发编程第二阶段02讲、介绍四种Singleton方式的优缺点在多线程情况下.wmv │ 高并发编程第二阶段03讲、...
java并发编程实战、驾校K1考试试卷批量生成mysql表结构和数据
│ Java并发编程.png │ ppt+源码.rar │ 高并发编程第二阶段01讲、课程大纲及主要内容介绍.wmv │ 高并发编程第二阶段02讲、介绍四种Singleton方式的优缺点在多线程情况下.wmv │ 高并发编程第二阶段03讲、...
分享自己整理和改进过的编程作业代码,有用的话,欢迎点赞收藏。 中国科学院大学,并发数据结构与多核编程_大作业,列车售票系统。
十余年JAVA从业经验,精通JAVA技术体系,有志于做JAVA技能提升的朋友可与我联系,交个朋友 十余年JAVA从业经验,精通JAVA技术体系,有志于做JAVA技能提升的朋友可与我联系,交个朋友 十余年JAVA从业经验,精通JAVA...
Java数据压缩与传输实例,可以学习一下实例化套按字、得到文件输入流、压缩输入流、文件输出流、实例化缓冲区、写入数据到文件、关闭输入流、关闭套接字关闭输出流、输出错误信息等Java编程小技巧。 Java数组倒置...
(1).TicketingDS.java文件,TicketingDS类是实现并发数据结构的类。 1⃣️方法:TicketingDS(int routenum, int coachnum, int seatnum, int stationnum, int threadnum),初始化方法,用来初始化并发数据结构和变量...
在java.util.concurrent 包中有很多 为并发使用情况下设计的数据结构
java并发编程入门 基本概念 并发: 同时拥有俩个或者多个线程,如果线程在单核处理器上运行,多个线程将交替的换入或者换出内存,这些线程是同时 "存在" 的,每个线程都处于执行过程中的某个状态,如果运行在多核...
数据结构和算法---求最佳时间/空间复杂度 项目目录结构 ├─java │ └─org │ └─pp │ ├─java8 │ │ ├─algorithm 算法--问题分类与分析 │ │ ├─concurrent 并发编程 │ │ ├─functional 函数式编程 │...
- JAVA并发编程 - JAVA容器类 - Java锁汇总 ## 数据库 - MySQL - MySQL数据库开发规范 ## 计算机网络 - 计算机网络 ## 算法 - 数据结构与算法 - LeetCode解题总结 - 海量数据处理总结 ## 操作系统 - ...
java与模式源码 Tesla Java并发编程实战、JDK基础源码、设计模式、数据结构与算法、LeetCode等。 了解更多Noah:
2、ConcurrentHashMap中的数据结构 47 3、ConcurrentHashMap初始化 48 4、ConcurrentHashMap的操作 51 二、JDK1.8中原理和实现 54 1、ConcurrentHashMap的数据结构 54 2、ConcurrentHashMap的初始化 55 3、Node链表...
通过阅读和理解这些程序,学习者可以深入掌握Java中的高级概念,如多线程、数据结构、算法等。 实际编程案例:每个程序阅读题都是一个实际的Java代码示例,这些示例代码来源于实际项目或场景。通过分析这些案例,...
java并发编程培训(阿里巴巴)ppt java反射机制总结pdf java数据结构上机实践指导教程pdf java网络编程pdf jvm内存问题最佳实践ppt jvm实现机制ppt jvm调优word tomcat详细资料word tomcat源码研究 java类库简介和...
ConcurrentHashMap可以做到读取数据不加锁,并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小,允许多个修改操作并发进行,其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的...
并发编程改进: 讨论 Java 8 中对并发编程的改进,包括 CompletableFuture、新的并发工具和并发数据结构等。 其他新特性: 简要介绍 Java 8 中引入的其他新特性,如接口的默认方法、方法引用、Optional 类型等。