1.1 HashMap分析
1.1.1 JDK7的HashMap
HashMap在日常开发中是很常见的,在JDK7中其底层是由数组+链表构成,数组被分成一个个桶(bucket),通过哈希值决定了键值对在这个数组中的位置。哈希值相同的键值对,会以链表形式进行存储。每一个键值对会以一个Entry实例进行封装,内部存在四个属性:key,value,hash值,和用于单向链表的next。
当对HashMap初始化时,其构造函数中需要传入两个参数:initialCapacity、loadFactor
hashMap中还有一个变量:threshold(扩容阈值。计算公式:capacity * load factor)
添加数据过程(put)
- 在第一个元素插入HashMap时做一次数组的初始化,先确定初始的数组大小,并计算数组扩容的阈值。
- 使用key进行Hash值计算,然后通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度),用于确定当前键值对要放入哪个Bucket中。
- 找到Bucket后,如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同;如果没有重复,则将此Entry放入链表的头部;如果出现重复,则将此Entry放入链表的尾部,同时建立与前一个节点的连接。
- 在插入新值时,如果当前Buckets数组大小达到了阈值,则触发扩容。扩容后,为原大小的两倍。扩容时会产生一个新的数组替换原来的数组,并将原来数组中的值迁移到新数组中。
1.1.2 JDK7的HashMap扩容流程
1.1.2.1 API调用过程
1)当调用HashMap的put方法时,其内部会调用addEntry方法添加元素。
2)在addEntry中,如果条件满足则调用resize方法进行扩容。扩展为原大小的两倍。
3)在resize方法中,会调用transfer方法根据新的容量去创建新的Entry数组,命名为newTable。
4)在transfer方法中会轮询原table中的每一个Entry重新计算其在新Table上的位置,并以链表形式连接
5)当全部轮询完毕,则在resize方法中将原table替换为新table。
1.1.2.2 图例分析
1)假设现在有一个hashMap,buckets数组大小为2,内部存在三个元素。假设现在通过key%buckets长度,则3、5、7%2 都为1,则这三个元素都进入1号中,形成一个链表。
2)当发生扩容时,根据源码会对原数组进行二倍扩容,则现在buckets数组长度为4。
3)当在transfer方法中对原数组中Entry进行遍历时,首先遍历到key为3的元素,此时需要通过3%4=3。所以该Entry会放入三号桶中。
4)接着遍历到key为7的元素,此时取模结果仍为3,则该Entry也会放入三号桶中。但是在HashMap中采用的是头插法,后进来的元素会放在队列的头部。
5)接着遍历到key为5的元素,此时取模结果为1,则该Entry放入一号桶中。
1.1.3 JDK7hashMap死循环解析
在JDK8之前,生产环境下的系统经常会出现CPU100%占用,当查看堆栈信息,经常发现程序都卡在了hashMap.get()上,当将系统重启就好了。但是过了一段时间就又会这样,而且在测试环境时又没有问题。后来发现是因为在多线程操作hashMap,当进行rehash时,会造成hashMap出现死循环,原因就在于其内部会形成一个循环链表。 该问题在JDK8之后得以解决,但是仍然不推荐在多线程环境下直接使用HashMap,因为有可能会造成数据丢失,建议使用ConcurrentHashMap。
1.1.3.1 死循环出现原因分析
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//从oldTable中获取元素,并放入newTable中。
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
1.1.3.2 单线程下的Rehash
假设了我们的hash算法就是简单的用key mod 一下表的大小(也就是数组的长度)。其中的Hash表的size=2, 所以key = 3, 7, 5,在mod 2以后都冲突在table[1]里。效果如下:
此时执行数组扩容,按照扩容规则,buckets数组扩容为原大小的两倍,变为长度为4,接着进行rehash重新计算原数组中元素在新数组中的位置。
第一次操作完后,key:3 放入到buckets[3]的位置,此时e指向原数组中的7,e.next也为7,结构如下所示:
接着进入到第二次循环,此时e为7,当执行Entry<K,V> next = e.next时,next指向5。接着执行后续逻辑,效果如下所示:
第二次操作完后,key:7放入到buckets[3]的位置,并且处于key:3的前面。继续进行遍历,此时e为5,e.next为null。
根据当前流程可以发现,当在JDK7中的hashmap采用的是头插法,会将扩容之前的元素顺序进行反转。
1.1.3.3 并发下的Rehash
假设现在有两个线程,红色为线程一,蓝色为线程二。
扩容前hash结构
此时两个线程同时执行,因为hashmap不能保证线程安全,所以两个操作的是同一个hashmap空间。当进入到transfer(),在执行完Entry<K,V> next = e.next时,两个线程状态如下所示:
假设线程一在执行到Entry<K,V> next = e.next;时被挂起了,那么此时线程一记录的e为3,e.next为7。结构如下
接着线程二执行,将整个rehash过程执行完毕。执行完毕效果如下:
接着线程一开始执行,但是线程一之前的记录为e为key3,e.next为key7。因此继续执行的话,会指向线程二Rehash之后的链表。形成结构如下:
此时可以发现问题,按理说,e应该是在next的前面,但是现在顺序发生问题了。
线程一操作的就是线程二Rehash之后的hashMap
接着线程一继续执行后续代码
当一次循环后,效果如下所示:
接着进行第二次循环。此时e指向7,当执行Entry<K,V> next = e.next时,此时next指向3。效果如下所示:
接着继续循环执行,效果如下所示:
此时可以发现,当这次循环完之后,3中的next指向7,7中的next指向3.此时死循环已经出现。
1.1.4 JDK8的HashMap
JDK8中对于HashMap的存储结构进行了优化,由数组+链表+红黑树组成。这么做的原因是因为:之前查找元素需要遍历链表,时间复杂度取决于链表的长度。
为了优化这部分的开销,在JDK中,如果链表中元素大于等于8个,则将链表转换为红黑树(前提是桶的大小达到64,否则会先对桶进行扩容);当红黑树中元素小于等于6个,则将红黑树转为链表。从而降低查询与添加的时间复杂度。
1.1.5 JDK8的HashMap源码分析
1.1.5.1 put流程
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//初始化时,map中还没有key-value
if ((tab = table) == null || (n = tab.length) == 0)
//利用resize生成对应的tab[]数组
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))))
//桶内第一个元素的key等于待放入的key
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) // -1 for 1st
//变成红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//检查是否应该扩容
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
1.1.6 jdk 7 与 jdk 8 中关于HashMap的对比
- 8时红黑树+链表+数组的形式,当桶内元素大于8时,便会树化
- 1.7 table在创建hashmap时分配空间,而1.8在put的时候分配,如果table为空,则为table分配空间。
- 在发生冲突,插入链中时,7是头插法,8是尾插法。
1.1.7 知识点延伸
1.1.7.1 HashMap 的buckets长度为什么永远是 2 的幂次方
为了能让存储更加高效,尽量的避免key冲突,让数据尽量均匀的进行分布,因此采用了hash值计算的方式,hash值的范围为-2147483648 到 2147483647。在这40亿的空间中,总的来说一般很难出现碰撞。但是这么大的空间,不可能一次性全部装入内存中,所以不能直接使用这块空间。因此才会对数组长度进行取模运算,根据余数用来对应数组的下标,来确定当前用于存放数据的位置。计算公式就是(n-1)&hash。所以buckets的长度才永远为2的幂次方。
取模运算不用hash%length,而使用(length-1)&hash,是因为&采用二进制进行操作,比 % 的运算效率高。
1.1.7.2 HashMap负载因子为什么是0.75
根据之前的讲解,负载因子是和扩容机制有关的。扩容公式为:数组容量*负载因子=扩容阈值。 当buckets数组达到阈值时,则会进行扩容操作。那么为什么在hashMap中不管是JDK7还是JDK8对于扩容因子都定义为0.75呢?
HashMap总的来说就是一个数据结构,那数据结构就是为了节省空间和时间。那负载因子的作用就是为了节省空间和时间的。
假设负载因子的值为1.0。那么结合扩容公式可知,当buckets桶数组全部用完之后才会进行扩容。因为在扩容时,hash冲突是无法避免的。因此当负载因子为1.0时,在进行扩容时,会出现更多的hash冲突,可能导致链表长度或红黑树高度会变得更长或更高,导致查询效率的降低。因此负载因子过大,虽然保证了空间,但牺牲了时间。
假设负载的值为0.5。那么结合扩容公式可知,当buckets数组使用一半时,就会触发扩容。因为数组中的元素少,所以出现hash冲突的几率也会变少,所以链表长度或者是红黑树的高度就会降低,从而提升了查询效率。但是这样的话,空间利用率又降低了。原本只要1M就能存储的数据,现在则需要2M。所以负载因子太小,虽然时间效率提升了,但是空间利用率降低了。
1.1.7.3 为什么JDK8采用红黑树,而不采用平衡二叉树
因为平衡二叉树条件太苛刻了,需要一直进行整棵树的平衡进行左旋或右旋的操作,红黑树相对来讲调整的少点,只要达到黑平衡即可。并且红黑树对于节点的增删和查找效率都是较为中肯的。
1.1.7.4 为什么链表转红黑树的阈值是8
因为红黑树的平均查找长度是log(n),长度为8的时候,平均查找长度为3,如果继续使用链表,平均查找长度为8/2=4,这才有转换为树的必要。链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。因此8是一个较为合理的值。
2.2 ConcurrentHashMap解析
2.2.1 简介
ConcurrentHashMap是一个线程安全且高效的HashMap。在并发下,推荐使用其替换HashMap。对于它的使用也非常的简单,除了提供了线程安全的get和put之外,它还提供了一个非常有用的方法putIfAbsent,如果传入的键值对已经存在,则返回存在的value,不进行替换; 如果不存在,则添加键值对,返回null。
public class MapDemo {
public static void main(String[] args) {
ConcurrentHashMap<String,String> map = new ConcurrentHashMap<>();
System.out.println("put不存在的值------");
System.out.println(map.put("AA","AA"));
System.out.println(map.get("AA"));
System.out.println("put已存在的key-------------");
System.out.println(map.put("BB","BB"));
System.out.println(map.get("BB"));
System.out.println("putIfAbsent已存在的key-------------");
System.out.println(map.putIfAbsent("AA","AA"));
System.out.println(map.get("AA"));
System.out.println("putIfAbsent不存在的key-------------");
System.out.println(map.putIfAbsent("CC","CC"));
System.out.println(map.get("CC"));
}
}
2.2.2 JDK7的ConcurrentHashMap
2.2.2.1 基础结构
一个ConcurrentHashMap里包含一个Segment数组,结构与HashMap类似(数组+链表)。一个Segment中包含一个HashEntry数组,每个HashEntry就是链表的元素。
Segment是ConcurrentHashMap实现的很核心的存在,Segment翻译过来就是一段,一般把它称之为分段锁。它继承了ReentrantLock,在ConcurrentHashMap中相当于锁的角色,在多线程下,不同的线程操作不同的segment。只要锁住一个 segment,其他剩余的Segment依然可以操作。这样只要保证每个 Segment 是线程安全的,我们就实现了全局的线程安全。
HashEntry则用于存储键值对。
2.2.2.2 构造方法和初始化
根据其构造函数可知,map的容量默认为16,负载因子为0.75。这两个都与原HashMap相同,但不同的在于,其多个参数concurrencyLevel(并发级别),通过该参数可以用来确定Segment数组的长度并且不允许扩容,默认为16。
并发度设置过小会带来严重的锁竞争问题;如果过大,原本位于一个segment内的访问会扩散到不同的segment中,导致查询命中率降低,引起性能下降。
2.2.2.3 API解析
2.2.2.3.1 get()
1)根据key计算出对应的segment
2)获取segment下的HashEntry数组
3)遍历获取每一个HashEntry进行比对。
注意:整个get过程没有加锁,而是通过volatile保证可以拿到最新值。
2.2.2.3.2 put()
初始化segment,因为ConcurrentHashMap初始化时只会初始化segment[0],对于其他的segment,在插入第一个值的时候再进行初始化。经过计算后,将对应的segment完成初始化。
向下调用ensureSegment方法,其内部可以通过cas保证线程安全,让多线程下只有一个线程可以成功。
在put方法中当初始化完Segment后,会调用一个put的重载方法进行键值对存放。首先会调用tryLock()尝试获取锁,node为null进入到后续流程进行键值对存放;如果没有获取到锁,则调用scanAndLockForPut()自旋等待获得锁。
在scanAndLockForPut()方法中首先会根据链表进行遍历,如果遍历完毕仍然找不到与key相同的HashEntry,则提前创建一个HashEntry。当tryLock一定次数后仍然无法获得锁,则主动通过lock申请锁。
在获得锁后,segment对链表进行遍历,如果某个 HashEntry 节点具有相同的 key,则更新该 HashEntry 的 value 值,否则新建一个节点将其插入链表头部。
如果节点总数超过阈值,则调用rehash()进行扩容。
2.2.3 JDK8的ConcurrentHashMap
2.2.3.1 与JDK7的区别
在JDK1.8中对于ConcurrentHashMap也进行了升级,主要优化点如下:
1)JDK7中使用CAS+Reentrant保证并发更新的安全,而在JDK8是通过CAS+synchronized保证。因为synchronized拥有了优化,在低粒度加锁下,synchronized并不比Reentrant差;在大量数据操作下,对于JVM的内存压力,基于API的ReentrantLock会开销更多的内存。
2)JDK7的底层使用segment+数组+链表组成。而在JDK8中抛弃了segment,转而使用数组+链表+红黑树的形式实现,从而让锁的粒度能够更细,进一步减少并发冲突的概率;同时也提高的数据查询效率。
3)在JDK7中的HashEntry在JDK8中变为Node,当转化为红黑树后,变为TreeNode。转换的规则与hashMap相同,当链表长度大于等于8则转换为红黑树,当红黑树的深度小于等于6则转换为链表。
2.2.3.2 核心属性
Node类:用于存储键值对。其与JDK7中的HashEntry属性基本相同。
TreeNode类:树节点类,当链表长度大于等于8,则转换为TreeNode。与hashMap不同的地方在于,它并不是直接转换为红黑树,而是把这些节点放在TreeBin对象中,由TreeBin完成红黑树的包装。
TreeBin类:负责TreeNode节点包装,它代替了TreeNode的根节点,也就是说在实际的数组中存放的是TreeBin对象,而不是TreeNode对象。
sizeCtl属性:用于控制table的初始化和扩容。-1表示正在初始化,-N表示由N-1个线程正在进行扩容,0为默认值表示table还没被初始化,正数表示初始化大小或Map中的元素达到这个数量时,则需要扩容了。
2.2.3.3 核心API
get()
get操作的思路比较简单,和HashMap取值过程类似。
put()
put操作较为复杂,需要考虑并发安全性的问题。
/** 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 (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
/*如果table为空,初始化table*/
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
/*CAS向Node数组中存值*/
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
/*扩容操作,当前线程协助扩容*/
tab = helpTransfer(tab, f);
else {
V oldVal = null;
/*
*基于synchronized锁住数组中的元素
*/
synchronized (f) {
if (tabAt(tab, i) == f) {
/*是链表中的节点*/
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
/*存放数据*/
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
/*如果遍历到了最后一个节点,则把它插入到链表尾部*/
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
/*按照树的方式插入值*/
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
/*达到阈值8,链表转换为红黑树*/
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
/*Map元素数量+1,检查是否需要扩容*/
addCount(1L, binCount);
return null;
}
2.2.3.4 与hashTable的区别
Hashtable的任何操作都会把整个表锁住,是阻塞的。好处是总能获取最实时的更新,比如说线程A调用putAll写入大量数据,期间线程B调用get,线程B就会被阻塞,直到线程A完成putAll,因此线程B肯定能获取到线程A写入的完整数据。坏处是所有调用都要排队,竞争越激烈效率越低。 更注重安全。
ConcurrentHashMap 是设计为非阻塞的。在更新时会局部锁住某部分数据,但不会把整个表都锁住。同步读取操作则是完全非阻塞的。好处是在保证合理的同步前提下,效率很高。坏处 是严格来说读取操作不能保证反映最近的更新。例如线程A调用putAll写入大量数据,期间线程B调用get,则只能get到目前为止已经顺利插入的部分数据。更注重性能。
标签:ConcurrentHashMap,hash,HashMap,数组,链表,源码,线程,key,null From: https://blog.csdn.net/2302_78191516/article/details/140243382