大聪明教你学Java | JDK8 中 HashMap 的那些事
前言
相信各位小伙伴都有感觉，我们去十家公司面试，八家都会问到关于 HashMap 的知识，由此就可以看出 HashMap 的重要性了，那么今天就跟大家聊一聊 HashMap 的那些事😊。
JDK8 中的 HashMap
在讨论 HashMap 之前，我们先简单说几句常用数据结构在执行基础操作时的性能👇
- 数组： 数组采用的是一段连续的存储单元来存储数据的集合。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，进行逐一比对，时间复杂度为O(N)；对于有序数组来说则可以采用二分法等方式进行查找，此时就可将时间复杂度提高为O(logN)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(N)。
- 链表： 对链表执行新增，删除等操作时，只需要处理结点间的引用即可，时间复杂度为O(1)，而执行查找操作时，则需要遍历整个链表，对数据逐一比对，此时复杂度为O(N)
- 二叉树： 对一棵相对平衡的有序二叉树来说，如果二叉树的元素个数为N，那么不管是对树进行插入、查找、删除节点都是执行 log(N) 次循环调用就可以了。它的时间复杂度相对于上述两种（数组、链表）数据结构来说是最优的
- HashMap（哈希表）：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，仅需一次定位即可完成，时间复杂度为O(1)
通过上面的比对，我们可以清楚的看出 HashMap 的性能是最优的，那它为什么可以拥有如此之高的性能呢？接下来我们就通过源码了解一下 HashMap 是如何实现的~
HashMap 的基本元素
不知道各位小伙伴有没有看过 HashMap 的源码，在 HashMap 的源码中我们可以看到几个基本元素，如下所示👇
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 此处省略N行代码....
*/
}
下面我们就对其中的重要元素做一个介绍👇：
DEFAULT_INITIAL_CAPACITY 和 MAXIMUM_CAPACITY： 当我们通过无参的构造函数 new 一个 hashMap 时，它会自动帮我们指定其默认大小为 DEFAULT_INITIAL_CAPACITY 也就是16，我们也可以自己制定初始容量的大小，需要注意的是，容量大小必须是 2^N^（N为正整数）且小于MAXIMUM_CAPACITY，也就要小于2^30^。我们一定要记住 HashMap 的容量永远是2的整数次幂。初始容量16，每次扩容之后的容量都是前一次容量的两倍。比如当前容量是16扩容一次就变成了32，再扩容一次就变成了64。而且如果我们在 new HashMap 的时候，给了一个非2的整数次幂的初始容量，构造函数内部也会调用 tableSizeFor() 方法讲容量转换成2的整数次幂的。比如：传递3会转换成4，传递13会转换成16。
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
DEFAULT_LOAD_FACTOR：DEFAULT_LOAD_FACTOR 所代表的含义就是默认的负载因子，我们同样可以根据有参的 HashMap 构造函数来指定初始负载容量的大小，如果不指定，默认的负载因子为0.75。
TREEIFY_THRESHOLD：TREEIFY_THRESHOLD 表示的是树化阈值，我们都知道 HashMap 底层结构采用【数组】+【链表 OR 红黑树】的形式来存储节点，首先 HashMap 是一个数组，而且数组里面每个位置可以放入多个元素，咱们可以把存放元素的位置想象成一个木桶，HashMap 为了最大程度的提高效率，开发源码的大神们在木桶的设计上也是相当的精辟。木桶可能是链表也可能是红黑树，一开始桶里元素不多的时候采用链表形式保存元素，随着 HashMap 里面的元素越来越多，也就是桶里面的元素越来越多，当元素个数超过8（TREEIFY_THRESHOLD）并且数组的长度超过64（MIN_TREEIFY_CAPACITY）的时候，就会把链表变成红黑树（也就是树化）；如果此时采用的是红黑树保存节点元素，那么随着节点个数的减少（也就是执行了删除操作），当节点元素个数小于6（UNTREEIFY_THRESHOLD）的时候，又会把红黑树降级为链表。
看到这里，有些小伙伴可能会问了：HashMap 为啥还要转换为红黑树？用平衡二叉树代替红黑树不行吗？ 其实这些都是 HashMap 源码大神们深思熟虑后的结果，如果链表过长，就会导致节点元素的查找效率不高，所以需要把链表转为红黑树。同时 HashMap 源码大神们兼顾了节点的插入删除效率，红黑树有不追求“完全平衡”的特性，所以往红黑树里面插入或者删除节点的时候任何不平衡都会在三次旋转之内解决，而平衡二叉树插入或者删除节点的时候为了追求完全平衡，旋转的次数是不固定的，导致执行效率会变得比较低，这也就是选择使用红黑树而不是二叉树的原因。
P.S. 关于红黑树和平衡二叉树的更多知识，这里就不具体展开了，有兴趣的小伙伴可以自行去百度，或移步至大聪明教你学Java——浅析红黑树。
HashMap 的常用方法
我们在使用 HashMap 的过程中，最常用的就是两个方法，分别是put() 和 get() ，下面我们就一起看看这两个方法的源码👇
put()方法
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
1. Implements Map.put and related methods.
2. * @param hash hash for key
3. @param key the key
4. @param value the value to put
5. @param onlyIfAbsent if true, don't change existing value
6. @param evict if false, the table is in creation mode.
7. @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//tab[]为数组，p是存放元素的桶
Node<K,V>[] tab; Node<K,V> p; int n, i;
// tab为空则创建数组，同时调用resize()方法进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// i = (n-1) & hash 计算下标，如果未碰撞，则直接存储节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//发生了碰撞，则存储在链表或者树中
else {
Node<K,V> e; K k;
// 如果数组上的那个节点hash相同，且key相同，则e指向该节点，等待后面覆盖
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;
}
//当key相同时，直接替换，此时e已经指向某个节点，直接退出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//检查e的null，进行覆盖操作，并且直接返回被覆盖的节点
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;
}
通过上面的源码，我们可以将向 HashMap 中存放元素的过程分为四个步骤： ① table为空，则调用resize()函数进行创建： 这里所说的 table 就是源码中的 Node<K,V>[] table ，它是 HashMap 的一个内部类，也是 HashMap 的基本子节点，同时它既是 HashMap 底层数组的组成元素，又是每个单向链表的组成元素。它其中包含了数组元素所需要的 key 与 value ，以及链表所需要的指向下一个节点的引用域，其源码如下👇
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
可能有小伙伴会产生疑问了，为什么在 putVal 的时候才调用 resize() 方法进行初始化呢？在创建 HashMap 的时候直接初始化不行吗？其实具体的原因我也不是很清楚，我个人觉得是在向 HashMap 插入数据时才进行初始化有利于资源的节约，就像某宝一样，打开某宝APP后并不是把所有的商品全部展示出来，而是边刷网页边加载商品数据。
② 计算元素所要储存的位置（index）,并对 null 做出处理： 在源码中有这么一行代码：p = tab[i = (n - 1) & hash]，也就是说 index = (n - 1) & hash，其中 n 代表了新创建的 table 数组的长度，咱们主要看看 hash 是从何而来的。通过源码我们看到这样一个方法：
/**
1. Computes key.hashCode() and spreads (XORs) higher bits of hash
2. to lower. Because the table uses power-of-two masking, sets of
3. hashes that vary only in bits above the current mask will
4. always collide. (Among known examples are sets of Float keys
5. holding consecutive whole numbers in small tables.) So we
6. apply a transform that spreads the impact of higher bits
7. downward. There is a tradeoff between speed, utility, and
8. quality of bit-spreading. Because many common sets of hashes
9. are already reasonably distributed (so don't benefit from
10. spreading), and because we use trees to handle large sets of
11. collisions in bins, we just XOR some shifted bits in the
12. cheapest possible way to reduce systematic lossage, as well as
13. to incorporate impact of the highest bits that would otherwise
14. never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
通过源码我们可以看到在获取index时，首先将得到 key 对应的哈希值【h = key.hashCode()】，然后通过 hashCode() 的高16位异或低16位【(h = k.hashCode()) ^ (h >>> 16)】来获取元素所要储存的位置。 这个是在 JDK8 中优化后的结果，它优化了高位运算的算法（速度、功效、质量），通过 hashCode() 的高16位异或低16位来计算元素储存的位置，可以在数组 table 的长度比较小的时候，也能保证高低 Bit 都参与到 Hash 的计算中，同时不会有太大的开销。
③ 判断是否为红黑树并添加元素：关于红黑树的部分这里就不讨论了，我们主要看看 else 里边所包含的内容，else 分支中包含了一个 for 循环（表示循环遍历链表），它在循环时经历了以下几个步骤👇
- e = p.next 以及后面的 p = e 实际上是在向后循环遍历链表，开始的时候 p 为每个桶的头元素，然后将 p 的引用域指向空节点 e，这个时候实际上就相当于将 p 的下一个元素赋值给了 e ，即 e 已经变成了 p 的下一个元素。
- 接下来我们把 e 单独提出来，进行了两个判断：if ((e = p.next) == null) 和 if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))。前者的含义是如果 e 也就是 p.next 为 null，那么说明当前的这个 p 已经是链表最后一个元素了。这个时候采取尾插法添加一个新的元素 p.next = newNode(hash, key, value, null)，即直接将 p 的引用域指向这个新添加的元素。如果添加了新元素之后发现链表的长度超过了TREEIFY_THRESHOLD - 1（也就是超过了8），那么调用 treeifyBin(tab, hash) 把这个链表转换成红黑树继续操作；后者则表示如果发现 key 值重复了，那么直接break，结束遍历。
- 最后又将 e 赋给 p，这个时候的 p 已经向后移动了一位，接着重复上面的过程，直到循环完整个链表，或者break出来。
④ 如果超出了最大限制，执行扩容操作：关于扩容我们这里多说两句，首先看一下源码👇
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
//创建一个oldTab数组用于保存之前的数组
Node<K,V>[] oldTab = table;
//获取原来数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//原来数组扩容的临界值
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果原来的数组长度大于最大值(2^30)
if (oldCap >= MAXIMUM_CAPACITY) {
//扩容临界值提高到正无穷
threshold = Integer.MAX_VALUE;
//返回原来的数组
return oldTab;
}
//else if((新数组newCap)长度乘2) < 最大值(2^30) && (原来的数组长度)>= 初始长度(2^4))
//这个else if 中实际上就是咋判断新数组(此时刚创建还为空)和老数组的长度合法性，同时交代了，
//我们扩容是以2^1为单位扩容的。下面的newThr(新数组的扩容临界值)一样，在原有临界值的基础上扩2^1
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0)
//新数组的初始容量设置为老数组扩容的临界值
newCap = oldThr;
// 否则 oldThr == 0,零初始阈值表示使用默认值
else {
//新数组初始容量设置为默认值
newCap = DEFAULT_INITIAL_CAPACITY;
//计算默认容量下的阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果newThr == 0，说明为上面 else if (oldThr > 0)的情况(其他两种情况都对newThr的值做了改变),此时newCap = oldThr;
if (newThr == 0) {
//ft为临时变量，用于判断阈值的合法性
float ft = (float)newCap * loadFactor;
//计算新的阈值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//改变threshold值为新的阈值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//改变table全局变量为，扩容后的newTable
table = newTab;
if (oldTab != null) {
//遍历数组，将老数组(或者原来的桶)迁移到新的数组(新的桶)中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//新建一个Node<K,V>类对象，用它来遍历整个数组
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//将e也就是oldTab[j]放入newTab中e.hash & (newCap - 1)的位置，
if (e.next == null)
//这个我们之前讲过，是一个取模操作
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 链表重排，这一段是最难理解的，也是JDK8做的一系列优化，我们在下面详细讲解
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
这里我们讲一下关于链表重排的内容：首先命名了两组 Node<K,V> 对象，loHead = null, loTail = null 与 hiHead = null, hiTail = null，这两组对象是为了针对 (e.hash & oldCap) == 0 是否成立这两种情况而作出不同的处理。如果(e.hash & oldCap) == 0，则 newTab[j] = loHead = e = oldTab[j]，即索引位置没变。反之 (e.hash & oldCap) != 0, newTab[j + oldCap] = hiHead = e = oldTab[j]，也就是说，此时把原数组 [j] 位置上的桶移到了新数组 [j+原数组长度] 的位置上了。
这里借用美团点评技术团队【Java 8系列之重新认识HashMap】一文中的部分解释：
我们之前一直说的一个移位运算就是—— a % (2^n) 等价于 a & (2^n - 1)，也即是位运算与取模运算的转化，且位运算比取模运算具有更高的效率，这也是为什么HashMap中数组长度要求为2^n的原因。我们复习一下，HanshMap中元素存入数组的下表运算为**index = hash & (n - 1) **，其中n为数组长度为2的整数次幂。 在上面的图中，n表示一个长度为16的数组，n-1就是15，换算成二进制位1111。这个时候有两种不同的哈希码来跟他进行与操作(对应位置都为1结果为1，否则为0)，这两种哈希码的低四位都是相同的，最大的不同是第五位，key1为0，key2为1； 这个时候我们进行扩容操作，n由16变为32，n-1=32,换算成二进制位11111，这个时候再和key1,key2进行与操作，我们发现，由于第5位的差异，得到了两种不同的结果👇
可以看到，得出的结果恰好符合上面我们将的两种情况。这也就是 JDK8 中扩容算法做出的改进，至于为什么这么搞？这是由于hashCode中新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。
这个时候有些小伙伴可能就有问题了，源码中明明是if ((e.hash & oldCap) == 0) ，并没有减1的操作呀？我们可以看看如果不减1的话，16就是10000，和key1（第5位为0）相与结果为0，而和 key2 （第5位上面为1）就成了16了，也符合上面两种情况。扩容之后同理。
get()方法
HashMap 中的 get() 方法就比较简单了，执行过程就是先检查下标位置的节点，然后在该节点next中检索。源码如下👇
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods.
* * @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
小结
最后对 HashMap 做一个简单的总结：
- HashMap的初始容量是16
- HashMap的容量永远都是2的整数次幂，扩容之后的容量 = 扩容之前的容量*2
- HashMap扩容时机，当HashMap里面的元素个数 > 容量 * loadFactor (默认0.75)
- 当桶里面的元素个数 >= 8(TREEIFY_THRESHOLD)并且HashMap的容量 > 64(MIN_TREEIFY_CAPACITY)，链表转化为红黑树
- 当红黑树里面的元素个数 <= 6（UNTREEIFY_THRESHOLD），红黑树转化为链表
- HashMap是线程不安全的
本人经验有限，有些地方可能讲的没有特别到位，如果您在阅读的时候想到了什么问题，欢迎在评论区留言，我们后续再一一探讨🙇
希望各位小伙伴动动自己可爱的小手，来一波点赞+关注 (✿◡‿◡) 让更多小伙伴看到这篇文章~ 蟹蟹呦(●'◡'●)
如果文章中有错误，欢迎大家留言指正；若您有更好、更独到的理解，欢迎您在留言区留下您的宝贵想法。
爱你所爱 行你所行 听从你心 无问东西