首页
更多
目录大纲

HashMap

7 0

HashMap

HashMap集合简介

  • HashMap 基于哈希表的 Map 接口进行实现，是以 key-value 的存储形式进行存放键值对。HashMap 的实现是不同步的，这意味着它不是线程安全的。他的 key、value 都可以为 null。此外，HashMap 中的映射不是有序的。
  • JDK 1.8 之前 HashMap 由 数组+链表 组成，数组是 HashMap 的主体，链表则是主要为了解决 哈希冲突（两个对象调用的 hashCode 方法计算的哈希值一致导致计算的数组索引值相同） 而存在的（“拉链法”解决冲突）。
  • JDK 1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，“默认为8”）并且当前数组的长度大于 64 时，此时此缩影位置上的所有数据改为使用红黑树存储。

补充

将链表转换成红黑树前会进行一次判断，即使阈值大于 8，但是数组长度小于 64，此时并不会将链表变为红黑树。而是选择进行数组扩容。

为什么这么做

这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下编委红黑树结构，反而会降低效率。因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡。同时数组长度小于 64 时，搜索时间相对要快。
所以综上所述，为了提高性能和减少搜索时间，底层在阈值大于 8 且数组长度大于 64 时，链表才转换为红黑树。具体参考 treeifyBin 方法。
当然虽然增加了红黑树作为底层数据结构，结构变复杂了，但是阈值大于 8 且数组长度大于 64 时，链表转换为红黑树时，效率也变得更高效了。

特点

  1. HashMap 存储读取是无序的；
  2. 键和值都可以是 null，但是键位置只能是一个 null；
  3. 键位置是唯一的，底层的数据结构控制键；
  4. JDK1.8 以前数据结构是：链表+数组；
  5. JDK1.8 以后数据结构式：链表+数组+红黑树；
  6. 阈值（边界值）大于 8 并且数组长度大于 64，才将链表转为红黑树，为了提高效率。

2 HashMap底层数据结构

2.1 数据结构概念

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在的一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行速度和更快的存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构：就是存储数据的一种方式。

2.2 底层数据结构与存储过程

  1. HashMap<String,Integer> map = new HashMap<>();

    • 当创建 HashMap集 合对象的时候，在JDK8以前，构造方法创建一个长度为 16 的 Entry[] table 用来存储键值对数据的。
    • 在JDK8以后，不是在HashMap的构造方法底层创建数组了，是在第一次调用put方法时创建的数组，Node[] table 用来存储键值对数据的。

  2. 假设项哈希表中存储 小明-5 ，根据 key 调用 String 类中重写之后的 hashCode() 方法计算出值，然后结合 数组长度 并采用 特定算法（例如：对长度取余）计算出向 Node 数组中存储数据的空间的索引值。

    • 如果计算出的索引空间没有数据，则直接将该键值对存储到数组中；
    • 例如：（对照图）计算出的索引是 3，则 “小明-5” 就被放入第 3 个位置；

  3. 向哈希表中存储数据 王阿姨-23 ，假设该键值对结合数组长度计算出的索引值也是 6 ，且此时数组空间不为 null，那么底层会比较 王阿姨 和 老王 的 hash 值是否一致。

    • 如果不一致：则在此空间上划出一个节点来存储键值对 王阿姨-23 （见图）；
    • 这种方式就称为：拉链法；

  4. 向哈希表中存储数据 小明-18 ，那么其计算出的 索引值 值肯定是 3，且计算出的 hash 值相等，则此时发生 哈希冲突（哈希碰撞） 。此时会调用 小明-5 的 equals 方法对 小明-18 进行比较内容是否相等。

    • 若相等：将之后添加的数据的 value 覆盖之前的 value；
    • 若不相等：那么继续向下和其他数据的 key 进行比较，若都不相等，则再划出一个节点进行存储数据，若相等则继续按照覆盖的方法执行覆盖（见图）；

  5. 如果节点长度（链表长度）大于阈值 8 并且数组长度大于 64 则将链表改为红黑树进行存储。

存储示意图

2.2 存储过程面试题

面试题 1 ：哈希表底层采用何种计算方式计算hash值？还有那些算法可以计算出hash值？
解答：
1. HashMap 底层采用 key 的重写 hashCode() 方法结合数组长度进行无符号右移(>>>)、按位异或(^)、按位与(&)计算出索引。
2. 还可以采用：平方取中值法、取余法、伪随机数。
3. 10%8=2，11%8=3，其他计算方式效率较低，而位运算效率要高。

面试题 2 ：当两个对象的 hashCode 相等时会发生什么？
解答：
会发生哈希碰撞，若 key 值内容相同则替换旧的 value ，不然连接到链表的后面，直至链表长度超过阈值 8 且数组长度超过 64 时再采用红黑树存储。

面试题 3 ：何时会发生哈希碰撞，什么是哈希碰撞，如何解决哈希碰撞？
解答：
只要两个元素的 key 经过计算后得到的 hash 值相同就会发生碰撞。JSDK8 以前采用链表来解决哈希碰撞。JSDK8 以后采用链表+红黑树来解决哈希碰撞。

面试题 4 ：如果两个键的 hashCode 相同，如何存储键值对？
解答：
hashCode 相同，通过 equals 比较内容是否相同并递归地进行如下的比较操作。
相同：将新的 value 覆盖旧的 value。
不相同：将新的键值对添加到哈希表中。

2.3 扩容与小结

  1. 在不断的添加数据的过程中，会涉及到扩容问题。当超出临界值（且要存放的位置）时，进行扩容操作。
    • 默认的扩容方式：扩容为原来容量的 2 倍，并将原有的数据复制过来。
    • 在 Java 中数组的长度时固定的，所以需要构造新的数组对象来存储原来的数据。
  2. 综上所述，当位于一个链表中的元素较多时（即：hash 值相等但是内容不相等的元素较多时）通过 key 值依次查找的效率较低。而 JDK1.8 中，哈希表存储采用 数组+链表+红黑树 实现，当链表长度（阈值）超过 8 且数组长度超过 64 时，转为红黑树存储法，大大减少了查找时间。

2.4 为什么使用红黑树

问题描述：针对传统 hashMap 的缺点，JDK1.8 为什么引入红黑树？这样结构不是更麻烦吗？为何阈值大于 8 就要换成红黑树？

  • JDK1.8 以前的方法，即使哈希函数取值再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存档到同一个桶中时，这个桶下就有一条长链表，这时候 HashMap 就相当于一个单链表，加入单链表有 n 个元素，遍历的时间复杂度就是 O(n) 失去了其优势。
  • 针对这种情况，JDK1.8 中引入了红黑树（红黑树的查找时间复杂度为：O(logn)）来优化这个问题，当链表长度很小的时候，即使遍历，速度也很快。一旦链表长度不断被增加，其查询速度对性能一定会有影响，所以采用红黑树算法。
  • 阈值为什么取 8 ，见后面源码解析。
graph TD

A(开始) --> B{Table是否为空<br>或length=0} --> |否| H[根据键值key计算hash值<br>得到插入数组的索引i] --> C(table&#91i&#93==null) --> |是| D[直接插入] --> E{++Size ><br>threshold} --> |否| F(结束)

B --> |是| G[resize - 扩容] --> |调用hashCode方法| H

C --> |否| I{key是否存在} --> |否| J{table&#91i&#93<br>是否为treeNode} --> |是| K[红黑树直接<br>插入简直对] --> E

I --> |是| L[直接覆盖value] --> E

E --> |是| M[resize - 扩容]

J --> |否| N[开始遍历链表<br>准备插入] --> O{链表长度<br>是否大于8} --> |否| P[链表插入&#44 若<br>key存在直接<br>覆盖value] --> E

O --> |是| Q[转换红黑树&#44<br>插入键值对]

说明：

  1. size 表示 HashMap 中 k-v的实时数量 ，注意这个不等于数组长度。
  2. threshold（临界值）= capacity（容量）* loadFactor（加载因子）。
  3. 临界值是当前已占用数组长度的最大值。size 超过这个临界值就重新 resize（扩容），扩容后的 HashMap 容量是之前容量的两倍。

3 HashMap继承关系

HashMap继承关系如下：

  • Cloneable 空接口，表示可以克隆。创建并返回 HashMap 对象的一个副本。
  • Serializable 序列化接口。属于标记性接口。HashMap 对象可以背序列化也可以被反序列化。
  • AbstractMap 父类提供了 Map 实现接口。以最大限度地减少实现此接口所需的工作。

补充问题：
通过上述继承关系我们发现一个问题。HashMap 已经继承了 AbstractMap 而 AbstractMap 类实现了 Map 接口，那 HashMap 为什么还要再继续实现 Map 接口呢？同样在 ArrayList 中与在 LinkedList 中都是这样的结构的设计思路是什么？
解答：
据 java 集合框架创始人 Josh Bloch 描述，这样写是一个失误。在 java 集合框架中，类似这样的写法很多，最开始写 java 集合框架的时候，他认为这样写在某些地方可能是有价值的，直到他意识到错了。很显然，JDK 的维护者，后来不认为这个小小的失误值得去修改，所以就这样保留下来了。

4 HashMap集合类成员

4.1 成员变量

4.1.1 序列化版本号

private static final long serialVersionUID = 362498820763181265L;

4.1.2 集合的初始化容量（必须是2的n次幂）

//默认的厨师容量是16 -- 1 << 4 相当于 1*2^4 -- 1*16
static final int DEFAULE_INITAL_CAPACITY = 1 << 4;

问题： 为什么必须是 2 的 n 次幂？如果输入值是 10 会怎么样？
解答： HashMap 构造方法还可以指定集合的初始化容量大小：

HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子（0.75）的空 HashMap。

综上所述，我们已经知道，当向 HashMap 中添加一个元素的时候，需要根据 key 的 hash 值，去确定其在数组中的具体位置。HashMap 为了存取高效，要尽量减少 哈希碰撞，就是要尽量吧数据分配均匀，每个链表长度大致相同。这个实现，就是“把数据存到哪个链表中”的算法。

为什么必须是 2 的 n 次幂 该算法的实际就是取模，hash%length ，计算机中直接取余的笑料并不如位运算。所以源码中作乐优化，使用了 hash%(length-1) ，而实际上 hash%length 的前提条件就是 length 必须是 2 的 n 次幂。

为什么能均匀分布减少哈希碰撞 2 的 n 次幂实际就是 1 后面 n 个 0 ，2 的 n 次方 - 1 实际就是 n 个 1。

举例说明：
按位与运算：相同的二进制数位上，都是 1 的时候，结果为 1，否则为 0。

"如果是 2 的 n 次幂"
例如长度为 8 的时候, 3&(8-1)=3 2%(8-1)=2 , 不同位置上不碰撞。
例如长度 length 为 8 的时候, 8 是 2 的 3 次幂，二进制是：00001000
00001000 → 8
-      1
--------
00000111 → 7

如下所示：

hash & (length - 1)
3 & (8 - 1) = 3
  00000011 → 3 hash
& 00000111 → 7 length-1
----------------------
  00000011 → 3 数组下标

hash & (length - 1)
2 & (8 - 1) = 2
  00000010 → 2 hash
  00000111 → 7 length-1
----------------------
  00000010 → 2 数组下标

说明：上述计算结果是不同位置上的，不发生碰撞。

"如果不是 2 的 n 次幂"
例如长度为 9 的时候, 3&(9-1)=0 2&(9-1)=0 , 都在 0 位置上发生了哈希碰撞。
例如长度 length 为 9 的时候, 9 不是 2 的 n 次幂, 二进制是：00001001
00001001 → 9
-      1
--------
00001000 → 8

如下所示：

hash & (length - 1)
3 & (9 - 1) = 0
  00000011 → 3 hash
& 00001000 → 8 length-1
----------------------
  00000000 → 0 数组下标

hash & (length - 1)
2 & (9 - 1) = 2
  00000010 → 2 hash
& 00001000 → 8 length-1
----------------------
  00000000 → 0 数组下标

说明：上述计算结果都在 0 位置上，发生了哈希碰撞。

注意：当然，如果不考虑效率，直接取余即可（就不需要要求长度必须是 2 的 n 次方了）

4.1.3 小结

  1. 由上面可以看出，当我们根据 key 的 hash 确定其在数组的位置时，如果 n 为 2 的幂次方，可能数组数组的一些位置永远不会插入数据，浪费数组的空间，增大 哈希冲突。
  2. 另一方面，一般我们可能会通过 % 取余来确定位置，这样也可以，只不过会降低性能。而且，当 n 为 2 的幂次方时满足：hash%(length-1) == hash%length
  3. 因此，HashMap 容量为 2 的幂次方的原因，就是为了数据的均匀分布，减少 哈希冲突。
  4. 如果创建 HashMap 对象时，输入的数组长度不是 2 的幂次方，HashMap 会通过不断的位运算和或运算得到距离其最近的 2 的幂次方的数。
    具体代码如下：
//创建HashMap集合对象，指定数组长度为10
HashMap map = new HashMap(10);
public HashMap(int initalCapacity) {
    this(initalCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initalCapacity, float loadFactor) {
    //initalCapacity = 10
    if(initalCapacity < 0)
        throw new IllegalArgumentException("Illegal inital capacity: " + initalCapacity);
    if(initalCapacity > MAXIMUN_CAPACITY)
        initalCapacity = MAXIMUN_CAPACITY;
    if(loadFactor <= 0 || FLoat.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initalCapacity);
    //initalCapacity = 10
}
static final int tableSizeFor(int cap) {
    //int cap = 10
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUN_CAPACITY) ? MAXIMUN_CAPACITY : n + 1;
}
代码解析：

由此可以看出，当在实例化 HashMap 实例时，如果给定来 initalCapacity（假设是10）由于 HashMap 的 capacity 必须都是 2 的幂指数 ，因此这个方法用于找到大于等于 initalCapacity 的最小 2 指数（如果已经是，则直接返回）。

算法分析：
  1. 对 cap 减 1 的操作：为了防止 cap 已经是 2 的幂次方。如果 cap 已经是 2 的幂次方，有没有执行 - 1 的操作，则执行完后面的无符号右移草组织好，返回的 capacity 将是这个 cap 的 2 倍。
  2. 如果 n 这时为 0（经过 cap - 1 后），则经过后面几次无符号右移操作后依然是 0，最后返回的 capacity 是 1（只讨论 n 不等于 0 的情况）。
  3. |（按位或运算）的运算规则是：相同的二进制位数上，都是 0 的时候，结果为 0，否则为 1。
第一次右移：
int n = cap - 1; // cap = 10 n = 9
n |= n >>> 1;
  00000000 00000000 00000000 00001001 → 9 n
| 00000000 00000000 00000000 00000100 → 4 n>>>1
-------------------------------------
  00000000 00000000 00000000 00001101 → 13 |=

由于 n 不等于 0，则 n 的二进制表示中总会有一个 bit 为 1，这是考虑最高位的 1。通过无符号右移 1 位，则将最高位的 1 右移了 1 位，再做或操作，使得 n 的二进制表示中与最高位的 1 紧邻的右边一位也为 1 。

第二次右移：
n |= n >>> 2;
  00000000 00000000 00000000 00001101 → 13 n
| 00000000 00000000 00000000 00000011 → 3 n>>>2
-------------------------------------
  00000000 00000000 00000000 00001111 → 15 |=

注意，这个 n 已经经过了 n |= n >>> 1; 的操作。

第三次右移：
n |= n >>> 4;
  00000000 00000000 00000000 00001111 → 15 n
| 00000000 00000000 00000000 00000000 → 0 n>>>4
-------------------------------------
  00000000 00000000 00000000 00001111 → 15 |=

以此类推。
注意，容量最大也就是 32 bit的正数，因此最后 n |= n >>> 16; 最多也就 32 个 1 （已经是负数。在执行 tableSizeFor 之前，对 initalCapacity 作了判断，如果大于 MAXIMUN_CAPACITY (2 ^ 30) 会执行位运算，所以这里面的位运算操作之后，最大为 30 个 1，不会大于等于 MAXIMUN_CAPACITY。30个 1，加 1 之后得到 2 ^ 30）

经过所有按位或运算之后将值赋给 threshold 。

4.2 红黑树转换

问题：为什么 Map 桶中节点个数超过 8 才转为红黑树结构？

8 这个阈值定义在 HashMap 中，针对这个成员变量，在源码的注释中只说明了 8 是 bin（bucket::桶）从链表转为树的阈值，但没有说明为什么是 8。
在 HashMap 对象中的说明为：

因为树节点的大小约为普通节点的 2 倍，所以我们只在箱子包含足够的节点时才使用树节点（参考 TREEIFY_THRESHOLD）。当它们变得太小（由于删除或调整大小）时，就会被转换会普通的桶。在使用分布良好的用户 hashcode 时，很少使用树箱。理想情况下，在随机哈希码下，箱子中节点的频率服从泊松分布。
(http://en.wikipedia.org/wiki/Poisson_distribution)
默认阈值为 0.75，平均参数约为 0.5，尽管由于调整粒度的差异很大，忽略方差，列表大小 k 的预期出现次数为 (exp(-0.5) * pow(0.5,k) / factorial(k))

4.2.1 链表节点泊松分布：

节点位置 存储概率
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 的两倍，所以只有当 bin 包含足够多的节点时才会转换成 TreeNodes，而“是否足够多”就是有 TREEIFY_THRESHOLD 的值决定的。当 bin 中节点数变少时，又会转成普通的 bin。并且查看源码可以发现，链表长度达到 8 就转成红黑树，长度降为 6 就传承普通 bin。

这样就解释了为什么不是一开始就将其转换为 TreeNodes，而是需要一定节点数才能转换为 TreeNodes，说白就是权衡了空间与时间。

当 hashCode 离散性很好的时候，树型 bin 用到的概率非常小，因为数据均匀分布在每个 bin 中，几乎不会有 bin 中链表的长度能够达到阈值。但是在随机 hashCode 下，离散性会变差，然而 JDK 又不能阻止用户实现这种不好的 hash 算法，因此就可能导致不均匀的数据分布。

不过理想情况下随机 hashCode 算法下所有 bin 中节点的分布频率会遵循泊松分布，我们可以看到，一个 bin 中链表长度达到 8 个元素的概率仅为 0.00000006，几乎是不可能事件，所以，之所以选择 8 ，不是随便决定的，而是根据概率统计决定的。

4.2.2 小结

4.2.2.1 泊松分布

Poisson分布（泊松分布），是一种统计与概率学里常见的离散[概率分布]。
泊松分布的概率函数为：

P(X=k)=\frac{\lambda^k}{k!}e^{-\lambda},k=0,1,...
泊松分布的参数 \lambda 是单位时间（或单位面积）内随机事件的平均发生次数。泊松分布适合描述单位时间内随机事件的发生次数。

4.2.2.2 参考解释

红黑树的平均查找长度是 log(n) ，如果长度为 8 ，平均查找长度为 log(8)=3 ，链表的平均查找长度为 \frac{n}{2} ，当长度为 8 时，平均查找长度为 \frac{8}{2}=4 ，这才有转换成树的必要，链表长度如果是小于等于 6，\frac{6}{2}=3 ，而 log(6)=2.6 ，虽然速度也很快，但是转化为树结构和生成树的时间并不会很短。

4.3 红黑树转回链表

//当桶(bucket bin)上的节点数小于这个值时树转为链表
static final int UNTREEIFY_THRESHOLD = 6;

当 Map 里面的数量超过这个值时，表中的桶才能树形化，否则桶内元素太多时会发生扩容，而不是树形化。为了避免扩容操作、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD(8)

//桶中结构转化为红黑树对应的数组长度的最小值
static final int MIN_FREEIFY_CAPACITY = 64;

4.4 table 用来初始化（重点）

重难点，必须是 2 的 n 次幂

//存储元素的数组
transient Node<K,V>[] table;

table 在JDK1.8 中我们了解到 HashMap 是由数组+链表+红黑树组成的结构，其中 table 就是 HashMap 中的数组，jdk8 之前数组类型是 Entry<K,V> 类型。从 JDK1.8 之后是 Node<K,V> 类型。只是换了个名字，但都实现了同样的接口：Map.Entry<K,V> 。负责存储键值对数据。

4.5 存放缓存

//存放具体元素的集合
transient Set<Map.Entry<K,V>> entrySet;

4.6 存放元素个数（重点）

//存放元素个数，注意这个不等于数组的长度
transient int size;

size 为 HashMap 中 key-value 的实时数量，不是数组 table 的长度。

4.7 记录HashMap修改次数

//每次扩容和更改map机构的计数器
transient int modCount;

4.8 调整下一次容量大小

//临界值 当实际大小（容量 * 负载因子）超过临界值时，会进行扩容
int threshold;

4.9 哈希表的加载因子（重点）

//加载因子
final float loadFactor;

说明：

  1. loadFactor 加载因子，是用来衡量 HashMap 满载的程度，表示 HashMap 的疏密程度，影响 hash 操作到同一个数组位置的概率， 计算 HashMap 的实时加载因子的方法为：size/capacity ，而不是占用桶的数量去除以 capacity 。capacity 是桶的数量，也就是 table 的长度 length 。
  2. loadFactor 太大导致查找元素效率低下，大小导致数组的利用率偏低，存放的数据会很分散。loadFactor 的默认值为 0.75 是官方给出的一个比较好的临界值。
  3. 当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时，表示 HashMap 太挤了，需要扩容。而扩容这个过程涉及到 rehash、复制数据等操作，非常消耗性能。所以开发中尽量减少扩容次数，可以通过创建 HashMap 集合对象时指定初始容量来避免。
  4. 同时在 HashMap 的构造器中可以定制 loadFactor。
//构造方法：
HashMap(int initalCapacity, float loadFactor)
//构造一个带制定初始容量和加载因子的空 HashMap

4.9.1 为什么加载因子设置为 0.75 初始化临界值是12

loadFactor 越趋近于 1 ，那么数组中存放的数据（entry）也就越多、越密集，也就是会让链表的长度增加。反之成立。

如果希望链表尽可能少一些。要提前扩容，有的数组空间有可能一直没有存储数据。加载因子要尽可能地小一些。

举例：

  1. 加载因子是 0.4 。那么 16 * 0.4 = 6 如果数组中满 6 个空间就会扩容会导致数组利用率非常低。
  2. 加载因子是 0.9 。那么 16 * 0.9 = 14 这样会导致链表过多。导致查找元素效率降低。
  3. threshold 计算公式： capacity（数组长度默认 16）* loadFactor（负载因子默认 0.75）。这个值时当前已占用数组长度的最大值。当 Size >= threshold 的时候，那么就要考虑数组的 resize（扩容）也就是说，这个的意思就是 衡量数组是否需要扩容的一个标准 。扩容后的 HashMap 容量是之前容量的两倍。

4.10 构造方法

HashMap 中重要的构造方法如下：

4.10.1 空构造

构造默认的初始容量为 16，默认负载因子为 0.75

public HashMap() {
    //将默认的加载因子0.75赋值给loadFactor，并没有创建数组
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

4.10.2 🈯️初始容量和负载因子

//指定"容量大小"的构造函数
public HashMap(int initalCapacity) {
    this(initalCapacity, DEFAULT_LOAD_FACTOR);
}

/*
    指定"容量大小"和"加载因子"的构造函数
    initalCapacity：指定的容量
    loadFactor：指定的加载因子
 */
public HashMap(int initalCapacity, float loadFactor) {
    //判断初始化容量initalCapacity是否小于0
    if(initalCapacity < 0)
        //如果小于0，则抛出非法的参数异常
        throw new IllegalArgumentException("Illegal inital capacity: " + initalCapacity);
    //判断初始化容量initalCapacity是否大于最大容量(2^30)
    if(initalCapacity > MAXIMUN_CAPACITY)
        //如果超过回滚容量大小
        initalCapacity = MAXIMUN_CAPACITY;
    //判断负载因子loadFactor是否小于等于0或者是否为一个数值
    if(loadFactor <= 0 || FLoat.isNaN(loadFactor))
    //如果满足上述条件之一则跑出异常
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    //将特定的加载因子赋值给HashMap成员变量的负载因子loadFactor
    this.loadFactor = loadFactor;
    //调用tableSizeFor()方法对初始化容量initalCapacity进行调整与判断
    this.threshold = tableSizeFor(initalCapacity);
}
static final int tableSizeFor(int cap) {
    //int cap = 10
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUN_CAPACITY) ? MAXIMUN_CAPACITY : n + 1;
}

说明：
对于 this.threshold = tableSizeFor(initalCapacity); 的解释：

tableSizeFor(initalCapacity) 判断制定的初始化容量是否为 2 的 n 次幂，如果不是那么会变为比指定初始化容量稍小一点的 2 的 n 次幂。上文已提及过。
但是注意，在 tableSizeFor 方法体内部将计算后的数据返回给调用这里了，并且直接复制给 threshold 边界值。
但很多人会认为应该这样写：
this.threshold = tableSizeFor(initalCapacity) * this.loadFactor
但是，在 jdk8 以后的构造方法中，并没有对 table 这个成员变量进行初始化，table 的初始化被推迟到了 put 方法中，在 put 方法中会对 threshold 重新计算，put 方法的具体实现见下文。

4.10.3 包含另一个"Map"构造

//构造一个映射关系与指定 Map 相同的新的 HashMap
//利用协变将泛型向上转变
public HashMap(Map<? extends K, ? extends V> m) {
    //负载因子loadFactor编委默认的负载因子0.75
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

最后调用 putMapEntries() 方法：

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    //获取参数集合的长度
    int s = m.size();
    if(s > 0) {
        //判断参数集合长度是否大于0
        if(table == null）{
            //判断table是否已经初始化 pre-size
            //未初始化，s为m的实际元素个数
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUN_CAPACITY) ? (int)ft : MAXIUM_CAPACITY);
            //计算得到的t大于阈值，则初始化阈值
            if(t > threshold)
                threshold = tableSizeFor(t);
        } else if(s > threshold)
            //已初始化，并且m元素的个数大于阈值，进行扩容处理
            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);
        }
    }
}

4.11 成员方法

4.11.1 增加方法

put方法是比较复杂的，实现步骤大致如下：

  1. 先通过 hash 值计算出 key 映射到哪个桶；
  2. 如果桶上面没有碰撞冲突，则直接插入；
  3. 如果出现了碰撞冲突，则需要处理冲突；
    • 如果该桶使用红黑树冲突处理，则调用红黑树的方法插入数据；
    • 否则使用传统的链式方法插入。如果链的长度达到临界值，则吧链转变为红黑树。
  4. 如果桶中存在重复的键，则为该键替换新的值 value；
  5. 如果 size 大于阈值 threshold ，则进行扩容处理；

具体的方法如下：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

说明：

  1. HashMap只提供了 put 用于添加元素，putVal 方法知识给 put 方法调用的一个方法，并没有提供给用户使用。所以重点关注 putVal 方法。
  2. putVal 方法中又使用了 hash() 方法，其实现原理为：
static final int hash(Object key) {
    int h;
    /*
        1) 如果key等于null
        可以看到当key等于null的时候也是有哈希值的，返回的是0
        2) 如果key不等于null
        首先计算出key的hashCode赋值给h，然后与h无符号右移16位后的二进制进行按位异或得到最后的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 值。计算过程如下所示：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在 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
    ...
}

计算过程如下所示：
说明：
key.hashCode()；返回散列值也就是 hashcode，假设随便生成的一个值。
n 表示数组初始化的长度是 16。
&（按位与运算）：运算规则：相同的二进制数位上，都是 1 的时候，结果为 1，否则为0。
^（按位异或运算）：运算规则：相同的二进制数位上，数字相同，结果为 0，不同为 1。

h=hashCode()    1111 1111 1111 1111 1111 0000 1110 1010 → 调用hashCode()
------------------------------------------------------
             h  1111 1111 1111 1111 1111 0000 1110 1010
      h >>> 16  0000 0000 0000 0000 1111 1111 1111 1111 → 计算hash

hash=h^(h>>>16) 1111 1111 1111 1111 0000 1111 0001 0101
-------------------------------------------------------
    (n-1)&hash  0000 0000 0000 0000 0000 0000 0000 1111
                1111 1111 1111 1111 0000 1111 0001 0101 → 计算下标
-------------------------------------------------------
                0101 = 5

简单来说就是：
高 16bit 不变，低 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 方法源代码如下所示：
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    /*
        1）transient Node<K,V>[] table; 表示存储Map集合中元素的数组。
        2）(tab = table) == null 表示将空的table赋值给tab，然后判断tab是否等于null，第一次肯定是null。
        3）(n = tab.length) == 0 表示将数组的长度0赋值给n，然后判断n是否等于0，n等于0，由于if判断使用双或，满足一个即可，则执行代码 n = (tab = resize()).length; 进行数组初始化，并将初始化好的数组长度赋值给n。
        4）执行完n = (tab = resize()).length，数组tab每个空间都是null。
    */
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /*
        1）i = (n - 1) & hash 表示计算数组的索引赋值给i，即确定元素存放在哪个桶中。
        2）p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给结点p。
        3) (p = tab[i = (n - 1) & hash]) == null 判断结点位置是否等于null，如果为null，则执行代码：tab[i] = newNode(hash, key, value, null);根据键值对创建新的结点放入该位置的桶中。
        小结：如果当前桶没有哈希碰撞冲突，则直接把键值对插入空间位置。
    */ 
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 创建一个新的结点存入到桶中
        tab[i] = newNode(hash, key, value, null);
    else {
         // 执行else说明tab[i]不等于null，表示这个位置已经有值了
        Node<K,V> e; K k;
        /*
            比较桶中第一个元素(数组中的结点)的hash值和key是否相等
            1）p.hash == hash ：p.hash表示原来存在数据的hash值  hash表示后添加数据的hash值 比较两个hash值是否相等。
                 说明：p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node对象。
                    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
                        return new Node<>(hash, key, value, next);
                    }
                    而在Node类中具有成员变量hash用来记录着之前数据的hash值的。
             2）(k = p.key) == key ：p.key获取原来数据的key赋值给k  key 表示后添加数据的key比较两个key的地址值是否相等。
             3）key != null && key.equals(k)：能够执行到这里说明两个key的地址值不相等，那么先判断后添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等。
        */
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                /*
                    说明：两个元素哈希值相等，并且key的值也相等，将旧的元素整体对象赋值给e，用e来记录
                */ 
                e = p;
        // hash值不相等或者key不相等；判断p是否为红黑树结点
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 说明是链表结点
        else {
            /*
                1)如果是链表的话需要遍历到最后结点然后插入
                2)采用循环遍历的方式，判断链表中是否有重复的key
            */
            for (int binCount = 0; ; ++binCount) {
                /*
                    1)e = p.next 获取p的下一个元素赋值给e。
                    2)(e = p.next) == null 判断p.next是否等于null，等于null，说明p没有下一个元素，那么此时到达了链表的尾部，还没有找到重复的key,则说明HashMap没有包含该键，将该键值对插入链表中。
                */
                if ((e = p.next) == null) {
                    /*
                        1）创建一个新的结点插入到尾部
                         p.next = newNode(hash, key, value, null);
                         Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
                                return new Node<>(hash, key, value, next);
                         }
                         注意第四个参数next是null，因为当前元素插入到链表末尾了，那么下一个结点肯定是null。
                         2）这种添加方式也满足链表数据结构的特点，每次向后添加新的元素。
                    */
                    p.next = newNode(hash, key, value, null);
                    /*
                        1)结点添加完成之后判断此时结点个数是否大于TREEIFY_THRESHOLD临界值8，如果大于则将链表转换为红黑树。
                        2）int binCount = 0 ：表示for循环的初始化值。从0开始计数。记录着遍历结点的个数。值是0表示第一个结点，1表示第二个结点。。。。7表示第八个结点，加上数组中的的一个元素，元素个数是9。
                        TREEIFY_THRESHOLD - 1 --》8 - 1 ---》7
                        如果binCount的值是7(加上数组中的的一个元素，元素个数是9)
                        TREEIFY_THRESHOLD - 1也是7，此时转换红黑树。
                    */
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 转换为红黑树
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                 
                /*
                    执行到这里说明e = p.next 不是null，不是最后一个元素。继续判断链表中结点的key值与插入的元素的key值是否相等。
                */
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    /*
                        要添加的元素和链表中的存在的元素的key相等了，则跳出for循环。不用再继续比较了
                        直接执行下面的if语句去替换去 if (e != null) 
                    */
                    break;
                /*
                    说明新添加的元素和当前结点不相等，继续查找下一个结点。
                    用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                */
                p = e;
            }
        }
        /*
            表示在桶中找到key值、hash值与插入元素相等的结点
            也就是说通过上面的操作找到了重复的键，所以这里就是把该键的值变为新的值，并返回旧值
            这里完成了put方法的修改功能
        */
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                // 用新值替换旧值
                // e.value 表示旧值  value表示新值 
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 修改记录次数
    ++modCount;
    // 判断实际大小是否大于threshold阈值，如果超过则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

4.11.3 将链表转换为红黑树 treeifyBin()

结点添加完成之后判断此时结点个数是否大于 TREEIFY_THRESHOLD 临界值 8，如果大于则将链表转换为红黑树，转换红黑树的方法 treeifyBin，整体代码如下：

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
   //转换为红黑树 tab表示数组名  hash表示哈希值
   treeifyBin(tab, hash);

treeifyBin 方法如下所示：

/*
    替换指定哈希表的索引处桶中的所有链接结点，除非表太小，否则将修改大小。
    Node<K,V>[] tab = tab 数组名
    int hash = hash表示哈希值
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    /*
        如果当前数组为空或者数组的长度小于进行树形化的阈值(MIN_TREEIFY_CAPACITY = 64)，就去扩容。而不是将结点变为红黑树。
        目的：如果数组很小，那么转换红黑树，然后遍历效率要低一些。这时进行扩容，那么重新计算哈希值，链表长度有可能就变短了，数据会放到数组中，这样相对来说效率高一些。
    */
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //扩容方法
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        /*
            1）执行到这里说明哈希表中的数组长度大于阈值64，开始进行树形化
            2）e = tab[index = (n - 1) & hash]表示将数组中的元素取出赋值给e，e是哈希表中指定位置桶里的链表结点，从第一个开始
        */
        // hd：红黑树的头结点   tl：红黑树的尾结点
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 新创建一个树的结点，内容和当前链表结点e一致
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p; // 将新创键的p结点赋值给红黑树的头结点
            else {
                p.prev = tl; // 将上一个结点p赋值给现在的p的前一个结点
                tl.next = p; // 将现在结点p作为树的尾结点的下一个结点
            }
            tl = p;
            /*
                e = e.next 将当前结点的下一个结点赋值给e，如果下一个结点不等于null
                则回到上面继续取出链表中结点转换为红黑树
            */
        } while ((e = e.next) != null);
        /*
            让桶中的第一个元素即数组中的元素指向新建的红黑树的结点，以后这个桶里的元素就是红黑树
            而不是链表数据结构了
        */
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

小结：上述操作一共做了如下几件事：

根据哈希表中元素个数确定是扩容还是树形化。
如果是树形化遍历桶中的元素，创建相同个数的树形结点，复制内容，建立起联系。
然后让桶中的第一个元素指向新创建的树根结点，替换桶的链表内容为树形化内容。

4.11.3 扩容方法 resize()

4.11.3.1 扩容机制：

什么时候才需要扩容
当 HashMap 中的元素个数超过数组大小(数组长度) * loadFactor(负载因子)时，就会进行数组扩容，loadFactor 的默认值是 0.75。
HashMap 的扩容是什么
进行扩容，会伴随着一次 重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。

HashMap 在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n - 1) & hash 的结果相比，只是多了一个 bit 位，所以结点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置。

例如我们从 16 扩展为 32 时，具体的变化如下所示：
扩容
因此元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n - 1 的标记范围在高位多 1bit(红色)，因此新的 index 就会发生这样的变化。
hash

说明：
5 是假设计算出来的原来的索引。这样就验证了上述所描述的：扩容之后所以结点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置。
因此，我们在扩充 HashMap 的时候，不需要重新计算 hash，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就可以了，是 0 的话索引没变，是 1 的话索引变成 “原位置 + 旧容量” 。可以看看下图为 16 扩充为 32 的 resize 示意图：
扩容
正是因为这样巧妙的 rehash 方式，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1bit 是 0 还是 1 可以认为是随机的，在 resize 的过程中保证了 rehash 之后每个桶上的结点数一定小于等于原来桶上的结点数，保证了 rehash 之后不会出现更严重的 hash 冲突，均匀的把之前的冲突的结点分散到新的桶中了。

4.11.3.2源码 resize 方法的解读

下面是代码的具体实现：

final Node<K,V>[] resize() {
    // 得到当前数组
    Node<K,V>[] oldTab = table;
    // 如果当前数组等于null长度返回0，否则返回当前数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //当前阀值点 默认是12(16*0.75)
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果老的数组长度大于0
    // 开始计算扩容后的大小
    if (oldCap > 0) {
        // 超过最大值就不再扩充了，就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 修改阈值为int的最大值
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        /*
            没超过最大值，就扩充为原来的2倍
            1) (newCap = oldCap << 1) < MAXIMUM_CAPACITY 扩大到2倍之后容量要小于最大容量
            2）oldCap >= DEFAULT_INITIAL_CAPACITY 原数组长度大于等于数组初始化长度16
        */
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 阈值扩大一倍
            newThr = oldThr << 1; // double threshold
    }
    // 老阈值点大于0 直接赋值
    else if (oldThr > 0) // 老阈值赋值给新的数组长度
        newCap = oldThr;
    else { // 直接使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;//16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize最大上限
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 新的阀值 默认原来是12 乘以2之后变为24
    threshold = newThr;
    // 创建新的哈希表
    @SuppressWarnings({"rawtypes","unchecked"})
    //newCap是新的数组长度--》32
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 判断旧数组是否等于空
    if (oldTab != null) {
        // 把每个bucket都移动到新的buckets中
        // 遍历旧的哈希表的每个桶，重新计算桶里元素的新位置
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 原来的数据赋值为null 便于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 { // 采用链表处理冲突
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 通过上述讲解的原理来计算结点的新位置
                    do {
                        // 原索引
                        next = e.next;
                        // 这里来判断如果等于true e这个结点在resize之后不需要移动位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

4.11.4 删除方法remove()

删除方法就是首先先找到元素的位置，如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除，树小于 6 的时候要转链表。
删除 remove() 方法：

// remove方法的具体实现在removeNode方法中，所以我们重点看下removeNode方法
public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

removeNode() 方法：

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;
    // 根据hash找到位置 
    // 如果当前key映射到的桶不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 如果桶上的结点就是要找的key，则将node指向该结点
        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 {
                // 判断是否以链表方式处理hash冲突，是的话则通过遍历链表来寻找要删除的结点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 比较找到的key的value和要删除的是否匹配
        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;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

小结 — get 方法实现的步骤：
a. 通过 hash 值获取该 key 映射到的桶
b. 桶上的 key 就是要查找的 key，则直接找到并返回
c. 桶上的 key 不是要找的 key，则查看后续的结点：

如果后续结点是红黑树结点，通过调用红黑树的方法根据 key 获取 value
如果后续结点是链表结点，则通过循环遍历链表根据 key 获取 value

上述红黑树结点调用的是 getTreeNode 方法通过树形结点的 find 方法进行查找：

 final TreeNode<K,V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, 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;
        if ((ph = p.hash) > h)
            p = pl;
        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;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        // 递归查找
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

查找红黑树，由于之前添加时已经保证这个树是有序的了，因此查找时基本就是折半查找，效率更高。

这里和插入时一样，如果对比结点的哈希值和要查找的哈希值相等，就会判断key是否相等，相等就直接返回。不相等就从子树中递归查找。

若为树，则在树中通过key.equals(k)查找，O(logn)。若为链表，则在链表中通过key.equals(k)查找，O(n)。

4.11.5 遍历 HashMap 集合几种方式

4.11.5.1 分别遍历 Key 和 Values
for (String key : map.keySet()) {
    System.out.println(key);
}
for (Object vlaue : map.values() {
    System.out.println(value);
}
4.11.5.2 使用 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());
}
4.11.5.3 通过 get 方式（不建议）
Set<String> keySet = map.keySet();
for (String str : keySet) {
    System.out.println(str + "---" + map.get(str));
}

说明：
根据阿里开发手册，不建议使用这种方式，因为迭代两次。keySet 获取 Iterator一次，还有通过 get 又迭代一次，降低性能。

4.11.5.4 jdk8 以后使用 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);
});

5 设计 HashMap 的初始化容量

5.1 问题描述

如果我们确切的知道我们有多少键值对需要存储，那么我们在初始化 HashMap 的时候就应该指定它的容量，以防止 HashMap 自动扩容，影响使用效率。

默认情况下 HashMap 的容量是 16，但是，如果用户通过构造函数指定了一个数字作为容量，那么 Hash 会选择大于该数字的第一个 2 的幂作为容量（3->4、7->8、9->16）。这点我们在上述已经进行过讲解。

5.2 《阿里巴巴Java开发手册》的建议

关于设置 HashMap 的初始化容量：
上面介绍过，HashMap 的扩容机制，就是当达到扩容条件时会进行扩容。HashMap 的扩容条件就是当 HashMap 中的元素个数（size）超过临界值（threshold）时就会自动扩容。所以，如果我们没有设置初始容量大小，随着元素的不断增加，HashMap 会有可能发生多次扩容，而 HashMap 中的扩容机制决定了每次扩容都需要重建 hash 表，是非常影响性能的。

但是设置初始化容量，设置的数值不同也会影响性能，那么当我们已知 HashMap 中即将存放的 KV 个数的时候，容量设置成多少为好呢？

关于设置 HashMap 的初始化容量大小：
可以认为，当我们明确知道 HashMap 中元素的个数的时候，把默认容量设置成 initialCapacity/ 0.75F + 1.0F 是一个在性能上相对好的选择，但是，同时也会牺牲些内存。

而 JDK 并不会直接拿用户传进来的数字当做默认容量，而是会进行一番运算，最终得到一个 2 的幂。