多线程面试--进阶篇3(并发工具类和并发容器)

男娘i 2022-03-27 09:05 174阅读 0赞

# 1.为什么要使用ConcurrentHashMap #

HashMap里也有failFast机制,在多线程环境下，使用HashMap进行put操作会引起死循环  
因为多线程可能会导致HashMap的Entry链表形成环形数据结构,一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环一直获取Entry  
HashTable容器是使用synchronized来保证线程安全,但是由于synchronized的原因,在线程竞争激烈的情况下HashTable的效率非常低下.  
而ConcurrentHashMap就应运而生.

# 2.ConcurrentHashMap有一些什么有用的方法 #

putIfAbsent(key,value): 原子性的实现了元素不存在时插入元素,存在则返回已存在的value  
**V putIfAbsent(K key, V value)**  
如果key对应的value不存在，则put进去，返回null。否则不put，返回已存在的value。  
**boolean remove(Object key, Object value)**  
如果key对应的值是value，则移除K-V，返回true。否则不移除，返回false。  
**boolean replace(K key, V oldValue, V newValue)**  
如果key对应的当前值是oldValue，则替换为newValue，返回true。否则不替换，返回false。

# 3.解释下Hash #

Hash:散列,属于压缩的映射。  
任意长度的输入,通过一种算法,变换成固定长度的输出。  
Md5，Sha，取余等等都是散列算法  
ConcurrentHashMap中是wang/jenkins算法

# 4.ConcurrentHashMap在1.7下的实现 #

**分段锁的设计思想**  
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成  
Segment实际是一种可重入锁(ReentrantLock),HashEntry则用于存储键值对数据。  
一个ConcurrentHashMap里包含一个Segment数组,  
Segment的结构和HashMap类似,是一种数组和链表结构.  
一个Segment里包含一个HashEntry数组,每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素  
当对HashEntry数组的数据进行修改时,必须首先获得与它对应的Segment锁。

ConcurrentHashMap初始化方法是通过initialCapacity,loadFactor和concurrencyLevel(参数concurrencyLevel是用户估计的并发级别  
就是说你觉得最多有多少线程共同修改这个map，根据这个来确定Segment数组的大小,concurrencyLevel默认是DEFAULT\_CONCURRENCY\_LEVEL = 16;)。  
ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的.  
HashEntry代表每个hash链中的一个节点,其中的对象属性要么是final的,要么是volatile的.

# 5.ConcurrentHashMap在1.8下的实现 #

对于1.7的基础上改进了2点  
一：取消了segments字段,直接采用transient volatile HashEntry<K,V>\[\] table保存数据，采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。  
二：将原先table数组＋单向链表的数据结构,变更为table数组＋单向链表/红黑树的结构可以改进性能。

# 6.ConcurrentSkipListMap 和ConcurrentSkipListSet #

ConcurrentSkipListMap是TreeMap的并发实现  
ConcurrentSkipListSet是TreeSet的并发实现

# 7.什么是跳表SkipList？ #

![在这里插入图片描述][20190112235705420.png]  
跳表SkipList其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。可以减少查找所需时间为O(n/2)  
因为我们可以先通过每个节点的最上面的指针先进行查找,这样子就能跳过一半的节点。  
比如我们想查找19,首先和6比较,大于6之后,在和9进行比较,然后在和12进行比较…最后比较到21的时候,发现21大于19,说明查找的点在17和21之间,  
从这个过程中,我们可以看出,查找的时候跳过了3,7,12等点,因此查找的复杂度为O(n/2)。  
跳跃表又被称为概率，或者说是随机化的数据结构  
目前开源软件 Redis 和 lucence都有用到它。

(**面试题:** 我如何在一万条数据查询中,增加数据查询的效率  
方案一:毫不犹豫的说,可以使用调表的方法;)

# 8.ConcurrentLinkedQueue 是什么有什么常用的方法 ? #

一个基于链接节点的无界非阻塞队列  
常用的方法  
Add,offer：添加元素  
Peek：get头元素并不把元素拿走  
poll()：get头元素把元素拿走

# 9.CopyOnWriteArrayList和CopyOnWriteArraySet #

写的时候进行复制，可以进行并发的读。  
**适用读多写少的场景：**  
**比如**  
黑名单  
商品类目的访问和更新场景,假如我们有一个搜索网站,用户在这个网站的搜索关键字搜索内容,但是某些关键字是不允许被搜索.  
这些不能被搜索的关键字会被放在一个黑名单当中,黑名单每天晚上更新一次.  
当用户搜索时，会检查当前关键字在不在黑名单当中，如果在，则提示不能搜索。  
(读多写少)  
**缺点:**  
内存占用高，数据一致性弱

# 10.常用阻塞队列 #

## 1.ArrayBlockingQueue： 是数组结构组成有界阻塞队列。 ##

遵循先进先出原则，初始化必须传大小，take和put时候用的同一把锁

## 2.LinkedBlockingQueue：是链表结构组成的有界阻塞队列 ##

也是遵循的先进先出原则，不过它在初始化时候可以不传大小，take和put时候锁是分离的

## 3.PriorityBlockingQueue：是支持优先级排序的无界阻塞队列 ##

它的优先级的排序是按照自然顺序升序排列的  
类自己实现compareTo()方法并初始化PriorityBlockingQueue指定一个比较器Comparator可以实现**更改排序方式**

## 4.DelayQueue：是使用了优先级队列的无界阻塞队列 ##

它支持延时获取(队列里的元素要实现Delay接口)。  
DelayQueue运用可以在以下应用场景。  
**缓存系统的设计：**  
可以用DelayQueue保存缓存元素的有效期，使用一个线程循环查询DelayQueue，一旦能从DelayQueue中获取元素时，表示缓存有效期到了。  
**还有订单到期，限时支付等**

## 5.SynchronousQueue：不存储元素的阻塞队列 ##

这个需要注意的是每个put操作必须要等take操作

## 6.LinkedTransferQueue：链表结构组成的无界阻塞队列 ##

Transfer,tryTransfer,生产者put时,当前有消费者take,生产者会直接把元素传给消费者

## 7.LinkedBlockingDeque：链表结构组成的双向阻塞队列 ##

可以在队列的两端插入和移除,xxxFirst头部操作,xxxLast尾部操作.工作窃取模式。

未完待续…

[20190112235705420.png]: /images/20220327/dd5e9fac33d34ec58f1f04510a9591dc.png