简介

是一种保证线程安全的map。HashMap是非线程安全的,而HashTable和ConcurrentHashmap都是线程安全的。而且ConcurrentMap比HashTable性能好得多。

对比HashMap：

HashMap的key和value均可以为null，而HashTable和Concur rentHashMap的key和value均不可以为null

对比HashTable：保证线程安全的方式不同

HashTable是通过给整张散列表加锁的方式来保证线程安全,这种方式保证了线程安全，但是并发执行效率低下。
JDK1.8开始, ConcurrentHashMap数据结构与1.8中的HashMap保持一致,均为数组+链表+红黑树，是通过乐观锁+Synchronized来保证线程安全的。

源码

核心成员变量包括：

// Node数组，存放map元素
transient volatile Node<K,V>[] table;

Node - ConcurrentHashMap的内部数据结构

继承自HashMap的Entry，核心成员变量：

final K key;
volatile V val;
volatile Node<K,V> next;

根据next可以看出来，是一个链表，且用lvolatile修饰value和next，是放置扩容时发生变化，使用volatile保持可见性和避免重排序

setValue

public final V setValue(V value) {
    throw new UnsupportedOperationException();
}

关键在于setValue，不允许修改值

TreeNode

当链表的节点数大于8时会转换成红黑树的结构，他就是通过TreeNode作为存储结构代替Node来转换成黑红树

核心成员变量：

TreeNode<K,V> parent;  // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;    // needed to unlink next upon deletion

可以看出来红黑树的数据结构是一个标准的二叉树

TreeBin

TreeBin是TreeNode的容器，提供红黑树转换和一些锁控制，核心成员变量包括：

static final int WRITER = 1; // 状态：持有写锁
static final int WAITER = 2; // 状态：等待写锁
static final int READER = 4; // 状态：持有读锁累计数量增加

ConcurrentHashMap操作

put操作的核心思想：

如果数组tab不存在，使用unsafe提供的同步能力初始化数组
如果对应哈希位没有元素，使用CAS操作插入
如果有哈希冲突，使用sychronized锁表

putVal

int hash = spread(key.hashCode()); //两次hash，减少hash冲突，可以均匀分布

首先两次hash，减少哈希冲突，然后遍历table数组

Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
    tab = initTable();

这里做了一个懒汉模式的初始化

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

第一个场景：判定数组当前哈希位置上没有Node，直接通过CAS做Node插入

else if ((fh = f.hash) == MOVED)
    tab = helpTransfer(tab, f);

第二个场景：如果map正在扩容，需要帮助扩容

else {
    V oldVal = null;
    synchronized (f) {

最终场景：存在hash冲突，这是就要用synchronized加锁了，下面的流程和map相似，即判定该位置的是链表还是红黑树，分别走不同的插入流程

addCount(1L, binCount);

插入完后有一个数量增加的方法，判定是否需要扩容

可以看出来，使用ConcurrentHaspMap的put方法锁是比较重的直接就sychronized排他了，这时候其他线程也没法get

get

也是两次哈希，然后判断条件包括：

table不为空
table对应哈希位置的链表不为空
头节点不为空

符合判断条件，找到对应位置的val值

else if (eh < 0)
    return (p = e.find(h, key)) != null ? p.val : null;

这个场景表明table[i]为一棵树或正在迁移，通过find方法寻找对应值，这里的负值是在fullAddCount方法里面更新的，这里包含两个场景：

eh=-1，说明正在扩容，该节点是ForwardingNode（树头节点），调用的是ForwardingNode的find方法，去nextTable找
eh=-2，说明是一个TreeBin，调用TreeBin的find方法，而红黑树有可能存在变色旋转，因此树的find方法里面是有读写锁的

可以看出来但是get方法正常情况下是全程无锁的，因此ConcurrentHashMap的效率高，而其不需要加锁的原因是：

get访问的变量是volatile关键字修饰的，如Node.val、Node.next、count，volatile关键字保证了其值修改对其他线程可见
引用类型的table数组也有volatile修饰，保证了数组扩容时引用改变对其他线程可见
当节点是红黑树的时候，如果树正在变色旋转并且要查询的值不是树头节点，会加一个读写锁

目录CONTENT

ConcurrentHashMap

简介

源码