ConcurrentHashMap

一：为什么要用ConcurrentHashMap?

在并发编程中使用HashMap可能会导致程序陷入死循环，而使用线程安全的HashTable效率又非常低，所以采用了ConcurrentHashMap。

二：put方法操作主要流程

1. ConcurrentHashMap 不允许key或value为NULL，会抛出异常
2. 写数据前，会先对key的hash值进行一次加工spread()
3. 整个写数据是一个 自旋(死循环) 的操作
   （1）判断tab是否初始化，如果table还没有被初始化，调用initTable()去尝试初始化table，然后继续自旋
   （2）当前table已经被初始化，调用寻址算法(hash & (table.length - 1))得到的桶位上的元素为NULL，尝试使用CAS操作将构造的节点写入桶位，成功退出循环，失败继续自旋
   （3）当前table已经被初始化了，但是当前桶位的节点是FWD节点，说明此时table正在发生扩容操作，此时当前线程就去参与扩容，扩容后继续自旋
   （4）说明当前桶位的形成了链表或者红黑树，发生了hash冲突，先使用synchronized加锁锁住当前桶位(锁对象就是当前桶位的头节点)，然后判断如果当前桶位形成了链表，就遍历链表中的节点查找是否存在和待插入的节点的key完全一致的节点，如果有的话就进行value替换，没有就将节点插入到链表末尾。 如果当前桶位已经形成了红黑树，就在树中查找是否存在和待插入的节点的key完全一致的节点，存在就将value替换，不存在就插入到树中
   （5）synchronized 代码块执行结束后，判断链表长度是否 >= 阈值 8，是则转为红黑树；如果待插入节点跟桶位上的某一个节点冲突后进行替换了(无论是链表还是红黑树)，直接将冲突节点的value返回 ，要么break 结束for循环
4. for 循环处理结束后，内部先对table中的节点进行计数，然后判断是否达到扩容标准

三：小结

1. ConcurrentHashMap 1.8 put 方法主要采用 CAS (hash未冲突使用) + synchronized （hash冲突使用），来解决并发时的线程安全问题
2. 链表转为红黑树，必要条件是数组长度不小于64，且链表长度不小于8

四：为什么ConcurrentHashMap不允许null值?

为了让ConcurrentHashMap的语义更加准确，是无法容忍模糊性的，map.get(key)返回null的时候，是没办法通过map.contains(key)检查来准确的检测，因为在检测过程中可能会被其他线程所修改，而导致检测结果并不可靠