前言:
在进行HashMap的线程安全测试前,我们先来思考几个问题,HashMap的正确使用方法是什么?你平时习惯的使用方式是否正确?如果不正确,那么正确的使用方式到底是什么呢?如果你对HashMap的使用存有疑虑,相信你在看完本篇博客后将会有所收获!
1.HashMap线程安全测试
1.1 HashMap的使用方式
1.1.1 习惯的使用方式
我们平常在使用HashMap时,通常的使用习惯可能如下:
Map<String,String> map = new HashMap<>();
但你认为这样是正确且合理的使用方法吗?
答案:并不是,因为在《阿里巴巴Java开发手册》中曾提到过,我们在使用HashMap时,应当在创建时指定其初始容量大小
那么,正确的使用方式是什么呢?请继续往下看
1.1.2 正确的使用方式
在使用HashMap之前,我们先简单查看一下HashMap构造函数的相关源码:
- HashMap(int, float)型构造函数源码
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
在看到 Float.isNaN(loadFactor) 这个判断条件时,感到有些疑惑,然后去看了下其对应的源码:
package java.lang;
public final class Float extends Number implements Comparable<Float> {
public static boolean isNaN(float v) {
return (v != v);
}
}
最后在看到 this.threshold = tableSizeFor(initialCapaity) 对于这个tableSizeFor又有些疑惑,查看其对应方法源码:
- HashMap的tableSizeFor方法源码:
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
看完了tableSizeFor源码后,我们得知:
在我们自定义HashMap的初始容量大小时, HashMap(int,float)构造函数并非直接使用我们所设置的容量值,而是调用了tableSizeFor方法, 把设置的容量值做为参数, 然后把该函数的返回值作为最后的初始容量大小!
在HashMap(int,float)构造函数中,我们了解到,在创建HashMap时,应该设置一下初始容量和负载因子大小,接下来看一下正确的使用方式
Map<String,String> map = new HashMap<>(16, 0.75F);
其中第一个参数是初始容量 (initialCapacity), 其默认值为16;而第二个参数是负载因子 (loadFactor), 其默认值为0.75F (F表示其为双精度浮点数,即为数据类型为float型)
那么请你再思考一个问题,在HashMap中的源码中,它的初始容量是直接用16表示吗?
答案:并不是,在HashMap源码中,关于默认初始容量大小表示如下:
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
这里初始容量大小使用了一个 1 << 4 表示形式,很多基础薄弱的小伙伴看到后就会心生疑惑,这个 << 到底是什么呢? 其实这是使用了位运算符来进行表示,这里简单介绍一下常用的三种位运算符:
<<:左移运算符 >>:右移运算符 >>>:无符号右移
这里以左移运算符为例,左移的运算规则是: 按照二进制形式把所有数字做移动对应的位数, 高位移出(舍弃),低位的空位补零
知道了原理后,我们来计算一下 1 << 4 转换为 十进制数后是不是16呢?
根据左移运算的规则,那么1 << 4 表示的就是向左移动4位,使用二进制数表示就是 0001 0000 ,再转换为十进制数后,你会发现,这个值刚好等于16
那么,为什么JDK开发人员不直接使用16,而偏偏要使用看上去难懂一些的 1 << 4 呢?
我的理解是:
这样做的目的是,在使用HashMap进行插入数据(即putValue操作)时,首先需要判断数组是否为空,若数组不为空,需要通过 (n-1) & hash 来计算插入元素应当存放在数组中的下标i,而使用1<<4 恰好可以将节点进行平均分配。
上面提到了HashMap中的putValue操作,很多小伙伴可能还不太明白,所以我们来看一下它的源码,顺便验证一下我上面的结论
putValue方法的相关字段:
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<K,V>[] table;
transient int size;
transient int modCount;
int threshold;
putValue方法源码:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
流程图:
步骤解释:
- 步骤一:首先判断数组是否为空,若数组为空,则将数组进行初始化
- 步骤二:若数组不为空,通过 (n-1) & hash 计算存放在数组中的下标 i 位置
- 步骤三:判断 tab [ i ] (数组中下标为 i 的位置) 是否存在数据,若不存在数据,则新建一个Node节点,将其存放在数组中的下标 i 位置中
- 步骤四:若数组的下标 i 位置存在数据 ,说明发生了哈希冲突 (即已存在节点和插入节点的key值和hash值相同),判断两个节点的key是否相等 (使用equals方法进行比较),若key值相同,则用插入节点的value值覆盖掉已存在节点的value值 (前提是onlyAbsent方法的值为false)
- 步骤五:若两个节点的key值不同,判断已存在节点是否为树形节点,若已存在节点为树形节点,则将新建节点插入到红黑树中
- 步骤六:若已存在节点不是树形节点,则创建一个普通Node节点,将新建节点插入到链表尾部;然后判断链表中的节点数是否达到树化阈值 (即链表节点数大于8并且数组长度大于64),若大于等于该值,则将链表转换成红黑树
- 步骤七:判断总节点数是否大于扩容阈值,若大于该阈值(threshold),则将当前数组进行扩容(扩容为原来的两倍)
上面我们提到,在使用HashMap时,需要指定它的初始容量大小,但很多小伙伴表示为什么要指定初始容量大小有些疑惑,那么接下来就来解释这个问题
1.1.3 为什么需要指定初始容量大小?
如果没有设置HashMap的初始容量大小,随着元素数量不断增加,HashMap会进行多次扩容,而HashMap中每次扩容都要执行rehash操作 (即重新格式化哈希表),频繁的扩容是非常消耗性能的
上面提到了HashMap会随着元素数量增多,而进行多次扩容,那么元素数量究竟达到多少,HashMap才会进行扩容呢?
HashMap扩容的触发条件如下:
当哈希表中的元素数目超过扩容阈值, 哈希表将执行rehash操作 (即重建内部的数据结构),以至于哈希表的存储桶数量会变为大约原来的两倍。
int threshold;
注意:临界值的计算公式为:threshold = initialCapacity * loadFactor (其中threshold表示扩容阈值,initialCapacity表示初始容量大小,loadFactor表示装载因子大小)
1.3.4 如何合理设置HashMap的初始容量大小?
关于HashMap初始容量大小的设置,在《阿里巴巴Java开发手册》中也有说明:
initiaCapacity(初始容量) = ( size (需要存储的元素个数) / loadFactor(负载因子) ) + 1
注意:loadFactor (即负载因子) 默认值为0.75,如果暂时无法确定初始值的大小,请设置其为16(即默认值)
按照阿里巴巴开发手册中的公式,我们可以来做个计算:
假设我们需要存储的元素个数为10个,负载因子使用默认的0.75,套入公式就是 (10 / 0.75) + 1,结果约等于 14,也就是说,如果我们想要存储10个元素,只需要将初始容量大小设置为14即可,但是JDK文档中说明初始容量必须是2的幂数,14显然不是2的幂数,我们发现14刚好在2的3次幂和2的4次幂之间,按照只大不小原则,那初始容量的大小就为16
讨论了如何合理设置HashMap的初始容量后,我们再来思考一个问题,为什么说初始容量不易设置太高(或负载因子设置太低)?
下面是在JDK文档中的相关解释:
HashMap为基础的操作(例如get和put)提供了持续时间的性能,假设哈希(散列) 函数将元素正确的分散存储在桶中,集合视图的迭代所需要的时间应该和HashMap实例的容量(桶的数量)加上它的大小(key-value(键值对)映射的数量)成正比。
因此, 如果重视迭代性能,不能设置初始容量太高(或者负载因子太低)。
你可能还注意到了,在上面提到,负载因子的默认值为0.75,那么为什么负载因子默认值要设置为0.75呢?让我们来继续看一下JDK文档中的相关解释:
1.3.5 为什么负载因子默认为0.75?
在解释负载因子的默认值为什么是0.75前,我们首先需要知道什么是负载因子?
JDK文档中负载因子的定义:
负载因子是在HashMap容量自动增加之前,用于衡量哈希表容量允许达到的满度。
如果你觉得这样的解释还是不够直观,我们可以结合哈希表的负载因子计算公式来理解
α = N / M (其中α是指装载因子,N表示哈希表中已存入的元素数,M表示哈希地址空间大小)
注意:α越小,冲突可能性就越小;α越大,冲突的可能性就越大
假设元素数N固定,如果α值越小,空间大小M就越大,即哈希表中的空闲单元比例就越大,因此待插入的元素和已插入的元素发生冲突的可能性就越小,但是其空间利用率就越低
反之,α值越大,空间大小M值就越小,哈希表中的空闲单元比例就越小,因此待插入的元素和已插入的元素发生冲突的可能性就越大,但其空间利用率就越高
JDK文档中关于负载因子默认值设置为0.75的相关解释:
作为一般规则, 默认的负载因子(0.75)在时间和空间开销上提供一个好的权衡,更高的值减少了空间开销,但会增加查找成本 (体现在HashMap类的大多数操作中, 包括get和put) 。
1.2 HashMap线程安全测试
1.2.1 测试代码
package com.kuang.unsafe;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
public class MapTest {
public static void main(String[] args) {
Map<String,String> map = new HashMap<>();
for (int i = 0; i < 30; i++) {
new Thread(()->{
map.put(Thread.currentThread().getName(), UUID.randomUUID().toString().substring(0,5));
System.out.println(map);
},String.valueOf(i)).start();
}
}
}
1.2.2 测试结果
结果:抛出ConcurrentModificationException(并发修改异常)!
1.2.3 结果分析
由此可知:HashMap是线程不安全的,只能在单线程下使用它
那么如果在多线程情况下,我们仍然想使用HashMap,该怎么办呢?
2. 解决HashMap线程不安全
2.1 HashMap线程安全解决方案
JDK官方给出的解决方案是,如果想保证HashMap的线程安全:
- 使用Collections集合工具类的synchronizedMap方法
Map m = Collections.synchronizedMap(new HashMap(...));
Map m = new ConcurrentHashMap();
2.2 使用Collections集合工具类的synchronizedMap方法
2.2.1 测试代码
package com.kuang.unsafe;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
public class MapTest {
public static void main(String[] args) {
Map<String,String> map = Collections.synchronizedMap(new HashMap<>());
for (int i = 0; i < 30; i++) {
new Thread(()->{
map.put(Thread.currentThread().getName(), UUID.randomUUID().toString().substring(0,5));
System.out.println(map);
},String.valueOf(i)).start();
}
}
}
2.2.2 测试结果
结果:执行成功, 没有抛出并发修改异常!
虽然在使用了使用Collections集合工具类的synchronizedMap方法后保证了HashMap线程安全,但很多小伙伴对它为什么就能保证线程安全感到疑惑,接下来就我们一起来查看一下它的底层源码!
2.2.3 源码解析
- Collections集合工具类的synchronizedMap方法源码
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
return new SynchronizedMap<>(m);
}
private static class SynchronizedMap<K,V>
implements Map<K,V>, Serializable {
private static final long serialVersionUID = 1978198479659022715L;
private final Map<K,V> m;
final Object mutex;
SynchronizedMap(Map<K,V> m) {
this.m = Objects.requireNonNull(m);
mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
public V get(Object key) {
synchronized (mutex) {
return m.get(key);
}
}
public V put(K key, V value) {
synchronized (mutex) {
return m.put(key, value);
}
}
@Override
public V putIfAbsent(K key, V value) {
synchronized (mutex) {
return m.putIfAbsent(key, value);
}
}
- 为了保证串行访问, 通过返回的map完成对备份map的所有访问是至关重要的;当用户迭代任何集合视图时, 必须手动同步返回的map集合:
使用方式:
Map m = Collections.synchronizedMap(new HashMap());
...
Set s = m.keySet();
...
synchronized (m) {
Iterator i = s.iterator();
while (i.hasNext())
foo(i.next());
}
注意:不遵循此建议可能会导致不确定性行为!
2.3 使用ConcurrentHashMap类
2.3.1测试代码
package com.kuang.unsafe;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
public class MapTest {
public static void main(String[] args) {
Map<String,String> map = new ConcurrentHashMap<>();
for (int i = 0; i < 30; i++) {
new Thread(()->{
map.put(Thread.currentThread().getName(), UUID.randomUUID().toString().substring(0,5));
System.out.println(map);
},String.valueOf(i)).start();
}
}
}
2.3.2 测试结果
结果:执行成功, 没有抛出并发修改异常!
限于篇幅长度,对HashMap和ConcurrentHashMap源码的解析将会在后续博客中继续更新!那么今天的有关HashMap线程安全问题的学习到这里就结束了,欢迎大家学习和讨论,点赞和收藏!
参考视频链接:https://www.bilibili.com/video/BV1B7411L7tE (B站UP主遇见狂神说的JUC并发编程基础)
|