网站建设文化案例,故宫博物院官网网站咋做的,一个网站多个子域名优化,建设银行网站注册用户HashMap不是线程安全#xff1a; 在并发环境下#xff0c;可能会形成环状链表#xff08;扩容时可能造成#xff0c;具体原因自行百度google或查看源码分析#xff09;#xff0c;导致get操作时#xff0c;cpu空转#xff0c;所以#xff0c;在并发环境中使用HashMap是… HashMap不是线程安全 在并发环境下可能会形成环状链表扩容时可能造成具体原因自行百度google或查看源码分析导致get操作时cpu空转所以在并发环境中使用HashMap是非常危险的 HashTable是线程安全的 HashTable和HashMap的实现原理几乎一样 与HashMap的差别 HashTable不允许key和value为null HashTable是线程安全的。
HashTable线程安全的策略实现代价却比较大get/put所有相关操作都是synchronized的这相当于给整个哈希表加了一把大锁多线程访问时候只要有一个线程访问或操作该对象那其他线程只能阻塞见下图 ConcurrentHashMap底层实现 JDK1.7
底层数据结构Segments数组HashEntry数组链表采用分段锁保证安全性
容器中有多把锁每一把锁锁一段数据这样在多线程访问时不同段的数据时就不会存在锁竞争了这 样便可以有效地提高并发效率。这就是ConcurrentHashMap所采用的”分段锁”思想见下图
一个ConcurrentHashMap中有一个Segments数组一个Segments中存储一个HashEntry数组每个HashEntry是一个链表结构的元素。
segment继承自ReentrantLock锁。 首先将数据分为一段一段的存储然后给每一段数据配一把锁当一个线程占用锁访问其中一段数据时其他段的数据也能被其他线程访问实现了真正的并发访问。
可以通过构造函数指定,数组扩容不会影响其他的segment,get无需加锁,volatile保证内存可见性
get()操作
HashEntry中的value属性和next指针是用volatile修饰的保证了可见性所以每次获取的都是最新值get过程不需要加锁。
1.将key传入get方法中先根据key的hashcode的值找到对应的segment段。
2.再根据segment中的get方法再次hash找到HashEntry数组中的位置。
3.最后在链表中根据hash值和equals方法进行查找。
ConcurrentHashMap的get操作跟HashMap类似只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置然后再hash定位到指定的HashEntry遍历该HashEntry下的链表进行对比成功就返回不成功就返回null。
put()操作
1.将key传入put方法中先根据key的hashcode的值找到对应的segment段
2.再根据segment中的put方法加锁lock()。
3.再次hash确定存放的hashEntry数组中的位置
4.在链表中根据hash值和equals方法进行比较如果相同就直接覆盖如果不同就插入在链表中。
JDK1.8
底层数据结构Synchronized CAS Node 红黑树.Node的val和next都用volatile保证,保证可见性,查找,替换,赋值操作都使用CAS
为什么在有Synchronized 的情况下还要使用CAS
因为CAS是乐观锁,在一些场景中(并发不激烈的情况下)它比Synchronized和ReentrentLock的效率要高,当CAS保障不了线程安全的情况下(扩容或者hash冲突的情况下)转成Synchronized 来保证线程安全,大大提高了低并发下的性能.
锁 : 锁是锁的链表的head的节点,不影响其他元素的读写,锁粒度更细,效率更高,扩容时,阻塞所有的读写操作(因为扩容的时候使用的是Synchronized锁,锁全表),并发扩容.
读操作无锁 :
Node的val和next使用volatile修饰,读写线程对该变量互相可见 数组用volatile修饰,保证扩容时被读线程感知 get()操作
get操作全程无锁。get操作可以无锁是由于Node元素的val和指针next是用volatile修饰的。
在多线程环境下线程A修改节点的val或者新增节点的时候是对线程B可见的。
1.计算hash值定位到Node数组中的位置
2.如果该位置为null则直接返回null
3.如果该位置不为null再判断该节点是红黑树节点还是链表节点
如果是红黑树节点使用红黑树的查找方式来进行查找
如果是链表节点遍历链表进行查找
put()操作
1.先判断Node数组有没有初始化如果没有初始化先初始化initTable();
2.根据key的进行hash操作找到Node数组中的位置如果不存在hash冲突即该位置是null直接用CAS插入
3.如果存在hash冲突就先对链表的头节点或者红黑树的头节点加synchronized锁
4.如果是链表就遍历链表如果key相同就执行覆盖操作如果不同就将元素插入到链表的尾部 并且在链表长度大于8 Node数组的长度超过64时会将链表的转化为红黑树。
5.如果是红黑树就按照红黑树的结构进行插入。
总线嗅探机制 使用 volatile 修饰共享变量后每个线程要操作变量时会从主内存中将变量拷贝到本地内存作为副本当线程操作变量副本并写回主内存后会通过 CPU 总线嗅探机制告知其他线程该变量副本已经失效需要重新从主内存中读取。
volatile 保证了不同线程对共享变量操作的可见性也就是说一个线程修改了 volatile 修饰的变量当修改后的变量写回主内存时其他线程能立即看到最新值。
在现代计算机中CPU 的速度是极高的如果 CPU 需要存取数据时都直接与内存打交道在存取过程中CPU 将一直空闲这是一种极大的浪费所以为了提高处理速度CPU 不直接和内存进行通信而是在 CPU 与内存之间加入很多寄存器多级缓存它们比内存的存取速度高得多这样就解决了 CPU 运算速度和内存读取速度不一致问题。
由于 CPU 与内存之间加入了缓存在进行数据操作时先将数据从内存拷贝到缓存中CPU 直接操作的是缓存中的数据。但在多处理器下将可能导致各自的缓存数据不一致这也是可见性问题的由来为了保证各个处理器的缓存是一致的就会实现缓存一致性协议而嗅探是实现缓存一致性的常见机制。 注意缓存的一致性问题不是多处理器导致而是多缓存导致的。
嗅探机制工作原理每个处理器通过监听在总线上传播的数据来检查自己的缓存值是不是过期了如果处理器发现自己缓存行对应的内存地址修改就会将当前处理器的缓存行设置无效状态当处理器对这个数据进行修改操作的时候会重新从主内存中把数据读到处理器缓存中。
注意基于 CPU 缓存一致性协议JVM 实现了 volatile 的可见性但由于总线嗅探机制会不断的监听总线如果大量使用 volatile 会引起总线风暴。所以volatile 的使用要适合具体场景。
使用 volatile 和 synchronized 锁都可以保证共享变量的可见性。相比 synchronized 而言volatile 可以看作是一个轻量级锁所以使用 volatile 的成本更低因为它不会引起线程上下文的切换和调度。但 volatile 无法像 synchronized 一样保证操作的原子性。
volatile 的原子性问题
所谓的原子性是指在一次操作或者多次操作中要么所有的操作全部都得到了执行并且不会受到任何因素的干扰而中断要么所有的操作都不执行。
在多线程环境下volatile 关键字可以保证共享数据的可见性但是并不能保证对数据操作的原子性。也就是说多线程环境下使用 volatile 修饰的变量是线程不安全的。
要解决这个问题我们可以使用锁机制或者使用原子类如 AtomicInteger。
这里特别说一下对任意单个使用 volatile 修饰的变量的读 / 写是具有原子性但类似于 flag !flag 这种复合操作不具有原子性。简单地说就是单纯的赋值操作是原子性的。 JDK1.8中为什么使用synchronized替换可重入锁ReentrantLock Segment继承了ReentrantLock所以Segment是一种可重入锁。
1.Segment可重入锁锁住的是一个HashEntry数组synchronized锁住的只是发生hash冲突的链表]的头节点或红黑树的节点提高了并发性能。
2.从JDK1.6开始对 synchronized 锁的实现引入了大量的优化并且 synchronized 有多种锁状态会从偏向锁 - 轻量级锁 - 重量级锁一步步转换。
只要并发的线程可以在一定次数的自旋内拿到锁偏向锁不用自旋那么synchronized就不会升级为重量级锁等待的线程也不会被挂起减少了线程挂起和唤醒的切换的过程开销。
而ReentrantLock不会自旋会直接挂起这样一来就很容易会多出线程上下文开销的代价。
3.减少内存开销 。假设使用可重入锁来获得同步支持那么每个节点都需要通过继承 AQS 来获得同步支持。但并不是每个节点都需要获得同步支持的只有链表的头节点红黑树的根节点需要同步这无疑带来了巨大内存浪费。
1.7结构图 整个ConcurrentHashMap是由一个一个的Segment组成Segment代表一个分段一个Segment里面包含一个HashEntry数组每个HashEntry是一个链表结构当对HashEntry数据的数据进行修改时必须先获取与它对应的Segment锁。 1.8结构图 摒弃了Segment的概念而是直接通过Node数组 链表红黑树的数据结构来实现并发控制使用Synchronized和CAS来操作。 总结与思考
其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap相对而言ConcurrentHashMap只是增加了同步的操作来控制并发
从JDK1.7版本的ReentrantLockSegmentHashEntry到JDK1.8版本中synchronizedCASHashEntry红黑树,相对而言
总结如下思考
JDK1.8的实现降低锁的粒度JDK1.7版本锁的粒度是基于Segment的包含多个HashEntry而JDK1.8锁的粒度就是HashEntry首节点JDK1.8版本的数据结构变得更加简单使得操作也更加清晰流畅因为已经使用synchronized来进行同步所以不需要分段锁的概念也就不需要Segment这种数据结构了由于粒度的降低实现的复杂度也增加了JDK1.8使用红黑树来优化链表基于长度很长的链表的遍历是一个很漫长的过程而红黑树的遍历效率是很快的代替一定阈值的链表这样形成一个最佳拍档JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock我觉得有以下几点 因为粒度降低了在相对而言的低粒度加锁方式synchronized并不比ReentrantLock差在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界更加的灵活而在低粒度中Condition的优势就没有了JVM的开发团队从来都没有放弃synchronized而且基于JVM的synchronized优化空间更大使用内嵌的关键字比使用API更加自然在大量的数据操作下对于JVM的内存压力基于API的ReentrantLock会开销更多的内存虽然不是瓶颈但是也是一个选择依据 知识来源
【基础】ConcurrentHashMap原理简述jdk7和jdk8的区别_哔哩哔哩_bilibili
ConcurrentHashMap底层结构和原理详解_concurrenthashmap底层原理_猿灰灰的博客-CSDN博客
ConcurrentHashMap底层原理_liyaomeng的博客-CSDN博客
ConcurrentHashMap的底层实现原理_concurrenthashmap底层原理_菜鸟gogoing的博客-CSDN博客
