HashMap的内部实现
深入学习Java基础知识
HashMap是用于存储键值对的数据结构，基本的get和put操作时间复杂度是O(1)，效率非常高，在Java 8中又对其进行了一系列优化，比如引入红黑树解决多次哈希碰撞导致的效率降低，还有扩容机制实现的优化。
一、hash函数
我们知道哈希表是通过hash值来快速定位键值在哈希表中的位置，hash值是一个数值，而key可以是任何类型，将键值转化为一个hash值就是通过hash函数来实现的，在HashMap中，hash函数是通过对键值对象的hashCode进行简单转换实现，实现如下
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}这里之所以将原来的hashCode的原本的值与其高16位的进行异或，是为了让hashCode的高16位也参与到计算中，增加离散程度，因为在使用hash值时会通过hash & length - 1来获取键值的索引，length是哈希表的长度，如果不这样做的话，当length小于216时，其实hash值的高16位根本没有用到。当然这只能降低很小的碰撞几率，不过这个操作也不会有多大性能损失。
参考：HashMap.java
注释二、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数组进行扩容。扩容流程大致如下：
- 首先计算新容量大小，一般情况下是旧容量的2倍，更新threshold值，一般情况是
新容量的值 * loadFactor。 - 创建新table数组，将原来数组中的节点转移到新数组中，如果节点没有形成链表或红黑树，则直接通过节点hash得到在新数组中的位置，直接转移即可，如果节点形成了链表或者红黑树，则对其进行拆分然后再转移。
由于容量是2的倍数，且扩容后的容量实际是原来容量左移一位，这样在计算位置时，hash值的二进制位上就可以多取一位，值要么是1，要么是0，所以在扩容之后，原来数组中的节点位置，要么在新数组中同样的位置，要么就是原来容量大小+原来的位置，这样就可以将这种数据分为两个部分，在拆分链表和红黑树时，可以通过这个将数据更加均匀的分散。
下面看看JDK 11中的resize方法中计算容量大小的代码实现。
1Node<K,V>[] oldTab = table;
2int oldCap = (oldTab == null) ? 0 : oldTab.length;
3int oldThr = threshold;
4int newCap, newThr = 0;
5//当前HashMap中有数据时
6if (oldCap > 0) {
7 //如果当前容量超过限制，则不扩容，会增加碰撞几率，但是可以正常使用
8 if (oldCap >= MAXIMUM_CAPACITY) {
9 threshold = Integer.MAX_VALUE;
10 return oldTab;
11 }
12 //扩充新容量为旧容量的2倍，如果没有新容量超过限制，则扩充新阈值为原来阈值的2倍
13 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
14 oldCap >= DEFAULT_INITIAL_CAPACITY)
15 newThr = oldThr << 1; // double threshold
16}
17else if (oldThr > 0) //初始化时指定初始容量或loadFactor时第一次会执行
18 newCap = oldThr;
19else { //初始化时不指定参数时，第一次会执行，设置默认容量和阈值
20 newCap = DEFAULT_INITIAL_CAPACITY;
21 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
22}
23//上面代码如果没有设置阈值，则默认设置阈值为新容量 * loadFactor
24if (newThr == 0) {
25 float ft = (float)newCap * loadFactor;
26 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
27 (int)ft : Integer.MAX_VALUE);
28}
29threshold = newThr;然后是转移原来数组中的键值对节点到新数组中的代码，由于节点可能因为哈希碰撞转化为链表和红黑树，所以需要对这普通节点、链表节点、红黑树节点这三种不同的节点进行区分转移。
1Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
2table = newTab;
3if (oldTab != null) {
4 //遍历转移数据
5 for (int j = 0; j < oldCap; ++j) {
6 Node<K,V> e;
7 if ((e = oldTab[j]) != null) {
8 oldTab[j] = null;
9 //如果当前节点非链表和红黑树节点，直接通过hash计算得到在新数组中的位置，转移即可
10 if (e.next == null)
11 newTab[e.hash & (newCap - 1)] = e;
12 else if (e instanceof TreeNode) //如果是红黑树，则拆分转移
13 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
14 else { // 如果是链表，也拆分转移，根据高低位拆分为两部分
15 Node<K,V> loHead = null, loTail = null;
16 Node<K,V> hiHead = null, hiTail = null;
17 Node<K,V> next;
18 do {
19 next = e.next;
20 if ((e.hash & oldCap) == 0) {
21 if (loTail == null)
22 loHead = e;
23 else
24 loTail.next = e;
25 loTail = e;
26 }
27 else {
28 if (hiTail == null)
29 hiHead = e;
30 else
31 hiTail.next = e;
32 hiTail = e;
33 }
34 } while ((e = next) != null);
35 if (loTail != null) {
36 loTail.next = null;
37 newTab[j] = loHead;
38 }
39 if (hiTail != null) {
40 hiTail.next = null;
41 newTab[j + oldCap] = hiHead;
42 }
43 }
44 }
45 }
46}参考：HashMap.java
注释