ConcurrentHashMap初始化以及put流程
-
ConcurrentHashMap执行流程
本文重点：
- ConcurrentHashMap如何保证线程安全
- ConcurrentHashMap的put流程
先看ConcurrentHashMap的构造方法：
public ConcurrentHashMap() { } //如果只传入initialCapacity，那么先执行initialCapacity = initialCapacity+(initialCapacity >>> 1)+ 1，再取大于等于这个新的initialCapacity的最小2^n public ConcurrentHashMap(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException(); int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); this.sizeCtl = cap; } //通过已有的Map构造新的ConcurrentMap public ConcurrentHashMap(Map<? extends K, ? extends V> m) { this.sizeCtl = DEFAULT_CAPACITY; putAll(m); } public ConcurrentHashMap(int initialCapacity, float loadFactor) { this(initialCapacity, loadFactor, 1); } //既传入initialCapacity又传入负载因子，那么初始化容量为大于等于1.0 + (long)initialCapacity / loadFactor的最小2^n public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); if (initialCapacity < concurrencyLevel) // Use at least as many bins initialCapacity = concurrencyLevel; // as estimated threads long size = (long)(1.0 + (long)initialCapacity / loadFactor); int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size); this.sizeCtl = cap; }我们知道JDK8之中ConcurrentHashMap是通过链表和红黑树来存储节点的，那么让我们来看看ConcurrentHashMap的put流程
public V put(K key, V value) { return putVal(key, value, false); } /** Implementation for put and putIfAbsent */ // onluIfAbsent默认为false，表示如果存在相同的key，那么新的value将会覆盖旧的vale // 如果onlyIfAbsent为true，表示key相同时，value不进行覆盖，value保持最开始的值。 final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); //通过key产生一个hash值，并将其打散，以减少冲突 int hash = spread(key.hashCode()); int binCount = 0; // table 的定义为transient volatile Node<K,V>[] table; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) //如果数组为空则初始化数组 tab = initTable(); // f = table[i] // 需要明白的是，n为tab.length，而数组的长度选取的是2的整数次幂,那么 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //如果table[i]为空则通过CAS控制只能一个线程在table[i]位置初始化一个节点 //这个节点将成为链表或者红黑树的（头）根节点 //如果table[i]被其他线程初始化，那么casTabAt返回false,直接退出循环 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } // fh = f.hash=table[i].hash // MOVED的定义为 static final int MOVED = -1; // hash for forwarding nodes else if ((fh = f.hash) == MOVED) // 如果table[i].hash为-1,那么说明链表或者红黑树的头（根）节点被移动(更改）， // 那么就进行节点的转移，tab记录转移后生成的新数组。 tab = helpTransfer(tab, f); else { // 如果头(根）节点没有被移动（更改） V oldVal = null; // 给f=table[i]加锁，防止在table[i]的链表或者红黑树进行插入时被其他线程更改 synchronized (f) { // tabAt(tab, i) == f属于再次确保table[i]在加锁过程中没有被修改 if (tabAt(tab, i) == f) { // 链表上的节点的hash都是>=0的，如果fh<0则不能插入到链表中 if (fh >= 0) { // binCount用于记录链表的节点数 binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; // 如果table[i]中已经存在相同的key，那么根据onlyIfAbsent决定是否覆盖value if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } // 不存在相同的key则插入新节点到链表的尾部，与JDK7不同，JDK7是头插法 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) { // 如果f是一个TreeBin（红黑树，HashMap的红黑树为TreeNode，两者本质是一样的，只是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) { // binCount达到阈值，则将链表转化为红黑树 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) // 如果key相同，那么put将key对应的原来的值返回,否则返回null return oldVal; break; } } } // 检查是否有resize（扩容）在进行，如果有则辅助扩容。（比较难以理解，如果你有好的理解，记得告诉我哦:)） addCount(1L, binCount); return null; }从上面对put主流程的分析可知，ConcurrentHashMap是通过加锁进行线程隔离的，通过CAS对数据进行相关操作可以保证线程安全。
-
源代码的注释纯属我个人理解，如果有错误还请指正哦
-
tabAt()方法为什么没有分析呢，这里将Node转为了树或链表的结点
-
@almoon tabAt返回的就是一个Node对象，Treebin和TreeNode都是Node的子类。
-
@fantasticpsq 那是根据什么情况返回哪个结点呢
