大纲
前言
HashMap底层是使用数组来实现哈希表的。之所以哈希表存储和查询快，是因为往哈希表里面放东西的时候，会先通过key算出一个哈希值(hash)，然后利用这个hash值来与哈希表的容量进行取余运算（取余和取模是由区别的），然后就得到了准确的数组下标，然后就可以快速地进行插入操作；同理查询也一样，通过准确的数组下标就可以快速得到结果。
HashMap解决了什么问题
查询速率不高的问题
因为HashMap是基于数组的，而数组查询速率是很高的，因为：
- 每一个元素的内存地址在空间中是连续的
- 每一个元素类型一样，所以占有空间大小一样
- 知道第一个元素的内存地址，知道了每一个元素的空间大小，又知道了要查的那一个元素的下标，所以通过数学表达式就可以计算出那个元素的准确内存地址，从而直接通过内存地址来定位那个元素，所以数组的查询效率是最高的。
哈希冲突
所谓的哈希冲突就是在插入元素的时候，通过计算得到的数组下标上已经存在元素（一个或多个）了，并且这个元素的key与要插入元素的key值不一样**（通过hash和equal()来判断）**，但又不能把原先那个元素的value给覆盖掉，所以就发生了冲突。HashMap解决这个冲突是同过链表和红黑树来解决的。如果不懂什么是红黑树也没关系，等下源码分析的时候会顺带讲到，现在只要知道它是一个平衡二叉树，并且效率要比AVL树要高就行了。
自动扩容
因为HashMap是基于数组来实现的，但虽然数组查询效率高，但它的长度是固定的，所以如果存的元素多了，很容易造成哈希冲突，达不到一个很好的散列效果。所以必须要对数组进行扩容，所以HashMap里面就会涉及到数组的自动扩容。
从put()方法开始了解源码
二话不说，学习源码之前先放一张UML图，来明确HashMap的继承关系
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kQOLtjC7-1635150735122)(HashMap源码详解.assets/image-20211024143751356.png)]
首先编写一段简单的代码，往HashMap里面放元素
public static void main(String[] args) {
Map<String,String> map = new HashMap<>();
map.put("hello","hello");
}
然后我们点进去看，因为这个方法是在Map接口里面声明了，而HashMap实现了该接口，所以来到HashMap类
public V put(K key, V value) {
//算出key的hash值
return putVal(hash(key), key, value, false, true);
}
我们发现真正执行添加元素的方法是putVal()，并且在这一步我们算出了key对应的hash值。然后继续
下面是执行添加元素的核心方法，遇到长代码先不要慌，先听我分析一下再看。首先putVal()方法主要做的事情就是算出要添加的元素要放到的数组下标是什么，算出下标后然后看看下标对应的那个位置有没有存在的元素，如果为空则直接放进去就行，如果不是则再分析这个原本就存在节点的key值到底和要添加的元素的key值一不一样，如果一样则会有对应操作，否则再继续判断这个节点是不是一棵树的根节点，如果是就再执行对应操作，否则就当成链来处理。然后请大家耐心看完并理解下面的代码。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定义了tab数组用来存放值
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//重新计算数组的长度
n = (tab = resize()).length;
//在这里jdk8使用了‘&’位运算来替代了jdk7的'%'取余运算符，因为位运算的效率更高
//用'&'取余是有限制的，必须是2的n次幂才行，所以规定初始容量必须是2的幂次
//等下会分析一下用'&'的可行性
if ((p = tab[i = (n - 1) & hash]) == null)
//如果对应的数组下标上没有节点，则直接赋一个新的节点上前去就好了
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//第一种情况是存在的key与现在要插进去的key相同(通过hash和equal()方法进行判断)
//理论上，如果一个类的equals方法重写了，那么hashCode()方法必须重写。
//并且equals方法返回如果是true，hashoCode()方法返回值必须一样
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;
}
}
//经过上面那些步骤，如果e不等于空，则说明存在key值与要添加元素的key值相同的情况
//所以接下来就要考虑到底是保留旧值还是用新值覆盖旧值
if (e != null) { // existing mapping for key
V oldValue = e.value;
//这里说明如果onlyIfAbsent为true的话，说明如果旧值存在，则不进行替换。
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//此说明此hashMap被修改的次数加一，在迭代器建立视图的时候会用到
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
笔者第一次看见’&'这个位运算符的时候，最后在网上查了多篇资料然后搞懂了，下面我整理一下我查到的资料。
首先用’&‘取余运算是有限制条件的：使用’&'运算的两个数必须有一个是2的n次幂才行，所以java规定了容量都必须为2的幂次
之所以一定是2的幂次，是因为对于一个数x，它要被除以2的n次方，也就是在位运算中相当把x右移了n位，而刚好被移出去的n位就是我们要求的余数。
其实这也不难理解，我们可以用十进制去理解一下，比如有一个数 1001，然后因为二进制被除以2就可以类比于十进制除以了10，都是向右移了一位，所以1001向右移了一位就是100，然后移出去的那一位是1，所以1001除10的余数就是1。
然后观察一下下面的例子
11%4=3
=> 1011 & (0011) //因为11除4的余数，相当于11化为二进制后向右移动两位，移出去的那两位就是余数。所以用0011与11进行按位('&')与运算，刚好就能得到后两位
=> 1011 & (0100 - 1)
=> 11 & (4 - 1) //在这里把4看所哈希表的容量，就可以理解为什么要规定容量为2的幂次了
综上所述，用 x&(2的n次幂-1) 可以实现取余操作
我们发现在putVal()方法里面有resize()方法，它就是用来实现自动扩容的。
resize()实现扩容的关键
老规矩，先讲诉一下下面的代码主要是干什么的，然后再请读者认真看看下面的代码。首先，进行扩容最棘手的问题就是如何把因为发生了哈希冲突而形成的链或者树重散列映射到新的数组去，无论是树还是链都有一个共通的做法，就是形成一条低位链和高位链，把低位链放在新数组的旧下标下，也就是在旧数组是什么下标在新数组就是什么下标；而高位链则放在新数组的（旧数组下标+旧数组容量）的下标上
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//在一开始阈值是被设0的
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 = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold(两倍的阈值)
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//这里表示旧容量和阈值都为0
newCap = DEFAULT_INITIAL_CAPACITY;//被赋值16
//DEFAULT_LOAD_FACTOR 是0.75
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//被赋值12
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//用新的容量来新建一个数组
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) //如果不是链，则重写计算在新数组的下标(这个很容易理解)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //对树进行处理 split()等下会介绍，不用着急
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //如果当前下标下的元素既不是单个，也不是一棵树的根节点，则当作链表处理
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//下面的循环就是把原来的一条链分为两条，一条是低位链，一条是高位链。
do {
next = e.next;
//下面这个(e.hash & oldCap) == 0 难理解不用怕，下面会讲诉一下
//如果等于零，则说明在新数组中的索引不变
//否则，在新数组中的索引等于就索引加上旧容量
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;
}
(e.hash & oldCap) == 0 到底是什么？
首先先放结论，通过这个算法可以巧妙地把节点分为两类
- 等于0时，该头节点放到新数组时的索引位置等于其在旧数组时的索引位置，它们记为低位 low
- 不等于0时，该头节点放到新数组时的索引等于其在旧数组的索引位置再加上数组的长度。
其实记住上面结论就可以了，但也不妨看看分析。
当(e.hash & oldCap) == 0时的推导
oldCap = 2^4 = 10000
e.hash = 01010 //这个是随便列的，只要满足(e.hash & oldCap) == 0即可
(2*oldCap-1)= 011111
(oldCap - 1) = 01111
//然后我们就会惊奇地发现(2*oldCap-1)&e.hash 与 (oldCap-1)&e.hash的结果是一样的，因为决定结果的(2*oldCap-1)和(oldCap-1)倒数四个低位都是1
//而(2*oldCap-1)&e.hash 和 (oldCap-1)&e.hash 刚好是分别用来算新数组下标和旧数组下标的，然后它们两个算出的结果一样，所有下标在新数组里没有变。
//所以有头节点放到新数组时的索引位置等于其在旧数组时的索引位置的结论
当(e.hash & oldCap) != 0时的推导
oldCap = 2^4 = 10000
e.hash = 11010 //这个是随便列的，只要满足(e.hash & oldCap) == 0即可
(2*oldCap-1)= 011111
(oldCap - 1) = 01111
(2*oldCap-1)&e.hash结果如下
011111
& 11010
----------
11010
(oldCap-1)&e.hash结果如下
01111
& 11010
----------
01010
我们发现，下面的结果加上一个旧容量(10000)就等于上面的结果了，所以也就印证了结论
//不等于0时，该头节点放到新数组时的索引等于其在旧数组的索引位置再加上数组的长度。
然后我们看看resize()中处理树的方法，split()
split()扩容时对红黑树的处理
还是先说说这个方法做了啥。其实这个方法不涉及任何有关红黑树的知识，大家可以无压力阅读，这个方法主要是基于红黑树各个节点所形成的双链表来实现的，而这个双链表是在由单链表节点转为红黑树的时候顺便实现的。所以下面的方法其实跟上面resize()处理链表没什么本质区别，核心都是把链分为低位和高位链。
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//因为红黑树的节点之前除了组成了一棵树的关系外，它们还组成了一条双链表
//所以可以通过简单的遍历这条双链表，来把它分为低位链和高位链
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
//形成一个低位双链表
//bit就是容量
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
//如果小于建树的阈值（6），就把这个由TreeNode组成的双链表换成由Node组成的单链表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) //否则，则可以进行树化
loHead.treeify(tab);
}
}
//高位双链表同样也会这样处理
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
通过看上面的方法，我们还会发现如果红黑树的双链表被分为两条后，如果它们没有到达指定条件去重新生成一棵树的话，就会重新变为普通的单链表。
在将treeify()方法来建立红黑树之前，先介绍红黑树的基础知识
关于红黑树的最少必要知识
首先先列一下红黑树的特性：
- 每个节点要么是红色，要么是黑色；
- 根节点永远是黑色的；
- 所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
- 每个红色节点的两个子节点一定都是黑色；
- 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
红黑树插入后保持平衡
关于往红黑树里插入新的元素，首先按照普通的二叉树的方法来找到正确的位置并插进去(新插进去的节点都会被标记成红色)，然后再分析插完节点后是否有不满足上诉规则的，如果有不满足，则要通过某些方法来使它满足，从而是红黑树重新达到平衡的状态。（下面的图都是子树而不是一棵完整的红黑树!）
- 第一种情况，插入的节点的父节点和其叔节点的颜色都是红色的。（N是新插入的节点）
这种情况很明显不满足上诉的第四条规则，所有要转换一下，变成下图所表示
如果G的父节点也是红色的，这样就又违反了规则四了，但其实这与把红色的N插进去时的场景是一样的。我们可以把G设为新的调整节点，然后重复进行上诉步骤，直到发现了调整节点的父节点不是红色的，那么就停止调整。
- 第二种情况，如果父亲节点是红色的，但叔叔节点是黑色的，像下图
这种情况下，我们可以通过对G节点进行右旋转并且更改相应节点的颜色来达到目的，转换后如下图
- 还有一种情况就是上一种情况的特例，就是插入的节点是父亲节点的右子节点，如下图
然后我们可以通过对P进行左旋转，来使得与上图一样。(转换后如下图)
treeify()建立红黑树(基于双链生成红黑树)
因为在建立红黑树之前，各个节点就已经形成了一条双链表，而双链表的头就是要建立的红黑树的头节点。所以这个方法大概就是遍历链表，然后逐步的把遍历到的节点加入到红黑树之中，如果有不平衡，就通过刚才所述的方法来调整，最终形成了一棵红黑树，代码如下
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
//根节点的hash大于当前节点的
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) //如果是可排序的,dir将被赋为排序后的结果
//当 hashCode 相等且不可比较时，就用下面的方法打破僵局
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
//在这里p被设为了左节点或右节点，如果不为空则继续循环下去，找到为空的为止
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
//hash值比根节点小的放左边
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//确保保证红黑树插入后的自平衡性
root = balanceInsertion(root, x);
break;
}
}
}
}
//确保给定的根节点是bin(桶)的第一个节点
//因为在上诉操作中，root节点可能发生变化，所以要重新确保。
moveRootToFront(tab, root);
}
上面的代码主要是把节点插到树里面，而确保平衡性的是调用了 balanceInsertion(root, x) 方法
untreeify()把双链变单链
如果双链表在经过split()方法拆分后，发现其不足以形成一棵新的红黑树，所以就要使用untreeify()来使双链表退化为单链表
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
balanceInsertion()确保插入后的平衡性
这个方法主要就涉及如果发现不平衡，就通过旋转来确保平衡性，下面是代码
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//如果没有父节点，说明这个是根节点
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//如果x的父节点不是红色，或者x的父节点就是根节点(因为祖父节点为空)
//这是不会影响红黑树的平衡性，所有直接返回root
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//如果父节点是祖父节点的左子节点
if (xp == (xppl = xpp.left)) {
//如果祖父右字节的为红色
if ((xppr = xpp.right) != null && xppr.red) {
//把祖父节点的左右子节点变为黑色，然后它自己变为红色，
//然后继续把祖父节点设为新的调整节点，然后继续循环调整
//直到调整节点的父节点不是红色的，就完成了
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//如果调整节点是父节点的右字节的，则要多进行一次左旋调整。
if (x == xp.right) {
//对xp进行左旋
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
//对xpp进行右旋
root = rotateRight(root, xpp);
}
}
}
}
//下面是上面的对称操作
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
至此，split()方法中对红黑树的处理就完成了，并且知道了resize()方法是怎样实现扩容的。
然后我们继续沿着putVal()方法往下看，然后我们发现了如果要插入的那个桶存在节点，并且那个节点就是树的根节点的时候，就会调用putTreeVal()
putTreeVal()往红黑树里插入数据
这个方法很简单，主要就是先找到要插入位置，然后插进去，再平衡一下，最后把root节点设为当前桶的节点（也是双链表的头节点），代码如下
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//放到左边
if ((ph = p.hash) > h)
dir = -1;
//放到右边
else if (ph < h)
dir = 1;
//如果遇到key值一样的，返回当前treeNode元素
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
//如果要插入的左子节点或右子节点不是空的，继续循环
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
继续在putVal()方法往下看，然后我们发现在对链处理的时候，会调用到treeifyBin()方法，目的是如果单链的长度在大于8的时候，就要生成红黑树，提高查找的效率。所以treeifyBin()就是把单链进化成双链，然后再调用treeify()方法基于双链生成一棵红黑树，代码如下
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;
//把单链表变成(TreeNode)双链表
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);
}
}
至此，往哈希表里放元素的原理就基本讲完了，下面对一些常见的问题进行总结
总结
为什么HashMap的容量一定是2的幂次
直接求余效率不如位移运算，正因为容量是2的幂次，所以才可以用’&‘来替代取余运算符’%’
为什么负载因子是0.75
我们知道，threshold(阈值)在一开始是通过负载因子乘以初始容量16来获取的，也就是 0.75*16=12，而为什么要设为0.75，官方文档的解释是：理想情况下，在随机 hashCodes 下，bins 中节点的频率遵循泊松分布 (http:en.wikipedia.orgwikiPoisson_distribution)，对于默认调整大小阈值 0.75，参数平均约为 0.5。
加载因子过高：
例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本。
加载因子过低：
例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash操作的次数。