HashMap简介
HashMap是一种利用哈希表原理存储元素的集合，当遇到哈希冲突时，HashMap会使用链地址法来解决冲突。在JDK1.7中，HashMap是由数组+链表构成的，在JDK1.8中则采用了数组+链表+红黑树的结构，新增了红黑树作为底层数据结构使得查询效率变得更高。本篇文章的源码基于JDK1.8。
鉴于笔者水平，如果表述不当之处请加笔者微信交流：Heroic-volition（麦田里的守望者）
HashMap理论基础
HashMap不同于ArrayList、LinkedList等集合类的实现原理比较简单，在阅读HashMap源码之前需要对其数据结构和存储方式等理论基础有一定的了解，否则直接啃源码的话会比啃石头还要硬。
一、HashMap数据结构
HashMap使用数组、链表和红黑树三者结合起来存储数据，构成一个哈希表。哈希表中每一个节点为HashMap集合存储的一个键值对，节点里面包含当前节点的哈希值、key、value和下一个节点的引用等信息。
HashMap的数据结构如下图：
1、数组
数组将元素在内存中连续存放，存储区间是连续的。
数组具有以下特点：
①线性排列，数据排列成一条线一样的结构。
②连续内存空间：计算机分配内存空间的时候都会分配一个对应的内存地址，连续的内存空间对应的是连续的内存地址，计算机是通过访问内存地址获取存储在对应内存空间的值。
③相同数据类型：相同数据类型，换句话说就是数据存储占用的内存大小是一样的。
因为计算机会给数组分配一个连续的内存空间，并且因为数组内存储的数据都是相同的类型，所以计算机为每个内存单元分配的大小也是一样的，那么只要根据数组的首地址和元素的下标就能计算出元素的内存地址，因此数组具有随机访问的特性，并不需要像链表那样依靠遍历来查找元素
。计算公示为a[i]_address = base_address + i * data_type_size，其中其中 data_type_size 表示数组中每个元素的大小， base_address为元素的首地址。
以下图片摘自网络：
2、链表
链表存储区间离散，占用内存比较宽松，通过存在元素中的指针联系到一起。
（1）链表动态地进行存储分配，可以适应数据动态地增减的情况。链表从堆中分配空间，自由度大但是申请管理比较麻烦。
（2） 当进行数据查询时，链表需要从第一个元素开始一直找到需要的元素位置。
（3）当进行增加或删除元素时，链表只需改动元素中的指针即可实现增加或删除元素。
3、哈希表
（1）Hash表的概念
散列表也叫做Hash表，是根据关键字来计算出关键字在表中地址的一种数据结构，而这种计算方式被称为散列函数。也就是说，Hash表建立了关键字与存储地址之间的一种直接映射关系。
这么说可能过于学术化，更加直白的表述就是通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录（哈希表使用数组为存储方式，这里的位置可以理解为数组的下标），这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
哈希表的存储方式是数组，但是哈希表和数组不是一个概念。数组是编程语言提供的一种数据类型，即用一组连续的内存空间来存放数据，可以通过一个首地址和一个数组下标，直接访问这组内存空间中的任意位置。哈希表则是一种数据结构，是以数组为存储方式，实现的一种可以快速查找数据的数据结构。它是将数据的值通过一个映射函数，求出一个散列结果，然后把数据放在这个结果对应的数组下标的位置。哈希表可以说数组+链表，也可以是数组+二叉树等结构。
下面是数组+链表组成的哈希表（图片摘自网络）：
（2）散列函数
①散列函数的定义
散列函数：一个把查找表中的关键字映射成该关键字对应地址的函数。记为Hash(key) = Addr.
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址（也就是数组的下标），则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
②散列函数的特点
a、散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小和地址范围；
b、散列函数计算出来的地址应当尽可能等概率、均匀的分布在整个地址空间，从而减少冲突的发生；
c、散列函数应该尽量简单，能够在较短时间内计算出任一关键字对应的散列地址；
（3）哈希冲突
散列函数可能会把两个或者两个以上的不同关键字映射到同一个地址，称这种情况为冲突，这些发生碰撞的不同关键字为“同义词”。在HashMap中，解决哈希冲突的方法是将发生哈希冲突的元素存储在一个链表（即“拉链法”）或者红黑树中，哈希表的数组中只存储链表的头节点或红黑树的根节点。
4、红黑树
jdk1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度(阀值)超过 8 时且当前数组的长度 > 64时，将链表转换为红黑树，这样大大减少了查找时间。jdk8在哈希表中引入红黑树的原因只是为了查找效率更高。是一种自平衡二叉查找树，其每个节点都是黑色或者红色。
红黑树涉及的数据结构知识面宽泛，想详细了解红黑树的话请读我的另一篇博客《深度解析红黑树》
二、HashMap的存储方式
JDK1.8之前的HashMap由数组+链表构成的哈希表来存储数据的。因为HashMap里面经常存储大量的元素，所以可能会有不同元素的哈希值相同，产生哈希碰撞问题。当不同的元素发生哈希冲突时，使用拉链法来解决，即对于不同的关键字可能会通过散列函数映射到同一个地址，可以把所有哈希地址相同的记录存储在一个线性链表中。
JDK1.8之后在因为链表的查询效率(时间复杂度为O(n))过低，当链表长度大于阈值（或者红黑树的边界值，默认为8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储，红黑树的查询效率比链表高很多，但是在插入或删除数据时可能需要进行自平衡。
三、HashMap的存储过程
HashMap使用哈希表来存储数据，每当新的元素存入时，首先要找到自己应当存入在哈希表的数组中的哪个位置，具体流程如下
1、获取元素key值的哈希值。
2、使用扰动函数获得新的哈希值
HashMap最后所使用的路由算法是(n – 1) & hash，计算结果就是插入数据所在数组位置的下标，其中n为数组长度，hash为插入key的哈希值，&为按位与运算。
因为hash值是一个int类型的数据，大小在-2147483648到2147483648，但是哈希表的数组的长度远小于此。那么如果用哈希值直接进行路由算法，则哈希值的二进制数字的高16位可能完全不参与运算。
例如，如果哈希值是8895415，数组长度是16， 那么n – 1) & hash的计算过程和结果为：
可以发现因为数组长度很小，二进制的前16位都是0，导致哈希值实际上只有最后3位参与路由运算。
在HashMap源码中，为了解决这个问题，使用扰动函数获取新的哈希值。所谓的扰动函数，就是让哈希值的高16位与低16位先进行一次异或运算，得到的新哈希值再进行路由寻址，这样可以使得哈希值的高16位和低16位均间接的参与了路由运算，使得运算结果更加散列，哈希表上的数据分布更加均匀。
在HashMap源码中，扰动函数为：hash ^ hash >>> 16，
如果hash值为8895415，则其计算过程和结果为：
哈希值先右移16为位，再与原值进行异或运算，相当于其自身的高16位与低16位进行了异或运算。
3、构造Node对象
Node是HashMap内部定义的一个内部类，其内部封装了key（键）、value（值）、hash（哈希值）、next（下一个节点的引用）等属性。
4、路由寻址
使用路由算法使用哈希值计算Node节点应该存放在数组的位置，即数组的下标。
HashMap使用的路由算法是(n – 1) & hash，hash是哈希值，n为数组长度。HashMap中哈希表的数组长度一定是2的幂，这在数组创建时就会定义好。而当n为2的幂时，(n – 1) & hash的值等于hash%n，所以HashMap实际上是使用哈希值对数组长度进行取模得到节点在数组中的下标，这是一种快速取模法。
至于为什么n为2的幂时，(n – 1) & hash和hash%n的值相等，笔者也没有找到资料给出证明，于是笔者自己尝试证明了一下：
HashMap源码
一、HashMap的相关属性
1、HashMap定义了其默认的初始容量（即哈希表所用数组的默认长度）为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
关于HashMap中指定初始容量为什么不直接赋值16，而是采用移位运算1<<4，根据网上和一些工程师的说法，是因为hash表容量必须是2的幂 这样写可读性高而且易于修改，与计算效率没有必然关系。
2、HashMap定义了哈希表的最大容量（即数组的最大长度）为1073741824，如果通过带参构造指定的容量大于此值，则仍然使用此值。
static final int MAXIMUM_CAPACITY = 1 << 30;
3、定义了树化阈值和树形化的最小表容量
如果当前bucket的位置链表长度大于8并且哈希表中所有元素的数量大于64的话就将此链表变成红黑树
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
4、扩容阈值
threshold表示HashMap的size（键值对的个数）超过这个数值时就会执行resize（容量扩容）操作，扩容后HashMap的容量是之前容量的两倍，threshold＝容量*加载因子。
int threshold;
5、哈希表的加载因子loadFactor，用来装载因子用来衡量HashMap满的程度，表示当HashMap的元素数量占容量的比重达到多少时，进行扩容操作。在HashMap中具体实现为threshold(阈值) = loadFactor(加载因子)*capacity(哈希表容量)，当HashMap的元素数量size > threshold就会进行扩容操作。
final float loadFactor;
6、默认的装在因子
选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折中选择， 加载因子越大,填满的元素越多,空间利用率越高，但冲突的机会加大了。反之,加载因子越小,填满的元素越少,冲突的机会减小,但空间浪费多了。冲突的机会越大,则查找的成本越高。反之,查找的成本越小。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
7、Node类
用来封装存入HashMap的数据，是HashMap的存储单元。
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; }
//计算节点的hash值去键与值的哈希值然后进行异或运算得出
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;
}
}
8、哈希表
本质上是一个Node类型的数组
transient Node<K,V>[] table;
二、构造方法
1、无参构造，使用默认的加载因子0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
2、传入初始容量的构造方法
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3、传入初始容量和加载因子的构造方法
在本方法中，主要做以下逻辑处理：
①判断传入的初始容量是否小于0，小于0则抛出异常。
②判断传入的初始容量是否大于HashMap的最大容量，大于则以最大容量作为初始容量。
③如果传入的加载因子小于等于0或者非数值，则抛出异常。
④因为HashMap的容量要求为2的幂，但是传入的容量实参未必满足这个要求，所以会有使用tableSizeFor(int cap)方法计算最接近容量实参的2的幂的值，作为哈希表的实际容量。但是同时HashMap采用的类似于“懒加载”的模式，在创建HashMap对象但是还未向里面添加元素的时候，不会实例化数组，而且HashMap没有定义当前容量的属性，所以只能将计算后的实际容量用threshold属性暂时保存一下，等到第一次向HashMap里面添加元素时会以threshold作为容量来构建数组。（一定要注意this.threshold = tableSizeFor(initialCapacity) 这句代码所得到的threshold 最后会被作为哈希表的容量使用，只不过用threshold 属性来暂存）。
public HashMap(int initialCapacity, float loadFactor) {
//初始容量小于0则直接抛异常
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;
//传入的容量不一定是2的幂，使用tableSizeFor方法获取最接近initialCapacity的2的幂
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor方法的作用是计算大于但是最接近所传入的集合容量的2的幂的值，作为哈希表的容量。如果给定的HashMap的容量不是2的幂，实际容量会是最接近但是大于指定容量的2的幂，比如 new HashMap<>(19)，比19大且最接近的2的幂是32，实际容量就是32。
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;
}
其中>>>为无符号右移运算，含义为：
按二进制形式把所有的数字向右移动对应位数，低位移出(舍弃)，高位的空位补零。
其中“n |= n >>> 1”含义为“n =n |n >>> 1”，“|”是按位或运算，是参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为1时，结果位就为1。当参与运算的是负数时，参与两个数均以补码出现。
具体规则为：1|1=1，1|0=1，0|1=1，0|0=0
通过连续的无符号右位移和按位或该运算可以让让最高位的1后面的位全变为1，其原理是：
最高位的1向右移1位，则得到最高位1的后1位变为1但是前1位变成0的二进制数，再和原二进制数字进行一次按位或运算，则使得原数字最高位1的后1位变成1。因为经过第一次运算后，已经数字已经有两个1，因此第二次可以直接向右移两位，再和原数字进行按位或得到4个1。通过不断的无符号右移和按位或，最终使得原二进制数字最高位的1后面的位全变为1。
具体过程为：
先来假设n的二进制为01xxx…xxx。接着
对n右移1位：001xx…xxx，再位或得到：011xx…xxx
对n右移2为：00011…xxx，再位或得到：01111…xxx
此时前面已经有四个1了，再右移4位且位或可得8个1
同理，有8个1，右移8位肯定会让后八位也为1。
综上可得，该算法让最高位的1后面的位全变为1。
举例说明：
cap = 201，n = cap -1 =200，则使用tableSizeFor方法来计算，是以下过程：
由此可见，tableSizeFor方法内，通过不断地以为和或运算，可以让某个数值的二进制数的最高位1后面全为1，再加上1就可以获得2的幂，而且所获得的2的幂必定大于且不等于该数值。也
因为获得的2的幂大于且不等于原数值，所以在计算时必须使用 cap -1，即将容量值减去1再计算，否则如果容量 cap本身就是2的幂，则再次获得大于原值的2的幂就会获得原值的2倍，会造成数组过长严重浪费空间
。
三、添加元素
（1）调用hashMap的put(K key, V value)方法，会先使用hash(Object key)获取哈希值。
/*
* 1、调用hash(key)方法获取key的新哈希值
* 2、调用putVal()方法增加元素
* */
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
其中hash(Object key)方法先使用hashCode()方法获取key的哈希值，然后使用扰动函数将key的哈希值将右移16位后与原值进行异或运算。这样做的效果前文已经分析过，可以让哈希值的前16位和后16位进行异或运算，获取新的哈希值，以便让哈希值经过散列函数获取的散列值更加离散。
/* 1、先使用hashCode()方法获取key的哈希值。
* 2、h ^ (h >>> 16)的作用是将哈希值右移16位后与原值进行异或运算得到新的哈希值，
* 新的哈希值在进行路由寻址计算后得到的散列结果更加离散，路由寻址计算方法为(n - 1) & hash,
* 其中n为哈希表的大小（数组长度）
* */
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
（2）使用putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法插入新元素，其中的onlyIfAbsent表示如果当前位置已存在一个值，是否替换，false是替换，true是不替换，evict表示是否在创建模式，如果为false，则表是在创建模式。
putVal方法的主要步骤为：
①判断哈希表是否为空，为空的话调用resize()初始化哈希表。HashMap在只有在存入元素时才会实例化哈希表，为了节省内存空间。
②使用(n – 1) & hash来计算元素在哈希表中的位置（下面称插入位置），其中n为哈希表的大小，hash为哈希值。因为哈希表的大小是2的幂，所以(n – 1) & hash等同于hash%n，这是一种快速取模方法。
③如果哈希表中插入的位置为空，则直接将新节点p插入到数组中。
④如果哈希表中插入位置不为空，则判断插入位置的首个节点的key值是否和插入元素的key相同，相同则根据onlyIfAbsent的实参决定是否覆盖value。
⑤如果key值不相同，则判断插入位置的首个节点是否是红黑树节点，是的话进行红黑树的插入操作。
⑥如果判断插入位置的首个节点不是红黑树节点，则开始遍历链表。如果链表中某个节点的key值与插入节点p的key值相同，则根据onlyIfAbsent的实参决定是否覆盖value。如果遍历到链表的尾节点，仍然没有找到与插入节点key值相同的节点，则将新节点插入到链表的末尾。
⑦如果将新节点插入到链表的末尾后链表长度达到了树化的阈值，则将链表转为红黑树。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//检查哈希表table是否为空，如果为空就调用resize()方法初始化。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//首先使用路由算法计算插入的元素在哈希表中的位置，并且将数组中该位置的节点赋给p。
//然后判断哈希表中插入位置是否为空。
//因为哈希表的容量是2的整数次幂，所以(n - 1) & hash = hash%n，这是一种快速取模方法。
if ((p = tab[i = (n - 1) & hash]) == null)
//如果哈希表中插入位置为空，则新建节点对象然后插入到数组中。
tab[i] = newNode(hash, key, value, null);
else {
//哈希表中插入的位置不为空
Node<K,V> e; K k;
//如果哈希表的插入位置中已经存在的元素的哈希值和插入元素的哈希值相等，
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//将新增节点的引用赋给e，e在最后用来根据onlyIfAbsent参数判断是否覆盖旧的value
e = p;
//判断插入位置已经存在的节点是否已经转为红黑树的节点
else if (p instanceof TreeNode)
//调用红黑树的putTreeVal方法向红黑树插入节点。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果插入位置的节点是链表节点，则开始使用循环来遍历链表，并进行key值比对
for (int binCount = 0; ; ++binCount) {
//如果链表已经没有下一个节点，说明已经遍历到链表的尾节点。
//遍历到末尾节点的时候，e的值同步变为null。
//当p为尾节点时，实际上尾节点已经做过key值比对，因为e = p.next，e在方法体中间
//是p的下一个节点，而且e会进行key值比对。因此，此时可以直接将新节点加入尾部，然后
//结束循环了。
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值相同，则跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//这里在遍历链表时，使用e = p.next和p = e，达到了p=p.next的效果来迭代链表。
p = e;
}
}
//如果e节点不为空，表示在遍历时未发现存在某个节点的key值与插入元素的key值相等。
//此时根据onlyIfAbsent的实参判断要不要覆盖value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//HashMap的版本号自增
++modCount;
//HashMap的大小自增，如果自增后大于扩容阈值，则使用resize()方法进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
四、哈希表扩容
HashMap的扩容方法非常精彩，使用的是resize()
在HashMap中，哈希表的数组的长度必须是2的n次幂，扩容后的HashMap容量是之前容量的两倍。HashMap扩容的步骤为：
（1）计算新表的容量和阈值，分为3种情况：
①如果旧哈希表是空表，说明之前没有初始化也没有向集合添加元素，则直接使用默认容量16，使用默认负载因子0.75来计算扩容阈值。
②如果旧表的容量为0，但是旧表的阈值不为0
这种情况是因为使用了HashMap(int initialCapacity, float loadFactor)带参构造方法传入了容量实参，因为Hash Map要求哈希表容量必须为2的幂，但是传入的容量不一定是2的幂，所以调用了tableSizeFor(initialCapacity)方法计算了一个最接近容量实参的2的幂值作为实际容量。因为Hash Map在存储元素之前不会实例化哈希表，所以需要将实际容量用threshold属性暂存。但是在第一次put进元素的时候，暂存的threshold需要当作哈希表容量来使用。
此时，将新表容量设为旧表的阈值，新表的阈值使用newCap * loadFactor来计算，newCap 为新表容量，loadFactor为负载因子。
③如果旧表不是空表，在不超过最大容量的前提下将新表容量和阈值均设为旧表的两倍。
（2）新建哈希表，重新排布所有节点
这里，HashMap的源码利用了两个数学上的规律，
第一：因为HashMap使用(n – 1) & hash来计算节点在哈希表中的位置，所以当hash & oldCap = 0时，则(n – 1) & hash = (2n – 1) & hash，又因为hashMap以2倍扩容，所以当某节点的哈希值满足hash & oldCap = 0，其扩容前后在哈希表中的位置相同。
其原理如下图所示，设oldCap 的是是2的n次幂，则oldCap 的二进制数字在从右到左第n位位1，其他均为0。因为hash & oldCap = 0，所以哈希值在oldCap 的1位置上对应的数字必须为0；则（oldCap – 1）&hash与（newCap– 1）&hash的值就只取决于hash值的二进制的从右到左n-1位的数字，则两者相等。
第二：另一个为哈希表扩容后，节点的位置要么等于原位置，要么是“原位置+oldCap”，即原位置和旧容量之和。这个很好理解，哈希值在oldCap 的1位置上对应的数字为1的话，（newCap– 1）&hash的值会减去（oldCap – 1）&hash的值的话得到的是oldCap的二进制数字，见下图。
因此HashMap在进行扩容后的链表重排布时，会首先使用hash & oldCap == 0 来判断节点在扩容后的位置是否有变化，如果变更了，再用“原位置+oldCap”计算节点再哈希表中的新位置。
具体逻辑为：
①从哈希表的第一个位置开始遍历哈希表，取出哈希表上的节点对象。
②如果哈希表在当前位置有节点对象，则从该头节点（根节点）开始遍历链表（红黑树）。
③如果当前节点是红黑树节点，则调用红黑树的重排布方法。
④如果当前节点是链表节点，使用loHead、loTail分别存储扩容后哈希表当前位置的头节点和尾节点，使用hiHead、hiTail分别存储储扩容后哈希表（当前位置+旧表容量）计算得到的位置的头节点和尾节点。
⑤首先使用hash & oldCap == 0判断该节点扩容后的位置是否和原位置相同。
⑥如果扩容后的位置和原位置相同，第一次时将当前节点的引用赋给loHead和loTail，因为新链表只要1个节点时其头节点和尾节点均指向一个节点。第二次包括以后将当前节点插入到链表的尾部。
⑦如果扩容后的位置和原位置不同，第一次时将当前节点的引用赋给hiHead和hiTail，因为新链表只要1个节点时其头节点和尾节点均指向一个节点。第二次包括以后将当前节点插入到链表的尾部。
⑧最终分别将loHead放入哈希表的当前位置，将hiHead放入哈希表的当前位置+旧表容量的位置。
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) {
//判断旧表的容量是否超过最大容量值：如果超过则将阈值设置为Integer的最大值，并直接返回旧表，因为已经无法扩容
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
}
//这种情况是因为使用了HashMap(int initialCapacity, float loadFactor)带参构造方法传入了容量实参，
//因为Hash Map要求哈希表容量必须为2的幂，但是传入的容量不一定是2的幂，所以调用了tableSizeFor(initialCapacity)方法
//计算了一个最接近容量实参的2的幂值作为实际容量。因为Hash Map在存储元素之前不会实例化哈希表，所以需要将实际容量用
//threshold属性暂存。但是在第一次put进元素的时候，暂存的threshold需要当作哈希表容量来使用,则将新表的容量设置为旧表的阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//旧表的容量为0, 老表的阈值为0，这种情况是没有传初始容量的new方法创建的空表，将阈值和容量设置为默认值
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);
}
//将当前阈值设置为刚计算出来的新的阈值，定义新表，容量为刚计算出来的新容量，将table设置为新定义的表
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;
//如果e.next为空, 则代表旧表的当前位置只有1个节点，计算新表的索引位置, 直接将该节点放在该位置即可
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是红黑树节点，则进行红黑树的重新分布(跟链表的hash分布基本相同)
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//loHead和loTail分别用来存储扩容之后新表原索引位置的链表的头节点和尾节点
Node<K,V> loHead = null, loTail = null;
//hiHead和hiTail分别用来存储存储扩容之后新表的“原索引位置+oldCap”位置的链表的的头节点和尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//使用do-while循环开始遍历链表
do {
next = e.next;
//如果e的hash值与旧表的容量oldCap进行与运算为0,则扩容后的索引位置跟旧表的索引位置一样
if ((e.hash & oldCap) == 0) {
// 如果loTail为空, 说明刚找到第一个位置不变的节点，则需要将当前节点的引用赋给loHead
//和loTail，因为此时当前位置的链表只有一个节点，则头尾节点的指针都要指向此节点
if (loTail == null)
//找到第一个位置不变的节点，将其引用赋给loHead
loHead = e;
//否则将节点添加在当前位置的链表的尾部
else
//将原尾节点的下一个节点指向当前节点
loTail.next = e;
//再将尾节点的指针改为指向当前节点，
loTail = e;
}
//如果e的hash值与旧表的容量进行与运算为非0,则扩容后的索引位置为:原索引位置＋oldCap
else {
//如果hiTail为空, 说明刚找到第一个位置变化了的节点，则需要将当前节点的引用赋给hiHead
//和hiTail，因为此时当前位置的链表只有一个节点，则头尾节点的指针都要指向此节点
if (hiTail == null)
hiHead = e;
//否则将节点添加在“原索引位置＋oldCap”位置的链表的尾部
else
//将原尾节点的下一个节点指向当前节点
hiTail.next = e;
//再将尾节点的指针改为指向当前节点
hiTail = e;
}
} while ((e = next) != null);
//如果loTail不为空，说明旧表的节点有一些重新排布还是在新表的原索引位置上，
//则将链表的头节点放到新表的原索引位置，并将链表的尾节点的下一个节点设为null
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//如果hiTail不为空，说明旧表的节点有一些重新排布到“原索引位置+oldCap”位置上，
// 则将链表的头节点放到新表的“原索引位置+oldCap”位置，并将链表的尾节点的下一个节点设为null
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
五、红黑树操作
HashMap的红黑树操作的代码较为复杂，本文选择其中的红黑树插入部分来讲一讲。
红黑树的插入方法包括两步，第一步是寻找插入位置，第二部是插入后的自平衡。红黑树也是二叉树的一种，和二叉树一样，需要将新节点插入查找失败的位置上。
1、寻址插入位置的putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v)方法。
这个方法的主要作用就是寻找插入位置，然后插入节点，最后调用balanceInsertion(root, x)方法进行红黑树的自平衡和moveRootToFront方法将红黑树新的根节点转移到哈希表上面。
其主要逻辑为：
①从根节点开始遍历红黑树，取出根节点，将其哈希值与插入节点的哈希值进行大小比较。
②如果当前节点的哈希值大于插入节点的哈希值，则从当前节点的左子树开始继续查找。
③如果当前节点的哈希值小插入节点的哈希值，则从当前节点的右子树开始继续查找。
④如果两个哈希值相等，则比较它们的key值是否相等。
⑤如果两者的key值相等，则返回当前节点。
⑥如果两者的key值不相等，则判断插入节点的key所属的类是否实现了comparable接口。
⑦如果插入节点的key实现了comparable接口，则使用comparable接口的compareTo(T o)方法来比较两个key的大小，再决定向其左子树或右子树继续查找。
⑧如果插入节点的key没有comparable接口或者使用compareTo(T o)方法比较出来的两个key的大小依然相同，则继续先向其左子树继续查找key值与插入节点key值相等的节点，左子树中找不到再向其右子树查找，看最后能不能找到key值相等的红黑树节点。
⑨如果能找到key值相等的节点返回该节点，如果找不到则使用tieBreakOrder(Object a, Object b)方法再次比较两者的key值，该方法将比较两个key对象的identityHashCode，identityHashCode由对象的内存地址生成，只要不是同一个对象，就必定不同，所以绝对能比较出大小。
然后通过两者key对象的identityHashCode的大小判断继续向左子树还是向右子树查找。
⑩重复以上操作，当遍历到红黑树的一个节点，其key的哈希值大于插入节点的哈希值，或者两者哈希值相同但是key使用compareTo(T o)方法比较出来的结果是红黑树节点的key值大，并且红黑树节点已经没有左子树，说明已经到了查找失败的位置，将新节点插入到这个红黑树节点的左下方。
同理，当遍历到红黑树的一个节点，其key的哈希值小于插入节点的哈希值，或者两者哈希值相同但是key使用compareTo(T o)方法比较出来的结果是红黑树节点的key值小，并且红黑树节点已经没有右子树，说明已经到了查找失败的位置，将新节点插入到这个红黑树节点的右下方。
总结：查找规则是先比较哈希值，哈希值相等再比较key值，key值不等则查找其子树上有没有key值相等的节点，找不到的话最后比较key对象的identityHashCode值。
/**
* Tree version of putVal.
* map：当前节点所在的HashMap对象
* tab：HashMap的哈希表
* h：插入节点key的哈希值
* k：插入节点的key值
* v：插入节点的value值
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
//searched 标识是否已经对比过当前节点的左右子节点了
boolean searched = false;
//获取根节点：如果当前节点的父节点是null，说名当前节点就是根节点，否则使用
//root()方法寻找根节点。
TreeNode<K,V> root = (parent != null) ? root() : this;
//从根节点开始遍历红黑树
for (TreeNode<K,V> p = root;;) {
//dir用来标记插入节点在当前节点的左边还是右边
//ph是当前节点的哈希值
//pk是当前节点的key值
int dir, ph; K pk;
//如果当前红黑树节点的哈希值大于插入节点的哈希值
if ((ph = p.hash) > h)
//插入节点在当前红黑树节点的右边
dir = -1;
//如果当前红黑树节点的哈希值大于插入节点的哈希值
else if (ph < h)
//插入节点在当前红黑树节点的左边
dir = 1;
//如果插入节点的哈希值和当前红黑树节点的哈希值相等，并且key值也相等
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
//直接返回当前红黑树节点
return p;
//如果两者的哈希值相等，但是key值不相等
//如果插入节点的key没有实现comparable接口或者实现了comparable接口并且和当前节点的键对象比较之后相等（仅限第一次循环）
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;
}
//如果遍历了所有子节点也没有找到和插入节点key值equals相等的红黑树节点
//tieBreakOrder方法用来比较插入节点键值和当前节点键值大小，使用identityHashCode值来比较，不可能再出现相等的情况
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
//如果dir小于等于0，则取出当前节点的左子节点，如果其左子节点为空，则将插入节点作为当前节点的左子节点，否则继续递归
//如果dir>0，则取出当前节点的右子节点，如果其右子节点为空，则将插入节点作为当前节点的右子节点，否则继续递归
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的父节点和前置节点都设为当前节点xp
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//通过balanceInsertion方法进行红黑树的自平衡操作，
//并且通过moveRootToFront方法将新的根节点移到哈希表
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
当发生红黑树的某节点与插入节点的哈希值相等但是key值不同并且不能通过compareTo(T o)方法比较两者的大小时，会调用find(int h, Object k, Class<?> kc)方法依次在其左右子树上查找有没有key值equals相等的节点：
/**
* Finds the node starting at root p with the given hash and key.
* The kc argument caches comparableClassFor(key) upon first use
* comparing keys.
* 依据键值查找节点对象的方法
* h：k的哈希值
* k：需要查找的键值的对象
* kc：k的Class对象，该Class应该是实现了Comparable<K>的，否则应该是null
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
//如果h小于当前节点的哈希值
if ((ph = p.hash) > h)
//则从其左子树开始查找
p = pl;
//如果h小于当前节点的哈希值
else if (ph < h)
//则从其右子树开始查找
p = pr;
//如果哈希值相同，键值相等，说明找到了节点
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//如果哈希值相等，但是键值不相等，则采用以下方式查找
//如果当前节点没有左子树，
else if (pl == null)
//从其右子树开始查找
p = pr;
//如果当前节点没有左子树，
else if (pr == null)
//从其左子树开始查找
p = pl;
//如果左右孩子都不为空，则使用comparable方法比较两个key值的大学
//来决定从哪个子树中查找
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
//如果key值没有实现comparable接口或者比较之后还是相等
//则从右子树开始递归查找
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
//如果右子树中找不到，从左子树上开始查找
p = pl;
} while (p != null);
return null;
}
如果调用find方法仍然在其子树上找不到key值相等的节点，最后将使用tieBreakOrder(Object a, Object b)方法再次比较key值，tieBreakOrder(Object a, Object b)方法最终将比较两者的identityHashCode，所以必定不会再得出相等的结果。
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
2、红黑树自平衡的balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x)方法。
这个方法用于红黑树插入节点后的自平衡，本处只将红黑树插入节点后自平衡的实现方式，至于为什么要这么去实现自平衡，请看我的另一篇博客《深度解析红黑树》
红黑树新增节点后的自平衡方式为：
1、新增的节点先默认为红色，因为红黑树要遵循黑色平衡，插入黑色节点无论如何都会破坏其平衡性
2、如果插入节点的父节点是黑色，那么插入后不会影响红黑树的性质（红色节点不能相连），不需要作自平衡处理
3、如果插入节点的父节点是红色，则需要作自平衡处理，具体步骤如下：
3-1、如果插入节点有叔叔节点（即父节点的兄弟节点）并且叔叔节点是红色，则只需要将父节点和叔叔节点变为黑色，
自身维持红色即可。
3-2、如果插入节点有叔叔节点并且叔叔节点是黑色或者没有叔叔节点，则需要以父节点为支点进行旋转，再变色。
/*红黑树新增节点后的自平衡方法
* 1、新增的节点先默认为红色，因为红黑树要遵循黑色平衡，插入黑色节点无论如何都会破坏其平衡性
* 2、如果插入节点的父节点是黑色，那么插入后不会影响红黑树的性质（红色节点不能相连），不需要作自平衡处理
* 3、如果插入节点的父节点是红色，则需要作自平衡处理，具体步骤如下：
* 3-1、如果插入节点有叔叔节点（即父节点的兄弟节点）并且叔叔节点是红色，则只需要将父节点和叔叔节点变为黑色，
* 自身维持红色即可。
* 3-2、如果插入节点有叔叔节点并且叔叔节点是黑色或者没有叔叔节点，则需要以父节点为支点进行旋转，再变色
*
*/
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//新插入的节点暂定为红色
x.red = true;
//开始循环平衡红黑树的节点，其中xp表示插入节点的父节点
//xpp表示插入节点的祖父节点，
//xppl表示插入节点的祖父节点的左子节点
//xppr表示插入节点的祖父节点的右子节点
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//如果插入节点没有父节点，说明插入节点是红黑树的第一个节点，
//直接将其设为黑色即可，不用作自平衡操作
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//如果插入节点的父节点为黑色时，不影响红黑树的平衡与性质，直接插入
//如果插入节点没有祖父节点，说明父节点就是根节点，根节点也是黑色，也可以直接插入
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) {
//以父节为支点左旋
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;
//以祖父节点为支点进行左旋
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);
}
}
}
}
}
}
3、根节点置顶的moveRootToFront方法
红黑树在经过自平衡（旋转和变色）后，根节点会发生变化，这个时候就需要将红黑树新的根节点置顶，就是放在哈希表上。
需要注意的是HashMap中的红黑树也具有双向链表的结构，TreeNode类不仅具有指向上一个节点的指针也有指向下一个节点的指针。
因此这里的调整包含了两步，第一步是将红黑树的根节点放入哈希表中，第二步是在双向链表中取出红黑树的根节点，放到链表的头部。
/**
* Ensures that the given root is the first node of its bin.
*此方法是将红黑树新的根节点置顶，就是放在哈希表上
*此时红黑树同时具备双向链表结构，所以需要将新的根节点调整为链表的头节点
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
//首先获取根节点在哈希表中的位置索引
int index = (n - 1) & root.hash;
//取得该位置的节点对象
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//如果哈希表中该位置的节点不是红黑树的根节点
if (root != first) {
Node<K,V> rn;
//第一步：把哈希表中该位置的节点设为红黑树的根节点
tab[index] = root;
//第二步：从这里开始是针对双向链表的操作，需要将红黑树新的根节点改为链表的头节点
//先将根节点从链表中取出，也就是让根节点和前后两个节点断开，其前后两个节点相连
//获取根节点的前一个节点
TreeNode<K,V> rp = root.prev;
//如果根节点有子节点
if ((rn = root.next) != null)
//将根节点的子节点的前置节点设为根节点的前置节点，相当于让根节点与子节点断开
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
//将根节点的前置节点的后一个节点设为根节点的子节点，相当于当根节点和前置节点断开
rp.next = rn;
//最后将根节点加入链表中，作为第一个节点
if (first != null)
first.prev = root;
root.next = first;
//根节点的前置节点设为null，因为根节点在链表中是第一个节点
root.prev = null;
}
assert checkInvariants(root);
}
}