登陆

极彩注册-高并发编程系列:深入探讨ConcurrentHashMap

admin 2019-05-14 309人围观 ,发现0个评论
HashMap、CurrentHashMap 的完成原理根本都是BAT面试必考内容,今日首要谈CurrentHashMap的完成原理,以及在JDK1.7和1.8的差异,我先从哈希表谈起。

01

哈希表

1.介绍

哈希表便是一种以 键-值(key-indexed) 存储数据的结构,咱们只需输入待查找的值即key,即可查找到其对应的值。

哈希的思路很简略,假如一切的键都是整数,那么就能够运用一个简略的无序数组来完成:将键作为索引,值即为其对应的值,这样就能够快速拜访任意键的值。这是关于简略的键的状况,咱们将其扩展到能够处理愈加杂乱的类型的键。

2.链式哈希表

链式哈希表从根本上说是由一组链表构成。每个链表都能够看做是一个“桶”,咱们将一切的元素经过散列的方法放到详细的不同的桶中。刺进元素时,首要将其键传入一个哈希函数(该进程称为哈希键),函数经过散列的方法奉告元素归于哪个“桶”,然后在相应的链表头刺进元素。

查找或删去元素时,用同们的方法先找到元素的“桶”,然后遍历相应的链表,直到发现咱们想要的元素。

3.运用场景

咱们熟知的缓存技能(比方redis、memcached)的中心其实便是在内存中保护一张巨大的哈希表,还有咱们熟知的HashMap、CurrentHashMap等的运用。

02

CurrentHashMap和HashMap等的差异

1.HashMap

咱们知道HashMap是线程不安全的,在多线程环境下,运用Hashmap进行put操作会引起死循环,导致CPU利用率挨近100%,所以在并发状况下不能运用HashMap

2.HashTable

HashTable和HashMap的完成原理简直相同,不同无非是

  • HashTable不允许key和value为null
  • HashTable是线程安全的

可是HashTable线程安全的战略完成价值却太大了,简略粗犷,get/put一切相关操作都是synchronized的,这相当于给整个哈希表加了一把大锁。

多线程拜访时分,只需有一个线程拜访或操作该目标,那其他线程只能堵塞,相当于将一切的操作串行化,在竞赛剧烈的并发场景中功能就会十分差。

3.ConcurrentHashMap

首要便是为了应对hashmap在并发环境下不安全而诞生的。

咱们都知道Map一般都是数组+链表结构(JDK1.8该为数组+红黑树)。

ConcurrentHashMap避免了对大局加锁改成了部分加锁操作,这样就极大地进步了并发环境下的操作速度,因为ConcurrentHashMap在JDK1.7和1.8中的完成十分不同,接下来咱们谈谈JDK在1.7和1.8中的差异。

03

JDK1.7下的CurrentHashMap完成

在JDK1.7中ConcurrentHashMap选用了数组+Segment+分段锁的方法完成。

1.Segment(分段锁)

ConcurrentHashMap中的分段锁称为Segment,它即类似于HashMap的结构,即内部具有一个Entry数组,数组中的每个元素又是一个链表,一起又是一个ReentrantLock(Segment承继了ReentrantLock)。

2.内部结构

ConcurrentHashMap运用分段锁技能,将数据分红一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁拜访其间一个段数据的时分,其他段的数据也能被其他线程拜访,能够完成真实的并发拜访。如下图是ConcurrentHashMap的内部结构图:

从上面的结构咱们能够了解到,ConcurrentHashMap定位一个元素的进程需求进行两次Hash操作。

第一次Hash定位到Segment,第2次Hash定位到元素地点的链表的头部。

3.该结构的优劣势

害处

这一种结构的带来的副作用是Hash的进程要比一般的HashMap要长

优点

写操作的时分能够只对元素地点的Segment进行加锁即可,不会影响到其他的Segment,这样,在最理想的状况下,ConcurrentHashMap能够最高一起支撑Segment数量巨细的写操作(刚好这些写操作都十分均匀地散布在一切的Segment上)。

经过这一种结构,ConcurrentHashMap的并发才能能够大大的进步。

04

JDK1.8的CurrentHashMap完成原理极彩注册-高并发编程系列:深入探讨ConcurrentHashMap

JDK8中ConcurrentHashMap参阅了JDK8 HashMap的完成,选用了数组+链表+红黑树的完成方法来规划,内部很多选用CAS操作,这儿我扼要介绍下CAS。

CAS是compare and swap的缩写,即咱们所说的比较交流。cas是一种根据锁的操作,并且是达观锁。在java中锁分为达观锁和失望锁。失望锁是将资源锁住,等一个之前取得锁的线程开释锁之后,下一个线程才能够拜访。而达观锁采取了一种广泛的情绪,经过某种方法不加锁来处理资源,比方经过给记载加version来获取数据,功能较失望锁有很大的进步。

JDK8中彻底抛弃了Segment转而选用的是Node,其规划思维也不再是JDK1.7中的分段锁思维。

Node:保存key,value及key的hash值的数据结构。其间value和next都用volatile润饰,确保并发的可见性。

class Node implements Map.Entry {

final int hash;

final K key;

volatile V val;

volatile No极彩注册-高并发编程系列:深入探讨ConcurrentHashMapde next;

//... 省掉部分代码}

Java8 ConcurrentHashMap结构根本上和Java8的HashMap相同,不过确保线程安全性。

在JDK8中ConcurrentHashMap的结构,因为引入了红黑树,使得ConcurrentHashMap的完成十分杂乱,咱们都知道,红黑树是一种功能十分好的二叉查找树,其查找功能为O(logN),可是其完成进程也十分杂乱,并且可读性也十分差,Doug

Lea的思维才能的确不是一般人能比的,前期彻底选用链表结构时Map的查找时刻杂乱度为O(N),JDK8中ConcurrentHashMap在链表的长度大于某个阈值的时分会将链表转换成红黑树进一步进步其查找功能。

05

CurrentHashMap的完成原理总结

ConcurrentHashMap的数据结构从JDK1.7版别的ReentrantLock+Segment+HashEntry,到JDK1.8版别中synchronized+CAS+HashEntry+红黑树的结构存储。

1.数据结构:取消了关雎原文Segment分段锁的数据结构,取而代之的是数组+链表+红黑树的结构。

2.确保线程安全机制:JDK1.7选用segment的分段锁机制完成线程安全,其间segment承继自ReentrantLock。JDK1.8选用CAS+Synchronized确保线程安全。

3.锁的粒度:本来是对需求进行数据操作的Segment加锁,现调整为对每个数组元素加锁(Node)。

4.链表转化为红黑树:定位结点极彩注册-高并发编程系列:深入探讨ConcurrentHashMap的hash算法简化会带来坏处,Hash抵触加重,因此在链表节点数量大于8时,会将链表转化为红黑树进行存储。

5.查询时刻杂乱度:从本来的遍历链表O(n),变成遍历红黑树O(logN)。

请关注微信公众号
微信二维码
不容错过
Powered By Z-BlogPHP