Java并发包学习

1. ConcurrentHashMap
顾名思义，ConcurrentHashMap是应用于高并发场景的HashMap.
由于HashMap是非线程安全的，而HashTable在HashMap的基础上使用了Synchronized, 以此来保证线程安全。但问题在于，HashTable的Synchronized是针对整个Hash表的，即每次锁定整张表让该线程独占，这样虽然保证了线程安全，确造成了巨大的浪费。
综上，ConcurrentHashMap出现了。

ConcurrentHashMap与HashTable的主要区别在于：锁的粒度。

ConcurrentHashMap允许多个线程同时对Hash表做修改操作，这是因为ConcurrentHashMap使用了“锁分离”。即ConcurrentHashMap默认将整个Hash表分为16个“段”(segment),每个segment其实就是一个小的HashTable, 他们有自己的锁。所以只要不同线程的修改操作在不同的segment上，他们就可以并发地执行了。

ConcurrentHashMap的有些方法也需要跨段，如size(), containsValue(),他们可能需要锁定整个表而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里“按顺序”的目的是为了避免出现死锁。

在ConcurrentHashMap的内部，Segment数组是final的，并且其成员变量也是final的，但Segment数组的成员并不一定是final的。这可以保证不会出现死锁，因为获得每个Segment的锁时的顺序是固定的，不变性是多线程编程中很重要的。

ConcurrentHashMap对于读操作并不加锁，所以多个线程的读操作完全可以并发地进行。

对于增加元素时导致的Hash冲突，ConcurrentHashMap与HashMap使用了相同的解决办法，都是将hash值相同的节点放在一个链表中，但与HashMap不同的是，ConcurrentHashMap使用了多个Hash表，也就是段(Segment)。

ConcurrentHashMap的迭代器与传统的不同：当iterator被创建后，如果集合再发生改变，ConcurrentHashMap的迭代器不会抛出ConcurrentModificationException,而是iterator仍然使用原来老的数据，而写线程也可以并发地完成，在iterator遍历完成后，在将头指针替换为新的数据。

ConcurrentHashMap的主要实体类有3个：ConcurrentHashMap(整个Hash表)，Segment(段)，HashEntry(节点)
ConcurrentHashMap的重要方法：
1）get(Object key):与HashTable的不同是将粒度细化到了Segment上：
首先判断当前Segment的元素个数是否为0，这是为了避免不必要的搜索。
然后，得到头结点，根据hash和key逐个判断是否是指定的值，如果是并且非空就找到了，直接返回。

代码如下：
V get(Object key) {
            int hash = hash(key.hashCode());
            if (count != 0) { // read-volatile
                HashEntry e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key)) {
                        V v = e.value;
                        if (v != null)
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
        }

V readValueUnderLock(HashEntry e) {
            lock();
            try {
                return e.value;
            } finally {
                unlock();
            }
        }

注意加粗部分关键代码：
由于ConcurrentHashMap不允许空的key或者空的value, 为什么v的值可能为null呢？这说明有其他的线程正在改变v的值，而get方法并未加锁，所以在这时，读的时候先加锁，再读，在释放锁。

所以说，ConcurrentHashMap的读（get）操作并不是完全不加锁的，在特定的情况(v为null时)也会加锁。

2）put(K key, V value):
put操作一上来就锁定整个Segment, 这当然是为了线程安全，因为修改数据是不能并发的。

3) remove方法与put类似。

2. CopyOnWriteArrayList
CopyOnWriteArrayList是一个线程安全的，并且在读操作时无所的ArrayList.

CopyOnWriteArrayList的核心思想是，利用高并发时，往往是读多写少的特性，对读操作不加锁，对写操作，先复制一份新的集合，在新的集合上面进行修改，然后将新的集合赋值给旧的引用，并通过volatile保证其可见性，在写操作时是加锁的。

1）add(E):
add方法并没有使用Synchronized, 它通过使用ReentrantLock来保证线程安全。
与ArrayList不同的是，它每次会创建一个新的Object数组，此数组的大小是当前数组大小加1，然后将之前数组中的内容复制到新的数组中，并将新增加的对象放入输入末尾，最后做引用切换，将新创建的数组对象赋值给全局的数组对象。

2) remove(E):
与add方法一样，也是通过ReentrantLock来保证其线程安全

3) get(int):
直接获取当前数组对应位置的元素，但此方法没有加锁，所以可能会读到脏数据。但相对而言，性能会非常高，对于读多写少且脏数据影响不大的场景而言，CopyOnWriteArrayList是不错的选择。

3. CopyOnWriteArraySet
CopyOnWriteArraySet是基于CopyOnWriteArrayList的实现，唯一不同在于add时，CopyOnWriteArraySet调用的是CopyOnWriteArrayList的addIfAbsent方法。addIfAbsent方法同样采用了锁保护，并创建一个新的大小+1的Object数组，如Object数组已有了当前元素，则直接返回，如没有则把新元素放到Object数组的尾部，并返回。

综上，CopyOnWriteArraySet在每次add时都要遍历数组，性能会略低于CopyOnWriteArrayList.

4.ArrayBlockingQueue
ArrayBlockingQueue是一个基于数组的，先进先出，线程安全的Queue，其特点是可以实现指定时间的阻塞读写，且其容量是可以限制的。

5. ConcurrentSkipListMap
1) ConcurrentHashMap与ConcurrentSkipListMap的性能测试
在4个线程，1.6万数据的条件下，ConcurrentHashMap的存取速度比ConcurrentSkipListMap快4倍左右。
那么ConcurrentSkipListMap的好处在哪呢？
    -- ConcurrentSkipListMap的key是有序的
    -- ConcurrentSlipListMap支持更高的并发。ConcurrentSkipListMap的存取时间是logN, 和线程数几乎无关。也就是说，在数据量一定的情况下，并发的线程数越多，ConcurrentSkipListMap越能体现出优势。
2）使用建议
在非多线程的情况下，应当尽量使用TreeMap。
此外，对于并发性相对较低的并发程序，可以使用Collections.synchronizedSortedMap将TreeMap进行包装，也可以提供更好的效率。
对于高并发的程序，应当使用ConcurrentSkipListMap。
3）什么是SkipList
Skip List（跳表）是一种可以代替平衡树的数据结构，默认是按照key值升序的。
Skip List让已排序的数据分布在多层链表中，以0--1随机数决定一个数据是否向上攀升，是通过“空间来换时间”的算法。
在每个节点中增加了向前的指针，在插入、删除、查找时，可以忽略一些不可能涉及到的节点，从而提高了效率。
SkipList比自平衡树简单，因为Skip List只需要从概率上保持数据结构平衡，而自平衡树需要严格保持数据结构平衡。
虽然SkipList和红黑树都有相同的时间复杂度LogN, 但Skip List的N会相对小很多，所以更快。Skip List在空间上也比红黑树节省，一个节点平均只需要1.333个指针。

4）Skip List的性质
    -- 由许多层结构组成，level是通过一定的概率随机计算出来的
    -- 每一层都是一个有序的链表，默认是升序，也可以根据创建映射时所提供的Comparator进行排序。
    -- 最底层（level 1)的链表包含了所有的元素
    -- 如果一个元素出现在Level i的链表中，那么它在level i之下的链表也会出现。
    -- 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

5）什么是ConcurrentSkipListMap
ConcurrentSkipListMap提供了一种线程安全的并发访问的排序映射表。
内部是SkipList（跳表）结构实现，在理论上能够在O(logN)时间内完成查找、插入、删除操作。
注：在调用ConcurrentSkipListMap的size方法时，由于多个线程可以同时对映射表进行操作，所以映射表需要遍历整个链表才能返回元素个数，这个操作是O(logN)

6) ConcurrentSkipListMap的存储结构



ConcurrentSkipListMap用到了Node和Index两种节点的存储方式，通过volatile关键字实现了并发的操作。

7）ConcurrentSkipListMap的查找



红色虚线，表示查找的路径；蓝色向右的箭头表示right引用；黑色向下箭头表示down引用。