Java并发编程系列-(5) Java并发容器 (10)

2.5 扩容操作

线程执行put操作，发现容量已经达到扩容阈值，需要进行扩容操作。ConcurrentHashMap支持并发扩容，实现方式是，将表拆分，让每个线程处理自己的区间。如下图：

迁移完毕的hash桶,会被设置成ForwardingNode节点，以此告知访问此桶的其他线程，此节点已经迁移完毕。此时线程2访问到了ForwardingNode节点，如果线程2执行的put或remove等写操作，那么就会先帮其扩容。如果线程2执行的是get等读方法，则会调用ForwardingNode的find方法，去nextTable里面查找相关元素。

2.6 Size

Put操作时，addCount 方法用于 CAS 更新 baseCount，但很有可能在高并发的情况下，更新失败，那么这些节点虽然已经被添加到哈希表中了，但是数量却没有被统计。

当更新 baseCount 失败的时候，会调用 fullAddCount 将这些失败的结点包装成一个 CounterCell 对象，保存在 CounterCell 数组中。

整张表实际的 size 其实是 baseCount 加上 CounterCell 数组中元素的个数。

public int size() { long n = sumCount(); return ((n < 0L) ? 0 :(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :(int)n); }

具体的计算count方法，

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; }

和JDK1.7一样，这样得到的size也只是大概数字，也具有弱一致性。

5.3 ConcurrentSkipListMap

ConcurrentSkipListMap是一个并发安全, 基于skiplist实现有序存储的Map。可以看成是TreeMap的并发版本。

ConcurrentHashMap采用空间换取时间, 但它有着ConcurrentHashMap不能比拟的优点: 有序数据存储.

SkipList的结构如下图所示：

从图中可以得出ConcurrentSkipListMap的几个特点:

ConcurrentSkipListMap 的节点主要由 Node, Index, HeadIndex 构成;

ConcurrentSkipListMap 的数据结构横向纵向都是链表

最下面那层链表是Node层(数据节点层), 上面几层都是Index层(索引)

从纵向链表来看, 最左边的是 HeadIndex 层, 右边的都是Index 层, 且每层的最底端都是对应Node, 纵向上的索引都是指向最底端的Node。

5.4 ConcurrentSkipListSet

ConcurrentSkipListSet基于ConcurrentSkipListMap实现，类似于TreeSet基于TreeMap实现。

5.5 ConcurrentLinkedQueue

ConcurrentLinkedQueue实现了一个高并发的队列，底层使用链表作为其数据结构。从性能角度看，可以算是高并发环境下性能最好的队列了。

ConcurrentLinkedQueue类中，核心节点Node的定义如下，item表示目标元素，next表示当前Node的下一个元素。

private static class Node<E> { volatile E item; volatile Node<E> next;

add,offer将元素插入到尾部，其中add实现上直接调用了offer。peek方法拿头部的数据，但是不移除和poll拿头部的数据，但是同时移除。

5.6 CopyOnWriteArrayList

CopyOnWrite（写时复制）的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再用新的容器替换旧的容器。

好处是我们可以对容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以写时复制容器也是一种读写分离的思想，读和写不同的容器。如果读的时候有多个线程正在向容器添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的，只能保证最终一致性。

下面介绍一下写的过程，

/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */ public boolean add(E e) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len + 1); newElements[len] = e; setArray(newElements); return true; } finally { lock.unlock(); } }