免费APP 微信 网站平台,英文网站建设600,学做美食交流网站,外贸网站平台排行榜HashMap、CurrentHashMap 的实现原理基本都是BAT面试必考内容#xff0c;阿里P8架构师谈#xff1a;深入探讨HashMap的底层结构、原理、扩容机制深入谈过hashmap的实现原理以及在JDK 1.8的实现区别#xff0c;今天主要谈CurrentHashMap的实现原理#xff0c;以及在JDK1.7和…HashMap、CurrentHashMap 的实现原理基本都是BAT面试必考内容阿里P8架构师谈深入探讨HashMap的底层结构、原理、扩容机制深入谈过hashmap的实现原理以及在JDK 1.8的实现区别今天主要谈CurrentHashMap的实现原理以及在JDK1.7和1.8的区别。内容目录1.哈希表2.ConcurrentHashMap与HashMap、HashTable的区别3.CurrentHashMap在JDK1.7和JDK1.8版本的区别哈希表1.介绍哈希表就是一种以 键-值(key-indexed) 存储数据的结构我们只要输入待查找的值即key即可查找到其对应的值。哈希的思路很简单如果所有的键都是整数那么就可以使用一个简单的无序数组来实现将键作为索引值即为其对应的值这样就可以快速访问任意键的值。这是对于简单的键的情况我们将其扩展到可以处理更加复杂的类型的键。2.链式哈希表链式哈希表从根本上说是由一组链表构成。每个链表都可以看做是一个“桶”我们将所有的元素通过散列的方式放到具体的不同的桶中。插入元素时首先将其键传入一个哈希函数(该过程称为哈希键)函数通过散列的方式告知元素属于哪个“桶”然后在相应的链表头插入元素。查找或删除元素时用同们的方式先找到元素的“桶”然后遍历相应的链表直到发现我们想要的元素。因为每个“桶”都是一个链表所以链式哈希表并不限制包含元素的个数。然而如果表变得太大它的性能将会降低。3.应用场景我们熟知的缓存技术(比如redis、memcached)的核心其实就是在内存中维护一张巨大的哈希表还有大家熟知的HashMap、CurrentHashMap等的应用。ConcurrentHashMap与HashMap等的区别1.HashMap我们知道HashMap是线程不安全的在多线程环境下使用Hashmap进行put操作会引起死循环导致CPU利用率接近100%所以在并发情况下不能使用HashMap。2.HashTableHashTable和HashMap的实现原理几乎一样差别无非是HashTable不允许key和value为nullHashTable是线程安全的但是HashTable线程安全的策略实现代价却太大了简单粗暴get/put所有相关操作都是synchronized的这相当于给整个哈希表加了一把大锁。多线程访问时候只要有一个线程访问或操作该对象那其他线程只能阻塞相当于将所有的操作串行化在竞争激烈的并发场景中性能就会非常差。3.ConcurrentHashMap主要就是为了应对hashmap在并发环境下不安全而诞生的ConcurrentHashMap的设计与实现非常精巧大量的利用了volatilefinalCAS等lock-free技术来减少锁竞争对于性能的影响。我们都知道Map一般都是数组链表结构(JDK1.8该为数组红黑树)。ConcurrentHashMap避免了对全局加锁改成了局部加锁操作这样就极大地提高了并发环境下的操作速度由于ConcurrentHashMap在JDK1.7和1.8中的实现非常不同接下来我们谈谈JDK在1.7和1.8中的区别。JDK1.7版本的CurrentHashMap的实现原理在JDK1.7中ConcurrentHashMap采用了数组Segment分段锁的方式实现。1.Segment(分段锁)ConcurrentHashMap中的分段锁称为Segment它即类似于HashMap的结构即内部拥有一个Entry数组数组中的每个元素又是一个链表,同时又是一个ReentrantLock(Segment继承了ReentrantLock)。2.内部结构ConcurrentHashMap使用分段锁技术将数据分成一段一段的存储然后给每一段数据配一把锁当一个线程占用锁访问其中一个段数据的时候其他段的数据也能被其他线程访问能够实现真正的并发访问。如下图是ConcurrentHashMap的内部结构图从上面的结构我们可以了解到ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。第一次Hash定位到Segment第二次Hash定位到元素所在的链表的头部。3.该结构的优劣势坏处这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长好处写操作的时候可以只对元素所在的Segment进行加锁即可不会影响到其他的Segment这样在最理想的情况下ConcurrentHashMap可以最高同时支持Segment数量大小的写操作(刚好这些写操作都非常平均地分布在所有的Segment上)。所以通过这一种结构ConcurrentHashMap的并发能力可以大大的提高。JDK1.8版本的CurrentHashMap的实现原理JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现采用了数组链表红黑树的实现方式来设计内部大量采用CAS操作这里我简要介绍下CAS。CAS是compare and swap的缩写即我们所说的比较交换。cas是一种基于锁的操作而且是乐观锁。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住等一个之前获得锁的线程释放锁之后下一个线程才可以访问。而乐观锁采取了一种宽泛的态度通过某种方式不加锁来处理资源比如通过给记录加version来获取数据性能较悲观锁有很大的提高。CAS 操作包含三个操作数 —— 内存位置(V)、预期原值(A)和新值(B)。如果内存地址里面的值和A的值是一样的那么就将内存里面的值更新成B。CAS是通过无限循环来获取数据的若果在第一轮循环中a线程获取地址里面的值被b线程修改了那么a线程需要自旋到下次循环才有可能机会执行。JDK8中彻底放弃了Segment转而采用的是Node其设计思想也不再是JDK1.7中的分段锁思想。Node保存keyvalue及key的hash值的数据结构。其中value和next都用volatile修饰保证并发的可见性。class Node implements Map.Entry { final int hash; final K key; volatile V val; volatile Node next; //... 省略部分代码} Java8 ConcurrentHashMap结构基本上和Java8的HashMap一样不过保证线程安全性。在JDK8中ConcurrentHashMap的结构由于引入了红黑树使得ConcurrentHashMap的实现非常复杂我们都知道红黑树是一种性能非常好的二叉查找树其查找性能为O(logN)但是其实现过程也非常复杂而且可读性也非常差DougLea的思维能力确实不是一般人能比的早期完全采用链表结构时Map的查找时间复杂度为O(N)JDK8中ConcurrentHashMap在链表的长度大于某个阈值的时候会将链表转换成红黑树进一步提高其查找性能。ConcurrentHashMap实现原理总结其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap相对而言ConcurrentHashMap只是增加了同步的操作来控制并发从JDK1.7版本的ReentrantLockSegmentHashEntry到JDK1.8版本中synchronizedCASHashEntry红黑树。1.数据结构取消了Segment分段锁的数据结构取而代之的是数组链表红黑树的结构。2.保证线程安全机制JDK1.7采用segment的分段锁机制实现线程安全其中segment继承自ReentrantLock。JDK1.8采用CASSynchronized保证线程安全。3.锁的粒度原来是对需要进行数据操作的Segment加锁现调整为对每个数组元素加锁(Node)。4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时会将链表转化为红黑树进行存储。5.查询时间复杂度从原来的遍历链表O(n)变成遍历红黑树O(logN)。更多高并发架构设计专题资料获取方式关注转发后私信关键词 【高并发】即可获取优知学院(youzhixueyuan.com):IT人升值加薪进阶站BAT总监经验分享平台分享bat面试架构CTO进阶干货编辑请点击输入图片描述
