帮忙纠错！ 诚恳感谢！

源码分析1.8

ConcurrentHashMap数据结构是: 数组 + 链表 + 红黑树，它是线程安全的。其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。在多并发情况下它的数据为弱一致性的，多并发下get()返回的结果可能不是预期的值（这点在最后论证）。适用场景为：多线程对HashMap数据添加删除操作时。

口述运行原理： ConcurrentHashMap是通过Node<K,V>[]数组来存储map中的键值对，而每个数组位置上通过链表和红黑树的形式保存， 数组只有在第一个put时才会初始化。 第一次添加元素的时候，默认初始值是16（DEFAULT_CAPACITY ）。当往map中继续添加元素的时候，通过hash值跟数组的长度来决定存放的那个位置（(h ^ (h >>> 16)) & HASH_BITS;），如果出现放在同一个位置上，优先以链表的形式存放，在同一位置上个元素个超过8个以上，这时如果数组的总长度小于64（MIN_TREEIFY_CAPACITY ），则进行数组扩容，扩容到原来的两倍大。 如果数组的长度大于等于64，那会将该节点的链表转换成红黑树。 通过扩容的方式来把这些节点给散开，然后将这些元素复制到扩容后的数组，同一个链表中的元素通过hash值和数组长度来区分( int b = p.hash & n;)，一部份将放到新数组的新位置上去，一部分放到新数组同样长度的位置上，在扩容完成后，如果某个树节点的长度小于等于6了，则会将其转成链表。 其实和HashMap有多地方相似。

// 扩容新数组 n是旧数组的长度 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1]; nextTab = nt; private static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 private static final int DEFAULT_CAPACITY = 16; //默认容量 static final int TREEIFY_THRESHOLD = 8; // 变成红黑树的阈值 static final int UNTREEIFY_THRESHOLD = 6; //从红黑树变回链表的阈值 static final int MIN_TREEIFY_CAPACITY = 64; // 树的最小容量 static final int MOVED = -1; // 表示正在转移 static final int TREEBIN = -2; // 表示已经转换成树 static final int RESERVED = -3; // hash for transient reservations static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash transient volatile Node<K,V>[] table; //默认没初始化的数组，用来保存元素 private transient volatile Node<K,V>[] nextTable; //转移的时候用的数组 /** * 用来控制表初始化和扩容的，默认值为0，当在初始化的时候指定了大小，这会将这个大小保存在sizeCtl中，大小为数组的0.75 * 当为负的时候，说明表正在初始化或扩张， * -1表示初始化 * -(1+n) n:表示活动的扩张线程 */ private transient volatile int sizeCtl;

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) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); // 获取hash值 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(); // 数组初始化。之前提到的只有第一次put的时候才会初始化数组 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 根据hash值获取下标位置 判断位置上是否为空 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 { V oldVal = null; synchronized (f) { // 同步代码块 if (tabAt(tab, i) == f) { if (fh >= 0) { // hash值大于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)))) { // key 相同直接覆盖value值 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; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); //统计节点个数，检查是否需要resize操作 return null; } // 红黑树的put处理方法 final TreeNode<K,V> putTreeVal(int h, K k, V v) { Class<?> kc = null; boolean searched = false; for (TreeNode<K,V> p = root;;) { int dir, ph; K pk; if (p == null) { first = root = new TreeNode<K,V>(h, k, v, null, null); break; } else if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((pk = p.key) == k || (pk != null && k.equals(pk))) return p; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { if (!searched) { TreeNode<K,V> q, ch; searched = true; if (((ch = p.left) != null && (q = ch.findTreeNode(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.findTreeNode(h, k, kc)) != null)) return q; } dir = tieBreakOrder(k, pk); } TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { TreeNode<K,V> x, f = first; first = x = new TreeNode<K,V>(h, k, v, f, xp); if (f != null) f.prev = x; if (dir <= 0) xp.left = x; else xp.right = x; if (!xp.red) x.red = true; else { lockRoot(); try { root = balanceInsertion(root, x); } finally { unlockRoot(); } } break; } } assert checkInvariants(root); return null; }

addCount分析

在put方法结尾处调用了addCount方法，把当前ConcurrentHashMap的元素个数+1这个方法一共做了两件事,更新baseCount的值，检测是否进行扩容。

/** * Adds to count, and if table is too small and not already * resizing, initiates transfer. If already resizing, helps * perform transfer if work is available. Rechecks occupancy * after a transfer to see if another resize is already needed * because resizings are lagging additions. * * @param x the count to add * @param check if <0, don't check resize, if <= 1 only check if uncontended */ private final void addCount(long x, int check) { CounterCell[] as; long b, s; if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { CounterCell a; long v; int m; boolean uncontended = true; if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null || !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { fullAddCount(x, uncontended); return; } if (check <= 1) return; s = sumCount(); } if (check >= 0) { Node<K,V>[] tab, nt; int n, sc; while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) { int rs = resizeStamp(n); if (sc < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); } } }

get源码分析

/** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code key.equals(k)}, * then this method returns {@code v}; otherwise it returns * {@code null}. (There can be at most one such mapping.) * * @throws NullPointerException if the specified key is null */ public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; int h = spread(key.hashCode()); // 获取hash值 if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { //各种比较不能为空 if ((eh = e.hash) == h) { //hash值比较 if ((ek = e.key) == key || (ek != null && key.equals(ek))) // key比较 return e.val; } else if (eh < 0) // 取值 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; } } return null; } Node<K,V> find(int h, Object k) { Node<K,V> e = this; if (k != null) { do { K ek; if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; } while ((e = e.next) != null); } return null; }

size and mappingCount 源码解析

size方法的返回呢有意思的！ size返回的是int类型 ，int的长度有限最大就是返回到Integer.MAX_VALUE.。 mappingCount返回的就是long 类型，是实际的长度。 由于这两个方法没使用同步锁机制，所以在多线程的环境下这个两个方法不能准确的返回正确的数组长度。 这个可以自己写一个main方法测试一下，可能后续我也会update下博客。

/** * {@inheritDoc} */ public int size() { long n = sumCount(); return ((n < 0L) ? 0 : // 因为int 类型的长度有限 这里它个处理了一下。最大返回的就是nteger.MAX_VALUE。 (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n); } public long mappingCount() { long n = sumCount(); return (n < 0L) ? 0L : n; // ignore transient negative values //这个方法它返回的就是实际的长度 } final long sumCount() { CounterCell[] as = counterCells; CounterCell a; long sum = baseCount; if (as != null) { for (int i = 0; i < as.length; ++i) { if ((a = as[i]) != null) sum += a.value; } } return sum; }

1.7和1.8的区别在哪里？？？

跟1.7版本相比，1.8版本又有了很大的变化，已经抛弃了Segment的概念，虽然源码里面还保留了，也只是为了兼容性的考虑。 1.8 在 1.7 的数据结构上做了大的改动，采用红黑树之后可以保证查询效率（O(logn)），甚至取消了 ReentrantLock 改为了 synchronized，这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的。

1.7使用的是分段锁实现多并发的，将数组分成多个快，每个块有自己的锁，这样操作A块的时候，BCD块不会被锁，get和put就不会受影响。 锁分段技术：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

1.8使用的是CAS无锁机制,在ConcurrentHashMap中，随处可以看到U, 大量使用了U.compareAndSwapXXX的方法，这个方法是利用一个CAS算法实现无锁化的修改值的操作，他可以大大降低锁代理的性能消耗。这个算法的基本思想就是不断地去比较当前内存中的变量值与你指定的一个变量值是否相等，如果相等，则接受你指定的修改的值，否则拒绝你的操作。因为当前线程中的值已经不是最新的值，你的修改很可能会覆盖掉其他线程修改的结果。这一点与乐观锁，SVN的思想是比较类似的。 https://blog.csdn.net/bill_xiang_/article/details/81122044

HashMap 和 CoucurrrentHashMap 区别and应用场景

这里推荐一个博客，并有代码demo演示，get(）方法到底准不准。 博客：https://blog.csdn.net/sinbadfreedom/article/details/80375048

最后在推荐一个博客：https://blog.csdn.net/programmer_at/article/details/79715177#14-table