ConcurrentHashMap#Put

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());        int binCount = 0;        for (Node<K,V>[] tab = table;;) {            Node<K,V> f; int n, i, fh;            if (tab == null || (n = tab.length) == 0)            //分支1:整个数组初始化                tab = initTable();            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {            //分支2:第[i]个元素初始化                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)            //分支3:扩容                tab = helpTransfer(tab, f);            else {            //分支4:放入元素                V oldVal = null;                synchronized (f) {                    if (tabAt(tab, i) == f) {                        if (fh >= 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)))) {                                    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) {                //如果是链表，binCount会一直累加                    if (binCount >= TREEIFY_THRESHOLD)                        treeifyBin(tab, i);// 超过阀值，转为红黑树                    if (oldVal != null)                        return oldVal;                    break;                }            }        }        //总元素个数累加        addCount(1L, binCount);        return null;    }

过程如下：

1，tab未初始化则初始化table2，两次hash，减少hash冲突，并计算下标3，数组该位置为空，无碰撞，通过CAS插入4，有碰撞　　4.1、如果正在扩容，协助其它线程去扩容　　4.2、如果是链表，插入链表　　4.3、如果是红黑树，插入红黑树　　4.4、如果链表长度超过8，转为红黑树　　4.5，如果key已经存在，覆盖旧值5，总元素个数累加，需要扩容，则扩容

其余分支我们后面可以细讲，现在简略讲下分支2，它使用cas无锁模式将元素添加到空桶，代码如下：

else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {

找该 hash 值对应的数组下标，得到第一个节点 f，使用tabAt方法：

@SuppressWarnings("unchecked")    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);    }

其中U.getObjectVolatile获取obj对象中offset偏移地址对应的object型field的值,支持volatile load语义。

volatile访问方法可用于访问表元素以及扩容中的next表的元素。 tab的使用必须由调用方进行非空检查。 所有调用者还预先检查tab的长度是否不为零（或其他等效检查），从而确保任何（length-1） & hash参数都是有效索引。 请注意，要纠正用户的并发错误，这些检查必须对局部变量进行操作。

如果数组该位置为空，用一次 CAS 操作将这个新值放入其中，跳出循环，如果 CAS 失败，那就是有并发操作，进到下一次循环，用了casTabAt方法：

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,                                        Node<K,V> c, Node<K,V> v) {        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);    }

compareAndSwapObject：

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);

compareAndSwapObject方法中的第一个参数和第二个参数，用于确定待操作对象在内存中的具体位置的，然后取出值和第三个参数进行比较，如果相等，则将内存中的值更新为第四个参数的值，同时返回true，表明原子更新操作完毕。反之则不更新内存中的值，同时返回false，表明原子操作失败。

这里涉及的Java Cas的特性，请看下图：

CAS，Compare and Swap 即比较并交换，设计并发算法时常用到的一种技术，java.util.concurrent 包建立在 CAS 之上。

当前的处理器基本都支持 CAS，但不同的厂家的实现不一样。

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。 如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值 。否则，处理器不做任何操作。无论哪种情况，它都会在 CAS 指令之前返回该 位置的值。

利用CPU的CAS指令，同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。而整个J.U.C都是建立在CAS之上的，因此对于synchronized阻塞算法，J.U.C在性能上有了很大的提升。

再看第四分支synchronized部分的锁代码。

其他更新操作（insert，delete和replace）需要锁。我们不想浪费空间，将不同锁对象与每个bin关联, 所以应该使用bin列表的第一个节点本身作为锁。对这些锁的锁定支持依赖于内置的“同步”监视器。

但是，将列表的第一个节点用作锁本身是不够的:当一个节点被锁定时，任何更新必须首先验证它仍然是锁定后的第一个节点，如果不是，则重试。因为新节点总是被附加到列表中，所以一旦一个节点在一个bin中是第一个节点，它就一直是第一个节点，直到删除或bin失效(通过扩缩容)。

每个bin锁的主要缺点是，受相同锁保护的bin列表中其他节点上的其他更新操作可能会暂停，例如，用户 equals（）或映射方法需要很长时间。 但是，从统计学上讲，在随机哈希码下，这不是一个普遍的问题。 理想情况下，bin中节点的频率遵循泊松分布。

如果 hash 计算的结果离散好的话，因为各个值都均匀分布，很少出现链表很长的情况，红黑树这种形式也很少会被用到的。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，概率仅为 0.00000006，小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。

* Ideally, the frequency of nodes in bins follows a Poisson distribution* (http://en.wikipedia.org/wiki/Poisson_distribution) with a* parameter of about 0.5 on average, given the resizing threshold* of 0.75, although with a large variance because of resizing* granularity. Ignoring variance, the expected occurrences of* list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The* first values are:     *     * 0:    0.60653066     * 1:    0.30326533     * 2:    0.07581633     * 3:    0.01263606     * 4:    0.00157952     * 5:    0.00015795     * 6:    0.00001316     * 7:    0.00000094     * 8:    0.00000006     * more: less than 1 in ten million

java达人

ID：drjava