并发容器——位运算、currentHashMap源码解析、写时复制容器

以你之姓@ 2023-05-30 15:54 12阅读 0赞

# ConcurrentHashMap #

## Hash ##

散列，哈希：把任意长度的输入通过一种算法（散列），变换成为固定长度的输出，这个输出值就是散列值。属于压缩映射，容易产生哈希冲突。Hash算法有直接取余法等。

产生哈希冲突时解决办法：开放寻址；2、再散列；3、链地址法（相同hash值的元素用链表串起来）。

ConcurrentHashMap在发生hash冲突时采用了链地址法。

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
        implements ConcurrentMap<K,V>, Serializable {

可以理解为线程安全的HashMap,新增几个方法  
putIfAbsent：如果已经存在值则返回，否则插入新的键值对

通过位运算得到的数据结果往往比直接的加减乘除等得到的结果快的多，节约内存开销和加快计算效率，jdk里面很多地方都是使用位运算进行存储和判断数据的属性状态

类似于ConcurrentHashMap的这段源码

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;
        }

举个关于增删改查的权限的栗子

public class Permission { 
        // 是否允许查询，二进制第1位，0表示否，1表示是 
        public static final int ALLOW_SELECT = 1 << 0; // 0001 
          
        // 是否允许新增，二进制第2位，0表示否，1表示是 
        public static final int ALLOW_INSERT = 1 << 1; // 0010 
          
        // 是否允许修改，二进制第3位，0表示否，1表示是 
        public static final int ALLOW_UPDATE = 1 << 2; // 0100 
          
        // 是否允许删除，二进制第4位，0表示否，1表示是 
        public static final int ALLOW_DELETE = 1 << 3; // 1000 
          
        // 存储目前的权限状态 
        private int flag;  
      
        /** * 重新设置权限 */  
        public void setPermission(int permission) {   
            flag = permission;  
        }  
      
        /** * 添加一项或多项权限 */  
        public void enable(int permission) {   
            flag = flag|permission;  
        }  
          
        /** * 删除一项或多项权限 */  
        public void disable(int permission) {   
            flag = flag&~permission;  
        }  
          
        /** * 是否拥某些权限 */  
        public boolean isAllow(int permission) {   
            return (flag & permission) == permission;  
        }  
          
        /** * 是否禁用了某些权限 */  
        public boolean isNotAllow(int permission) {   
            return (flag & permission) == 0;  
        }  
          
        /** * 是否仅仅拥有某些权限 */  
        public boolean isOnlyAllow(int permission) {   
            return flag == permission;  
        } 
        
        public static void main(String[] args) { 
    		int flag = 15;//拥有所有权限
    		Permission permission = new Permission();
    		permission.setPermission(flag);
    		permission.disable(ALLOW_DELETE|ALLOW_INSERT);
    		System.out.println("ALLOW_SELECT="+permission.isAllow(ALLOW_SELECT));
    		System.out.println("ALLOW_INSERT="+permission.isAllow(ALLOW_INSERT));
    		System.out.println("ALLOW_UPDATE="+permission.isAllow(ALLOW_UPDATE));
    		System.out.println("ALLOW_DELETE="+permission.isAllow(ALLOW_DELETE));
    	}
    }

## ConcurrentHashMap实现原理（jdk1.7） ##

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment实际继承自可重入锁（ReentrantLock），在ConcurrentHashMap里扮演锁的角色；HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，每个Segment里包含一个HashEntry数组，我们称之为table，每个HashEntry是一个链表结构的元素。  
![在这里插入图片描述][2020052514175423.png]  
![在这里插入图片描述][20191112150110262.png]

初始化有三个参数  
**initialCapacity**：初始容量大小 ，默认16。  
**loadFactor**, 扩容因子，默认0.75，当一个Segment存储的元素数量大于initialCapacity\* loadFactor时，该Segment会进行一次扩容。  
**concurrencyLevel** 并发度，默认16。并发度可以理解为程序运行时能够同时更新ConccurentHashMap且不产生锁竞争的最大线程数，实际上就是ConcurrentHashMap中的分段锁个数，即Segment\[\]的数组长度。如果并发度设置的过小，会带来严重的锁竞争问题；如果并发度设置的过大，原本位于同一个Segment内的访问会扩散到不同的Segment中，CPU cache命中率会下降，从而引起程序性能下降。

初始化时只会对第一个segment进行初始化。

### get（）方法 ###

定位segment和定位table后，依次扫描这个table元素下的的链表，要么找到元素，要么返回null。  
在高并发下的情况下如何保证取得的元素是最新的？  
答：用于存储键值对数据的HashEntry，在设计上它的成员变量value等都是volatile类型的，这样就保证别的线程对value值的修改，get方法可以马上看到。

### 扩容操作 ###

Segment 不扩容，扩容下面的table数组，每次都是将数组翻倍

### size方法 ###

size的时候进行两次不加锁的统计，两次一致直接返回结果，不一致，重新加锁再次统计

### 弱一致性 ###

get方法和containsKey方法都是通过对链表遍历判断是否存在key相同的节点以及获得该节点的value。但由于遍历过程中其他线程可能对链表结构做了调整，因此get和containsKey返回的可能是过时的数据，这一点是ConcurrentHashMap在弱一致性上的体现。

# Jdk 8中的实现 #

数据模型  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70]  
1、 取消了segment数组，直接用table(实际上就是一个node的数组)保存数据，锁的粒度更小，减少并发冲突的概率。

transient volatile Node<K,V>[] table;

2、储数据时采用了链表+红黑树的形式，纯链表的形式时间复杂度为O(n)，红黑树则为O（logn），性能提升很大。==什么时候链表转红黑树？==当key值相等的元素形成的链表中元素个数超过8个的时候。（关于红黑树的内容，在本人博客里有写），当元素小于6个时又会从红黑树转链表  
3、1.8中hashentry命名改成了node,但结构还是一样  
引进了一个sizeCtl的属性，其为以下值时：  
负数：表示进行初始化或者扩容,-1表示正在初始化，-N，表示有N-1个线程正在进行扩容  
正数：0 表示还没有被初始化，>0的数：初始化或者是下一次进行扩容的阈值  
同时新增以下变量  
TreeNode 用在红黑树，表示树的节点,  
TreeBin是实际放在table数组中的，代表了这个红黑树的根。

初始化时只是简单的赋值成员变量

### java8中put方法是怎么定位数据的？ ###

若table不存在就初始化table  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70 1]  
当当前的table正在扩容时会调用helpTransfer方法帮助扩容  
![f即元素本身][f]  
![在这里插入图片描述][20191120151828489.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70 2]  
![大于等于8时][8]

### Get方法定位元素 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70 3]

## 扩容操作 ##

transfer()方法进行实际的扩容操作，table大小也是翻1倍的形式，有一个并发扩容的机制。并且当某个table下node小于8时会重新转为一个链表

### size方法 ###

估计的大概数量，不是精确数量。因为会在sumCount方法中对还未统计金baseCount中的值进行循环累加（循环导致）![在这里插入图片描述][20200525163654584.png]

# 跳表SkipList #

跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，一般的链表查找起来很慢，为解决这个问题，可以随机获取一些节点建立一级索引，再随机从这些一级索引中获取一些节点建立二级索引，以此类推。选取这些节点的方式可以是随机true/false，判断是否需要建立索引  
![在这里插入图片描述][20191205094912222.png]

## 什么是CopyOnWrite容器 ##

写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以写时复制容器也是一种读写分离的思想，读和写不同的容器。如果读的时候有多个线程正在向容器添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的，只能保证最终一致性。  
适用读多写少的并发场景，常见应用：白名单/黑名单， 商品类目的访问和更新场景。  
存在内存占用问题。但可以做到写的时候不排斥读

**ConcurrentLinkedQueue**  
无界非阻塞队列，底层是个链表，遵循先进先出原则。  
add,offer将元素插入到尾部，peek（拿头部的数据，但是不移除）和poll（拿头部的数据，但是移除）

[2020052514175423.png]: https://img-blog.csdnimg.cn/2020052514175423.png
[20191112150110262.png]: https://img-blog.csdnimg.cn/20191112150110262.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191120152601266.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191126153611152.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw,size_16,color_FFFFFF,t_70
[f]: https://img-blog.csdnimg.cn/20191120151523862.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw,size_16,color_FFFFFF,t_70
[20191120151828489.png]: https://img-blog.csdnimg.cn/20191120151828489.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191120152026980.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw,size_16,color_FFFFFF,t_70
[8]: https://img-blog.csdnimg.cn/20191120152140739.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191126154202611.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw,size_16,color_FFFFFF,t_70
[20200525163654584.png]: https://img-blog.csdnimg.cn/20200525163654584.png
[20191205094912222.png]: https://img-blog.csdnimg.cn/20191205094912222.png