JDK集合HashMap 底层源码细致分析
前言
提示：对于初始 HashMap 的小伙伴来说，不推荐直接硬啃，建议先看一下如下几个视频教程之后再回头好好理解。（一遍看不懂则反复看，一小块一小块的找对应博客阅读）
散列（哈希）表
核心理论：
Hash 也称散列、哈希，对应的英文都是 Hash。基本原理就是把任意长度的输入，通过 hash 算法变成固定长度的输出。这个映射的规则就是对应的 Hash 算法，而原始数据映射后的二进制串就是哈希值。
Hash 的特点：
- 从 Hash 值不可以反向推导出原始的数据。
- 输入数据的微小变化会得到完全不同的 hash 值，相同的数据会得到相同的值
- 哈希算法的执行效率要高效，长的文本也能快速的计算出哈希值。
- Hash 算法的冲突概率要小
由于 Hash 的原理是将输入空间的值映射成 Hash 空间内，而 Hash 值的空间远小于输入的空间
根据抽屉原理：一定会存在不同的输入被映射成相同输出的情况。
抽屉原理
桌上有10个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果，这一个现象就是我们所说的抽屉原理。
HashMap 的简述：
- HashMap 即基于哈希表的 Map 接口实现，是以 key - value 存储形式存在，即主要用来存放键值对。HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value 都可以为 null，此外，HashMap 中的映射不是有序的。
- jdk1.8 之前HashMap 由 数组 + 链表 组成，数组是 HashMap 的主体，链表则是为了解决哈希冲突（两个对象调用 hashCode 方法计算的哈希值经过哈希函数算出来的地址被别的元素占用）而存在的（“拉链法”解决冲突）。JDK1.8以后在解决哈希冲突的时候有了较大的改变，当链表的长度大于阙值（或者红黑树的边界值，默认为8）并且当前数组的长度大于64的时候，此时索引的所有数据改为红黑树存储。
HashMap 扩容机制简述
HashMap == 数组 + 链表 + 红黑树
- HashMap 的默认初始桶位数是 16（如果使用的是空构造方法的话），如果某个桶中的链表长度大于等于8，则先进行判断：
- 如果桶位数小于64，则先进行扩容（2倍），扩容之后重新计算哈希值，这样桶中的链表长度就变短了（之所以链表长度变短与桶的定位方式有关，请接着往下看）。
- 如果桶位数大于等于64，且某个桶中的链表长度大于等于8，则对链表进行树化（红黑树，即自平衡的二叉树）。
- 如果红黑树的节点数小于6，树也会重新变为链表
所以得出树化条件：链表阙值大于8，且桶位数大于64（数组长度），才进行树化。
元素放入桶中，定位桶的方式：通过数组下标 i 定位，添加元素的时候，目标桶位置 i 的计算方式，i = hash & (cap - 1)，cap为数组的容量。
为什么优先扩容桶位数（数组长度），而不是直接树化？
- 这样做的目的是因为，当桶位数（数组长度）比较小的时候，应该尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率。因为红黑树需要左旋、右旋、变色这些操作来保持平衡。同时数组长度小于 64 的时候，搜索时间相对要快些。所以综合上述为了提高性能和减少时间，链表阙值大于等于 8 并且数组长度大于 等于64 的时候，链表才转化为红黑树，具体可以参考下文要讲述的 treeifyBin() 方法。
- 而当链表长度大于等于 8 并且数组长度大于等于 64的时候，虽然增加了红黑树作为底层数据结构，结构变得更加复杂了，但是长度较长的链表转换为红黑树的时候，效率也变高了。
HashMap 特点：
- 存储无序
- 键和值的位置都可以是 null，但是键位置只能存在一个 null，因为键值是不能重复的；
- 键位置是唯一的，是由底层的数据结构控制的；
- jdk1.8 之前数据结构是 链表 + 数组，jdk1.8之后是 链表 + 数组 + 红黑树；
- 树化阙值 >= 8 并且桶位数（数组长度）大于 64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。
1、HashMap 的存储结构
注意：相对于直接去读 HashMap 源码来说，先debug 一下其执行数据存储的流程，更方便理解。
测试代码：
@Test
public void test01() {
HashMap<String, Integer> hashMap = new HashMap();
hashMap.put("a", 3);
hashMap.put("b", 4);
hashMap.put("c", 5);
hashMap.put("a", 88888);// 修改
System.out.println(hashMap);
}
输出结果：
{a=88888, b=4, c=5}
执行流程分析：
- 首先，
HashMap<String,Integer> hashMap = new HashMap<>();当创建 HashMap 集合对象的时候，HashMap 的构造方法并没有创建数组，而是在第一次调用 put 方法的时候创建一个长度是 16 的数组（即16个桶位），Node[] table（jdk1.8 之前是 Entry[] table）用来存储键值对数据。 - 当向哈希表中存储
put("a", 3)的数据的时候，根据"w"字符串调用 String 类中重写之后的 hashCode() 方法计算出哈希值，然后结合数组长度（桶数量）采用某种算法计算出向 Node 数组中存储数据的 空间索引值（比如table[i]，这里的 i 就是该 Node 数组的空间索引）。如果计算出的索引空间没有数据（即，这个桶是空的），则直接将<"a", 3>存储到数组中。
举例：如果计算出的索引是 3，则存储到如下桶位：
- 当向哈希表中存储数据
<"b", 4>的时候，假设算出的 hashCode() 方法结合数组长度计算出的索引值也是 3，那么此时数组空间不是 null（即，这个桶目前不为空），此时底层会比较"a"和"b"的 hash 值是否一致，如果不一致，则在空间上划出一个节点来存储键值对数据对<"b", 4>，这种方式称为拉链法。 - 当向哈希表中存储数据
<"a", 88888>的时候，那么首先根据"a"调用 hashCode() 方法结合数组长度计算出索引肯定是 3，此时比较后存储的数据"a"和已经存在的数据的 hash 值是否相等，如果 hash 值相等，此时发生哈希碰撞，那么底层会调用"a"所属类 String 中的 equals() 方法比较两个内容是否相等：- 相等：将后添加的数据的 value 覆盖之前的 value。
- 不相等：继续向下和其他数据的 key 进行比较，如果都不相等，则划出一个节点存储数据，如果节点长度即链表长度大于扩容阙值 8 并且数组长度大于 64 则将链表变为红黑树。
在不断的添加的数据的过程中，会涉及到扩容问题，当超出阙值（且要存放的位置非空）的时候，扩容。默认的扩容方式：扩容为原来的容量的 2 倍，并将原有的数据复制过来。
综上描述，当位于一个表中的元素较多，即 hash 值相等但是内容不相等的元素较多的时候，通过 key 值依次查找的效率较低。而 jdk1.8 中，哈希表采用数组 + 链表 + 红黑树实现，当链表长度（阙值）超过 8 且当前数组的长度大于64的时候，将链表转换为红黑树，这样大大减少了查找时间。
简单的来说，哈希表是由数组 + 链表 + 红黑树（JDK 1.8 增加了红黑树部分）实现的。如下图所示：
W8qe)JDK 1.8 中引入红黑树的进一步原因：
- JDK 1.8 之前 HashMap 的实现是数组 + 链表，即使哈希函数取得再好，也很难达到元素百分之百均匀分布。当HashMap 中有大量的元素存放在同一个桶中的时候，这个桶下有一条长长的链表，这个HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。
- 针对这种情况，JDK1.8 中引入了红黑树（查找的时间复杂度为O（logn））来优化这个问题。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。
总结：
说明：
- size 表示 HashMap 中键值对的实时数量（即，所存储元素的数量），注意这个不等于数组的长度。
- thresold（临界值）= capacity（容量）* loadFactor（负载因子）。这个值是当前已占用数组长度的最大值。size 超过这个值就重新 resize（扩容），扩容后的 HashMap 容量是之前容量的 2 倍。
2、HashMap 相关面试题
具体原理我们下文会具体分析，这里先大概了解下面试的时候会问什么，带着问题去读源码，便于理解！
1、HashMap 中 hash 函数是怎么实现的？还有哪些 hash 函数的实现方式？
- 对 key 的 hashCode 做 hash 操作，如果 key 为 null 则直接赋哈希值为 0，否则，无符号右移 16 位然后做异或运算或者位运算，如，代码所示：
(key == null) ? 0 : ((h = key.hashCode) ^ (h >>> 16)); - 除上面的方法外，还有平方取中法，伪随机数法和取余法。这三种效率都比较低，而无符号右移 16 位异或运算或者位运算效率是最高的。
2、当两个对象的 hashCode 相等的时候会怎么样？
会产生哈希碰撞，若 key 值内容相同则替换旧的 value，不然连接到链表的后面，链表长度超过阙值 8 并且哈希表长度超过 64 旧转化为红黑树存储。
3、什么是哈希碰撞，如何解决哈希碰撞？
只要两个元素的 key 计算的哈希值相同就会发生哈希碰撞。JDK1.8 之前使用链表解决哈希碰撞。JDK 1.8 之后使用链表 + 红黑树解决哈希碰撞。
4、如果两个键的 hashCode 值相同，如何存储键值对？
通过 equals 比较内容是否相同。
- 相同：则新的 value 覆盖之前的 value。
- 不相同：遍历该桶位的链表（或者红黑树）：v给他人非法v应该改改吧宝宝乖乖乖乖乖乖乖乖乖乖乖乖乖乖乖乖乖
- 如果找到相同的 key，则覆盖该 key 对应的 value
- 如果找不到，则将新的键值对添加到链表（或者树）的末尾中
3、HashMap 的继承体系
从继承体系上可以看出：
- HashMap 实现了 Cloneable 接口，可以被克隆。
- HashMap 实现了 Serializable 接口，属于标记性接口，HashMap 对象可以被序列化和反序列化。
- HashMap 继承了 AbstractMap ，父类提供了Map 实现接口，具有 Map 的所有功能，以最大限度地减少实现此接口所需地工作。
知识扩展：
通过上述继承关系我们发现一个很奇怪地现象，就是HashMap 已经继承了 AbstractMap 类，而AbstractMap 实现了 Map 接口，那为什么HashMap 还要在实现 Map 接口呢？同样在 ArrayList 中 LinkedList 中都是这种结构。
根据 Java 集合框架的创始人 Josh Bloch 描述，这样的写法是一个失误。在 JAVA 集合框架中，类似这样的写法很多，最开始写 JAVA 集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。但是，JDK 的维护者，后来不认为这个小小的失误值得去修改，所以就这样保留了下来。
在 JAVA 中，HashMap 的实现采用了 （数组 + 链表 + 红黑树）的复杂结构，数组的一个元素又称作桶。
在添加元素的时候，会根据 hash 值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素了，则把该元素以链表的方式放置在链表的尾部。
当一个链表的元素个数达到一定的数量（且数组的长度达到一定的长度后），则把链表转化为红黑树，从而提高效率。
数组的查询效率为 O(1)，链表的查询效率为O(k)，红黑树的查询效率是O(logn)，n为桶中元素的个数，所以当元素数量非常多的时候，转化为红黑树能极大的提高效率。
4、HashMap 的基本属性与常量
// 序列化版本号
private static final long serialVersionUID = 362498820763181265L;
// 缺省的数组table大小，默认为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 数组table的的最大大小，2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 缺省的负载因子大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 树化阙值，当一个桶中的元素个数大于等于8的时候进行树化
static final int TREEIFY_THRESHOLD = 8;
// 树降级为链表的阙值，当一个桶中的元素个数小于等于6的时候把树转化为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 哈希表中的另一个参数，当哈希表中的所有元素个数超过64的时候，才会允许树化
static final int MIN_TREEIFY_CAPACITY = 64;
// 哈希，初始化为null
// 还有，它什么时候开始初始化呢？第一次添加元素的时候进行初始化
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
// 当前哈希表中的元素个数
transient int size;
// 当前哈希表中结构修改次数
transient int modCount;
// 扩容阙值，当哈希表中的元素超过阙值的时候触发扩容机制
int threshold;
/**
* The load factor for the hash table.
*
* 负载因子，使用默认的0.75，可以计算出来扩容阙值threshold：threshold = capacity * loadFactory
*
* @serial
*/
final float loadFactor;
- 容量：容量为数组的长度，亦为桶的个数，默认为 16，最大为 2 的 30 次方，当数组容量达到64的时候才可以进树化。
- 负载因子：负载因子用来计算容量达到多少的时候才可以进行扩容，默认负载因子为 0.75.
- 树化：树化，当数组容量达到 64 并且链表的长度大于等于 8 的的时候才进行树化，当链表的长度小于等于 6 的时候反树化。
4.1、DEFAULT_INITIAL_CAPACITY
集合的初始化容量（必须是 2 的 n 次幂）:
// 默认的初始容量是16 1 << 4 相当于 1*2的4次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
面试问题：为什么必须是集合的容量 2 的 n 次幂？如果输入的值不是 2 的 n 次幂会怎么样？
HashMap 构造方法可以指定集合的初始化容量大小，如：
// 构造一个带指定初始容量和默认负载因子（0.75)的空 HashMap。
public HashMap(int initialCapacity)
根据上述讲解我们已经知道，当向 HashMap 中添加一个元素的时候，需要根据 key 的 hash 值，去确定其在数组中的具体位置。HashMap 为了存取高效，减少碰撞，就是要尽量把数据分配均匀，每个链表的长度大致相同，这个实现的关键就在数据存到哪个链表的算法。
这个算法实际就是取模， hash % length，而计算机中直接求余效率不如移位运算。所以源码中做了优化，使用hash % (length - 1)，而实际上 hash % length 等于 hash & (length - 1) 的前提是 length 是 2 的 n 次幂。
例如，数组长度为 8 的时候，3 & (8 - 1) = 3, 2 & (8 - 1) = 2，桶的位置是（数组的索引）3 和2 ，不同位置上，不碰撞。
再来看一个数组长度（桶位数）不是 2 的 n 次幂的情况：
从上图可以看出，当数组长度为 9 （非 2 的 n 次幂）的时候，不同的哈希值的 hash，hash & (length - 1)所得到的数组下标相等（很容易出现哈希碰撞）。
小结一下 HashMap 数组容量使用 2 的 n 次幂的原因：（面试也会问）
- 由上面可以看出，当我们根据 key 的 hash 位置确定其在数组的位置的时候，如果 n 为 2 的 幂次方，可以保证数据的均匀插入，如果 n 不是 2 的幂次方，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大 hash 冲突。
- 另一方面，一般我们可能会想通过**求余运算%**来确定位置，这样也可以，只不过性能不如 & 运算。而且当 n 是 2 的幂次方的时候：hash & (length - 1) == hash % length。
- 因此，HashMap 容量为 2 次幂的原因，就是为了数据的均匀分布，减少 hash 冲突，毕竟 hash 冲突越大，代表数组中一个链的长度越大，这样的话会降低 hashMap 的性能。
问题：如果创建 HashMap 对象的时候，输入的数组长度 length 是 10，而不是2 的 n 次幂会怎么样呢？
HashMap<String, Integer> hashMap = new HashMap(10);
HashMap 双参构造函数会通过 tableSizeFor(initialCapacity) 方法，得到一个最接近 length 并且大于 length 的 2 的 n次幂数，比如最接近的 10 且大于 10 的 2 次幂的数是 16
这一块比较难理解，下文讲构造方法的时候还会再举例：
/**
* Returns a power of two size for the given target capacity.
* 返回一个大于等于当前值cap的一个数字，并且这个数字一定是2的次方数
* cap = 10
* n = 10 - 1 = 9
* 0b1001 | 0b0100 ==> 0b1101 右移一位
* 0b1101 | 0b0011 ==> 0b1111 右移两位
* 0b1111 | 0b0000 ==> 0b1111 右移四位
* ....
*
* 0b1111 => 15
*
*/
static final int tableSizeFor(int cap) {
// 这里为什么要减一，因为cap是32位的二进制数字，而我们最后得到的是将所有可用位的二进制位数转化为1
// 如果不减一的话，当我们传入的刚好是2的次方数的话，就会出现得到的是我们传入的数的2倍，这样就不符合了
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;
}
说明：
当在实例化 HashMap 实例的时候，如果给定了 initialCapacity，由于 HashMap 的 capacity 必须是 2 的 次幂，因此这个方法tableSizeFor(initialCapacity);用于找到大于等于 initialCapacity 的最小的 2 的次幂。
分析：
int n = cap - 1;为什么要减去 1 呢？防止这 cap 已经是 2 的幂。如果 cap 已经是 2 的幂，有没有这个减 1 的操作，则执行完后面的几条无符号操作之后，返回的 capacity 将是这个 cap 的2 倍。
最后为什么有个 n + 1 的操作呢？
如果 n 这时候为 0 了（经过 cap - 1后），则经过后面的几次无符号右移依然是 0，返回 0 是肯定不行的，所以最后返回
n + 1最终得到的 capacity 是 1；注意：容量最大也就是 32 bit 的正数，因此最后
n |= n >>> 16;最多也就 32 个 1（但是这已经是负数了，在执行 tableSizeFor 之前，对initialCapacity 做了判断，如果大于 MAXIMUM_CAPACITY(2 ^ 30)，则取 MAXIMUM_CAPACITY。如果等于 MAXIMUM_CAPACITY，则会执行位移操作。所以这里面的位移操作之后，最大 30个1，不会大于等于 MAXIMUM_CAPACITY。30 个 1，加 1 后得 2 ^ 30）。
所以有结果可得，当执行完 tableSizeFor(initialCapacity);方法后，得到的新的 capacity 是最接近 initialCapacity 且大于 initialCapacity 的2 的 n 次幂的数。
4.2、DEFAULT_LOAD_FACTOR
默认的负载因子（默认值是 0.75）
static final float DEFAULT_LOAD_FACTOR = 0.75f;
4.3、MAXIMUM_CAPACITY
集合的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次幂
4.4、TREEIFY_THRESHOLD
当链表的长度超过 8 则会转化为红黑树（JDK1.8 新增）
// 当桶（bucket）上的结点数大于这个值时会转为红黑树
static final int TREEIFY_THRESHOLD = 8;
面试问题：为什么 HashMap 桶中的节点个数超过 8 才能转化为 红黑树？
8 这个阙值定义在 HashMap 中，针对这个成员变量，在源码的注释中只说明了 8 是 bucket 桶从链表结构转化成树的阙值，但是并没有说明为什么是 8
在HashMap中有一段注释说明：
Because TreeNodes are about twice the size of regular nodes, we use them only when bins
contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too
small (due to removal or resizing) they are converted back to plain bins. In usages with
well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes,
the frequency of nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution)
with a parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance,
the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:
翻译：因为树节点的大小约是普通节点的两倍，所以我们只在箱子包含足够的节点的时候才使用树节点（参照TREEIFY_THRESHOLD）
当它们变得太小（由于删除或者调整大小的时候），就会倍转换为普通的链表，在使用分布良好的 hashCode的时候，很少使用树箱，理想情况下，在随机hashCode下，箱子中节点的频率服从泊松分布
默认调整阙值为0.75，平均参数约为0.5，尽管由于调整粒度的差异很大。忽略方差，列表大小k的预出现次数为(exp(-0.5)*pow(0.5, k) / factorial(k)
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
TreeNodes（树）占用空间是普通 Nodes（链表）的两倍，所以只有当 bucket（桶）包含足够多的节点的时候才会转化成 TreeNodes，而是足够多就是由 REEIFY_THRESH〇LD 的值决定的。当bucket 中的节点数变少，又会转成普通的 bucket（桶），并且我们查看源码的时候发现，链表长度达到 8 就转成红黑树，当长度降到 6 就转成普通的桶。
这样就解释了为什么不是一开始就将其转化为 TreeNodes，而是需要一定节点数之后才转化为 TreeNodes，说白了就是权衡时间和空间。
这段内容还说到：当 hashCode 离散型很好的时候，树型 bin用到的概率就会非常小，因为i数据均匀分布在每一个 bin 中，几乎不会有 bin 中链表长度达到树化阙值。但是在随机 hashCode 下，离散型可能会变得很差，然而 JDK 又不能阻止用户实现这种不好的 hash 算法，因此就可能导致不均匀的数据分布。不理想情况下随机 hashCode 算法下所有 bin 中节点的分布频率会遵循泊松分布，我们可以看到，一个 bin 中链表长度达到 8 个元素的概率为 0.00000006，几乎是不可能事件。所以，之所以选择 8，不算随便决定的，而是根据概率统计决定的。由此可见，发展将近 30 年的 JAVA 中每一项改动和优化都是非常严谨和科学的。
面试答案：hashCode 算法下所有桶中节点的分布会遵循泊松分布，这时一个桶中链表长度超过 8 个元素的概率非常小，权衡空间和时间复杂度，所以选择 8 这个数字。
扩展补充：
- Poisson分布（泊松分布），是一种统计与概率学里面常见到的离散[概率分布]。泊松分布的概率函数为：
泊松分布的参数 A 是单位时间（或者单位面积）内随机事件的平均发生次数。泊松分布适合于描述单位时间内随机事件发生的次数。
以下是我在研究这个问题的时候，在一些资料上面翻看的翻译，供大家参考：
红黑树的平均查找长度是 O(logn)，如果长度为 8，平均查找长度为 log(8) = 3，链表的平均查找长度为 n / 2，当长度为 8 的时候，平均查找长度为 8 / 2 = 4，这才有转换成树的必要；链表长度如果是小于等于 6，6 / 2 = 3，而log(6) = 2.6，虽然速度也很快，但是转化为树结构和生成树的时间并不会太短。
4.5、MIN_TREEIFY_CAPACITY
当 HashMap 里面的数量超过这个值的时候，表中的桶才能进行树化，否则桶内元素太多的时候会扩容，而不是树化为了避免扩容、树化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD（8）
// 桶中结构转化为红黑树对应的数组长度最小的值
static final int MIN_TREEIFY_CAPACITY = 64;
4.6、UNTREEIFY_THRESHOLD
当链表的值小于等于 6 的时候则会从红黑树转化为链表
// 当桶（bucket）上的结点数小于这个值，树转为链表
static final int UNTREEIFY_THRESHOLD = 6;
4.7、table（重点）
table 用来初始化（长度必须是 2 的 n 次幂）
// 存储元素的数组
transient Node<K,V>[] table;
在 JDK1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构，其中 table 就是 HashMap 中的数组，JDK1.8之前数组类型是 Entry<K,V> 类型。从 JDK1.8之后是 Node<K,V> 类型。只是换了个名字，都实现了一样的接口：Map.Entry<K,V>。负责存储键值对数据的。
4.8、entrySet
用来存放缓存
// 存放具体元素的集合
transient Set<Map.Entry<K,V>> entrySet;
4.9、size（重点）
HashMap 中存放元素的个数
// 存放元素的个数，注意这个不等于数组的长度
transient int size;
size 为 HashMap 中 K - V 的实时数量，不是数组 table 的长度。
4.10、modCount
用来记录 HashMap 结构的修改次数
// 每次扩容和更改 map 结构的计数器
transient int modCount;
4.11、thresold（重点）
用来调整大小下一个容量的值计算方式为：（容量 * 负载因子）
// 临界值 当实际大小（容量*负载因子）超过临界值时，会进行扩容
int threshold;
4.12、loadFactor（重点）
哈希表的负载因子（默认为 0.75）
// 负载因子
final float loadFactor;// 0.75f
说明：
- loadFactor 是用来衡量 HashMap 满的程度，表示 HashMap 的疏密程度，影响 hash 操作到同一个数组位置的概率，计算 HashMap 的实时负载因子的方法为：size / capacity，而不是占用桶的数量去除以 capacity。capacity 是桶的数量，也就是 table 的长度 length。
- loadFactor 太大导致查找元素的效率降低，太小导致数组利用率降低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的 一个比较好的临界值。
- 当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 了，表示 HashMap 太挤了，需要扩容，而扩容这个过程涉及到的 rehash、复制数据等操作，非常消耗性能。所以开发中尽量减少扩容的次数，可以通过创建 HashMap 集合对象的时候指定初始容量来尽量避免。
- 在 HashMap 的构造器中可以定制 loadFactor
// 构造方法，构造一个带指定初始容量和负载因子的空HashMap
HashMap(int initialCapacity, float loadFactor);
为什么加载因子 loadFactor 设置为 0.75，初始化临界值 thresold 是 12？
loadFactor 越趋近于 1，那么数组中存放的数据（entry）也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0 ，数组中存放的数据（entry）也就越少，也就越稀疏。
如果希望链表尽可能少些，要提前扩容，有的数组空间可能一直没有存储数据，负载因子尽可能小一些。
举例：
负载因子是0.4,那么 16 * 0.4 --> 6 如果数组中满6个空间就扩容会导致数组利用率过低。
负载因子是0.9,那么 16 * 0.9 --> 14 那么这样就导致链表有点多，导致查找 元素效率较低。
所以既要兼顾数组利用率又考虑链表不要太多，经过大量测试 0.75 是最佳方案。
**thresold **计算方式：capacity （数组长度默认6） * loadFactor（负载因子默认 0.75）== 12
这个值是当前已经占用数组长度的最大值。当 size >= thresold（12）的时候，那么就要考虑对数组的 resize（扩容），也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准，扩容之后的 HashMap 的容量是之前容量的 两倍。
5、HashMap 的构造方法
HashMap 中一共有四种构造方法，它们分别如下：
5.1、HashMap()
构造一个空的 HashMap ，默认初始化容量（16）和默认负载因子（0.75）
public HashMap() {
// 将默认的负载因子0.75赋值给loadFactor，并没有创建数组
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
5.2、HashMap(int initialCapacity)
构造一个具有初始指定容量和默认负载因子（0.75）的 HashMap.
// 指定“容量大小”的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
5.3、HashMap(int initialCapacity，float loadFactor)构造方法
/**
* 构造方法
* @param initialCapacity 哈希表的初始化容量
* @param loadFactor 负载因子大小
*/
public HashMap(int initialCapacity, float loadFactor) {
// 如果初始化容量 < 0的时候，直接抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// MAXIMUM_CAPACITY：数组的最大容量值 2<<<30 不当初始化容量大于最大值的时候，则赋值为最大容量值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 如果负载因子的值小于等于0或者不是一个数字的时候，则报错
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 通过初始化容量给扩容阙值进行赋值，确定哈希表的长度为2的次方数
this.threshold = tableSizeFor(initialCapacity);
}
// 这里，最后调用了tableSizeFor函数来给 thresold（用来调整大小的时候下一个容量的值）
/*
返回比指定cap容量大的最小2的n次幂数：
前面第一遍讲述的应该有些小伙伴难以理解，这里我在举例解析一下：
-------------------------------------------------------
首先假定传入的cap = 10
则，n = 10 -1 => 9
n |= n >>> 1 就等同于 n = (n | n >>> 1),所以：
(位运算不懂的可以去看我的《Java基础提高之位运算》这篇文章)
9 => 0b1001 9 >>> 1 => 0b0100
n |= n >>> 1; ===> 0b1001 | 0b0100 => 0b1101
n |= n >>> 2; ===> 0b1101 | 0b0011 => 0b1111
n |= n >>> 4; ===> 0b1111 | 0b0000 => 0b1111
n |= n >>> 8; ===> 0b1111 | 0b0000 => 0b1111
n |= n >>> 16; ===> 0b1111 | 0b0000 => 0b1111
得到：
0b1111 => 15
返回：
return 15 + 1 => 16
-------------------------------------------------------
如果cap 不减去1，即直接使n等于cap的话，int n = cap;
我们继续用上边返回的cap => 16 传入tableSizeFor(int cap)：
cap = 16
n = 16
16 => 0b10000 16 >>> 1 => 0b01000
n |= n >>> 1; ===> 0b10000 | 0b01000 => 0b11000
n |= n >>> 2; ===> 0b11000 | 0b00110 => 0b11110
n |= n >>> 4; ===> 0b11110 | 0b00001 => 0b11111
n |= n >>> 8; ===> 0b11111 | 0b00000 => 0b11111
n |= n >>> 16; ===> 0b11111 | 0b00000 => 0b11111
得到：
0b11111 => 31
返回 return 31 +1 => 32
而实际情况是应该传入cap = 16 , n = cap -1 = 15
15 => 0b1111
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
经过上面运算后得到：还是15
返回结果：
return 15 + 1 = 16
所以我们得出结果：
防止 cap 已经是 2 的幂数情况下。没有这个减 1 操作，
则执行完几条无符号位移或位运算操作之后，返回的cap(32)将是实际所需cap(16)的 2倍。
最后在解释一下为什么要刚好移动31位呢？因为我们知道 int 转化位二进制的话是32位，但是int类型的
最大值是2^31 - 1，只有31位，因为是无符号的移动，所以这里我们只需要移动31位
*/
static final int tableSizeFor(int cap) {
// 这里为什么要减一，因为cap是32位的二进制数字，而我们最后得到的是将所有可用位的二进制位数转化为1
// 如果不减一的话，当我们传入的刚好是2的次方数的话，就会出现得到的是我们传入的数的2倍，这样就不符合了
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;
}
说明：
对于this.thresold = tableSizeFor(initialCapacity);疑问？
tableSizeFor(initialCapacity) 判断指定的初始化容量是否是 2 的 n 次幂，如果不是那么会变为比指定初始化容量大小的大的最小的 2 的 n 次幂。
但是注意，在 tableSizeFor 方法体内部计算后的数据返回给调用这里了，并且直接复制给 thresold 边界值了。有些人会觉得这里是一个 bug，应该这样书写：
this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
这样才符合 thresold 的意思（当 HashMap 的 size 达到 thresold 这个阙值的时候会扩容）
但是请注意，在 JDK1.8 之后的构造方法中，并没有对 table 这个成员变量进行初始化，table 的初始化被推迟到了 put 方法中，在 put 方法中会对 thresold 进行重新计算（准确来说是第一次调用 put 方法的时候对 table 进行初始化的时候调用 resize 作为table的数组长度）。
5.4、HashMap(Map<? extends K, ? extends V> m)
包含另一个 Map 的构造函数：
// 构造一个映射关系与指定 Map 相同的新的 HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 获取参数集合的长度
int s = m.size();
if (s > 0) { // 判断集合的参数是否大于0，因为只有大于0才有数据嘛
if (table == null) { // 判断table 是否已经初始化
// 未初始化，s 为 m 的实际元素个数
float ft = ((float)s / loadFactor) + 1.0F; // 得到新的扩容阙值
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY); // 新的扩容阙值 ft 自动向下转型为 int
if (t > threshold) // 此时 thresold 为0
threshold = tableSizeFor(t);
}
// 如果 table 已经初始化过了，并且m的元素个数大于阙值，则进行扩容操作扩容
else if (s > threshold)
resize();
// 将集合m 中的所有元素放入到 HashMap 中
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);
}
}
}
注意：
面试问题：float ft = ((float) s / loadFactor) + 1.0F; 这一行代码中为什么要加 1.0F 呢？
(float)ft / loadFactor的结果是小数，加 1.0F 与 int ft 相当于是对小数做一个向上取整以尽可能地保证更大容量，更大地容量能够减少 resize() 地调用次数（为了效率，应当尽量减少扩容地次数）。所以 + 1.0F 是为了获得更大地容量。
例如：原来的集合数量是 6个，那么 6 / 0.75 是 8，由于 8 是 2 的 n 次幂，那么
if(t > thresold) thresold = tableSizefor(t); 执行过后，新的数组大小就是 8 了。然后原来数组的数据就会存储到长度是 8 的新的数组中了，这样会导致在存储元素的时候，容量不够，还得继续扩容，那么性能就降低了，而如果 + 1呢，数组直接变为 16了，这样可以减少数组的扩容。
6、内部类
6.1、Node 内部类
Node是一个典型的单链表节点，其中，hash 用来存储 key 计算的来的 hash 值。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;// hash用来存储key计算得来的hash值
final K key;// 键
V value;// 值
Node<K,V> next;// 下一个node节点
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; }
public final int hashCode() {// 调用底层c++ 返回Key/Value的哈希码值，如果此对象为null,则返回0
return Objects.hashCode(key) ^ Objects.hashCode(value);// 将Key/Vaule
}
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;
}
}
6.2、TreeNode 内部类
TreeNode内部类，它继承自 LinkedHashMap 中的 Entry 类，关于 LinkedHashMap.Entry 这个类之后会单独发文章论述，TreeNode 是一个典型的树型节点，其中，prev 是链表中的节点，用于在删除元素的时候可以快速找到它的前置节点。
// 位于HashMap中,文章接下来会逐步分析
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中，典型的双向链表节点，这个类之后会单独发文章论述
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
7、HashMap 的成员方法
7.1、put(K key , V value) 方法
put 方法是比较复杂的，实现步骤大致如下：
- 先通过 hash 值计算出 key 映射到哪个桶
- 如果桶上没有碰撞冲突，则直接插入
- 如果出现碰撞冲突了，则需要处理冲突
- 如果该桶使用红黑树处理冲突，则调用红黑树的方法插入数据
- 否则采用传统的链式方法插入。如果链的长度达到临界值，则把链表转化为红黑树
- 如果桶中存在重复的键值，则为该键替换新值 value
- 如果 size 大于阙值 thresold，则进行扩容
具体的方法如下：
public V put(K key, V value) {
// 调用hash(key)计算出key的hash值
return putVal(hash(key), key, value, false, true);
}
说明：
- HashMap 只提供了 put 用于添加元素，putVal 方法只是给 put 方法调用的一个方法，并没有提供给用户使用。所以我们重点看putVal 方法。
- 我们可以看到在 putVal 方法中 key 在这里执行了一下 hash 方法，来看一下 hash 方法是如何实现的
static final int hash(Object key) {
int h;
// 如果 key 为null，则hash 的值为0
// 否则调用 key 的hashCode() 方法计算出key 的哈希值然后赋值给h
// 后与h无符号右移16位后的二进制进行按位异或得到最后的hash值
// 这样做是为了使计算出来的hash更分散
// 为什么要更分散呢？因为越分散，某个桶的链表长度就越短，之后生成的红黑树越少，效率越高
// 可能你还有疑问？为什么让高16位参与运算就能使得hash值更加分散呢？
// 因为当数组的长度较短的时候，高位的字节可能就无法参与运算了，只有低位的才能参与运算，这样会导致
// hash值的分布不均匀，让高位参与运算可以使得hash值分散得更加均匀
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
从上面可以得知 HashMap 是支持 key 为空的，而 HashTable 是直接用 key 来获取 hashCode 所以 key 为空会抛出异常
解读上述的 hash 方法：
我们先研究下 key 的哈希值是如何计算出来的，key 的哈希值是通过上述方法计算出来的。
这个哈希方法首先计算出 key 的 hashCode 赋值给 h，然后与 h 无符号右移 16 位后的二进制进按位异或得到最后的 hash 值。
在 putVal 函数中使用到了上述 hash 函数计算的哈希值：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
...
if ((p = tab[i = (n - 1) & hash]) == null) // 这里的n表示数组长度16 ，公式
// (length - 1) & hash = 桶位下标 当数组长度为2的n次幂数时，
// 该公式相当于：hash % length 哈希值对数组长度取余
// 例如：hash % 32 = hash & (32-1)
...
}
计算过程如下所示：
说明：
key.hashCode();返回散列值也就是 hashCode，假设随便生成的一个值。- n 表示数组初始化的长度是 16。
- &（按位与运算）：运算规则：相同的二进制数位上，都是 1 的时候，结果为 1，否则为 0；
- ^（按位异或运算）：运算规则：相同的二进制数位上，数字相同，结果为0，不同为1；
最后获得 0101 ==> 下标为 5 的桶
简单来说就是：
高 16 bit 不变，低 16bit 和高 16bit 做了一个异或操作（得到的 hashCode 转化为 32 位二进制，前 16 位和后 16 位, 低16bit 和高 16bit 做了一个异或 ）。
问题：为什么要这样操作呢？
如果当 n 即数组长度很小，假设是 16 的话，那么 n - 1即为 1111，这样的值和 hashCode 直接按位与操作，实际上只使用了哈希值的后 4 位，如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决乐这个问题。
下面，我们来看看 putVal 方法，看看它到底做了什么。
主要参数：
- hash：key 的 hash 值
- key：原始的 key
- value：要存放的值
- onlyIfAbsent：如果 true 代表不更改现有的值
- evict：如果为 false 表示 table 为创建状态
putVal 方法源代码如下所示：
/**
*
* @param hash 通过扰动函数hash计算key值得到的hash值，其中高16位和低16位都参与了运算
* @param key key值
* @param value value
* @param onlyIfAbsent 代表如果散列表中已经存在该key，就替换该value值
* @param evict
* @return
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab：引用当前 hashMap 的散列表
// p：表示当前散列表的元素
// n：表示散列表数组的长度
// i：表示路由寻找的结果
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 延迟初始化逻辑，第一次调用 putVal 的时候会初始化 hashMap 对象中最耗费内存的散列表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 最简单的一种情况，寻址找到的桶位，刚好是null，这个时候，直接将当前 k -v => node 扔进去就可以了
// 寻址的方式通过 length - 1 & hash 进行寻址，所得到的结果一定在0 - length - 1中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// e：临时node元素，不为null的话表示找到了一个与当前要插入的 key - value 一致的key的元素
// k：表示临时的一个key，用于记录当前计算出来的桶位节点p的key值
Node<K,V> e; K k;
// 表示桶位中的该元素，与你当前插入元素的key完全一致，表示后续需要进行替换value操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 到这里表示桶位节点不为空，并且插入节点的key和桶位节点不同
// 所以，这里又要判断当前桶位节点 p 是否是红黑树节点
else if (p instanceof TreeNode)
// 是红黑树的话直接插入就可
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 表示不是红黑树节点，就是链表结构，并且插入前还没达到要树化的地步
else {
// 注意，是链表结构的话需要想到，我们之前比较的p节点是桶位节点，并没有与链表中的其他
// 节点比较 key 值是否相同，如果相同还是要进行替换操作，不相同则将其添加到链表的末尾
for (int binCount = 0; ; ++binCount) {
// 双指针来确定链表的末尾元素，e 为空的时候p是链表最末尾的元素，要将其插入到p节点的后面
if ((e = p.next) == null) {
// 插入操作
p.next = newNode(hash, key, value, null);
// 注意，在插入成功后，需要判断满不满足树化的条件，TREEIFY_THRESHOLD = 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不等于null，条件成立说明，找到了一个与你插入元素key完全一致的数据，需要进行替换操作
// 判断临时节点 e 是否为空来代表是否是替换操作（看当前哈希表中是否存在相同key值的节点）
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// modeCount：表示散列表结构被修改次数，替换 Node元素的value不计数
++modCount;
// 插入新元素 size++，如果自增后的值大于扩容阙值，则触发扩容机制
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
- 计算 key 的 hash 值
- 如果哈希表 table 没有初始化（为 null）或者长度为0，则先进行扩容处理
- 如果 key 所在的桶没有元素，则直接插入；
- 如果 key 所在的桶中的第一元素的 key 与待插入的 key 相同，说明找到了元素，转后续 [9] 操作处理
- 如果第一个元素是树节点，则调用树节点的 putTreeVal() 寻找元素或者插入树节点
- 如果不是以上三种情况，则遍历对应的链表查找 key 是否存在于链表中
- 如果找到了对应 key 的元素，则转后续流程 [9] 处理；
- 如果没找到对应 key 的元素，则在链表最后插入一个新节点并判断是否需要树化；
- 如果找到了对应 key 的元素，则判断是否需要替换旧值，并直接返回旧值；
- 如果插入了元素，则数量 +1 并判断是否需要扩容；
7.2、扩容方法：resize()
扩容机制：
什么时候才需要扩容？
当 HashMap 中的元素个数超过数组大小（数组长度） * loadFactor（负载因子）的时候，就会进行数组扩容，loadFactor 的默认值是 0.75.
HashMap 的扩容是什么？
进行扩容，会伴随着依次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。
HashMap 在进行扩容干的时候，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n - 1) & hash 的结果相比，只是多了一个 bit 位，所以节点要么就在原来的位置，要么旧被分配到原位置 + 旧容量这个位置。
例如，我们从 16 扩容到 32 的时候，具体的变化如下所示：
因此元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n - 1 的标记范围在高位多 1 bit（红色），因此新的index就会发生这样的变化。
说明：
5 是假设计算出来的原来的索引，这样旧验证了上述所描述的：扩容之后所有节点要么就在原来的桶位上，要么旧倍分配到原位置 + 旧容量这个位置。
因此，我们在扩充 HashMap 的时候，不需要重新计算 hash ，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就可以了，是 0 的话索引没变，是 1 的话索引变成 原位置 + 旧容量，可以看看下图为 16 扩充为 32 的 resize 示意图。
正是由于这样巧妙地 rehash 方式，既省去了重新计算 hash 值得时间，而且同时，由于新增的 1 bit 是 0 还是 1 可以认为是堆积的，在 resize 的过程中保证了 rehash 之后每个桶上的结点数一定小于等于原来桶上的节点数，保证了 rehash 之后不会出现更严重的 hash 冲突，均匀的把之前的冲突的节点分散到新的桶中了。
源码 resize 方法的解读：
// 为什么需要扩容？
// 为了解决哈希冲突导致的链化影响查询效率的问题，扩容会缓解该问题
final Node<K,V>[] resize() {
// oldTab：引用扩容前的哈希表
Node<K,V>[] oldTab = table;
// oldCap：表示扩容之前哈希表 table 数组的长度，当oldTab为null的时候，代表第一次插入元素，需要进行扩容处理
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// oldThr：表示扩容之前的扩容阙值，触发本次扩容的阙值
int oldThr = threshold;
// newCap：扩容之后的table数组的大小
// newThr：扩容之后下次再次触发扩容的条件
int newCap, newThr = 0;
// 条件如果成立说明 hashMap 中的散列表已经初始化过了，是一次正常的扩容情况
if (oldCap > 0) {
// 扩容之前的table数组大小已经达到最大的阙值了，则不扩容，且设置扩容条件为Integer最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// oldCap 左移一位实现数值翻倍，并且赋值给newCap，newCap小于数组的最大值，且扩容之前的数组长度oldCap大于等于默认数组长度16
// 这种情况下，则下一次扩容的阙值 等于当前阙值翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// oldCap == 0，说明当前散列表table 还没有被初始化为null
// 注意，oldThr>0且hashMap为null的情况只有三种情况：
// 1.new HashMap(int , float)
// 2.new HashMap(int)
// 3.new HashMap(Map)，并且这个Map有数据
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// oldCap == 0，oldThr == 0 说明是使用空构造方法进行创建的hashMap对象
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; // 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12
}
// 什么情况下 newThr才可能为0呢？
/**
* 两种情况；
* 1.当前hashMap中的散列表已经初始化过但是不满足((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
* oldCap >= DEFAULT_INITIAL_CAPACITY)这个条件，此时newThr会为0
* 2.当oldCap == 0但是 oldThr > 0的时候，此时newThr也会为0
* 第二种情况多处出现于构造方法的时候给定了散列表数组tab的长度，然后生成了thresola的值
*
* newThr为0的时候，通过newCap和loadFactor计算出一个newThr
*/
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 将新的扩容阙值赋值给thresold
// 根据新数组的长度创建出一个更长、更大的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 条件成立，说明hashMap在本次扩容之前，table不为null，即里面有数据
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
// e表示当前node节点，表示当前散列表中的每一个桶节点
Node<K,V> e;
// 说明当前桶位中有数据，但是数据具体是单个数据，还是链表，还是红黑树不知道
if ((e = oldTab[j]) != null) {
// 方便 JVM GC 回收内存
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;
// hash -> .... 1 1111
// hash -> .... 0 1111
// 0b 10000 oldCap
// 跟原数组的长度相比，比较判断高位是否为1来决定是存放在高位链表还是低位链表
// 为0的话要存放在低位链表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 这种情况是为1，代表要存放在高位链表中
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 将链表放入到数组中
if (loTail != null) {
// 这里注意，一定要把不管是高位链表还是低位链表的loTail尾节点的next设置为null，因为我们不能确定
// 尾部节点loTail或者hiTail是原链表的最后一个节点，如果不是最后一个节点那么它的next肯定是不为null，就会出错
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 高位链表，存放在扩容之后的数组的下标位置为当前数组下标位置 + 扩容之前数组长度
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
- 如果使用的是默认空构造方法：则第一次插入元素的时候初始化为默认值，容量为 16，扩容门槛为 12；
- 如果使用的是 非默认空构造方法：则第一次插入元素的时候初始化容量等于扩容门槛，扩容门槛在构造方法里面等于传入容量向上最近的 2 的 n 次方。
- 如果旧容量大于 0，则新容量等于旧容量的2倍，但是不超过最大容量 2 的 30次方，新扩容门槛为旧扩容门槛的 2 倍。
- 创建一个新容量的 Node数组
- 搬移元素，原链表分化成两个链表，低位链表存储在原来的桶中，高位链表搬移到原来的 桶位置 + 旧容量 的位置。
7.3、删除方法 remove()
删除方法就是首先先找到元素的位置，如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除，树小于等于 6 的时候就要转化为链表。
删除 remove 方法：
// remove方法的具体实现在removeNode方法中，所以我们重点看下removeNode方法
// 根据key删除
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
// 根据key,value 删除
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
remoevNode 方法：
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// tab：引用当前hashMap中的散列表
// p：当前node元素
// n：表示当前散列表数组长度
// index：表示寻址结果
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 条件成立：说明散列表不为null并且散列表中是有数据的，并且hash对应的桶位中是有数据的，需要进行查找操作，并且删除
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// node：表示查找到的结果
// e：表示当前node的下一个元素
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节点是因为删除链表中的节点的时候需要当前节点的前一个节点
p = e;
} while ((e = e.next) != null);
}
}
// 判断node不为null的话，说明按照key查找到需要删除的数据了
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 第一种情况：node是树节点，说明需要进行树节点移除操作
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 第二种情况：说明我们要删除的数据是桶位头节点，则将该元素的下一个元素放至桶位中
else if (node == p)
tab[index] = node.next;
// 第三种情况：将当前元素p的下一个元素设置成要删除元素的下一个元素
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
7.4、查找元素方法 get()
查找方法，通过元素的 key 找到 value。
代码如下：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
get 方法主要调用的是 getNode()，代码如下：
final Node<K,V> getNode(int hash, Object key) {
// tab：引用当前 hashMap 的散列表
// first：当前hash值对应的桶位中的头元素
// e：临时node元素
// n：table数组长度
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 满足该条件说明：当前table散列表不为null并且散列表中有元素，并且当前hash值对应桶位的头元素不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 第一种情况：定位出来的桶位元素 即为咱们要get的数据
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 第二种情况：满足条件：说明当前桶位不是单个元素，要么是红黑树，要么是链表
if ((e = first.next) != null) {
// 说明是红黑树
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 说明是链表
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
小结：
- get 方法实现的步骤：
- 通过 hash 值获取该 key映射到的桶
- 桶上的 key 就是要查找 key，则直接找到并返回
- 桶上的 key 不是要找的 key，则查看后续的节点：
- 如果后续节点是红黑树节点，通过调用红黑树的方法根据 key 获取 value
- 如果后续节点是链表节点，则通过循环遍历链表根据 key 获取 value
8、遍历 HashMap 的几种方式
分别遍历 key 和 values
for (String key : map.keySet()) {
System.out.println(key);
}
for (Object vlaue : map.values() {
System.out.println(value);
}
使用 Iterator 迭代器迭代
Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Object> mapEntry = iterator.next();
System.out.println(mapEntry.getKey() + "---" + mapEntry.getValue());
}
通过 get 方法（不建议使用）
Set<String> keySet = map.keySet();
for (String str : keySet) {
System.out.println(str + "---" + map.get(str));
}
说明：
根据阿里开发手册，不建议使用这种方式，因为迭代两次，keySet 获取 Iterator 迭代器一次，还有通过 get 又迭代一次，降低性能。
- JDK1.8 以后使用 Map 接口中的默认方法：
default void forEach(BiConsumer<? super K,? super V> action)
// BiConsumer接口中的方法：
void accept(T t, U u) 对给定的参数执行此操作。
参数
t - 第一个输入参数
u - 第二个输入参数
遍历代码：
HashMap<String,String> map = new HashMap();
map.put("001", "zhangsan");
map.put("002", "lisi");
map.forEach((key, value) -> {
System.out.println(key + "---" + value);
});
9、总结
- HashMap 是一种散列表，采用（数组 + 链表 + 红黑树）的存储结构；
- HashMap 的默认初始容量为 16（1 <<< 4），默认负载因子为 0.75F，数组容量必须是 2 的 N 次方，通过 tableSizeFor 方法实现
- HashMap 扩容时每次容量变为原来的两倍
- 当桶的数量小于 64 的时候不会进行树化，只会扩容
- 当桶的容量大于 64 且单个桶中元素的数量大于 8 的时候，进行树化
- 当单个桶中元素数量小于 6 的时候，进行反树化（即转化为链表）
- HashMap 是非线程安全的容器
- HashMap 查找添加元素的时间复杂度:
- 不管插入还是查找，由 key 获取 hash 值然后定位到桶得时间复杂度都是 O(1)，其实真正决定时间复杂度的实际上是桶里面链表 / 红黑树的情况
- 如果桶里面没有元素，那么直接将元素插入 / 或者直接返回 null。时间复杂度都是 O(1)，如果里面有元素，那么久沿着链表或者红黑树进行遍历，时间复杂度是O(n) 或者 O(logn)，元素数量大于等于 8 且数组长度大于等于 64的时候为红黑树。
- 所以说，平均时间复杂度很难说，只能说在最优的情况下是 O(1)