欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

ConcurrentHashMap底层源码分析

程序员文章站 2022-05-13 09:34:30
ConcurrentHashMap在JDK1.8以后使用的是Node数组+链表+红黑树的结构来实现的,并发控制使用Synchronized和CAS来操作,所以整个过程看起来是安全的,但是实际上在写入过程中是用CAS执行操作,只是表征安全,实际上不安全,但是独占锁时安全;// node数组最大容量:2^30private static final int MAXIMUM_CAPACITY = 1 << 30;// 默认初始值大小为16,必须是2的幂数private static final...

ConcurrentHashMap

ConcurrentHashMap在JDK1.8以后使用的是Node数组+链表+红黑树的结构来实现的,并发控制使用Synchronized和CAS来操作,所以整个过程看起来是安全的,但是实际上在写入过程中是用CAS执行操作,只是表征安全,实际上不安全,但是独占锁时安全;

// node数组最大容量:2^30

private static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认初始值大小为16,必须是2的幂数

private static final int DEFAULT_CAPACITY = 16;

//数组可能最大值,需要与toArray()相关方法关联

static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// 负载因子

private static final float LOAD_FACTOR = 0.75f;

// 链表转红黑树阀值,当链表长度超过8时链表转换为红黑树结构

static final int TREEIFY_THRESHOLD = 8;

// 2^15-1,help resize的最大线程数

private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;

// 32-16=16,sizeCtl中记录size大小的偏移量

private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

//存放node的数组

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

//初始化容器的方法
private final Node<K,V>[] initTable() {Node<K,V>[] tab; int sc;

	//如果容器为空或者容器大小为空,则开始循环
	
    while ((tab = table) == null || tab.length == 0) {
    
        //如果目前需要扩容的大小是小于0的,则让出当前扩容线程的执行过程
		//因为必然有其他线程在尝试扩容
		
		if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
            
		//如果sc>=0,则去执行一次CAS过程,将本对象中的SIZECTL值替换为-1	
		//原来的比较用的值是sc
		
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
            
			//如果tab是空,或者没有长度
			
                if ((tab = table) == null || tab.length == 0) {
                
				//刚才已经替换过sc了,这个时候的sc应该是-1
				
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    
					//所以第一次初始化容量的时候,容量是16
					
                    @SuppressWarnings("unchecked")
                    
					//创建一个容量为16的数组
					
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    
					//重置sc为12
					
                    sc = n - (n >>> 2);
                }
            } finally {
            
				//重置CTL为12
				
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

//put方法
final V putVal(K key, V value, boolean onlyIfAbsent) {

	//如果判断key或者value为空,那么直接抛出空指针异常
	
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    
	//定义一个int型的值,用来记录对应链表的长度
	
    int binCount = 0;
    
	//遍历数组
	
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        
		//如果数组为空或者数组长度为零,则初始化
		
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
            
		//如果数组当前的位置为空,则用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)
            tab = helpTransfer(tab, f);
        else {
        
			//如果f是头结点
			
            V oldVal = null;
            
			//则给f上锁

            synchronized (f) {
                if (tabAt(tab, i) == f) {
                
					//判断如果头结点的hash大于等于零,则说明是链表
					
                    if (fh >= 0) {
                    
						//给链表长度 +1
						
                        binCount = 1;
                        
						//遍历链表
						
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            
							//判断是否有相等的 key,继而判断是否要进行值覆盖
							
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            
							//如果e.next为空,则到了链表的末端,将新值放到链表的末端
							
                            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;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            
			//判断链表长度是否等于零
			
            if (binCount != 0) {
            
				//如果链表长度大于8,则转为红黑树结构
				
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

本文地址:https://blog.csdn.net/Yyuxiansheng/article/details/110193563