面试造飞机系列:用心整理的HashMap面试题,以后都不用担心了
本文思维导图
HashMap简介
HashMap
是很常用的一种集合框架,其底层实现方式在 JDK 1.7
和 JDK 1.8
中却有很大区别。
HashMap
是用来存储数据的,它底层在JDK 1.7
是数组+链表实现的,而JDK 1.8
是使用数组+链表+红黑树实现,通过对 key
进行哈希计算等操作后得到数组下标,把 value
等信息存放在链表或红黑树存在此位置。
如果两个不同的 key
运算后获取的数组下标一致,就出现了哈希冲突。数组默认长度是16,如果实际数组长度超过一定的值,就会进行扩容。
HashMap
的面试不管小厂还是大厂都是高频问点,特别是大厂一定会深究底层,采用持续的追问,知道你怀疑人生,在Java7
和Java8
中对HashMap
的数据结构进行了很大的优化。
今天这篇文章就以HashMap
的高频问点为主,层层的剖析HasMap
的底层实现,话不多说,直接进入正题。
问点一:你了解HashMap的底层数据结构吗?
对于HashMap
的底层数据结构在Java7
和Java8
中的实现是不同的,在Java7
中是采用数组+链表的数据结构进行实现,而在Java8
中是采用数组+链表+红黑树的数据结构实现的。
说时迟那时快,刚话说完,从兜里拿出笔和纸,啪地一声放在桌子上画了起来,许久之后,出现了两幅jdk7和jdk8的HashMap的内部结构图:
上图是
jdk7
内部结构图,以Entry<K,V>[]
数组作为哈希桶,每个哈希桶的后面又可以连着一条单向链表,在链表中以k,v
的形式存储数据,并且每一个节点有指向下一节点的指针。上图是
jdk8
的HashMap
的内部结构图,此时在源码源码中就不再使用Entry<K,V>[]
作为数组,而是使用Node<K,V>[]
数组作为哈希桶,每个哈希桶的后面也可能连着一条单向链表或者红黑树。当单向链表的值>8
的时候,链表就会转换为红黑树进行存储数据,具体详细的红黑树介绍之前已经写过一篇,这里就不再赘述,未详细了解的请移至这一篇[B树、B-树、B+树、B*树图文详解]。
在面试大厂的时候,其实答到这里,还是不完整的,为什么呢?因为你想你说的上面的实际由jdk7
和jdk8
转变的一个结果,但是重要的为什么要这样做?你还没有回答。
如果你聪明点的话,就不会等着面试官抛出接下来的问题?而是自己去回答这个为什么?不是等着面试官继续抛出这个为什么?一个会聊天的人他会去猜测对方想知道什么?
问点二:为什么JDK 7使用数组+链表?JDK8中为什么要使用红黑树?哈希冲突是怎么回事?HashMap又是怎么解决的?
在深入这些问题之前,首先要了解一些概念,比如什么是hash
函数,对于hash
函数,之前已经详细的写过一篇,这里就不再赘述,详细参考这一篇[大白话之哈希表和哈希算法]。
哈希冲突是怎么回事呢?当<k,v>
的数据将要存进HashMap
中的时候,会先,把k
值经过hash
函数进行计算得到hash
值,再通过hash
值进行计算得到数据在数组的下标,在jdk7
中的源码如下:
//key 进行哈希计算
int hash = hash(key);
//获取数组下标
int i = indexFor(hash, table.length);
通过计算后的下标,从而得到数组的对应下标的位置,最后把k,v值存进去,同样的当再次第二次存值的时候,同样把k,v
传进来,当k再次进行计算出数组下标index
,有可能和第一次计算的index
的值相同。
为什么有可能相同呢?这个是hash
函数的原因,看完上面推荐的那篇hash
函数详细介绍你就懂了。当两次的计算index
相同,这就是hash冲突。
但是,两次的需要存进去的value
值是不同的,这就出现了同一个数组后面有一条链表,会比较链表上的每一个value
值与当前的value
是否相同,若是不相同,通过头插法,将数值插入链表中。如下图所示:
接下来通通过源码进行分析,在jdk 7插入的put 方法源码如下:
public V put(K key, V value) {
//数组为空就进行初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//key 进行哈希计算
int hash = hash(key);
//获取数组下标
int i = indexFor(hash, table.length);
//如果此下标有值,遍历链表上的元素,key 一致的话就替换 value 的值
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//新增一个key
addEntry(hash, key, value, i);
return null;
}
put
方法中主要做了以下几件事:
判断
table
数组是否为空,若为空进行初始化table
数组。判断key值是否为
null
,将null是作为key
存进去。若
key
不为空,通过key
计算出数组下标,判断table[i]
是否为空。若是不为空通过链表循环,判断在链表中是否存在与该
key
相等,若是存在,直接将value
替换成新的value
。若是table[i]
为空或者链表中不存在与之相同的key
,就addEntry(hash, key, value, i)
新增一个节点。
接下来看看addEntry(hash, key, value, i)
新增节点的源码如下:
void addEntry(int hash, K key, V value, int bucketIndex) {
//数组长度大于阈值且存在哈希冲突(即当前数组下标有元素),就将数组扩容至2倍
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
这个方法很简单,直接就是判断当前数组的大小是否>=threshold
并且table[bucketIndex]
是否为null
。若成立扩容,然后rehash,重新得到新数组的下标值,最后 createEntry(hash, key, value, bucketIndex)
创建新节点。
最后来看一下createEntry(hash, key, value, bucketIndex)
创建新节点的源码如下:
void createEntry(int hash, K key, V value, int bucketIndex) {
//此位置有元素,就在链表头部插入新元素(头插法)
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
该方法就是通过头插法加入新节点,方法非常简单,相信都能看懂。经过上面对put
方法的源码分析,在jdk 7
中put
操作的原理图如下所示:
在
JDK 7
中,链表存储有一个缺点,就是当数据很多的时候,链表就会很长,每次查询都会遍历很长的链表。因此在JDK 8
中为了优化HashMap
的查询效率,将内部的结构改为数组+链表+和红黑树,当一个哈希桶后面的链表长度>8
的时候,就会将链表转化为红黑树,红黑树是二分查找,提高了查询的效率。接下来通过JDK 8
的put
源码分析如下:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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;
//key 相同就覆盖原来的值
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);
//链表长度超过8,就把链表转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key相同就覆盖原来的值
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;
}
通过分析源码,上面的方法主要做了以下几件事:
判断当前桶是否为空,空的就需要初始化(
resize
中会判断是否进行初始化)。根据当前
key
的hashcode
定位到具体的桶中并判断是否为空,为空表明没有Hash
冲突就直接在当前位置创建一个新桶即可。如果当前桶有值( Hash 冲突),那么就要比较当前桶中的
key
、key
的hashcode
与写入的key
是否相等,相等就赋值给 e。如果当前桶为红黑树,那就要按照红黑树的方式写入数据。
如果是个链表,就需要将当前的
key、value
封装成一个新节点写入到当前桶的后面(形成链表)。接着判断当前链表的大小是否大于预设的阈值,大于时就要转换为红黑树。
如果在遍历过程中找到
key
相同时直接退出遍历。如果
e != null
就相当于存在相同的key
,那就需要将值覆盖。最后判断是否需要进行扩容。
继续看下 treeifyBin 的源码:
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//链表转为红黑树时,若此时数组长度小于64,扩容数组
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//链表转为树结构
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
由此可以看到1.8中,数组有两种情况会发生扩容:
一是超过阈值
二是链表转为红黑树且数组元素小于64时
由此在jdk1.8
中,默认长度为16
情况下,要么元素一直放在同一下标,链表转为红黑树且数组元素小于64时就会扩容,要么超过阈值12
时才会扩容。
依据上面的源码分析,在JDK 1.8
中put
方法的执行的原理图如下:
通过上面的分析,我们可以看到
jdk1.7
和1.8
情况下 hashmap
实现方式区别是非常大的。在源码的分析中,也可以找到下面问题的答案。问点三:HashMap的扩容机制是怎么样的?JDK7与JDK8有什么不同吗?
JDK 1.7
的扩容条件是数组长度大于阈值且存在哈希冲突,在JDK 7
中的扩容的源码如下:
void addEntry(int hash, K key, V value, int bucketIndex) {
//数组长度大于阈值且存在哈希冲突(即当前数组下标有元素),就将数组扩容至2倍
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
而JDK 1.8
扩容条件是数组长度大于阈值或链表转为红黑树且数组元素小于64时,源码中的体现如下所示:
//数组长度大于阈值,就扩容
if (++size > threshold)
resize();
//链表转为红黑树时,若此时数组长度小于64,扩容数组
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
问点四:HashMap中的键值可以为Null吗?能简单说一下原理吗?
在JDK7
中是允许null
存进去的,通过 putForNullKey(value)
方法来存储key
为null
值,具体的实现的源代码如下:
if (key == null)
return putForNullKey(value);
而在JDK 8
中当传进key
为null
值的时候,就直接将hash
值取0
,进行计算存入值的位置。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
问点五:HashMap中能put两个相同的Key吗?为什么能或为什么不能?
这个问题比较简单,在JDK7
和JDK8
中的做法是一样的,若是存入的key
值一样,就会将原来的key所对应的value值直接替换掉,可以从源码中看出:
// JDK1.7
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
// 直接替换原来的value值
e.value = value;
e.recordAccess(this);
return oldValue;
}
// JDK 1.8
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;
}
// 存在key值相同
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)
// 替换掉原来value值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
问点六:聊一聊JDK 7的HashMap中的“死锁”是怎么回事?
HashMap
是线程不安全的,在HashMap
的源码中并未对其操作进行同步执行,所以在并发访问的时候就会出现线程安全的问题。
由于上一篇的ConcurrentHashMap
篇中讲到了死锁,也画了图,但是很多读者说看不懂,这里我的锅,在这里详细的进行图解。
假设:有线程A和线程B,并发访问HashMap中的数据。假设HashMap
的长度为2
(这里只是为了讲解方便假设长度为2),链表的结构图如下所示:
4和8都位于同一条链表上,其中的threshold为1,现在线程A和线程B都要进行put操作,首先线程A进行插入值。
此时,线程A执行到transfer
函数中(transfer
函数是resize扩容方法中调用的另一个方法),当执行(1)
位置的时候,如下所示:
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next; ---------------------(1)
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;
} // while
}
}
此时线程A挂起,在此时在线程A的栈中就会存在如下值:
e = 4
next = 8
此时线程B执行put
的操作,并发现在进行put
操作的时候需要扩容,当线程B执行 transfer
函数中的while
循环,即会把原来的table
变成新一table
(线程B自己的栈中),再写入到内存中。
执行的过程如下图所示(假设两个元素在新的hash函数下也会映射到同一个位置):
此时线程A有获取到
cpu
的执行时间,接着执行(但是纤层A中的数据仍是旧表数据),即从transfer
代码(1)处接着执行,当前的 e = 4, next = 8
, 上面已经描述,执行的的过程若下图所示:当操作完成,执行查找时,会陷入死循环!
问点七:HashMap是线程安全的吗?为什么安全或者不安全?
从上图JDK8
的put
操作原理图中可以看出为HashMap
的put
方法的详细过程,其中造成线程不安全的方法主要是resize
(扩容)方法.
假设,现在有线程A 和线程B 共同对同一个HashMap
进行put
操作,假设A和B插入的Key-Value
中key
的hashcode
是相同的,这说明该键值对将会插入到Table
的同一个下标的,也就是会发生哈希碰撞。
此时HashMap
按照平时的做法是形成一个链表(若超过八个节点则是红黑树),现在我们插入的下标为null(Table[i]==null)
则进行正常的插入。
此时线程A进行到了这一步正准备插入,这时候线程A堵塞,线程B获得运行时间,进行同样操作,也是Table[i]==null
。此时它直接运行完整个put
方法,成功将元素插入.。
随后,线程A获得运行时间接上上面的判断继续运行,进行了Table[i]==null
的插入(此时其实应该是Table[i]!=null
的操作,因为前面线程B已经插入了一个元素了),这样就会直接把原来线程B插入的数据直接覆盖了,如此一来就造成了线程不安全问题.
问点八:为什么重写对象的Equals方法时,要重写HashCode方法?这个和HashMap有关系吗?为什么?
对于这个问题,我之前已经详细写过一篇文章,这里就不再做赘述,详细的了解,请参考这一篇文章[再也不怕面试问为什么要重写 hashcode 和 equals 方法了]
【往期精彩】
[为了把mysql的索引底层原理讲清楚,我把计算机翻了个底朝天]
[面试官:听说你sql写的挺溜的,你说一说查询sql的执行过程]