ConcurrentHashMap底层实现是什么

ConcurrentHashMap整体结构

        ConcurrentHashMap是一个K-V的存储结构，在JDK1.8中，它的存储结构如下，是由数组、单向链表、红黑树组成。当我们初始化一个实例时，默认会初始化一个长度为16的数组。由于ConcurrentHashMap本质上还是一个hash表，所以key会存在hash冲突，它采用链式寻址法来解决hash冲突。当hash冲突比较多时，会使链表长度过长，因此查询的复杂度就增加。因此JDK1.8中引入了红黑树的算法，当数组长度大于64（源码中MIN_TREEIFY_CAPACITY参数），且链表长度大于等于8时（源码中是TREEIFY_THRESHOLD参数），链表会转化为红黑树。另外随着ConcurrentHashMap的自动扩容，一旦链表长度小于6 时（源码中是：UNTREEIFY_THRESHOLD参数），红黑树又会退化为单向链表。

ConcurrentHashMap的基本功能：

        ConcurrentHashMap本质是一个HashMap，因此功能与HashMap一样，但是ConcurrentHashMap在HashMap的基本上，提供了并发安全的功能。并发安全功能的实现主要是对指定node节点上加锁来保证数据的安全性的。

ConcurrentHashMap所做的优化

        如何在并发性能与安全性上做好平衡，很多地方都会存在类似的设计，比如CPU的三级缓存，mysql的buffer pool，Synchronized的锁升级等。

        在JDK1.8中，ConcurrentHashMap锁的粒度是node，而JDK1.7及以前是对Segment进行锁定，锁粒度大了，性能也会低很多。

        引入红黑树，在hash冲突较大时，会降低查询的时间复杂度，红黑树查询的时间复杂度为O（logn）.