HashMap（jdk1.7）之构造方法和 put 方法过程分析

计算新插入元素所在数组索引

addEntry 方法详解

modCount++

是

inflateTable 方法详解

true 表示数组尚未初始化

返回旧值

return null

初始化底层数组

查找要插入的 key，是否已经存在于 hashmap 了

需要

1、参数合法性检查；2、设置参数；并没有初始化底层数组！（table）

从索引位置链表查询

new HashMap()

默认负载因子为何设置为 0.75负载因子设置越大，空间利用越充分，但同时会降低put/get性能；反之，设置越小，空间利用越不充分，但put/get性能越好。0.75 是基于数学上的 牛顿二项式 计算出来的一个相对比较合适的值。

检查数组是否已初始化

计算哈希值：int hash = hash(key)

Entry 对象，封装了 key，value。hash 是 key 的哈希值，next 是指向的下一个 Entry 对象。

创建新的底层数组

不需要。元素直接插入链表

table == EMPTY_TABLE？

插入 key 为 null 的处理逻辑

本图形详细展示了 HashMap 的构造方法和 put 方法执行流程，包括：构造方法的执行过程、put 元素时，底层数组的初始化过程、数组索引计算过程、查找相同 key 元素过程、底层数组扩容过程、插入 key = null 的处理过程。① 初始化底层数组② 计算插入元素在底层数组的索引位置③ key 为 null 的处理逻辑④ key 不是 null，判断之前是否已经存在这个 key了，若存在，替换其 value，并返回之前 value⑤ key 不是 null，且这个 key 不存在 HashMap 中，执行元素插入之前的扩容逻辑。⑥ 使用头插法，将 Entry 对象插入链表。

初始化

able[0] == null?

false

是否查找到了？

resize 方法详解

根据 toSize，得到第一个 大于等于 toSize 的 2 的幂，作为数组容量。为什么要是 2 的幂？1、能使用 & 计算数组下标；2、效率比取余更高；2、防止数组越界

inflateTable(threshold)

否

初始化完成，开始添加元素

重新设置 table 和 threshold

createEntry

putForNullKey

根据数组下标（i），到对应的链表查找，而不是在所有链表查找。

addEntry

newCapacity 是原来的两倍。

初始化 hashSeed。hashSeed 初始值为 0，一般情况下，如果不设置jdk.map.althashing.threshold 系统参数，hashSeed 是不会被初始化为其他值的。

当添加的 key 是null时，执行这个处理逻辑。可以看到，key = null 的元素，是固定

采用头插法，将 Entry 插入链表头部，步骤：1）e 指向链表第一个元素（可能为 null）2）构建新的 Entry 对象，其 next 属性指向 e3）将链表第一个元素，执行上面新建的 Entry 对象。

false 表示已经初始化

构造方法

执行扩容逻辑

找到对应的 Entry 对象，将其 value 替换，并返回旧的 value

initHashSeedAsNeeded(capacity)

HashMap 的底层实现：jdk1.7 及之前的版本：数组 + 链表；jdk1.8 及之后的版本：数组 + 链表 + 红黑树。其中，链表转红黑数的条件包括：1）链表大小超过 8 （即 >= 9）。为什么是 8？根据泊松分布定律计算出来的：同一个链表元素超过 8 的概率几乎是上千万分一了，概率非常低（之所以这么低，是因为 loadFactor 会在链表达到 8 之前，就会扩容，扩容会使得链表变小）。2）为什么需要转红黑树：因为链表太长，会影响查找效率，红黑树的查找时间复杂度，比链表高（但插入和删除效率比链表低）

哈希算法有很多种：md5，crc32，crc64...这里，通过 k.hashCode 得到哈希值后，又进行了一系列的位运算，目的是为了让 key 的高位，也能参与到哈希值计算中，得到更好的散列值。这样是为了防止我们重写的 hashCode 散列性太差，导致分布不均的问题。

查找到 e.key == null 的 Entry 对象了？

1、当添加的是 key == null 的键值对时，参数 hash = 0，bucketIndex = 0。即：key = null 的元素，固定添加到 index == 0 位置的链表上。2、jdk1.7中，同时满足两个条件，才会触发扩容：1、数组中当前元素个数 >= threshold2、即将插入元素的链表不为空（即已经初始化过）

扩容处理逻辑

putForNullKey 方法详解

HashMap

key == null？

true 表示 index == 0 的链表尚未初始化

添加元素

② 扩容后，重新计算元素在数组索引位置

table = new Entry[capacity];

是否需要扩容？

元素加入链表的处理逻辑

key 值是否已存在这个链表中？

插入到链表

执行新 key-value 插入逻辑

1、参数 rehash == false2、两层循环，外层遍历数组，内层遍历链表。3、对每个元素，重新计算在新数组的索引，这个索引，和在旧数组的索引，存在一定关系的：若元素在旧数组索引为 i，旧数组容量为 size，则在新数组的索引只会是 i，或 i + size4、新生成的链表，顺序和原来是相反的（头插法导致）

计算数组容量int capacity = roundUpToPowerOf2(toSize)

true

transfer

用新的 value 替换 Entry 对象原有 value 值，并返回原来的值。

无参

从数组坐标 为 0 的链表中，查找属性 key == null 的 Entry 对象。