HashMap添加一个键值对的过程是怎么样的？

1. **计算哈希值**： 当调用 `put(key, value)` 方法时，首先会根据键 `key` 计算出一个哈希值 (`hash`)，这是通过 Java 的 `hashCode()` 方法得到的。为了提高散列效果，HashMap 在 JDK 8 中会对这个哈希值进行一定的扰动处理。 2. **检查是否需要扩容**： 在插入新键值对之前，**HashMap** 会先检查当前存储的元素数量是否已经达到了**阈值**（由 `容量 × 负载因子` 计算得出）。如果达到了这个阈值，HashMap 就会**先进行扩容**（把数组大小翻倍），并将现有的所有键值对重新分配到新的、更大的数组中。这就是 **扩容检查**。 > 扩容前：旧数组的大小为 `capacity`，新的数组的大小为 `capacity * 2`。扩容时，所有的键值对都需要重新计算哈希值对应的数组索引，然后重新放入新的数组中。 3. **计算索引**： 一旦确认不需要扩容（或者扩容完成），HashMap 会根据哈希值和数组的大小来计算应该把键值对存储到数组的哪个索引位置上。具体是通过 `hash & (table.length - 1)` 来计算。 4. **检查是否发生冲突**： HashMap 会检查该索引位置上是否已经有元素： - 如果该位置是空的，直接将键值对插入。 - 如果该位置已有其他元素（发生了哈希冲突），则会通过**链地址法**（使用链表或在 JDK 8 中超过一定阈值后转为红黑树）来解决冲突。 5. **插入或更新键值对**： - 如果该键已经存在于 HashMap 中，HashMap 会遍历链表或树，找到该键并更新其对应的值。 - 如果该键不存在，HashMap 就会在该索引位置的链表或树中新增一个节点来保存这个新的键值对。 ### **扩容流程的关键** 扩容的过程实际上是为了确保 HashMap 在存储大量元素时仍然保持高效的性能。HashMap 在扩容时的关键点有两个： 1. **扩容时机**：当 HashMap 的元素数量超过了**阈值**（`容量 × 负载因子`）时，触发扩容。默认情况下，HashMap 的负载因子为 0.75，也就是说当数组中元素数量达到容量的 75% 时就会进行扩容。 2. **扩容的步骤**： - 扩容时，HashMap 将数组的容量增加一倍。 - 然后，需要将所有旧的键值对重新计算哈希值对应的索引位置，分配到新的数组中（**rehash**）。 由于哈希值与数组大小相关联，扩容后，哈希值的低位将起到新的作用，因此所有键值对都需要根据新的数组大小重新计算存储的位置。 ### 正确的流程总结： - **Step 1**: 计算哈希值 `hash = key.hashCode()`。 - **Step 2**: 检查是否需要扩容（如果元素数量超过阈值，进行扩容）。 - **Step 3**: 计算键值对的存储索引 `index = hash & (table.length - 1)`。 - **Step 4**: 检查该索引位置是否已有元素： - 如果没有元素，直接插入。 - 如果已有元素，处理哈希冲突（链表或红黑树）。 - **Step 5**: 插入或更新键值对。 ### 例子 假设 HashMap 的当前容量为 16，负载因子为 0.75，阈值为 `16 × 0.75 = 12`，即当存储的元素数量达到 12 个时会触发扩容。当第 13 个元素要插入时，HashMap 会先扩容到 32，然后将已有的 12 个键值对重新分配到新的数组中，再插入第 13 个元素。 ### 总结 - 在向 HashMap 中添加键值对时，**扩容检查发生在插入操作之前**。 - 扩容是为了避免 HashMap 过于拥挤，降低哈希冲突的几率，从而保证高效的查找和插入性能。

在 `HashMap` 中添加一个键值对的过程可以分为以下几个步骤。 ### 1. 初始化 `table` 首先，`HashMap` 会检查 `table` 是否为 `null` 或者为空。如果是，则通过 `resize()` 方法进行初始化。`resize()` 方法通常用于扩容，但在 `HashMap` 初次使用时，也会调用该方法来初始化 `table`。 ### 2. 计算 `hash` 值 `HashMap` 使用 `hash(Object key)` 方法计算键的 `hash` 值。这个方法首先调用键的 `hashCode()` 方法获取原始的 `hashCode`，然后将其高位与低位进行异或运算，以生成更分散的 `hash` 值。这种处理方式有助于降低哈希冲突的可能性。 ```java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` ### 3. 插入或更新节点 接下来，`HashMap` 根据 `(n - 1) & hash` 计算插入位置的数组下标 `i`，然后执行以下判断： - **3.1 数组为空**：如果 `table[i]` 为空，表示此位置没有任何节点，则直接在此位置新建节点并插入。 - **3.2 下标首元素存在且相同**：如果 `table[i]` 的首个节点的 `hash` 值与新插入的 `hash` 值相同，并且键也相等，则更新该节点的值为新值。 - **3.3 下标存储的是红黑树**：如果 `table[i]` 是红黑树节点，则直接在红黑树中插入键值对。 - **3.4 下标存储的是链表**：如果 `table[i]` 存在且为链表节点，遍历链表查找是否已有相同 `key` 的节点。如果找到则更新值；如果未找到则在链表末尾插入新节点。插入后如果链表长度超过阈值（8），则将链表转换为红黑树。 ### 4. 扩容 每次插入节点后，`HashMap` 会检查当前实际的键值对数量 `size` 是否超过了最大容量 `threshold`（通常是 `table` 长度乘以负载因子0.75）。如果超过，则执行扩容操作，即重新调整 `table` 的大小。 ### 源代码的总结  源码中的 `putVal` 方法整合了上述逻辑，详细描述了 `HashMap` 中添加键值对的全过程。它通过各种判断确保了在不同情况下的插入和更新操作的正确性，以及在需要时自动扩容以维护 `HashMap` 的性能。 ```java 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.tab为空则创建 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 2.计算index，并对null做处理 // 3.插入元素 //(n - 1) & hash 确定元素存放在哪个数组下标下 //下标没有元素，新生成结点放入中(此时，这个结点是放在数组中) if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 下标中已经存在元素 else { Node<K,V> e; K k; // 节点key存在，直接覆盖value // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 将第一个元素赋值给e，用e来记录 e = p; // 判断该链为红黑树 // hash值不相等，即key不相等；为红黑树结点 else if (p instanceof TreeNode) // 放入树中 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 该链为链表 // 为链表结点 else { // 在链表最末插入结点 for (int binCount = 0; ; ++binCount) { // 到达链表的尾部 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值与插入的元素的key值是否相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 相等，跳出循环 break; // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表 p = e; } } // 表示在桶中找到key值、hash值与插入元素相等的结点 if (e != null) { // 记录e的value V oldValue = e.value; // onlyIfAbsent为false或者旧值为null if (!onlyIfAbsent || oldValue == null) //用新值替换旧值 e.value = value; // 访问后回调 afterNodeAccess(e); // 返回旧值 return oldValue; } } ++modCount; // 超过最大容量 就扩容 // 实际大小大于阈值则扩容 if (++size > threshold) resize(); // 插入后回调 afterNodeInsertion(evict); return null; } ```