网站做什么内容,河北seo网络优化培训,济南建设高端网站,延安做网站今天我们来讨论一下一个比较经典的面试题就是 ConcurrentHashMap 为什么放弃使用了分段锁#xff0c;这个面试题阿粉相信很多人肯定觉得有点头疼#xff0c;因为很少有人在开发中去研究这块的内容#xff0c;今天阿粉就来给大家讲一下这个 ConcurrentHashMap 为什么在 JDK8 … 今天我们来讨论一下一个比较经典的面试题就是 ConcurrentHashMap 为什么放弃使用了分段锁这个面试题阿粉相信很多人肯定觉得有点头疼因为很少有人在开发中去研究这块的内容今天阿粉就来给大家讲一下这个 ConcurrentHashMap 为什么在 JDK8 中放弃了使用分段锁。什么是分段锁我们都知道 HashMap 是一个线程不安全的类多线程环境下使用 HashMap 进行put操作会引起死循环导致CPU利用率接近100%所以如果你的并发量很高的话所以是不推荐使用 HashMap 的。而我们所知的HashTable 是线程安全的但是因为 HashTable 内部使用的 synchronized 来保证线程的安全所以在多线程情况下HashTable 虽然线程安全但是他的效率也同样的比较低下。所以就出现了一个效率相对来说比 HashTable 高但是还比 HashMap 安全的类那就是 ConcurrentHashMap而 ConcurrentHashMap 在 JDK8 中却放弃了使用分段锁为什么呢那他之后是使用什么来保证线程安全呢我们今天来看看。什么是分段锁其实这个分段锁很容易理解既然其他的锁都是锁全部那分段锁是不是和其他的不太一样是的他就相当于把一个方法切割成了很多块在单独的一块上锁的时候其他的部分是不会上锁的也就是说这一段被锁住并不影响其他模块的运行分段锁如果这样理解是不是就好理解了我们先来看看 JDK7 中的 ConcurrentHashMap 的分段锁的实现。在 JDK7 中 ConcurrentHashMap 底层数据结构是数组加链表这也是之前阿粉说过的 JDK7和 JDK8 中 HashMap 不同的地方源码送上。//初始总容量默认16
static final int DEFAULT_INITIAL_CAPACITY 16;
//加载因子默认0.75
static final float DEFAULT_LOAD_FACTOR 0.75f;
//并发级别默认16
static final int DEFAULT_CONCURRENCY_LEVEL 16;static final class SegmentK,V extends ReentrantLock implements Serializable {transient volatile HashEntryK,V[] table;}在阿粉贴上的上面的源码中有SegmentK,V,这个类才是真正的的主要内容 ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成.我们看到了 SegmentK,V,而他的内部又有HashEntry数组结构组成. Segment 继承自 RentrantLock 在这里充当的是一个锁而在其内部的 HashEntry 则是用来存储键值对数据.图就像下面这个样子也就是说一个Segment里包含一个HashEntry数组每个HashEntry是一个链表结构的元素当需要put元素的时候并不是对整个hashmap进行加锁而是先通过hashcode来知道他要放在哪一个分段中然后对这个分段进行加锁。最后也就出现了如果不是在同一个分段中的 put 数据那么 ConcurrentHashMap 就能够保证并行的 put 也就是说在并发过程中他就是一个线程安全的 Map 。为什么 JDK8 舍弃掉了分段锁呢这时候就有很多人关心了说既然这么好用为啥在 JDK8 中要放弃使用分段锁呢这就要我们来分析一下为什么要用 ConcurrentHashMap 1.线程安全。2.相对高效。因为在 JDK7 中 Segment 继承了重入锁ReentrantLock,但是大家有没有想过如果说每个 Segment 在增长的时候,那你有没有考虑过这时候锁的粒度也会在不断的增长。而且前面阿粉也说了一个Segment里包含一个HashEntry数组每个锁控制的是一段那么如果分成很多个段的时候这时候加锁的分段还是不连续的是不是就会造成内存空间的浪费。所以问题一出现了分段锁在某些特定的情况下是会对内存造成影响的什么情况呢我们倒着推回去就知道1.每个锁控制的是一段当分段很多并且加锁的分段不连续的时候内存空间的浪费比较严重。大家都知道并发是什么样子的就相当于百米赛跑你是第一我是第二这种形式同样的线程也是这样的在并发操作中因为分段锁的存在线程操作的时候争抢同一个分段锁的几率会小很多既然小了那么应该是优点了但是大家有没有想过如果这一分块的分段很大的时候那么操作的时间是不是就会变的更长了。所以第二个问题出现了2.如果某个分段特别的大那么就会影响效率耽误时间。所以这也是为什么在 JDK8 不在继续使用分段锁的原因。既然我们说到这里了我们就来聊一下这个时间和空间的概念毕竟很多面试官总是喜欢问时间复杂度这些看起来有点深奥的东西但是如果你自己想想用自己的话说出来是不是就没有那么难理解了。什么是时间复杂度百度百科是这么说的在计算机科学中时间复杂性又称时间复杂度算法的时间复杂度是一个函数它定性描述该算法的运行时间,
这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数其实面试官问这个 时间复杂度 无可厚非因为如果你作为一个公司的领导如果手底下的两个员工交付同样的功能提测A交付的代码运行时间50s内存占用12MB交付的代码运行时间110s内存占用50M 的时候你会选择哪个员工提交的代码A 还是 B 这个答案一目了然当然我们得先把 Bug 这种因素排除掉没有任何质疑肯定选 A 员工提交的代码因为运行时间快内存占用量小那肯定的优先考虑。那么既然我们知道这个代码都和时间复杂度有关系了那么面试官再问这样的问题你还觉得有问题么答案也很肯定没问题你计算不太熟但是也需要了解。我们要想知道这个时间复杂度那么就把我们的程序拉出来运行一下看看是什么样子的我们先从循环入手for(i1; in; i)
{j i;j;
}它的时间复杂度是什么呢上面百度百科说用大O符号表述那么实际上它的时间复杂度就是 O(n),这个公式是什么意思呢线性阶 O(n)也就是说我们上面写的这个最简单的算法的时间趋势是和 n 挂钩的如果 n 变得越来越大那么相对来说你的时间花费的时间也就越来越久也就是说我们代码中的 n 是多大我们的代码就要循环多少遍。这样说是不是就很简单了关于时间复杂度阿粉以后会给大家说话题跑远了我们回来继续说JDK8 的 ConcurrentHashMap 既然不使用分段锁了那么他使用的是什么呢JDK8 的 ConcurrentHashMap 使用的是什么从上面的分析中我们得出了 JDK7 中的 ConcurrentHashMap 使用的是 Segment 和 HashEntry而在 JDK8 中 ConcurrentHashMap 就变了阿粉现在这里给大家把这个抛出来我们再分析 JDK8 中的 ConcurrentHashMap 使用的是 synchronized 和 CAS 和 HashEntry 和红黑树。听到这里的时候我们是不是就感觉有点类似HashMap 是不是也是使用的红黑树来着有这个感觉就对了ConcurrentHashMap 和 HashMap 一样使用了红黑树而在 ConcurrentHashMap 中则是取消了Segment分段锁的数据结构取而代之的是Node数组链表红黑树的结构。为什么要这么做呢因为这样就实现了对每一行数据进行加锁减少并发冲突。实际上我们也可以这么理解就是在 JDK7 中使用的是分段锁在 JDK8 中使用的是 “读写锁” 毕竟采用了 CAS 和 Synchronized 来保证线程的安全。我们来看看源码//第一次put 初始化 Node 数组
private final NodeK,V[] initTable() {NodeK,V[] tab; int sc;while ((tab table) null || tab.length 0) {if ((sc sizeCtl) 0)Thread.yield(); // lost initialization race; just spinelse if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {try {if ((tab table) null || tab.length 0) {int n (sc 0) ? sc : DEFAULT_CAPACITY;SuppressWarnings(unchecked)NodeK,V[] nt (NodeK,V[])new Node?,?[n];table tab nt;sc n - (n 2);}} finally {sizeCtl sc;}break;}}return tab;}public V put(K key, V value) {return putVal(key, value, false);}/** Implementation for put and putIfAbsent */final V putVal(K key, V value, boolean onlyIfAbsent) {if (key null || value null) throw new NullPointerException();int hash spread(key.hashCode());int binCount 0;for (NodeK,V[] tab table;;) {NodeK,V f; int n, i, fh;if (tab null || (n tab.length) 0)tab initTable();//如果相应位置的Node还未初始化则通过CAS插入相应的数据else if ((f tabAt(tab, i (n - 1) hash)) null) {if (casTabAt(tab, i, null,new NodeK,V(hash, key, value, null)))break; // no lock when adding to empty bin}else if ((fh f.hash) MOVED)tab helpTransfer(tab, f);...//如果该节点是TreeBin类型的节点说明是红黑树结构则通过putTreeVal方法往红黑树中插入节点else if (f instanceof TreeBin) {NodeK,V p;binCount 2;if ((p ((TreeBinK,V)f).putTreeVal(hash, key,value)) ! null) {oldVal p.val;if (!onlyIfAbsent)p.val value;}//如果binCount不为0说明put操作对数据产生了影响如果当前链表的个数达到8个则通过treeifyBin方法转化为红黑树如果oldVal不为空说明是一次更新操作,返回旧值if (binCount ! 0) {if (binCount TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal ! null)return oldVal;break;}}addCount(1L, binCount);return null;}put 的方法有点太长了阿粉就截取了部分代码大家莫怪如果大家有兴趣大家可以去对比一下去 JDK7 和 JDK8 中寻找不同的东西这样亲自动手才能收获到更多不是么文章参考《百度百科-时间复杂度》
