一、介绍
本期为大家介绍java集合框架中的Map一族，Map完全不同于Collection。从api上来看，Collection是以线性表的方式保存一个集合，而Map提供给我们的是<K，V>键值对映射，通过key获取对应的value。
看一下Map家族的UML类图：
Map家族由Map抽象接口定义，常用的实现类有线程不安全的HashMap、线程安全的HashTable、底层为红黑树的TreeMap、在节点上添加前驱后继以表示节点的插入顺序的LinkedHashMap，而今天我们的重点就是HashMap。
Map顾名思义，就是映射的意思，当我们向map对象传入一个关键字key时，它会返回给我们一个对应的value；当我们要向map对象传入一个数据value的同时，也要向其中传入该value所对应的关键字key。这与我们前面的Collection集合文章中所讲的有所不同，Collection集合是一个线性表，其中保存的是数据value本身，而非key → value这样的映射。
二、类的声明
我们来看一下HashMap的声明，可以大致了解他的功能。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
- 继承了AbstractMap类，提供了一些Map相关的基本功能如添加、删除、判空、获取元素数量等。
- 实现了Map接口，说明HashMap是一个以
<K，V>键值对存储数据的结构 - 实现了Cloneable接口，提供了对象克隆方法，但请注意，是浅克隆。
- 实现了Serializable接口，支持序列化。
三、底层实现
HashMap是以哈希表作为底层实现的，通过key的哈希函数与数组长度计算出其位于数组的下标。当发生冲突时，即两个key需要保存到同一个数组下标位置时，采用拉链法来解决hash冲突，将键值对保存在一个线性表(如链表)中，线性表的首部放在对应的数组中即可。
如果大量的key发生hash冲突，导致这些键值对被保存在同一个线性表中，从而使该线性表中出现大量数据，最后导致遍历效率降低，因此当线性表达到一定的长度后，hashMap将该链表进化为红黑树，红黑树的遍历效率自然要比线性表好得多。相反地，当红黑树中数据减少到一定数量后，红黑树再退化为线性表。
如下图所示
四、内部类Node与TreeNode
在HashMap中，当我们要向其中保存一个键值对时，HashMap会根据该键值对对应的数组下标，判断当前下标保存的是线性表还是红黑树，如果是红黑树，则根据键值对创建一个TreeNode对象，并将其保存到对应的红黑树中。如果是线性表，则根据键值对创建一个Node对象，并将其保存到对应的线性表中。
我们看一下这两个内部类的UML图，红色实线有➕的一端表示内部类，绿色虚线表示实现接口，蓝色实线表示继承关系。
从上图可以清楚的看到，HashMap.TreeNode继承于LinkedHashMap.Entry，LinkedHashMap.Entry继承于HashMap.Node，HashMap.Node实现了Map.Entry。因此，HashMap中的所有节点，无论是Node对象，还是TreeNode对象，都可以认为是Entry接口的对象。理解这四个内部类对理解HashMap底层结构哈希表的节点是很重要的。
判断方法
在HashMap中，每个节点都是Node对象，而TreeNode是Node的子类，因此可以通过node instance of TreeNode来判断该node对象的实际类型是否为TreeNode
两个内部类的属性如下所示：
Node类
static class Node<K,V> implements Map.Entry<K,V> { // 根据key计算出的哈希值 final int hash; // 传入的key final K key; // 传入的value V value; // 线性表中当前节点的下一个节点 Node<K,V> next; }TreeNode类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { // 当前节点的父节点 TreeNode<K,V> parent; // red-black tree links // 左孩子节点 TreeNode<K,V> left; // 右孩子节点 TreeNode<K,V> right; // 进化为红黑树之前，当前节点前面的节点 TreeNode<K,V> prev; // needed to unlink next upon deletion // 默认为红色节点 boolean red; // 以下属性继承自父类LinkedHashMap.Entry，分别表示当前节点的前驱后继 Entry<K,V> before, after; // 以下属性继承自父类HashMap.Node // 根据key计算出的哈希值 final int hash; // 传入的key final K key; // 传入的value V value; // 链表进化为红黑树之前，当前节点后面的节点 Node<K,V> next; }
五、成员变量
// 默认的初始容量为16，即哈希表数组的长度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量为2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的加载因子，当前键值对数量 > 容量*加载因子0.75时，将会对该数组进行扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当数组长度>=64，且链表长度达到8时，则将链表进化为红黑树
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
// 红黑树中节点数量<=6时，则将红黑树退化为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 哈希表的数组
transient Node<K,V>[] table;
// 哈希表中所有节点的set集合
transient Set<Map.Entry<K,V>> entrySet;
// 哈希表中节点数量
transient int size;
// 结构性修改次数，用于快速失败
transient int modCount;
// 扩容的阈值，值为容量*加载因子0.75
int threshold;
// 加载因子，可以由构造函数指定，但不建议这样做，0.75是减少哈希冲突的最优解
final float loadFactor;
六、构造方法
HashMap提供了以下四个构造方法来创建实例
无参构造
通过该方法实例的HashMap对象的所有属性均为默认值，如数组长度为16等，且数组的实例化延迟到首次调用put()方法时
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }通过初始容量实例化
指定底层数组的初始长度，并使用默认的加载因子0.75。
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }通过初始容量和加载因子实例化
指定初始容量和加载因子，并对这两个参数进行非法校验；对传入的初始容量重新计算获取一个大于等于该容量且为2的n次方的最小值作为底层数组的实际容量，该计算过程在tableSizeFor()方法实现，具体实现我们下面会聊。
另外发现，通过tableSizeFor()方法得到的实际容量赋值给
threshold了，但是threshold表示的并不是数组的实际长度而是扩容的阈值。这是因为HashMap在实例化底层数组时采用的是延迟策略，此时底层数组还未实例化，因此也就无从指定其长度，单独使用一个内部属性表示数组长度的意义不大，且数组长度本来就是通过数组.length表示的。因此在这里只是借用threshold属性表示数组实例化前的实际长度。即数组为空时threshold表示数组长度。在聊扩容resize()方法时我们会再次说到这个问题。public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }通过传入一个Map对象实例化
该方法主要是通过调用
putMapEntries()方法，从传入的map对象中获取包含所有entry节点(Node对象或TreeNode对象)的集合，通过遍历这个集合，将集合中的entry对象逐个插入到该HashMap对象中。但在此之前会根据传入的map集合中的数据量以及当前HashMap对象的底层数组是否为空，来判断是否需要扩容或重新计算底层数组的初始大小。putMapEntries()方法将在后面讲到。public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
七、hash()方法
此方法将根据指定的key，获取其对应的hash值，hash值用来确定数组下标。
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* 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);
}
符号>>>为无符号右移，高位补0。hash值的计算过程如下：
为什么不直接使用key的hashcode()值，而是将hashcode的高16位与低16位异或结果作为hash值？
首先看一下我们是如何获取数组下标的。
// 数组长度
n = tab.length;
// 数组下标
i = (n - 1) & hash;
我们来比较一下直接使用key的hashcode值作为hash值 和 将hashcode的高16位与低16位异或结果作为hash值的区别，我们以数组长度n=16为例：
- 如果直接使用hashcode作为hash值，由于数组长度-1导致低4位为1，其余高28位均为0。导致仅仅在高28位变化的那些hashcode与15进行与运算后得到的结果一致，从而发生碰撞。已知的例子是在小表中保存连续整数的Float键集。
- 经过高16位与低16位的异或运算而得到的hash值，是一种比特传播速度、效率、系统损失之间的权衡，通过这种方式，可以在尽量减少碰撞的同时也减少系统损失。
我们把此方法上面的注释看一下就知道了。
计算key.hashCode()并将较高的散列位扩散到较低的散列位。
因为表使用的是2的幂掩码，所以仅在当前掩码以上的位上变化的哈希集总是会碰撞。(其中一个已知的例子是在小表中保存连续整数的Float键集。)因此，我们应用了一个转换，将较高位的影响向下扩散。这里涉及到比特传播的速度、效用和质量之间的权衡。
因为许多常见的哈希集已经合理地分布(因此不会从扩散中受益)，而且因为我们使用树来处理箱子中的大型碰撞集，所以我们只是以最便宜的方式对一些移位的位进行XOR，以减少系统损失，并合并由于表边界而永远不会在索引计算中使用的最高位的影响。
另外，从这个方法中我们也应该知道，在hashMap中保存的key，必须重写hashcode()方法，如String、Integer。
八、comparableClassFor()方法
该方法接收一个对象obj，返回该对象所表示的类。前提是该对象对应的类，必须直接实现Comparable接口，并且Comparable的泛型是该对象对应的类本身。否则就返回一个null。
例如：
// String类直接实现了Comparable接口，且传入的泛型为自己本身。
public final class String implements Comparable<String>
我们看一下这个方法怎么做的：
/**
* Type：Classs实现的接口，也表示一个类
* ParameterizedType：具有泛型的接口，继承于Type接口
**/
static Class<?> comparableClassFor(Object x) {
// 如果x不是Comparable的子类，则不啰嗦直接返回null
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
// 如果参数x是String类型的，直接返回String
if ((c = x.getClass()) == String.class) // bypass checks
return c;
// 调用getGenericInterfaces()获取直接实现的所有接口ts，并遍历ts
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
// 遍历过程中，如果当前接口是具有泛型的接口，
if (((t = ts[i]) instanceof ParameterizedType) &&
// 并且当前接口为Comparable接口，
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
// 并且泛型数量只有一个且该泛型与参数x的类相同。
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
// 则返回x的类
return c;
}
}
}
return null;
}
九、tableSizeFor()方法
该方法接收一个int类型的参数，通过一系列的位运算，返回一个大于等于该参数的最小的2的n次方。如传入9，返回16；传入16，返回16。
源码如下图所示，其中>>>表示无符号右移， |=表示或运算并赋值，即 a|=b 表示 a=a|b。
/**
* 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;
}
我们以传入参数cap=257为例，257的二进制表达为100000001。
int n = cap - 1，此时n=256，即100000000n |= n >>> 1，将n与n无符号右移1位的结果进行或运算，并将结果赋值给n。此时n=110000000
n |= n >>> 2，将n与n无符号右移2位的结果进行或运算，并将结果赋值给n。此时n=111100000
n |= n >>> 4，将n与n无符号右移4位的结果进行或运算，并将结果赋值给n。此时n=111111110
n |= n >>> 8，将n与n无符号右移8位的结果进行或运算，并将结果赋值给n。此时n=111111111
n |= n >>> 16，将n与n无符号右移16位的结果进行或运算，并将结果赋值给n。此时n=111111111
(n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1因为此时
n=111111111，即511，补全高位后n=00000000 00000000 00000001 11111111，最高位为0，说明为非负数。所以最终计算结果为
n+1= 511 + 1 = 512。即2的9次方。
在这几个右移和或运算的过程中，我们发现它的目的就是将最高有效位以及后面的位都置为1，再配合最后一步的n+1使得结果变为2的n次方。
为什么在这个方法的首行要进行减1操作呢int n = cap - 1？
我们先把这行代码去掉，那么该方法就如下所示：
static final int tableSizeFor(int n) {
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;
}
如果我们传入参数n=4，即n = 4 = 100，按照上面的方法进行一系列运算后，得到的n = 111 = 7，在最后一行会再进行一次n + 1操作，得到的结果就变成了8，因此得出结论，如果不进行减1操作，那么返回的结果将是大于该参数的最小的2的n次方，这与本方法的预期结果不一致。
所以int n = cap - 1的目的就是为了避免传入的参数恰好为2的n次方而导致结果不符合预期。
十、扩容原理
HashMap的扩容方法resize()高达70行代码，可谓是相当多了，很多初次接触的同学面对这么多代码可能会直接劝退，但如果静下心来梳理的话，其实也就两部分：
- 确定扩容后的新容量和下次扩容的阈值，并根据新容量创建一个新数组。
- 将原数组中的数据放在新数组中
现在我们根据梳理出来的两部分，看一下完整的源码：
final Node<K,V>[] resize() {
// 确定扩容后的新容量和下次扩容的阈值
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
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
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// preserve order
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;
}
下面我们以梳理出来的两部分内容，来看一下其中的细节
1.确认新的容量和阈值
我们把这一部分源码再次贴出来具体分析一下其中的细节
// 确定扩容后的新容量和下次扩容的阈值
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
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
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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];
首先，获取原数组的容量
oldCap，即原数组的长度。由于HashMap对底层结构采用延迟初始化的策略，就是说实例化HashMap对象时，其实并没有立即对底层结构实例化，底层数组依然为空，因此当我们首次像该HashMap对象中put数据时，才会通过扩容来创建底层数组的实例。而当底层数组为空时，就认为数组长度为0即可。
int oldCap = (oldTab == null) ? 0 : oldTab.length;获取原阈值，即
threshold我们在聊构造方法时，如果我们指定了数组的初始容量，HashMap使用
tableSizeFor()方法重新确定容量时，将确定的容量赋值给阈值threshold了，如下所示：public HashMap(int initialCapacity, float loadFactor) { // ...... this.threshold = tableSizeFor(initialCapacity); }因此，阈值
threshold可能表示其本省的含义此时为0，也可能暂时表示底层数组长度。确定新数组的长度
newCap和下次扩容时的阈值thresholdif (oldCap > 0) { 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 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];如果原数组容量大于0，说明原数组已经初始化了，相应的阈值也已经设置过了。
此时只需要将原数组容量 2作为新数组容量，原阈值 2作为新阈值。
如果原数组容量为0，说明原数组还没有初始化，这种情况针对的是两个参数的构造方法。
这时如果原阈值大于0，说明该原阈值目前只是暂时表示数组长度，就回到了上面的问题了，只需要将该原阈值作为新数组容量就可以了。然后再根据 数组容量 * 加载因子
loadFactor的值 作为 新的阈值即可。如果原数组容量为0，原阈值也为0，这种情况针对的是无参构造方法。
这是只需要将新数组容量设置为默认的初始容量，新阈值设置为默认的初始容量与加载因子的乘积即可。
2.将原数组中的数据放在新数组中
同样，我们也把这一部分源码再次贴出来具体分析一下其中的细节，看起来很复杂吧，别慌。
其中判断节点位于原数组和新数组中的下标是否变化，下一节会详细介绍
Node<K,V>[] oldTab = table;
table = newTab;
if (oldTab != null) {
// 遍历原数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 获取原数组中下标为j的节点e
// 并将原数组中下标为j的节点设置为空
oldTab[j] = null;
if (e.next == null)
// 如果节点e没有后置节点，即表示该位置不存在链表或红黑树
// 通过节点e的hash值与新数组的容量计算出节点e在新数组中的下标
// 并将e放在该下标处
// 以下代码处理该位置仅有一个节点的情况
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 节点e为TreeNode对象，即表示该位置存在以节点e为根的红黑树
// 以下代码处理红黑树情况
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// preserve order
// 节点e既有后置节点，又不是TreeNode对象，即表示该位置存在以节点e为头节点的链表
// 以下代码处理链表情况
// loHead表示从原数组移动至新数组的过程中下标不变的链表的头节点
// loTail表示从原数组移动至新数组的过程中下标不变的链表的尾节点
// 简单点说，以loHead为头节点的链表在原数组与新数组的下标相同，loTail是该链表的尾节点
Node<K,V> loHead = null, loTail = null;
// hiHead表示从原数组移动至新数组的过程中下标变化的链表的头节点
// hiTail表示从原数组移动至新数组的过程中下标变化的链表的尾节点
// 简单点说，以hiHead为头节点的链表在原数组与新数组的下标不同，hiTail是该链表的尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
// 遍历以节点e为头节点的链表
next = e.next;
// 如果下标不变，则为true
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;
}
}
}
}
}
3.对红黑树的处理
上面代码中直接处理单节点和链表这两种情况，而当遇到红黑树时调用split()方法单独处理，该方法由HashMap内部类TreeNode提供。
注意：虽然当前处理的是红黑树，但是别忘了TreeNode中依然存在一个next属性，也就是说，当我们以left和right遍历时，它是红黑树；当我们以next遍历时，它是链表。这对下面的方法实现很重要。
下面我们看一下此方法如何实现
// map - hashMap对象
// tab - hashMap对象中的新数组
// index - 红黑树根节点位于hashMap对象中原数组的下标
// bit - hashMap对象中原数组的长度
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
// 红黑树的根节点
TreeNode<K,V> b = this;
// 下面四个对象的含义与上面遇到的相同
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
// lc和hc都表示当前红黑树中节点数量，它两个的区别与上面四个对象的区别一样
int lc = 0, hc = 0;
// 通过next，将红黑树以链表的形式遍历，并记录红黑树中的节点数量
// 遍历结果，获得以loHead为头结点、以loTail为尾节点的链表，或以hiHead为头结点、以hiTail为尾结点的链表
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
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块代码逻辑相同，分别处理位于数组的下标不变和变化两种情况。只会处理一个，
// 并且根据红黑树中节点数量是否小于UNTREEIFY_THRESHOLD，来判断是否将红黑树退化为链表
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
// 将红黑树退化为链表，因为当前已经将红黑树遍历成链表了
// 因此只需要将各个节点从treeNode对象转为Node对象即可
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
// 将遍历出的链表再转为红黑树
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);
}
}
}
如何将链表转为红黑树，其实它的原理与HashMap的关系不大了，可以参考一下我们之前的文章红黑树
4.通过图例理解扩容细节
现在我们通过图片好好分析一下扩容原理，以下图为例，对其进行扩容，其实按照扩容阈值threshold = capcity * 0.75早就应该扩容了，这里只是为了演示。
首先遍历到原数组的下标为0的节点W，发现该位置存在链表，如下图所示
遍历到原数组的下标为1的节点X，发现该位置仅有一个节点X，不存在链表和红黑树，如下图所示
遍历到原数组的下标为3的节点X，发现该位置存在链表，如下图所示
遍历到原数组的下标为7的节点Z，发现该位置存在红黑树，如下图所示
5.如何判断出下标是否变化
在源码中，我们看到，节点位于原数组与新数组的下标是否相同，可以通过(e.hash & oldCap) == 0来判断，
例如我们有一个原数组oldTab.length = 8，一个新数组newTab.length = 16。在原数组中有两个节点A和B，且A.hash=9，B.hash=3。
如下图所示
十一、putVal()
1.源码解读
在HashMap中，final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)方法是所有存放数据的核心方法，是面试中常见的知识点之一。j下面我们贴上源码来分析一下
/**
* hash - 根据参数key调用 hash(Object key) 方法得到的hash值
* key - 传入的key
* value - key对应的value
* onlyIfAbsent - Absent为缺席的意思，ture - 在当前哈希表中不存在当前key的情况下，才会保存或覆盖该key对应的value
* evict - 该参数用于LinkedHashMap的putVal()方法，在HashMap中可忽略该参数，
* 返回 - 如果产生了value覆盖，则返回原value，否则返回为空
**/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果底层数组为空，或其长度为0，则通过扩容的方式对底层数组初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根据key对应的hash值，与数组长度减一，进行与运算，得出该key应保存在数组位置的下标
// 如果该下标处没有数据，则直接通过newNode()来实例化一个Node对象，并保存在该数组位置。
if ((p = tab[i = (n - 1) & hash]) == null)
// 已经通过hash值确定了数组下标
// 处理当前位置不存在数据的情况
tab[i] = newNode(hash, key, value, null);
else {
// e表示将要保存的Node对象
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 如果当前位置所保存数据的hash值、key值与将要保存数据的hash值、key值相同，则将该Node对象作为要保存的Node对象e，进行value的覆盖
e = p;
else if (p instanceof TreeNode)
// 如果当前位置所保存数据是TreeNode对象，说明该位置保存的是一个红黑树
// 调用TreeNode类的putTreeVal把将要保存的数据保存到红黑树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 当前位置既有数据，但其key与将要保存的key不相同，且该位置保存了一个链表
for (int binCount = 0; ; ++binCount) {
// 遍历链表并记录该链表上node对象的数量binCount
if ((e = p.next) == null) {
// 以尾插法的方式，通过newNode()来实例化一个Node对象，并保存在该链表尾部，并结束遍历
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 如果该链表上node对象的数量达到8个，则调用treeifyBin()方法将该链表进化为红黑树。
// 注意，在该方法中，还会进一步判断数组长度，
// 当数组长度达到64时，才会真正的将其进化为红黑树
// 否则，仅仅将数组进行扩容
treeifyBin(tab, hash);
break;
}
// 在遍历链表的过程中，如果某个node对象的hash值和key值与将要保存的hash值和key值相同，则结束遍历
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 遍历链表的操作
p = e;
}
}
// 如果在上面的逻辑中，找到了key值相同的node对象，则将value值进行覆盖
if (e != null) {
// existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 至此，数据key-value已经保存到哈希表中了
++modCount;
if (++size > threshold)
// 如果当前哈希表中的节点数量超过扩容阈值(即 数组长度 * 0.75)，则对数组进行扩容。
resize();
// 该方法在LinkedHashMap中实现，作为插入数据后的回调
afterNodeInsertion(evict);
return null;
}
在上面的注释中我们已经把该方法讲的非常透彻了，下面再通过简洁的叙述对其进行概括
当我们向HashMap中保存一个key-value键值对时
如果地层数组尚未实例化，或数组长度为0，则通过扩容对其进行实例化以及初始化
首先，通过key计算出的hash值，找到当前key-value键值对应保存的位置，即数组的下标
如果数组该位置没有数据，则直接将key-value键值对保存在该位置即可。
如果该位置有数据，则通过判断key是否相同(通过
equals()方法)，如果key相同，则将value值进行覆盖，并返回原value值。注意：判断key是否相同时，
(k = e.key) == key || (key != null && key.equals(k))说明key是允许为空的判断该位置数据的类型(红黑树或链表)，并以不同的方式遍历红黑树或链表，在遍历的过程中，依然是通过判断key是否相同(通过
equals()方法)，如果key相同，则将value值进行覆盖，并返回原value值。否则，将以红黑树或链表的方式将该key-value键值对保存到红黑树或链表中。
2.图例
下面再以图例进行分析
当我们插入一个
key=F，value=6的键值对时，通过hash()方法得出F的hash值为6，根据hash & length - 1得到该键值对应保存在数组下标为2的位置。而下标为2的位置上为空，因此直接将该键值对保存到该位置即可。
当我们插入一个
key=G，value=7的键值对时，通过hash()方法得出G的hash值为0，根据hash & length - 1得到该键值对应保存在数组下标为0的位置。而下标为0的位置上已经存在一个key-value键值对(A-1)了，因此比较A是否与G相等，因为A ≠ G，所以通过尾插法将 < G - 7 > 插入到 < A - 1 > 后面
当我们插入一个键值对 < D - 8 > 时，通过
hash()方法得出D的hash值为5，根据hash & length - 1得到该键值对应保存在数组下标为1的位置。而下标为1的位置上已经存在一个key-value键值对(B-2)了，因此比较D是否与B相等，因为D ≠ B，所以通过节点的next属性来遍历链表，然后遍历到键值对 < C - 3 > ，比较C是否与B相等，因为D ≠ C，所以继续通过next属性遍历。当遍历到键值对 < D - 4 > 时，比较D是否与D相等，因为D == D，所以将value值进行覆盖即可。
如果插入一个键值对 < H - 9 > 时，通过
hash()方法得出H的hash值为3，根据hash & length - 1得到该键值对应保存在数组下标为3的位置。而通过key值的判断，E ≠ H，所以需要通过遍历红黑树的方式找出该红黑树中key也等于H的节点并将其value值进行覆盖，如果没有找到key也等于H的节点，则将键值对 < H - 9 > 构造成TreeNode对象，以红黑树的插入方式，将该对象插入树中。红黑树的操作可参考前面的文章红黑树当插入操作完成后，再判断当前链表是否需要进化为红黑树，当前数组是否需要扩容。
3.小结
延迟初始化
底层数组在第一次调用put()方法是通过resize()扩容进行实例化的。
当出现哈希冲突或扩容，且当前位置为链表时，采用尾插法将节点插入到链表
key可以为空，value也可以为空
先插入，后扩容
插入的数据是无序的，从整个流程中并没有什么信息能体现出插入顺序。
十二、putMapEntries()
在HashMap中，final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)方法是所有存放批量数据的核心方法。由于是存放批量数据，所以聪明的小伙伴可能会想到是遍历一个数据集合并对集合中的每一条数据调用putVal()方法进行存放。下面我们贴上源码来分析一下
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 获取集合大小，
int s = m.size();
if (s > 0) {
// 如果底层数组尚未实例化，则需要计算出满足该数据量的数组长度和响应的阈值，避免在保存数据的时候频繁扩容
if (table == null) {
// pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
// 如果底层数组已经实例化过了，且要保存的数据量大于扩容阈值，则进行扩容
else if (s > threshold)
resize();
// 将参数map集合，转换为entry的set集合，并对每一个entry进行遍历，通过putVal()将每一个entry中的key和value保存到哈希表中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
这个方法其实没什么好说的，无非就是判断底层数组是否需要扩容，然后对map集合进行批量插入。但即使是批量插入，最终也是循环调用putVal()方法将集合数据逐个插入的。
其中有一行代码对于初次阅读源码的同学可能有所疑惑
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// ...
float ft = ((float)s / loadFactor) + 1.0F;
// ...
}
((float)s / loadFactor) + 1.0F; 为什么要将 集合大小s 除以 加载因子loadFactor 的值 再加一 呢？
首先我们要知道执行这行代码的前提是底层数组为空，因此在批量插入后，集合大小就是当前hashMap对象的数据量了。还有一个就是HashMap的扩容机制是当数据量 = 底层数组长度 * 加载因子loadFactor 时，需要扩容。也就是说，当 数据量 / 加载因子loadFactor = 底层数组长度 时需要对其扩容。因此，如果我们把底层数组的初始长度设置为 数据量 / 加载因子loadFactor 时，其实就需要第二次扩容了，为了避免这第二次扩容，将其商值加一是非常不错的办法。
所以 集合大小s 除以 加载因子loadFactor 的值 再加一 就是为了在确定底层数组长度时一步到位，避免频繁扩容。同时也可以使底层数组的空间利用率最大化。
说到这里，我发现putMapEntries()这个方法有个比较矛盾的地方，不知道大家注意到没有
在else if (s > threshold)这个代码块中，如果结果为true，则执行一次resize()进行扩容。我们来分析一下：
进入该代码块的前提是底层数组已经实例化过了，其扩容阈值为threshold，当我们要插入的集合map的数据量s大于该阈值时，进行一次扩容。问题来了
如果集合map的数据量大于该阈值，仅扩容一次就够了吗？
试想一下，数组长度为16，则阈值为12，当前哈希表中有11个 键值对。此时我需要批量插入一个数据量为100的数据量，按照源码进行一次扩容，扩容后的数组长度为32，则阈值为24，而我要插入100个 键值对，况且现在已经存在11个了，这种情况下，在遍历集合并调用putVal()方法保存数据时，依然会进行多次扩容，直到数组长度为256，阈值为192，也就是说在遍历期间将会再扩容3次。
因此，集合map的数据量大于该阈值，仅扩容一次可能是不够的，为什么不能像上面那样一步到位，从而避免频繁扩容呢？
所以我说这个方法比较矛盾，是因为它既做到了一步到位，又没有做到一步到位。
十三、getNode()
在HashMap中，getNode()方法是所有查询方法的核心，他提供了查询的基本思路，是面试中最重要最常遇到的问题。它的实现思路非常简单，我们先看一下源码实现：
/**
* hash - 参数key对应的hash值
* key - 通过key获取对应的<key,value>键值对
* 返回<key,value>键值对
**/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 如果底层数组不为空，且底层数组长度大于0，且hash值对应的数组下标位置上的元素不为空，才进行下面的逻辑
// 否则说明不存在key对应的键值对，直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// first即代表底层数组当前位置的元素。
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
// 如果当前位置的元素的hash值和key与传入的hash值和key相同，则说明当前位置的元素即为要查找的元素，返回该元素即可
return first;
if ((e = first.next) != null) {
// 当前位置的元素的key与传入的key不相同，则根据当前位置元素的类型进行遍历
if (first instanceof TreeNode)
// 如果当前位置元素类型为TreeNode，说明为红黑树
// 则遍历红黑树，找到其中key与传入的key相同的节点并返回，如果没找到，则返回null
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 当前位置元素类型为Node，说明为链表
// 则遍历链表，找到其中key与传入的key相同的节点并返回，如果没找到，则返回null
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
从上面的注释中，我们可以看出来，查找键值对时通过hash值和key进行的，hash值用来确定数组下标，key用来和已确定的数组下标位置上的元素进行equals()比较(包含下标位置的元素，或红黑树中的元素，或链表中的元素)。
下面我们用以下图示举例，该底层数组长度为8：
查询
key=U的节点，其对应的hash值为2，通过(n - 1) & hash计算得出其对应的下标为2由于下标为2的位置元素为空，因此直接返回空。
查询
key=X的节点，其对应的hash值为9，通过(n - 1) & hash计算得出其对应的下标为1查找下标为1的元素，其
key=X，与要查询的节点的key相同，因此返回该元素查询
key=C的节点，其对应的hash值为8，通过(n - 1) & hash计算得出其对应的下标为0查找下标为0的元素，其
key=W，与要查询的节点的key不同，且该节点为链表，key=W的next不为空，因此通过next遍历链表；遍历的下一个元素，其
key=A，与要查询的节点的key不同，key=A的next不为空，继续遍历；遍历的下一个元素，其
key=B，与要查询的节点的key不同，key=B的next不为空，继续遍历；遍历的下一个元素，其
key=C，与要查询的节点的key相同，则说明查找成功，返回该键值对。查询
key=T的节点，其对应的hash值为7，通过(n - 1) & hash计算得出其对应的下标为7查找下标为7的元素，其
key=Z，与要查询的节点的key不同，且该节点为红黑树，因此通过遍历红黑树的方式，直到找到某个元素的key与我们要查找的key相同。将该元素返回即可。
1.小结
由于查找元素是通过hash值和key.eqauls()方法进行的，而hash值是通过key.hashcode()方法得到的，所以我们使用的key应当以合适的方式去实现equals()方法和hashcode()方法。所以经常会有面试官问你，可以用自己定义的类作为HashMap的key吗？ 这时你应该知道怎么回答了吧。
十四、removeNode()
removeNode()方法是HashMap中删除键值对方法的核心。如果同学们理解了getNode()方法，那么removeNode()方法自然就迎刃而解了。该方法实现思路分为两步：①找到要删除的节点，②删除该节点。看一下源码
/**
* hash - key对应的hash值
* key - <key, value>的key
* value - <key, value>的value
* matchValue - 匹配value，如果为true，则当查找到的键值对的key和value都匹配时，才会删除该键值对
* movable - 删除节点后是否移动，true-移动。false-不移动。可忽略该节点，仅在操作红黑树时生效
**/
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// 以下逻辑为根据key查找到对应的键值对，其实现与getNode()方法一致，
// 在遍历过程中会记录当前节点的前驱p
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 以下逻辑为删除节点。
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
// 该方法在LinkedHashMap中实现，作为插入数据后的回调
afterNodeRemoval(node);
return node;
}
}
return null;
}
因为上面我们已经详细聊过getNode()方法了，因此这里的查找部分我们就忽略掉。直接进入删除节点部分即可。
在删除部分，如果传入的matchValue参数为true，代表着更严格的删除条件：当查找到的键值对的value值与我们传入的参数value值也相同时，才会对该键值对进行真正的删除，否则不会删除。但如果传入的matchValue参数为false，则直接将查找到的键值对删除即可。
由于在遍历的过程中，记录了当前键值对的前驱p，而每一个键值对都是通过next组成链表或红黑树的，所以：
- 如果是红黑树，则按照红黑树的方式删除，由于过于繁琐，同学们可查看另一篇文章红黑树
- 如果不是红黑树，则直接通过
p.next = node.next;将当前键值对的后继作为前驱p的后继。
十五、常用方法
1.put()
保存一个 键值对
参考核心方法putVal()，注意，如果传入的key已存在，则覆盖其对应的value
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
2.putIfAbsent()
保存一个 键值对
参考核心方法putVal()，注意，如果传入的key已存在，则不覆盖其对应的value，与put()方法区分
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
3.putAll()
批量保存一个map集合
参考核心方法putMapEntries()
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
4.get()
根据参数key获取其对应的键值对的value值，如果不存在，则返回null
通过调用前面讲过的getNode()方法获取到该key对应的键值对，再将该键值对的value值返回即可。核心方法参考getNode()
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
5.getOrDefault()
根据参数key获取其对应的键值对的value值，如果不存在，则返回默认值。
与get()方法一致。核心方法参考getNode()
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
6.remove(key)
删除参数key对应的键值对
参考核心方法removeNode()，这里仅删除key相同的键值对，
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
7.remove(key, value)
删除参数key和value对应的键值对
参考核心方法removeNode()，这里删除key和value同时相同的键值对，与remove(key)方法区分
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
8.replace()
将参数key对应的键值对的value值进行覆盖
参考核心方法getNode()，
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
9.size()
获取当前HashMap中的键值对数量
10.isEmpty()
判断当前HashMap中的键值对数量是否为0
11.containsKey()
判断当前hashMap中是否存在指定的关键字key。
其实就是通过getNode()方法，判断该key对应的键值对是否存在。核心方法参考getNode()
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
12.containsValue()
判断当前hashMap中是否存在指定的值value。
该方法在遍历底层数组的过程中，嵌套遍历了数组中每一个位置上的链表和红黑树。对没错，正如你所见，在这里，红黑树的遍历方式也是通过next进行的，因为红黑树的节点TreeNode继承了父类LinkedHashMap的内部类Entry，而此Entry中记录了每一个节点的前驱和后继，也就是说，红黑树虽然是由TreeNode节点组成的，但是他也继承了父类LinkedHashMap的内部类Entry的特性，红黑树也记录了每一个TreeNode节点的前驱和后继，因此可以通过next遍历。其实前面介绍过的，这里的红黑树既可以通过left、right作为红黑树，也可以通过next作为链表
为什么不通过红黑树的方式遍历红黑树，而是通过链表的方式？
因为红黑树的查找是通过两个key之间的比较进行的，如果要查找指定的value对应的节点，需要遍历整棵红黑树，所以通过链表的方式也可以遍历整个红黑树，且不存在效率上的丢失。
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
13.entrySet()
获取每个键值对entry的set集合
在HashMap中，每个键值对无论是Node还是TreeNode，他们都继承自Map接口的内部接口entry，都是entry接口的子类，因此通过向上转型的方式，获取所有键值对的集合
14.clear()
清空hashMap中的元素。
就像清空一个数组那样，遍历底层数组，将数组中的元素统统置为空即可
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
十六、总结
哈希表数组长度为2的n次方，初始容量为16，默认加载因子为0.75
扩容后的底层数组长度为扩容前的2倍
底层结构为数组+单链表+红黑树实现的哈希表，当链表长度为8且数组长度为64时，该链表进化为红黑树；当红黑树中节点数为6时，红黑树退化为单链表。
线程不安全
延迟初始化
底层数组在第一次调用put()方法是通过resize()扩容进行实例化的。
当出现哈希冲突或扩容，且当前位置为链表时，采用尾插法将节点插入到链表
key可以为空，value也可以为空
先插入，后扩容
插入的数据是无序的
纸上得来终觉浅，绝知此事要躬行。
————————————————我是万万岁，我们下期再见————————————————
