ConcurrentHashMap提供了一个在并发下比较有用的方法putIfAbsent(K key，V value)，如果传入key对应的value已经存在，就返回存在的value，不进行替换。如果不存在，就添加key和value，返回null。在代码层面它的作用类似于：
synchronized(map) {if(!map.containsKey(key)) {return map.put(key,value);}else {return map.get(key);}}
JDK1.7
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁，即：ReentrantLock，在ConcurrentHashMap里扮演锁的角色； HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组。Segment的结构和HashMap类似，是一种数组和链表结构。一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得与它对应的Segment锁。
并发度(级别)
ConcurrentHashMap初始化方法是通过initialCapacity、loadFactor和concurrencyLevel(是用户估计的并发级别，就是说你觉得最多有多少线程共同修改这个map，根据这个来确定Segment数组的大小concurrencyLevel默认是DEFAULT_CONCURRENCY_LEVEL=16)等几个参数来初始化segment数组、段偏移量segmentShift、段掩码segmentMask和每个segment里的HashEntry数组来实现的。
并发级别可以理解为程序运行时能够同时更新ConcurrentHashMap且不产生锁竞争的最大线程数，实际上就是ConcurrentHashMap中的分段锁个数，即：Segment[]的数组长度。
ConcurrentHashMap默认的并发度为16，但用户也可以在构造函数中设置并发度。当用户设置并发度时，ConcurrentHashMap会使用大于等于该值的最小2次幂指数作为实际并发度，假如用户设置并发度为17，实际并发度则为32。
如果并发度设置的过小，会带来严重的锁竞争问题；如果并发度设置的过大，原本位于同一个Segment内的访问会扩散到不同的Segment中，CPU cache命中率会下降，从而引起程序性能下降。
segments数组的长度ssize是通过concurrencyLevel计算得出的。为了能通过按位与的散列算法来定位segments数组的索引，必须保证segments数组的长度是2的N次方，所以必须计算出一个大于或等于concurrencyLevel的最小的2的N次方值来作为segments数组的长度。假如concurrencyLevel等于14、15或16，ssize都会等于16，即容器里锁的个数也是16。
初始化segmentShift和segmentMask
这两个全局变量需要在定位segment时的散列算法里使用，sshift等于ssize从1向左移位的次数，在默认情况下concurrencyLevel等于16，1需要向左移位移动4次，所以sshift等于4。segmentShift用于定位参与散列运算的位数，segmentShift等于32减sshift，所以等于28，这里之所以用32是因为ConcurrentHashMap里的hash()方法输出的最大数是32位的。segmentMask是散列运算的掩码，等于ssize减1，即15，掩码的二进制各个位的值都是1。因为ssize的最大长度是65536，所以segmentShift最大值是16，segmentMask最大值是65535，对应的二进制是16位，每个位都是1。
输入参数initialCapacity是ConcurrentHashMap的初始化容量，loadfactor是每个segment的负载因子，在构造方法里需要通过这两个参数来初始化数组中的每个segment。
ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的以及volatile关键字。
get操作
get操作先经过一次再散列，然后使用这个散列值通过散列运算定位到Segment，再通过散列算法定位到table。整个get过程，没有加锁，而是通过volatile保证get总是可以拿到最新值。
put操作
ConcurrentHashMap初始化的时候会初始化第一槽segment[0]，对于其他槽，在插入第一个值的时候再进行初始化。
ensureSegment方法考虑了并发情况，多个线程同时进入初始化同一个槽segment[k]，但只要有一个成功了就可以了。
put方法会通过tryLock()方法尝试获得锁，获得了锁，node为null进入try语句块，没有获得锁，调用scanAndLockForPut方法自旋等待获得锁。
scanAndLockForPut方法里在尝试获得锁的过程中会对对应的hashcode的链表进行遍历，如果遍历完毕仍然找不到与key相同的HashEntry节点，则为后续的put操作提前创建一个HashEntry。当tryLock一定次数后仍无法获得锁，则通过lock申请锁。
在获得锁之后，Segment对链表进行遍历，如果某个HashEntry节点具有相同的key，则更新该HashEntry的value值，否则新建一个HashEntry节点，采用头插法，将它设置为链表的新head节点并将原头节点设为新head的下一个节点。新建过程中如果节点总数，含新建的HashEntry超过threshold，则调用rehash()方法对Segment进行扩容，最后将新建HashEntry写入到数组中。
rehash操作
扩容是新创建数组，然后进行迁移数据，最后再将newTable设置给属性table。
为了避免让所有的节点都进行复制操作：由于扩容是基于2的幂指来操作，假设扩容前某HashEntry对应到Segment中数组的index为i，数组的容量为capacity，那么扩容后该HashEntry对应到新数组中的index只可能为i或者i+capacity，因此很多HashEntry节点在扩容前后index可以保持不变。
如：原来table长度为4，那么元素在table中的分布是这样的：
扩容后table长度变为8，那么元素在table中的分布变成：
可以看见hash值为34和56的下标保持不变，而15,23,77的下标都是在原来下标的基础上+4即可，可以快速定位和减少重排次数，该方法没有考虑并发，因为执行该方法之前已经获得了锁。
remove操作
与put方法类似，都是在操作前需要拿到锁，以保证操作的线程安全性。
ConcurrentHashMap的弱一致性
对链表遍历判断是否存在key相同的节点以及获得该节点的value。但由于遍历过程中其他线程可能对链表结构做了调整，因此get和containsKey返回的可能是过时的数据，这一点是ConcurrentHashMap在弱一致性上的体现。如果要求强一致性，那么必须使用Collections.synchronizedMap()方法。
JDK1.8
在JDK1.7基础上的改进
改进一：取消segments字段，直接采用transient volatile Node
改进二：将原先table数组+单向链表的数据结构，变更为table数组+单向链表+红黑树的结构。对于hash表来说，最核心的能力在于将key hash之后能均匀的分布在数组中。如果hash之后散列的很均匀，那么table数组中的每个队列长度主要为0或者1。但实际情况并非总是如此理想，虽然ConcurrentHashMap类默认的加载因子为0.75，但是在数据量大或者运气不佳的情况下，还是会存在一些队列长度过长的情况，如果还是采用单向链表方式，那么查询某个节点的时间复杂度为O(n)；因此，对于个数超过8的链表，jdk1.8中采用了红黑树的结构，那么查询的时间复杂度可以降低到O(logN)，可以改进性能。
使用Node1.7为Entry作为链表的数据节点，仍然包含key，value，hash和next四个属性。红黑树的情况使用的是TreeNode extends Node。根据数组元素中，第一个节点数据类型是Node还是TreeNode可以判断该位置下是链表还是红黑树。
用于判断是否需要将链表转换为红黑树的阈值
static final int TREEIFY_THRESHOLD=8;
用于判断是否需要将红黑树转换为链表的阈值
static final int UNTREEIFY_THRESHOLD=6;
数据结构和属性
Node
Node是最核心的内部类，它包装了key-value键值对。
定义基本和1.7中的HashEntry相同。而这个map本身所持有的也是一个Node型的数组 transient volatile Node
增加了一个find方法来用以辅助map.get()方法。其实就是遍历链表，子类中会覆盖这个方法。
在map中还定义了Segment这个类，不过只是为了向前兼容而已。
TreeNode
树节点类，另外一个核心的数据结构。当链表长度过长的时候，会转换为TreeNode。
与1.8中HashMap不同点：
- 它并不是直接转换为红黑树，而是把这些节点放在TreeBin对象中，由TreeBin完成对红黑树的包装；
TreeNode在ConcurrentHashMap扩展自Node类，而并非HashMap中的扩展自LinkedHashMap.Entry
TreeBin
负责TreeNode节点。它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap数组中，存放的是TreeBin对象，而不是TreeNode对象，另外这个类还带有了读写锁机制。
ForwardingNode
一个特殊的Node节点，hash值为-1，其中存储nextTable的引用。有table发生扩容的时候，ForwardingNode发挥作用，作为一个占位符放在table中表示当前节点为null或者已经被移动。
sizeCtl
用来控制table的初始化和扩容操作。
负数代表正在进行初始化或扩容操作- -1 代表正在初始化；
- -N 表示有N-1个线程正在进行扩容操作；
- 0 为默认值，代表当时的table还没有被初始化；
正数表示初始化大小或Map中的元素达到这个数量时，需要进行扩容了。
核心方法
tabAt：利用硬件级别的原子操作，获得在i位置上的Node节点，Unsafe.getObjectVolatile()可以直接获取指定内存的数据，保证了每次拿到数据都是最新的。
casTabAt：利用CAS操作设置i位置上的node节点。
setTabAt：利用硬件级别的原子操作，设置在i位置上的node节点Unsafe.putObjectVolatile()可以直接设定指定内存的数据，保证了其他线程访问这个节点时一定可以看到最新的数据。
构造方法
可以发现，在new出一个map的实例时，并不会创建其中的数组等等相关的部件，只是进行简单的属性设置而已，同样的，table的大小也被规定为必须是2的乘方数，真正的初始化放在了是在向ConcurrentHashMap中插入元素的时候发生的。如调用put、computeIfAbsent、compute、merge等方法的时候，调用时机是检查table==null。
get方法
给定一个key来确定value的时候，必须满足两个条件key相同hash值相同，对于节点可能在链表或树上的情况，需要分别去查找。
put方法
总结来说，put方法就是，沿用HashMap的put方法的思想，根据hash值计算这个新插入的点在table中的位置i，如果i位置是空的，直接放进去，否则进行判断，如果i位置是树节点，按照树的方式插入新的节点，否则把i插入到链表的末尾。
整体流程上，就是首先定义不允许key或value为null的情况放入，对于每一个放入的值，首先利用spread方法对key的hashcode进行一次hash计算，由此来确定这个值在table中的位置。
如果这个位置是空的，那么直接放入，而且不需要加锁操作。
如果这个位置存在节点，说明发生了hash碰撞，首先判断这个节点的类型。如果是链表节点，则得到的节点就是hash值相同的节点组成的链表的头节点。需要依次向后遍历确定这个新加入的值所在位置。如果遇到hash值与key值都与新加入节点是一致的情况，则只需要更新value值即可。否则依次向后遍历，直到链表尾插入这个节点。如果加入这个节点以后链表长度大于8，就把这个链表转换成红黑树。如果这个节点的类型已经是树节点的话，直接调用树节点的插入方法进行插入新的值。
初始化
构造方法中并没有真正初始化，真正的初始化在放在了在向ConcurrentHashMap中插入元素的时候发生的。具体实现的方法就是initTable。
private final Node<K,V>[] initTable() {Node<K,V>[] tab; int sc;while ((tab = table) == null || tab.length == 0) {//小于0表示有其他线程正在进行初始化操作，把当前线程CPU时间让出来，//因为对于table的初始化操作，只能有一个线程在进行if ((sc = sizeCtl) < 0)Thread.yield(); // lost initialization race; just spin//利用CAS操作把sizectl的值设置为-1，表示本线程正在进行初始化else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {try {if ((tab = table) == null || tab.length == 0) {int n = (sc > 0) ? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];table = tab = nt;//n右移2位，就是n变为n原值的1/4，sc=0.75*nsc = n - (n >>> 2);}} finally {//设置扩容阈值sizeCtl = sc;}break;}}return tab;}
transfer
当ConcurrentHashMap容量不足的时候，需要对table进行扩容。这个方法的基本思想跟HashMap是很像的，但是由于它是支持并发扩容的，所以要复杂的多。大概原理是，因为在扩容的时候，总是会涉及到从一个数组到另一个数组拷贝的操作，如果这个操作能够并发进行，就能利用并发处理去减少扩容带来的时间影响。
整个扩容操作分为两个部分：
1.构建一个nextTable，它的容量是原来的2倍；
2.将原来table中的元素复制到nextTable中，这里允许多线程进行操作；
整个扩容流程就是遍历和复制：
为null或者已经处理过的节点，会被设置为forwardNode节点，当线程准备扩容时，发现节点是forwardNode节点，跳过这个节点，继续寻找未处理的节点，找到了，对节点上锁，如果这个位置是Node节点(fh>=0)，说明它是一个链表，就构造一个反序链表，把他们分别放在nextTable的i和i+n的位置上如果这个位置是TreeBin节点(fh<0)，也做一个反序处理，并且判断是否需要红黑树转链表，把处理的结果分别放在nextTable的i和i+n的位置上，遍历过所有的节点以后就完成了复制工作，这时让nextTable作为新的table，并且更新sizeCtl为新容量的0.75倍，完成扩容。
并发扩容其实就是将数据迁移任务拆分成多个小迁移任务，在实现上使用了一个变量stride作为步长控制，每个线程每次负责迁移其中的一部分。
remove
移除方法的基本流程和put方法很类似，只不过操作由插入数据变为移除数据而已，如果存在红黑树的情况下，会检查是否需要将红黑树转为链表的步骤。
treeifyBin
用于将过长的链表转换为TreeBin对象。但是他并不是直接转换，而是进行一次容量判断，如果容量没有达到转换的要求，直接进行扩容操作并返回。如果满足条件才将链表的结构转换为TreeBin，这与HashMap不同的是，它并没有把TreeNode直接放入红黑树，而是利用了TreeBin这个小容器来封装所有的TreeNode。
size
在jdk1.8版本中，对于size的计算，在扩容和addCount()方法就已经有处理了，可以注意一下put方法，里面就有addCount()方法，早就计算好的，然后size的时候直接给你。jdk1.7是在调用size()方法才去计算，其实在并发集合中去计算size是没有多大意义的，因为size是实时在变的。
在具体实现上，计算大小的核心方法都是sumCount()。
可以看见，统计数量时使用了baseCount和CounterCell类型的变量counterCells。其实baseCount就是记录容器数量的，而counterCells则是记录CAS更新baseCounter值时，由于高并发而导致失败的值。这两个变量的变化在addCount()方法中有体现，大致的流程就是：
1、对baseCount做CAS自增操作；
2、如果并发导致baseCountCAS失败了，则使用counterCells；
3、如果counterCells CAS失败了，在fullAddCount方法中，会继续死循环操作，直到成功。
问题一：JDK8中的ConcurrentHashMap为什么使用synchronized来进行加锁？
JDK8中使用synchronized加锁时，是对链表头结点和红黑树根结点来加锁的，而ConcurrentHashMap会保证，数组中某个位置的元素一定是链表的头结点或红黑树的根结点，所以JDK8中的ConcurrentHashMap在对某个桶进行并发安全控制时，只需要使用synchronized对当前那个位置的数组上的元素进行加锁即可，对于每个桶，只有获取到了第一个元素上的锁，才能操作这个桶，不管这个桶是一个链表还是红黑树。
相比于JDK7中使用ReentrantLock来加锁，因为JDK7中使用了分段锁，所以对于一个ConcurrentHashMap对象而言，分了几段就得有几个ReentrantLock对象，表示得有对应的几把锁。
而JDK8中使用synchronized关键字来加锁就会更节省内存，并且jdk也已经对synchronized的底层工作机制进行了优化，效率更好。
问题二：HashMap扩容流程是怎么样的？
- HashMap的扩容指的就是数组的扩容， 因为数组占用的是连续内存空间， 所以数组的扩容其实只能新开一个新的数组，然后把老数组上的元素转移到新数组上来，这样才是数组的扩容
2. 在HashMap中也是一样，先新建一个2倍数组大小的数组
3. 然后遍历老数组上的每一个位置，如果这个位置上是一个链表，就把这个链表上的元素转移到新数组上去
4. 在这个过程中就需要遍历链表，当然jdk7，和jdk8在这个实现时是有不一样的，jdk7就是简单的遍历链表上的每一个元素，然后按每个元素的hashcode结合新数组的长度重新计算得出一个下标，而重新得到的这个数组下标很可能和之前的数组下标是不一样的，这样子就达到了一种效果，就是扩容之后，某个链表会变短，这也就达到了扩容的目的，缩短链表长度，提高了查询效率
5. 而在jdk8中，因为涉及到红黑树，这个其实比较复杂，jdk8中其实还会用到 一个双向链表来维护红黑树中的元素，所以jdk8中在转移某个位置上的元素时，会去判断如果这个位置是一个红黑树，那么会遍历该位置的双向链表，遍历双向链表统计哪些元素在扩容完之后还是原位置，哪些元素在扩容之后在新位置，这样遍历完双向链表后，就会得到两个子链表，一个放在原下标位置， 一个放在新下标位置，如果原下标位置或新下标位置没有元素，则红黑树不用拆分，否则判断这两个子链表的长度，如果超过八，则转成红黑树放到对应的位置，否则把单向链表放到对应的位置。
6. 元素转移完了之后，再把新数组对象赋值给HashMap的table属性，老数组会被回收。问题三：解释下JAVA里面的直接内存
直接内存有一种叫法，堆外内存。
直接内存(堆外内存)指的是 Java 应用程序通过直接方式从操作系统中申请的内存。这个差别与之前的堆、栈、方法区，那些内存都是经过了虚拟化。所以严格来说，这里是指直接内存。
若有收获，就点个赞吧
0 人点赞
