Java 集合框架（四）

我们来看看他的注释

原来这个方法是跟构造函数和伪构造函数挂钩的，所以构造函数之所以没有调用 super 来构造继承的 AbstractMap 是因为调用了 init 方法吗？

[](()总结构造方法

• 作者不想让我们使用自定义的容量和负载因子

• 默认的容量为 16，负载因子为 0.75

• 无参构造方法就是使用默认参数来调用有参构造方法

• 构造方法并没有马上去给 table 数组设置容量，而是将阈值设为了容量

[](()put 方法

我们来看看方法上的注释

从注释上就可以得知，当再次 put 相同 key 时会发生 value 的替换

从构造方法上可以知道，构造方法并没有立即给底层空数组立即扩上默认的容量，而是将门限值设为了默认容量

所以在 put 方法的开头，判断操作的 table 是不是 EMPTY_TABLE，即针对第一次插入要对底层数组进行操作

调用 inflateTable 方法进行操作，这个参数是使用 threshold 作为参数的，也就是作为了下面的 toSize，

[](()inflateTable

下面来看看 inflateTable 方法做了什么

步骤如下

• 找到指定容量最近的一个 2 的幂次方数（要大于等于指定容量），作为真正的容量

• 然后对 threshold 进行计算，取最大的容量+1 和容量乘于负载因子的最小值

• 然后重新给底层主数组 table 赋值，容量为指定容量最近的一个 2 的幂次方数

• 然后初始化 hashSeed（前面提到过，这个 hashSeed 是关联哈希算法的）

所以，可以得知，构造方法将 threshold 设为指定容量，只是用来暂时存储指定的容量，底层主数组真正有容量是在第一次 put 之后

接下来我们看看怎么获取最近的一个 2 的幂次方数（该 2 的幂次方数大于等于指定容量）的，也就是 roundUpToPowerOf2 方法

步骤如下

• 比较指定容量是否大于等于最大允许的容量

• 如果大于指定容量就取最大容量（ 2 30 2^{30} 230）

• 如果小于指定容量就再判断指定容量是否大于 1

• 如果小于等于 1，容量就取 1（1 也是 2 的幂次方，为零次幂）

• 如果大于 1，那么就调用 Integer 的 highestOneBit 方法

Integer 的 highestOneBit 方法是用来获取指定参数的最小 2 次幂

现在我们分析一下，为什么要取指定容量减一的两倍的最小 2 次幂，也就是为什么参数为(nuber-1) << 1

前面已经提过，设置的容量是最近的大于或等于指定容量的 2 次幂，我们就围绕他来论证

2 次幂，也就是 0、1、2、4、8、16。。。。。这些二次幂数会形成一个个区间，如同下面所示

那么指定容量就会出现两种情况

1. 指定容量在区间内

2. 指定容量就是一个 2 次幂

当指定容量在区间内时，代表这个容量大于左边的二次幂数，小于右边的二次幂数，因此就有这样一个表达式 2 ( n ? 1 ) < x < 2 n 2^{(n-1)} < x < 2^n 2(n?1)<x<2n(x 代表容量），那么我们对条表达式进行乘 2 变成 2 n < 2 x < 2 ( n + 1 ) 2^n < 2x < 2^{(n+1)} 2n<2x<2(n+1)，所以 2 倍的容量的最近的小二次幂就是容量的最近的大二次幂

当指定容量就是一个 2 次幂，也就是不落在上述的区间内，那么就需要进行减 1，来让其落在区间内（而且这个减 1 操作对于本就在区间内的数没有影响），当然，比如 2 和 1，如果指定容量为 2，那么减一就变成了 1，但这里要注意的是必须要大于 1，才会执行这个方法，所以我们不用考虑 1 的情况

至于 Integer 的 highestOneBit 方法的细节，能力不足，看不懂，这里就贴上源码自己看吧

最后就是进行 initHashSeedAsNeeded，这个方法是用来使用代替散列才使用的， 不太重要，因为我们一般使用 hashMap 都不会使用字符串来代替散列

inflateTable 方法到此结束

总结一下 inflateTable 干了什么东西

• 确定容量，容量大小为指定容量的最近的大二次幂

• 修改扩容门限，扩容门限为扩容因子乘上容量

• 如果要使用代替散列，对 hashseed 变量进行修改

[](()添加 Key 不为 null 元素

先贴上代码

我们将其分为两部分

• 第一部分是形成链表时独有的操作

• 第二部分是没有形成链表和形成链表时都有的操作

第一个部分步骤如下

1. 先判断要添加的键值对的 key 是否为 null，如果为空，就调用 putForNullKey 方法

2. 如果 key 不为空，调用 hash 方法来计算 key 的 hash 值

3. 调用 indexFor 来找到 key 的 hash 值对应的索引

4. 最后根据索引找到位置，判断这个位置是否已经有键值对

5. 如果有，代表整个位置形成了之前发生过哈希冲突，形成了链表，就需要遍历这个链表看是否出现相同的键

6. 判断相同的键是先根据链表中的键值对的 hash 值是否与当前要添加的键值对相等，如果不相等，再比较 key 是不是相同，判断是否是相同的 key 是根据是不是同一个与 equals 方法进行综合考虑的

7. 如果出现相同的键，那么就记录旧的键值对的 value，将旧的键值对的 value 修改成新的 value（也就是键不变，值替换）

8. 调用 recordAccess 方法

9. 最后将旧的 value 返回

第二个部分步骤如下

• 让 modCount 自增（之前研究 ArrayList 也有这个变量，是用来记录年代的，也就是这个底层数组的版本变化）

• 最后调用 addEntry 方法，参数为哈希值，键，值，索引

总体的架构就是如上，现在来看调用的各个方法

hash 方法

先来看看 hash 值是怎么计算的

上面那部分不用管，是替代散列时使用的（使用字符串替代散列值）

步骤如下

1. 先调用 key 自己拥有的 hashCode 方法

2. 最后使用一序列的扰乱函数

所以键值对的 hash 值生成是跟 key 有关的，而且细节来说是跟 key 的 hashCode 有关（这也就是为什么使用集合来存储对象时，一定要重写 hashCode 方法，而且 hashCode 要 《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》开源 跟对象的属性值有关，这样就可以将相同属性值的对象视为同一个对象）

接下来我们看看扰乱函数是干什么的，从注释来看

总的来说这个扰乱函数就是用来减少哈希冲突的

indexFor 方法

这个方法就是用来根据哈希值寻找到底层主数组的索引的

可以看到这个方法单纯是用哈希值与上了底层数组的最大索引（也就是长度减一）

这里是利用了与运算的特点，前面已经提到过，底层数组的长度一定是 2 的幂次方，那么减一操作就会让其变成全为 1 的二进制数，也就确保了底层数组的索引数量化成二进制里面所有数字一定全部都为 1

那么此时这个算法就会等效成用哈希值对最大索引进行取余，也就是 h % ( length - 1 )

所以索引的计算方法其实就是哈希值对最大索引进行取余操作，保证不会超过底层数组的最大索引

这也是为什么长度必须为 2 的幂次方

recordAccess

可以看到这个方法什么都没干，可能是为了以后方便拓展

我们再看下注释

注释上提到这个方法是出现重复 key 的时候都会调用

addEntry

最后我们再看看 addEntry 的方法

我们可以看到，addEntry 方法里面竟然包含了扩容操作即 resize 方法

步骤如下

• 判断当前 HashMap 的元素数量是否大于门限

• 如果大于，再进行比较当前要添加键值对的位置是否为空

• 如果也为空，那就会进行扩容操作

• 所以，要扩容必须满足两个条件

• 一个是 HashMap 的元素数量大于门限值

• 另一个是当前添加键值对的索引位置必须发生冲突

• 下面进行扩容，扩容调用的是 resize 方法，而且传的参数是当前底层数组长度的两倍

• 扩容了之后，首先进行再次 hash，即重新计算当前键值对的 key 的 hash 值

• 然后再用新的 hash 值计算出新的索引位置

• 最后就是调用 createEntry 方法来正式添加元素

[](()扩容

我们来看看 resize 是如何进行扩容的

可以看到，扩容操作也是会进行判断

• 先判断旧的容量，也就是当前主数组的长度，是否等于最大容量

• 如果已经等于，就不可以继续扩了

• 然后将扩容门限设为 Integer 的最大值

• 结束

• 如果主数组的长度，不等于最大长度，那么就代表一定小于最大容量

• 那么就会创建一个新容量的数组（前面已经知道容量为旧容量的两倍）

• 然后调用 transfer 方法

• 让底层的 table 数组指向新容量的数组

• 最后就是重置了门限值，让门限值为最大的容量+1 和新的容量乘上负载因子的最小值

可以看到，是不是少了就是将旧的数据放在新数组上的步骤，所以，可以推测到，这一步是放在了 transfer 上去完成的

可以看到，对于旧数组，不是像 ArrayList 那样单纯的进行复制过去，而是要重新散列的

可以看到，使用了增强 for 来桥套 while 循环，来遍历所有元素（增强 for 遍历数组，while 循环来遍历每个项的链表），然后对所有键值对的 hash（键值对不仅保存键值，还保存着哈希值和下一个键值对的指向）进行了重新计算，这一步称为 rehash，当然，计算的规则依然是使用 key 来计算的，重新计算了 hash 当然也要重新计算索引，然后根据重新计算的索引，对应存放在新创建的扩容数组里面

不过这里有一个问题？如果 rehash 了之后重新装填又发生了哈希冲突会怎样？

根据源码来看，如果重新装填的过程发生了哈希冲突，那么后面的键值对就会替代前面的键值对。

至此，整个扩容过程就结束了

总结一下

• 扩容要先判断旧的容量是否已经最大，最大的话，只是单纯改变了门限值为 Integer 最大值

• 扩容后的容量为旧的容量的 2 倍

• 扩容后要将旧的数据重新装填进新的数组里面，重新装填并不是单纯的复制，而是要遍历所有项的链表进行重新 hash，重新计算索引值，然后根据新的索引值放在数组里面

• 假如重新装填过程中发生哈希冲突，产生的索引值一样，那么就会进行数据替换，会产生数据丢失

• 最后将底层 table 指向新扩容后的数组

• 将门限改为新的容量乘上负载因子

[](()createEntry

最后我们来看看 createEntry 方法

这个方法也就是真正底层的添加操作

1. 首先获取底层数组指定索引位置处的旧键值对

2. 让后新建一个键值对，键值对存要添加的键值、哈希值和指向下一个的旧键值对

可以知道，底层的插入使用的是一个头插法

[](()补充：当添加的是 key 为 null 的元素

前面 put 方法源码上，是会判断 key 是否为 null 的，假如为 null 就会执行 putForNullKey 的方法

这样拆开是因为 hash 值是根据 key 的 hashCode 来生成的，如果 key 为 null 就不能生成 hashCode，所以需要进行拆开

可以判断，putForNullKey 的执行跟 put 方法后面的操作差不多

可以看到 for 循环里面，遍历的是底层 table 数组的第一个项，也就是第一个项的链表

那么就可以知道，key 为 null 的键值对都是放置在底层 table 数组第一个项里面来形成链表的，当然里面还存在 key 不为 null 的键值对对象，然后如果发现有 key 也为 null，而且 value 相等的，就会发生 value 替换，返回旧的 value

可以看到，addEntry 里面的 bucketIndex 变为了 0，hash 值也变成了 0

所以，key 为 null 的元素的 hash 为 0，即使判断要进行扩容，重新 hash 的时候，因为 key 为 null，索引也是为 0 的，因为 bucketIndex 为 0，所以是存储在底层 table 数组里面的第一个项里面

[](()get 方法

接下来看看 get 方法是如何执行的

步骤如下

• 先判断 key 是否为 null

• 如果为 null 就要在执行 getForNullKey 方法

• 如果 Key 不为 null，执行 getEntry 方法

• 然后判断是否找到

• 通过比对获得的 entry 是否为 Null 来判断

• 如果为 null 就返回 null

• 如果不为 null，就返回 entry 的 value 属性

[](()getEntry

我们先来看看如果 key 不为 null 时执行的 getEntry 方法

步骤如下

• 先判断 HashMap 里面的元素数量是否为 0，如果为 0 就直接返回 null

• 如果不为 0，就要根据给的 key 计算哈希值

Java 核心架构进阶知识点

面试成功其实都是必然发生的事情，因为在此之前我做足了充分的准备工作，不单单是纯粹的刷题，更多的还会去刷一些 Java 核心架构进阶知识点，比如：JVM、高并发、多线程、缓存、Spring 相关、分布式、微服务、RPC、网络、设计模式、MQ、Redis、MySQL、设计模式、负载均衡、算法、数据结构、kafka、ZK、集群等。而这些也全被整理浓缩到了一份 pdf——《Java 核心架构进阶知识点整理》，全部都是精华中的精华，本着共赢的心态，好东西自然也是要分享的

内容颇多，篇幅却有限，这就不在过多的介绍了，大家可根据以上截图自行脑补