深入分析 HashMap
阿里工作5年面试官分享Java面试,文章首发在公众号:liebao小奕,回复1024获取Java开发扫盲思维导图。回复加群进粉丝群。
前言
之前讲过一篇关于ArraList
文章,ArrayList几大问题,看完还不懂来打我。 今天我们来分析另一个容器HashMap
。原因很简单,面试的时候相信99%读者都有被面过HashMap
,我也相信大家都知道会用,但是里面蕴含的知识点远远不止put
和get
那么简单。这里面涉及到Java内存模型问题、线程可见不可见问题、Hash计算问题、链表结构、二进制 &,|,<<,>> 等一系列问题,所以面试常问能考察一个人的技术扎不扎实。
文章较长,请耐心看完,必有收获。
HashMap的数据结构和原理
HashMap由数组和链表组合构成的数据结构。
数组里面每个地方都存了Key-Value
这样的实例,在Java 7
叫Entry
在Java 8
中叫Node
。因为他本身所有的位置都为null
,在put
插入的时候会进行hash
计算出index
值。
比如我put("orange","橘子")
,我插入了orange
元素,这个时候我们会通过哈希函数计算出插入的位置,假设通过计算出来index
是1
,则插入结果如下:
HashMap为什么需要链表,链表是什么样子
数组长度是有限的,在有限的长度里面我们使用哈希,哈希本身就存在概率性,就是orange
和orang
我们都去hash有一定的概率会一样(hash 碰撞
),这个时候就需要链表,可以将同一数据放在同一index
中。
如上Node源码所示,每个节点保存自身的Hash
、key
、value
、以及下个节点。
新的Entry节点怎么插入链表的
Java 8
之前都是头插法。新来的值会取代原有的值,原来在数组中的值,就顺推至链表中了 。
Java 8
之后就是尾部插入了。新来的值会直接顺着链表来到链表的尾部。
为什么改为尾部插入?
可能就有人就觉得并没有什么用,真的是这样的嘛?
当然不是了。
因为在HashMap
中有扩容机制。HashMap
中数组的数量是有限的,数据如果多次插入,到达了其上限就需要扩容了,也就是resize
。
那么问题又来了,什么时候resize
呢?不急,我们先看一下HashMap
的源码。
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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);
}
由上可知,决定resize
的因素有两个:
-
initialCapacity
:HashMap
的初始化容量,从源码中可知map
的最大容量是1<<30,也就是1左移30位,每左移一位乘以2,所以就是1*2^30=1073741824
。 -
loadFactor
:负载因子,要大于0,且是非无穷大的数字,默认值为0.75f
。就比如当前的容量大小为100,当你存第76个的时候,判断 发现需要进行resize
了。
如何进行扩容?
扩容:创建一个新的Entry
空数组,长度原数组的2倍。
ReHash
:遍历Entry
数组,将之前的所有的Entry
重新通过hash算法放入到新的数组中。
第二步中需要重新hash
,hash
公式如下:
Hash的公式---> index = HashCode(Key) & (Length - 1)
由此可知,原来的长度(Length
)假设为8,那么新的长度为16进行位运算,结果显而易见是不一样的。
回到之前的问题,java 8为什么改为尾部插入?
假设我们继续使用头插法来使用resize
的赋值方式,单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置,在旧数组中同一条Entry
链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上,但是我们的链表还没有断开,这就导致下面这种情况 :
如果我们这个时候去取值,就出现了一个问题--无限循环(Infinite Loop
)
而在Java 8
之后链表有红黑树部分,代码中多了很多【if else
】的判断,将原本O(n)
降到了O(logn)
。
头插法会改变链表的上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。
本质:
Java 7
在多线程操作HashMap
时可能引起死循环,原因是扩容转移后前后链表顺序倒置,在转移过程中修改了原来链表中节点的引用关系。
Java8在同样的前提下并不会引起死循环,原因是扩容转移后前后链表顺序不变,保持之前节点的引用关系。
HashMap的默认初始化长度是多少?
废话不多说,直接上代码:
static final int EDFAULT_INITIAL_CAPACITY = 1 << 4;
由上可知,HashMap
的初始化长度为16
,使用的是位运算,因为位运算比算数计算效率高(在我们初始化的时候在我们初始化的时候,尽量指定初始值大小)。而HashMap的初始化长度为16
,是为了服务将key
映射到index
的算法。
前面提到过先拿到key
然后通过hash
算法得到的index
值。我们先来看看index
的计算公式:
index = HashCode(key) & (length - 1)
HashMap
的大小为16,则length-1
为15,二进制就是1111
,不难看出其二进制为全为1
,这样index
的结果等同于HashCode
后几位的值,也就意味着,只要输入的HashCode
本身分布均匀,hash算法
的结果就是均匀的,实现了均匀分布。比如在Java
中,所有的对象都是继承于Object
类。Object
类中有两个方法equals();
、hashCode();
,这两个方法都是用来比较两个对象是否相等的。在未重写equals();
方法我们是继承了Object
的equals();
方法,其equals();
是比较两个对象的内存地址,而我们new的2个对象内存地址不一样。
- 值对象,
==
比较的是两个对象的值, - 引用对象,比较的是两个对象的地址。
之前提到过HashMap
是通过key
的HashCode
去寻找index
的,那index
一样就形成链表了,也就是说orange
和orang
的index
都可能是2,在一个链表上的。
当get
的时候,都是根据key
去hash
然后计算出index
,找到了2
,那我怎么找到具体的orange
和orang
呢?是的,这里使用了equals();
方法,如果我们对equals()
方法进行重写,一定要对hashCode();
方法重写,以保证相同的对象返回相同的hash
值,不同的对象返回不同的hash
值。不然一个链表的对象发现hashCode
都一样。
hashmap为什么是线程不安全的
之前提过HashMap
从java 7
到java 8
中的做了很多优化,对于多线程的情况,我们分开分析,这里先给出结论,然后我们在一步一步进行分析:
在java 7多线程环境下,扩容时可能会造成环形链或数据丢失。
在java 8多线程环境下,可能会发生数据覆盖的情况。
我们先分析java 7
多线程的环境。因为在多线程的环境中,HashMap
是在扩容时会造成环形链或者导致数据丢失,那么可能是在扩容函数中,在扩容函数中的transfer
方法,具体代码如下:
void transfer(Entry[] newTable, boolean rehash) {
//新table的容量
int newCapacity = newTable.length;
//遍历原table
for (Entry<K,V> e : table) {
while(null != e) {
//保存下一次循环的 Entry<K,V>
Entry<K,V> next = e.next;
if (rehash) {
//通过e的key值计算e的hash值
e.hash = null == e.key ? 0 : hash(e.key);
}
//得到e在新table中的插入位置
int i = indexFor(e.hash, newCapacity);
//采用链头插入法将e插入i位置,最后得到的链表相对于原table正好是头尾相反的
e.next = newTable[i];
newTable[i] = e;
//下一次循环
e = next;
}
}
}
我们先分析一下上面的代码,在对table
进行扩容到newTable
后,需要将原来的数据转移到newTable
中,其中代码中的第10-12行代码中元素进行转移,使用的是头插法(之前我们提到过),链表顺序就会发生翻转。
扩容之前已经具体分析过单线程环境中执行过程如下图:
当 单线程变成多线程环境 时,可能发生如下情景:
- 线程
Thread1
在第17行【newTable[i] = e;】
(数组中的指针正好要指向链表)挂起,如下图:
- 此时线程
Thread2
开始执行了,Thread2
能正常执行,并完成resize
操作,如下图:
- 由于线程
B
已经执行完毕,根据Java内存模型,现在newTable
和table中的Entry
都是主存中最新值【 Ora1.next=Ora5,Ora4.next=Ora2,Ora2.next=null】
,此时再切换到线程Thread1
继续执行,就会出现数据【Ora1】
和【Ora5】
丢失了(环形情况类似),如下图:
在java 8中对HashMap进行了优化 ,在发生hash碰撞
,不再采用头插法方式,而是直接插入链表尾部,因此不会出现环形链表的情况,但是在多线程的情况下仍然不安全 。这是为什么呢?
同理,我们依然从代码看起,这里我们就先看一下put
操作的源码
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) // 如果没有hash碰撞则直接插入元素
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) // -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;
}
注意第6
行代码,如果没有hash碰撞
则会直接插入元素,我们进行如下操作:
线程Thread1
和线程Thread2
同时进行put操作,但是当这两条不同的数据hash值相同,且插入位置的数据为null,所以这个时候线程Thread1
和Thread2
都会进入到第6
行代码中。在这种情况下,假如Treand1进入后还未进行数据插入时就挂起了,而Thread2正常运行,也正常插入了数据,然后Thread1
获取到了CPU的时间片,此时Thread1
不用进行hash
判断,而是直接把Thread2
插入的数据进行覆盖,这样就导致了Thread2
的数据被修改了,也就是线程不安全。
综上所述,HashMap
在java 7
和java 8
中多线程下都是不安全的。
对于HashMap在多线程下不安全的问题,我们改如何解决呢?
有以下三种解决方式:
Collection.SynchronizedMap(Map)
Hashtable
ConcurrentHashMap
Collections.synchronizedMap
是如何实现线程安全?
在SynchronizedMap
内部维护了一个普通对象Map
,还有排斥锁mutex
,代码如下:
private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
private static final long serialVersionUID = 1978198479659022715L;
private final Map<K,V> m; // Backing Map
final Object mutex; // Object on which to synchronize
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;
}
}
从上方代码可以看出,SynchronizedMap
有两种构造器,两种构造器中,Map
是必传的,如果在构造器种传入了mutex
参数,则将对象 排斥锁赋值并传入。若不传入,默认使用SynchronizedMap
的对象,创建出SynchronizedMap
之后,对于操作map
的方法都使用synchronized
修饰,当有线程对其进行操作时,就会进行上锁。这样,其他线程就无法对其进行操作了。
HashTable
如何实现线程安全?
相对于HashMap
,HashTable
是线程安全的,所以HashTable
在多线程的环境下也是可以正常使用的,但是效率并不是很好。这是为什么呢?
首先,我们先来看看源码(此处是对数据的操作源码):
public synchronized V get(Object key) {
Entry<?, ?> tab[] = table;
int hash = key.hasCode();
}
我们可以看出,因为HashTable
在操作数据时,使用的是synchronized
修饰符进行修饰的,所以某个线程在操作数据的时候会进行上锁,导致效率比较低下。
HashTable和HashMap的区别
-
实现方式不同:
Hashtable
继承了Dictionary
类,而HashMap
继承的是AbstractMap
类 - 初始化容量不同:HashMap的初始容量是16,Hashtable初始化容量为11,但两者的负载因子一致,默认都为0.75。
-
扩容机制不同:当(现有的容量>总容量 * 负载因子),
HashMap
直接扩容为(当前容量 * 2
),Hashtable
则扩容为(当前容量 * 2 + 1
)。 -
迭代器不同:
HashMap
的Iterator
迭代器是使用的快速失败机制(fail-fast
),Hashtable
的Enumerator
是安全失败机制(fail-safe
)。
在Hashtable
中使用了安全失败机制(fail-safe
),这种机制使得我们每次在读取数据时不一定为最新数据。这样我tain(key)
来对key
是否存在进行判断。
Hashtable
是不允许键值为null
,而在HashMap
中键值都可以为空。我们在Hashtable
使用put();
方法时,当参数为空值会直接抛空指针异常,但是在HashMap
中做了特殊处理,如下:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
fail-fast
是什么
fail-fast
即快速失败机制,在用迭代器遍历一个集合对象是,如果遍历过程中对集合对象的内容进行了修改(增、删、改)操作,则抛出Concurrent Modification Exception
。
因为迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个modCount
变量。集合在被遍历期间如果集合的内容发生改变,就会修改modCount的值。而每次迭代器使用hashNext();
或者next();
遍历下一个元素之前,都会检测modCount==expectedmodeCount
值。若是其结果则返回遍历;否则抛出异常,终止遍历。
注意:因为异常的检测条件是
modCount != expectedmodCount
,如果在这个时候发生了修改,使得modCount
值和设置的expectedmodCount
值相等,就不会抛出异常。
ConcurrentHashMap如何实现线程安全
在ConcurrentHashMap
中,Java 7
和Java 8
版本区别还是挺大的,首先我们先看看Java 7
环境。
ConcurrentHashMap
是由Segment数组
、HashEntry
组成的,其实是和HashMap
一样,也是【数组+链表】的数据结构。其中Segment
是ConcurrentHashMap
的一个内部类,具体代码如下:
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
// 和 HashMap 中的 HashEntry 作用一样,真正存放数据的桶
transient volatile HashEntry<K,V>[] table;
transient int count;
// 记得快速失败(fail—fast)么?
transient int modCount;
// 大小
transient int threshold;
// 负载因子
final float loadFactor;
}
HashEntry
和HashMap
差不多,只是HashEntry
使用了volatile
修饰了它的Value
和下一个结点next
。因为我们都知道volatile
有以下三个特性:
- 可见性:保证不同线程对这个变量的操作时的可见性,即一个线程修改了某个变量的值,这个新值对其它的线程是立即可见的。
- 有序性:禁止指令重排(指令重排可能导致代码执行顺秀修改 )。
-
原子性:保证了 对单次读/写的原子性(
i++
这种操作)。 这样就使得ConcurrentHashMap
能在多线程的环境下运行。
在java 8
中,如果数组+链表的方式,我们在查询的时候,需要遍历链表,这样做的话导致效率低下,
就抛弃了原有的恶Segment
分段锁,采用了CAS+sychronized
来保证并发的安全性。其中和HashMap
类似 ,把之前的HashEntry
改成了Node
,但是作用不变,通过volatile
修饰值和next
,保证了其可见性。除此之外,还使用了红黑树,在链表大于一定值(默认为8)的时候会发生转换。因为采用了红黑树可以保证查询的效率,也将ReentrantLock
改为了synchronized
。
ConcurrentHashMap
为什么并发度高
在Java 7
环境中,我们从前面看到的Segment
源码可以看出,它其实继承于ReentrantLock
,即采用了分段锁的技术。这样不会像Hashtable
一样,不管是put
还是get
操作都需要进行同步操作 。每当一个线程占用锁访问一个Segment时,不会影响其他的Segment。所以理论上来说ConcurrentHashMap
支持CurrentLevel
即Segment
数组数量的线程并发,如果Segment
的数量为16
,其并发度就是16
,可以同时允许16
个线程操作16
个Segment
。
ConcurrentHashMap如何存取元素?
在Java 7
环境中,我们先看看put
操作。先看源码:
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
// 遍历该 HashEntry
// 如果不为空则判断传入的 key 和当前遍历的 key 是否相等,
// 相等则覆盖旧的 value。
if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}else {
// 不为空则需要新建一个 HashEntry 并加入到 Segment 中,
// 同时会先判断是否需要扩容。
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
//释放锁
unlock();
}
return oldValue;
}
从源码可以看出,put
操作有以下两个步骤:
- 尝试获取锁,如果获取锁操作失败说明存在多线程的竞争,这时通过
scanAndLockForPut()
自旋来获取锁; - 如果尝试获取锁的次数达到了
MAX_SCAN_RETRIES
则改为阻塞锁获取,保证其能成功获取锁(要不然这里一直获取不到,数据也就写不进去了)。
下面我们再分析get
操作
- 将
key
值通过hash
定位到对应的Segment
; - 再通过一次
hash
定位到对应的元素。
前面我们已经了解到HashEntry
中的value
属性时用volatile
修饰的,因其具有内存可见性的特性,这样就保证了我们每次获取到的都是最新值。
在java 8
环境中,同样先分析put
操作。put
操作主要可以分为以下几个步骤:
- 根据key计算出其
hashcode
; - 判断是否需要初始化;
- 为当前的
key
定位出对应的Node
,如果 为空则写入数据,利用CAS
尝试写入,失败则通过自旋保证成功; - 如果 当前位置的
hashcode == MOVE
,其中MOVE为-1,则 需要扩容; - 如果都不满足,则利用
synchronized
锁写入数据。 - 如果数量大于
TREEFY_THRESHOLD
则需要转换为红黑树。
get操作主要有以下三个步骤:
- 根据计算出来的
hashcode
找到对应的地址,如果在桶上就直接返回值; - 如果计算出来是红黑树,就按照树的方式获取值;
- 如果不满足,按照链表的方式遍历获取值。
前面我们在分析ConcurrentHashMap
的时候提到过CAS
,下面我们就来简单分析一下。
CAS
是一种乐观锁,也是一种轻量级锁。
CAS
主要的流程是线程在读取数据时不用进行加锁,在往回写数据的时候,比较原值和现值是否一致,若一致数据可能(注意,此处是可能会修改,具体原因后面分析)未被修改,则可以将数据写回,若数据不一致数据已经被修改过,则重新执行读取操作。具体流程如下:
前面我们在判断数据一致时,对数据是否被修改抱有疑问。因为其中有一个经典的ABA问题。具体情况是这样的:
有一个线程将数据A
改成了B
;
这时又来了一个线程将数据改成了A
;
这个时候的线程在判断的时候发现它的值时没有发生改变的,但是它的数据已经修改过了。
对于这个ABA
的问题,我们有什么方法解决呢?
其实只要加一个修改的标志,比如说版本号,每次修改一次数据,版本号就进行修改,又或者加一个时间戳,每次修改的时间戳都是不一样的,所以我们只需要先对比数据,在数据一致的情况下,在比较一下标志位是否一致,只有两个都一致才说明数据未发生改变。
学习了HashMap数据结构及其这样设计的原因,那么基于HashMap衍生出哪些其他容器呢?它们在使用上有哪些不同点呢?什么场景用什么可能会有什么坑呢? 关注Java核心&面试专栏。后续将会继续分享。
最后
- 文章均原创,原创不易,感谢掘金平台,觉得有收获,帮忙三连,笔芯
- 文章涉及的所有代码、时序图、架构图均共享,可通过公众号留言获取
- 文章若有错误,欢迎评论留言指出,也欢迎转载,麻烦标注下出处就好
推荐阅读
-
手绘 | 深入分析机器学习在 8 个风控场景中的应用
-
深入分析 HWIDGen:程序员的数字指纹生成器和吉纳维芙之谜
-
Java 创建了一个 HashMap 对象,并将学生姓名和成绩添加到其中,键是学生姓名,值是学生成绩,使用增强 for 循环遍历 HashMap 并输出学生成绩。
-
深入分析如何设计订单超时自动取消功能
-
深入分析 Java 中的 MyBatis Plus 注释 @InterceptorIgnore:拦截器行为的优雅控制
-
叶子深入分析美团的分布式唯一 ID 方案
-
从中心到边缘--深入分析云原生边缘计算在地面上的痛点
-
掌握 JavaScript 面向对象编程的核心代码:深入分析 JavaScript 面向对象机制的对象基础、原型模式和继承策略全面指导高效创建高质量、可维护的代码 - V. 继承机制
-
一篇了解文件上传全过程的文章(1.8W 字的深入分析,进阶必读)
-
彻底搞清楚 python 中文乱码问题(深入分析)