ConcurrentHashMap详解 什么时候CAS什么时候synchronized

2024-06-03 11:36
文章标签 详解 synchronized concurrenthashmap cas

本文主要是介绍ConcurrentHashMap详解 什么时候CAS什么时候synchronized，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

jdk:1.7 segment数组+hashEntry数组+链表实现

jdk版本：1.8：hashEntry+数组+红黑树实现

1、基本参数

//**1、最大容量**  hashmap的最大容量也是这个，菜鸟一面被问到了
private static final int MAXIMUM_CAPACITY = 1 << 30;//数组默认为16
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;//float浮点数，LOAD_FACTOR为final 不可更改
private static final float LOAD_FACTOR = 0.75f;

2、初始化1

也就是说不是你输入什么就是什么容量，内部还有一个算法优化用户的输入。（防止用户输入参数太差）  
//逻辑：如果init>max的一半，则返回max，否则返回tableSizeFor(init + (initialCapacity >>> 1) + 1)); 
public ConcurrentHashMap(int init) {if (init < 0)throw new IllegalArgumentException();int cap = ((init >= (MAXIMUM_CAPACITY >>> 1)) ?MAXIMUM_CAPACITY :tableSizeFor(init + (init >>> 1) + 1));this.sizeCtl = cap;    //`sizeCtl` 表示容量
}//c=2返回2，c=3返回4，c=9返回16
//tableSizeFor 方法通过一系列位操作，将输入值 c 转换为大于或等于 c 的最小 2 的幂次方。这是为了确保哈希表的数组大小总是 2 的幂次方，从而优化哈希分布和查找性能。private static final int tableSizeFor(int c) {int n = c - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

初始化2

 public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) {if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)throw new IllegalArgumentException();if (initialCapacity < concurrencyLevel)   // Use at least as many binsinitialCapacity = concurrencyLevel;   // as estimated threads//非常神奇啊，传入的loadFactor不会改变装填因子，但是会改变传入的容量参数，影响最终容量long size = (long)(1.0 + (long)initialCapacity / loadFactor);int cap = (size >= (long)MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY : tableSizeFor((int)size);this.sizeCtl = cap;}

3、sizeCtl 不太理解

sizeCtl 是 ConcurrentHashMap 中一个非常重要且复杂的控制字段，其作用有很多个。

addCount()里面判断是否要扩容是和sizeCtl比较，而不是和装填因子比较。为什么使用 sizeCtl 而不是直接使用负载因子？

  1. 简化计算：
    • 通过将负载因子的计算隐式地包含在 sizeCtl 中，可以避免每次插入或删除元素时重新计算负载因子，从而减少了计算开销。
  2. 并发控制：
    • 使用 sizeCtl 可以有效地协调多个线程同时进行扩容操作。负值表示正在扩容，并且包含扩容的状态信息。这样，可以避免多个线程重复触发扩容。
  3. 性能优化：
    • 在高并发环境下，频繁访问和修改共享变量（如负载因子）会带来性能瓶颈。通过使用 sizeCtl，可以减少这种共享变量的访问次数，从而提高性能。
// Unsafe mechanicsprivate static final long SIZECTL;
//初始化map时候，this.sizectl = cap; //cap为容量//比如public ConcurrentHashMap(Map<? extends K, ? extends V> m) {this.sizeCtl = DEFAULT_CAPACITY;putAll(m);}在扩容期间：当扩容开始时，sizeCtl 被设置为一个负值，表示当前参与扩容的线程数量。这样其他线程可以知道表正在扩容并可以协同进行扩容操作。

4、put 重点

public V put(K key, V value) {return putVal(key, value, false);}/** Implementation for put and putIfAbsent */final V putVal(K key, V value, boolean onlyIfAbsent) {//1、数据检查if (key == null || value == null) throw new NullPointerException();//2、求key哈希int hash = spread(key.hashCode());int binCount = 0;  //记录遍历的节点数，可以用于判断是否要链表转化为红黑树for (Node<K,V>[] tab = table;;) {  //死循环Node<K,V> f; int n, i, fh;if (tab == null || (n = tab.length) == 0)  //检查 table 是否初始化tab = initTable();//使用哈希值计算索引 i 并检查该位置是否为空。如果为空，使用 CAS 操作插入新节点，并跳出循环。else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))break;                   // no lock when adding to empty bin}else if ((fh = f.hash) == MOVED) // MOVEDd标志用于判断是否已经节点迁移//当一个桶（bin）中的所有节点都被迁移到新的数组中后，原来的位置上会放置一个特殊的转发节点，表示这个桶已经处理完毕。此时，转发节点的 hash 字段会被设置为 MOVED（即 -1）。tab = helpTransfer(tab, f);//协助迁移else {   //如果碰撞了  需要使用synchronized，放弃cas,f是table那个碰撞节点V oldVal = null;synchronized (f) {if (tabAt(tab, i) == f) { // 经典的双重检查，防止当前线程获取table锁之前，tabAt(tab, i)被其它线程改变了if (fh >= 0) {// 哈希值>=0代表是链表，<0代表是红黑树binCount = 1;for (Node<K,V> e = f;; ++binCount) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {  // 三比较，hashcode==hashcode，key==key,key.equals(key)oldVal = e.val;if (!onlyIfAbsent)e.val = value;break;}Node<K,V> pred = e;if ((e = e.next) == null) {pred.next = new Node<K,V>(hash, key,value, null);break;}}}else if (f instanceof TreeBin) { // 红黑树Node<K,V> p;binCount = 2;  //binCount 被初始化为 2，因为红黑树中的节点数计算方式不同于链表。 具体原因我不知道if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}}}if (binCount != 0) {   // 判断是否要扩容 TREEIFY_THRESHOLD=8if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}}}addCount(1L, binCount);  //计数 里面通过cas维护元素个数。return null;}

总结：

  1. 判断key value是否合法 判null
  2. 求key哈希
  3. 判断table是否初始化，如果没有就初始化
  4. 找到key哈希在table中的位置，判断是否为null
    1. 如果是Null则cas直接添加节点
    2. 如果碰撞了 需要使用synchronized（f）{}，放弃cas,f是table那个碰撞节点
      1. 如果f.hash>=0，则说明是链表，遍历查找，当(hashhash && keykey && key.equals(key))的时候返回元素。下一个节点为null还没有找到，则插入节点
      2. 如果f.hash<0, 则说明是红黑树，遍历查找。找不到就插入。
    3. 判断是否要转化为红黑树
  5. 调用addCount（）计算map总的元素个数，内部通过cas来实现。
    1. 这里面会检查table要不要扩容

**5、remove(Object key) **和put差不多

 final V replaceNode(Object key, V value, Object cv) {int hash = spread(key.hashCode());for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;if (tab == null || (n = tab.length) == 0 ||(f = tabAt(tab, i = (n - 1) & hash)) == null)    // 空直接返回 没得删break;else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);else {          //不空则锁起来 再遍历 找到就删V oldVal = null;boolean validated = false;synchronized (f) {if (tabAt(tab, i) == f) {if (fh >= 0) {  // hash>=0 链表validated = true;for (Node<K,V> e = f, pred = null;;) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {V ev = e.val;if (cv == null || cv == ev ||(ev != null && cv.equals(ev))) {oldVal = ev;if (value != null)e.val = value;else if (pred != null)pred.next = e.next;elsesetTabAt(tab, i, e.next);}break;}pred = e;if ((e = e.next) == null //找不到break;}}else if (f instanceof TreeBin) {validated = true;TreeBin<K,V> t = (TreeBin<K,V>)f;TreeNode<K,V> r, p;if ((r = t.root) != null &&(p = r.findTreeNode(hash, key, null)) != null) {V pv = p.val;if (cv == null || cv == pv ||(pv != null && cv.equals(pv))) {oldVal = pv;if (value != null)p.val = value;else if (t.removeTreeNode(p))setTabAt(tab, i, untreeify(t.first));}}}}}if (validated) {     // 计数if (oldVal != null) {if (value == null)addCount(-1L, -1);return oldVal;}break;}}}return null;}

6、get(Object key)

public V get(Object key) {// 定义一些局部变量Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;// 计算键的哈希值，并进行哈希值扩散以减少碰撞int h = spread(key.hashCode());// 如果哈希表不为空并且哈希表长度大于0if ((tab = table) != null && (n = tab.length) > 0 &&// 计算哈希表索引，取出对应位置的节点(e = tabAt(tab, (n - 1) & h)) != null) {// 如果找到的节点的哈希值等于目标哈希值if ((eh = e.hash) == h) {// 并且键也相等（引用相等或 equals 相等），则返回该节点的值if ((ek = e.key) == key || (ek != null && key.equals(ek)))return e.val;}// 如果节点的哈希值小于0，表示该节点是一个特殊节点（如红黑树节点或转移节点）else if (eh < 0)// 调用 find 方法在该节点中查找目标键对应的值return (p = e.find(h, key)) != null ? p.val : null;// 否则，遍历该链表中的所有节点while ((e = e.next) != null) {if (e.hash == h &&((ek = e.key) == key || (ek != null && key.equals(ek))))return e.val;}}// 如果没有找到，返回 nullreturn null;
}

这篇关于ConcurrentHashMap详解 什么时候CAS什么时候synchronized的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1026878。

相关文章

Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息，即可快速实现设备配网，是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递，利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力，实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后，即可发送相关配网数据。同时还支持与常规Sof
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
K8S（Kubernetes）开源的容器编排平台安装步骤详解

K8S（Kubernetes）开源的容器编排平台安装步骤详解

K8S（Kubernetes）是一个开源的容器编排平台，用于自动化部署、扩展和管理容器化应用程序。以下是K8S容器编排平台的安装步骤、使用方式及特点的概述： 安装步骤： 安装Docker：K8S需要基于Docker来运行容器化应用程序。首先要在所有节点上安装Docker引擎。 安装Kubernetes Master：在集群中选择一台主机作为Master节点，安装K8S的控制平面组件，如AP
阅读更多...
嵌入式Openharmony系统构建与启动详解

嵌入式Openharmony系统构建与启动详解

大家好，今天主要给大家分享一下，如何构建Openharmony子系统以及系统的启动过程分解。 第一：OpenHarmony系统构建      首先熟悉一下，构建系统是一种自动化处理工具的集合，通过将源代码文件进行一系列处理，最终生成和用户可以使用的目标文件。这里的目标文件包括静态链接库文件、动态链接库文件、可执行文件、脚本文件、配置文件等。      我们在编写hellowor
阅读更多...
LabVIEW FIFO详解

LabVIEW FIFO详解

在LabVIEW的FPGA开发中，FIFO（先入先出队列）是常用的数据传输机制。通过配置FIFO的属性，工程师可以在FPGA和主机之间，或不同FPGA VIs之间进行高效的数据传输。根据具体需求，FIFO有多种类型与实现方式，包括目标范围内FIFO（Target-Scoped）、DMA FIFO以及点对点流（Peer-to-Peer）。 FIFO类型 **目标范围FIFO（Target-Sc
阅读更多...
019、JOptionPane类的常用静态方法详解

019、JOptionPane类的常用静态方法详解

目录 JOptionPane类的常用静态方法详解 1. showInputDialog()方法 1.1基本用法 1.2带有默认值的输入框 1.3带有选项的输入对话框 1.4自定义图标的输入对话框 2. showConfirmDialog()方法 2.1基本用法 2.2自定义按钮和图标 2.3带有自定义组件的确认对话框 3. showMessageDialog()方法 3.1
阅读更多...
脏页的标记方式详解

脏页的标记方式详解

脏页的标记方式 一、引言 在数据库系统中，脏页是指那些被修改过但还未写入磁盘的数据页。为了有效地管理这些脏页并确保数据的一致性，数据库需要对脏页进行标记。了解脏页的标记方式对于理解数据库的内部工作机制和优化性能至关重要。 二、脏页产生的过程 当数据库中的数据被修改时，这些修改首先会在内存中的缓冲池（Buffer Pool）中进行。例如，执行一条 UPDATE 语句修改了某一行数据，对应的缓
阅读更多...
关键字synchronized、volatile的比较

关键字synchronized、volatile的比较

关键字volatile是线程同步的轻量级实现，所以volatile性能肯定比synchronized要好，并且volatile只能修饰于变量，而synchronized可以修饰方法，以及代码块。随着JDK新版本的发布，synchronized关键字的执行效率上得到很大提升，在开发中使用synchronized关键字的比率还是比较大的。多线程访问volatile不会发生阻塞，而synchronize
阅读更多...
OmniGlue论文详解（特征匹配）

OmniGlue论文详解（特征匹配）

OmniGlue论文详解（特征匹配） 摘要1. 引言2. 相关工作2.1. 广义局部特征匹配2.2. 稀疏可学习匹配2.3. 半稠密可学习匹配2.4. 与其他图像表示匹配 3. OmniGlue3.1. 模型概述3.2. OmniGlue 细节3.2.1. 特征提取3.2.2. 利用DINOv2构建图形。3.2.3. 信息传播与新的指导3.2.4. 匹配层和损失函数3.2.5. 与Super
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2