HashMap的内部实现

HashMap是用于存储键值对的数据结构，基本的get和put操作时间复杂度是O(1)，效率非常高，在Java 8中又对其进行了一系列优化，比如引入红黑树解决多次哈希碰撞导致的效率降低，还有扩容机制实现的优化。

一、hash函数

我们知道哈希表是通过hash值来快速定位键值在哈希表中的位置，hash值是一个数值，而key可以是任何类型，将键值转化为一个hash值就是通过hash函数来实现的，在HashMap中，hash函数是通过对键值对象的hashCode进行简单转换实现，实现如下

这里之所以将原来的hashCode的原本的值与其高16位的进行异或，是为了让hashCode的高16位也参与到计算中，增加离散程度，因为在使用hash值时会通过hash & length - 1来获取键值的索引，length是哈希表的长度，如果不这样做的话，当length小于2^16时，其实hash值的高16位根本没有用到。当然这只能降低很小的碰撞几率，不过这个操作也不会有多大性能损失。

二、HashMap的存储结构

HashMap使用数组来存储数据，当存入键值对到HashMap时，先通过hash函数计算key的hash值，然后通过hash值得到数据应该在table数组中的存储位置i，创建节点Node对象，将键值对信息存放在Node对象中，如果

• table[i]为空，将新节点赋值给table[i]。
• table[i]不为空，如果table[i]是链表节点，遍历以table[i]为头节点的链表，将新的节点添加到链表尾部，如果table[i]是红黑树节点，遍历table[i]为根节点的红黑树，将新节点添加到红黑树适当的位置。

HashMap使用链表来解决哈希碰撞问题，当链表长度变大时，效率会降低，这时候将链表转化为红黑树，从而提高效率，存储结构图如下

三、扩容机制

HashMap有两个成员变量在扩容时会用到，一个是threshold，存放下一次该扩容的大小，另外一个是loadFactor，用于计算下一次该扩容的大小，一般情况下，threshold = 扩容后大小 * loadFactor，当HashMap存放的键值对数量达到threshold后，将会调用resize方法对table数组进行扩容。扩容流程大致如下：

1. 首先计算新容量大小，一般情况下是旧容量的2倍，更新threshold值，一般情况是新容量的值 * loadFactor。
2. 创建新table数组，将原来数组中的节点转移到新数组中，如果节点没有形成链表或红黑树，则直接通过节点hash得到在新数组中的位置，直接转移即可，如果节点形成了链表或者红黑树，则对其进行拆分然后再转移。

由于容量是2的倍数，且扩容后的容量实际是原来容量左移一位，这样在计算位置时，hash值的二进制位上就可以多取一位，值要么是1，要么是0，所以在扩容之后，原来数组中的节点位置，要么在新数组中同样的位置，要么就是原来容量大小+原来的位置，这样就可以将这种数据分为两个部分，在拆分链表和红黑树时，可以通过这个将数据更加均匀的分散。

下面看看JDK 11中的resize方法中计算容量大小的代码实现。

然后是转移原来数组中的键值对节点到新数组中的代码，由于节点可能因为哈希碰撞转化为链表和红黑树，所以需要对这普通节点、链表节点、红黑树节点这三种不同的节点进行区分转移。