Java中的ConcurrentHashMap集合源码解析

目录

• 前言
• put
• get

前言

在并发环境下，HashMap会出现线程安全问题，HashMap的扩容操作会出现闭环现象，当调用get方法时，会出现死循环。

所以，JDK给我们提供了另一个线程安全容器，ConcurrentHashMap。

在本章中我们来详细探讨JDK 1.8中ConcurrentHashMap的核心方法，且为什么是线程安全的以及和JDK 1.8之前的又有何区别。

ConcurrentHashMap底层容器和HashMap相同，同样是Node数组+链表+红黑树，不同的是在原来的基础之上使用了Synchronized+CAS来保证线程安全，下面我们来进行源码分析。

put

public V put(K key, V value) {
		return putVal(key, value, false);
	}
 
	final V putVal(K key, V value, boolean onlyIfAbsent) {
		//从这我们可以看出ConcurrentHashMap的key和value不能为null
		if (key == null || value == null) throw new NullPointerException();
		//得到key的hash值
		int hash = spread(key.hashCode());
		//这是用来记录链表的长度
		int binCount = 0;
		//table：核心的Node数组。
		for (Node<K,V>[] tab = table;;) {
			Node<K,V> f; int n, i, fh;
			//如果数组为空，则进行数组的初始化。这里相当于懒汉模式，使用的时候才去初始化
			if (tab == null || (n = tab.length) == 0)
				//进行数组的初始化
				tab = initTable();
			//根据key的hash计算出该key在Node数组中的位置，并判断这个位置是否为null
			else if ((f = taBAT(tab, i = (n - 1) & hash)) == null) {
				//当前的数组位置为null，则使用CAS插入一个新的Node
				if (casTabAt(tab, i, null,
						new Node<K,V>(hash, key, value, null)))
					break;                   // no lock when adding to empty bin
			}
			//表示正在进行扩容操作 涉及了ForwardingNode 这个特殊的Node，
                        //在扩容时会进行创建，且固定传入的hash值为 -1
			else if ((fh = f.hash) == MOVED)
				tab = helpTransfer(tab, f);
			//到了这里表示，出现了hash冲突，key在Node数组中的索引位置不为null。
			//需进行链表或红黑树的插入操作。
			else {
				V oldVal = null;
	SefhEMziNY			//这个 f编程客栈 存放是 根据key在数组中找到的Node，相当于红黑树或链表的头结点，并进行加锁
				synchronized (f) {
					//这里再进行一次判断，保证f没被其它线程修改
					if (tabAt(tab, i) == f) {
						//如果是链表
						if (fh >= 0) {
							//统计链表的长度
							binCount = 1;
							//对f这个Node进行累加链表的长度，并遍历链表
							for (Node<K,V> e = f编程客栈;; ++binCount) {
								K ek;
								//如果存在相同的value，则覆盖
								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;
								//遍历到最后一个Node，插入一个新的Node到链表的尾部
								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;
							//使用红黑树的方式进行Node的插入
							if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
									value)) != null) {
								oldVal = p.val;
								if (!onlyIfAbsent)
									p.val = value;
							}
						}
					}
				}
				if (binCount != 0) {
					//判断链表的长度是否大于TREEIFY_THRESHOLD，是则转红黑树
					if (binCount >= TREEIFY_THRESHOLD)
						treeifyBin(tab, i);
					if (oldVal != null)
						return oldVal;
					break;
				}
			}
		}
		//统计整个的数组长度，并判断是否需要扩容
		addCount(1L, binCount);
		retandroidurn null;
	}

好了，以上就是大致的分析内容，但还有许多步骤没有展开代码详细说明，如初始化、链表转红黑树及扩容等，其中扩容步骤非常复杂，有机会我会单独写一篇博客详细介绍，在这就不多说了。我们接下来介绍较为简单的初始化及get方法。

初始化数组

private final Node<K,V>[] initTable() {
		Node<K,V>[] tab; int sc;
		while ((tab = table) == null || tab.length == 0) {
			//表示已经有线程在进行初始化操作，让出CPU的执行权
			if ((sc = sizeCtl) < 0)
				Thread.yield(); // lost initialization race; just spin
			//把sc赋值为 -1，表示当前线程开始执行初始化操作
			else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
				try {
					if ((tab = table) == null || tab.length == 0) {
						//获取数组的初始长度，默认为16
						int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
						@SuppressWarnings("unchecked")
						//初始化数组
						Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
						table = tab = nt;
						sc = n - (n >>> 2);
					}
				} finally {
					//sizeCtl 参数 第一个if判断需要用到
					sizeCtl = sc;
				}
				break;
			}
		}
		return tab;
	}

get

public V get(Object key) {
		Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
		//计算key的hash
		int h = spread(key.hashCode());
		if ((tab = table) != null && (n = tab.length) > 0 &&
				//根据hash值做运算获取数组对应的Node（相当于头结点）
				(e = tabAt(tab, (n - 1) & h)) != null) {
			//根据hash和equals判断该Node的key是否和get的key相等,是则返回value
			if ((eh = e.hash) == h) {
				if ((ek = e.key) == key || (ek != null && key.equals(ek)))
					return e.val;
			}
			//这里判断是否正在扩容 或者 该节点为红黑树
			else if (eh < 0)
				return (p = e.find(h, key)) != null ? p.val : null;
			//到了这一步表示该结构为链表，遍历链表，返回value
			while ((e =python e.next) != null) {
				if (e.hash == h &&
						((ek = e.key) == key || (ek != null && key.equals(ek))))
					return e.val;
			}
		}
		return null;
	}

好了，核心的源码部分就分析到这里，我们在来看看JDK 1.8之前的ConcurrentHashMap大致是怎么实现的，区别相当大。

1.8之前的ConcurrentHashMap是采用了ReentrantLock+Segment+HashEntry的结构

整体就是由一个个 Segment 组成，Segment中包含了HashEntry数组，HashEntry数组就是1.8的那个table，只不过它这里是多个。

其中Segment在实现上继承了ReentrantLock，这样就自带了锁的功能，它在进行put的时候只会锁住一个Segment，所以理论上，最多可以同时支持 Segment 个数的线程并发写，只要它们的操作分别分布在不同的 Segment 上。get的时候也是先找到一个Segment，然后在根据Hash值找到数组中的值。

至于为什么JDK在之后使用Synchronized来保证线程安全，是因为在JDK在版本迭代中一直在对Synchronized进行优化，使得Synchronized关键字在某些场景下已经不比ReentrantLock效率慢，甚至更快。

到此这篇关于Java中的ConcurrentHashMap集合源码解析的文章就介绍到这了,更多相关ConcurrentHashMap集合源码内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！