【源码解析】ConcurrentHashMap

阳光穿透心脏的1/2处 2022-09-11 15:20 211阅读 0赞

> 废话不多说，Just show me your code

## 常量、变量： ##

**常量：**

1. 数组容量：
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    private static final int DEFAULT_CAPACITY = 16;
    
    2. 并发级别，桶位比这个小，按照这个来init
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    
    3. 负载因子，JDK1.8中 ConcurrentHashMap 是固定值
    private static final float LOAD_FACTOR = 0.75f;
    
    4. 树化、树的退化阈值：
    static final int TREEIFY_THRESHOLD = 8;
    static final int MIN_TREEIFY_CAPACITY = 64;
    static final int UNTREEIFY_THRESHOLD = 6;
    
    5. 线程迁移数据最小步长，控制线程迁移任务最小区间一个值
    private static final int MIN_TRANSFER_STRIDE = 16;
    private static int RESIZE_STAMP_BITS = 16;
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
    
    6. 节点状态
    static final int MOVED     = -1; // hash for forwarding nodes
    static final int TREEBIN   = -2; // hash for roots of trees
    static final int HASH_BITS = 0x7fffffff; // xx^HASH_BITS 维护值变为正数

**变量：**

1. normal
    transient volatile Node<K,V>[] table;
    private transient volatile Node<K,V>[] nextTable;
    
    2. 并发
    private transient volatile long baseCount; // +所有cells
    private transient volatile int sizeCtl; // >=0 表阈值、 <0 在迁移
    private transient volatile int transferIndex;
    private transient volatile CounterCell[] counterCells;

## 构造方法： ##

一共5个，其他都是套娃  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 1]

还有其他的一些小方法：tableSizeFor、spread都是HashMap中见过的

## get方法： ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 2]

### 关于find方法 ###

自己在思考的时候遇到了一些错误，**get的时候怎么确定会进入到哪个方法？**

1.  put的时候已经确定了是FWD还是TreeBin，
2.  在扩容时，当前桶挪完在桶位上放置FWD节点，其他线程定位到这个桶位，会调用FWD的find方法。
3.  非扩容时，不会调用FWD的find方法。

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

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 4]

## put方法 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 5]

![在这里插入图片描述][274b473ebcae4fb3ad665175db455272.png]  
**链表情况：**

fh >= 0：链表
    fh = -1：FWD
    fh = -2：TreeBin节点

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 6]

**TreeBin节点情况：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 7]

**最后：**  
检查是否需要树化 以及有没有发生替换操作  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 8]

## addCount方法： ##

类比HashMap 的resize方法

1.统计当前table一共有多少数据  
2.判断是否达到扩容阈值标准，触发扩容。

## remove方法： ##

public V remove(Object key) {
        
            return replaceNode(key, null, null);
        }

### replaceNode: ###

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;
            // CASE1：表空、桶空  =》 break
            if (tab == null || (n = tab.length) == 0 || (f = tabAt(tab, i = (n - 1) & hash)) == null)
                break;
            // CASE2：正在搬移，去帮忙
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
    		// CASE3： 链表或者红黑树TreeBin节点
            else {
        
                V oldVal = null;  // 检查是否发生替换
                boolean validated = false;   // 校验标记，是否有确定为链表或者红黑树TreeBin节点
                // 经典的double check
                synchronized (f) {
        
                    if (tabAt(tab, i) == f) {
        
                        if (fh >= 0) {
         // 链
                            validated = true;
                            for (Node<K,V> e = f, pred = null;;) {
        
                                K ek;
                                // hash和key都相同 确定是需要replace 的节点
                                if (e.hash == hash && ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
        
                                    V ev = e.val;
                                    
                                    //条件一：cv == null true->替换的值为null 那么就是一个删除操作
                                    //条件二：cv == ev || (ev != null && cv.equals(ev))  那么是一个替换操作
                                    if (cv == null || cv == ev || (ev != null && cv.equals(ev))) {
        
                                        oldVal = ev;
                                        // 1、替换操作
                                        if (value != null) e.val = value;
                                        // 2、要找的值在中间，移动next指针
                                        else if (pred != null) pred.next = e.next;
                                        // 3、repalce在头节点，桶位设置为头结点的下一个节点。
                                        else setTabAt(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;
                                    // 1、替换
                                    if (value != null) p.val = value;
                                    // 2、删除
                                    else if (t.removeTreeNode(p))
                                    	setTabAt(tab, i, untreeify(t.first));
                                }
                            }
                        }
                    }
                }
                if (validated) {
        
                    if (oldVal != null) {
        
                    	//替换的值 为null，说明当前是一次删除操作
                    	// oldVal ！=null 成立，说明删除成功，更新当前元素个数计数器。
                        if (value == null) addCount(-1L, -1);
                        return oldVal;
                    }
                    break;
                }
            }
        }
        return null;
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/071e594dd9bb4f58a045614cd2bdbfbf.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/22f6d512111e4ebabdaea841f0d9e55a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/241ad51139874b1a94d52b02afd2103f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/5043fe3c84874506becdedf348f39403.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/b6a1e4dcd704404db952242bbdf29073.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/6969a0ad652548f38fb6e35107911438.png
[274b473ebcae4fb3ad665175db455272.png]: /images/20220828/df002baeeda5409cac925afde2c0b5e5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/aae88ab57b7e4a78b1f8af5b91c995ff.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/2765d4ecc9a94a799ff24a5bc224340e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/63beeddb2d71405fbbc69373f6ab57d2.png