​ 在Jdk的实现中，对于HashMap的实现是线程非安全的，在大量并发读的情况下，HashMap能够保持线程安全，但是在存在大量写的情况下，HashMap将会出现并发错误，所以JDK实现了ConcurrentHashMap来保证线程安全并且高效的HashMap。
JDK还实现了ConcurrentLinkedQueue来实现在并发中的非阻塞的队列和BlockingQueue的阻塞线程的队列。

HashMap的实现

​ 在ConcurrentHashMap讲述之前，先对HashMap的底层实现做一下总结。
HashMap：散列表。在Java中HashMap通过分离链接法来进行实现，也就是通过数组+链表的方法来进行实现。在JDK1.8后，如果有一个散列表某个散列值对应的链表的元素超过一定值，这个对应的链表将会转化为红黑树的实现，这个值默认为8。也就是说，实际上HashMap的实现为数组+链表+红黑树的实现。
在HashMap的实现中，如果HashMap的数组容量不足，也就是散列后超出现有容量大小，将会对数组大小进行扩增，将新的数组大小扩展成为当前状态的两倍，然后将数据重新散列到新的数组上，所以扩容阶段将会消耗很多资源，并且在并发过程中，出现问题的地方就在扩容阶段。

HashMap的get
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

​ HashMap将会对关键词key进行hash，然后在数组中进行查找到这个值，然后对整个整个链表进行查找查看是否有这个key对应的value。

HashMap的put
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

​ 首先先判断是否需要扩容，然后根据key的散列查找到数组索引，然后新建节点进行插入，插入过程中分别按照红黑树或者链表的方法进行插入。

ConcurrentHashMap的实现

​ 在并发环境下如果同时对HashMap进行写操作，那么HashMap将会导致内部的Entry数据会链表形成环状数据结构，然后Entry的next节点将永远不为空，也就是会产生死循环获取Entry。而如果对写过程进行加锁，那么错误将不会发生，但是会导致在线程竞争激烈的情况下会出现大量线程阻塞的状态，进而导致效率低下。
针对这个问题，ConcurrentHashMap提供了锁分段技术来提高并发访问率。
分段锁也就是对当前线程访问的数组部分进行加锁，而不是对整个数组进行加锁，通过这种方法，实现写入的时候只有部分加锁，而其他部分将允许线程正常访问。

ConcurrentLinkedQueue的实现

​ 在普通的队列实现中，在并发环境下，那么两个线程对同一个队列进行push的时候，尾节点指向两个不同的新加入节点，那么将会有一个节点被销毁；如果是两个线程同时对一个元素进行pop操作，也会出现错误。在JDK里面，实现了非阻塞的队列和阻塞队列，非阻塞队列被实心为ConcurrentQueue，阻塞队列实现为BlockingQueue。
在ConcurrentQueue中，采用CAS算法来对队列中的元素进行写操作。并且在队列内部维护两个节点：head节点和tail节点，head节点指向队列的尾节点。

入队列和出队列

不同于一般的队列，ConcurrentQueue在入队列和出队列中采用了不一样的方法。
在入队列调整tail节点的时候，会首先判断tail节点当前的指向，如果添加的节点为第一个元素，那么head和tail节点中的next都会指向这个节点，在添加非首节点的时候，判断tail的节点中的next节点，如果为空，会将tail节点的next节点设置为添加节点，如果不为空，将tail节点指向添加节点。
在出队列的时候，先检查当前的head节点，如果当前head节点指向的节点元素为空，那么表示已经有其他线程将头节点取走，继续判断下一个头节点，直到能够取出当前节点的元素。

BlockingQueue阻塞队列

​ 在阻塞队列中对队列的插入和移除操作进行了扩展：

支持阻塞的插入方法：当队列满的时候，队列阻塞插入元素的线程，直到队列不满。
支持阻塞的移除方法：当队列为空的时候，获取元素的线程会阻塞直到队列变为非空。

​ 在JDK7里面，一共提供了7个阻塞队列：

ArrayBlockingQueue：由数组结构组成的有界阻塞队列
LinkedBlockingQueue：由链表结构组成的有界阻塞队列
PriorityBlockingQueue：支持优先级排序的无界阻塞队列
DelayQueue：使用优先级队列实现的无界阻塞队列
SynchronousQueue：不储存元素的阻塞队列
LinkedTransferQueue：由链表结构组成的无界阻塞队列
LinkedBlockingDeque：由链表结构组成的双向阻塞队列

​ 在队列中元素为空的时候，如果有线程想要获取元素，那么将会进行等待，当有其他线程添加元素到队列中的时候，JDK采用了多种不同的模式提醒阻塞线程：Condition、LockSupport的park对线程进行唤醒操作。