学Java的这些HashMap的知识点必须得懂(JDK1.8)

HashMap的扩容机制

扩容步骤

1. 扩容条件判断：当 HashMap 中的元素数量超过了负载因子与当前容量的乘积时，就会触发扩容操作。具体判断条件可以参考 threshold 的计算方式。

   int threshold = (int)(capacity * loadFactor);

   • 在 HashMap 中，threshold 是用来判断是否需要进行扩容的阈值。threshold 的计算方式是将当前容量 (capacity) 乘以负载因子 (loadFactor)，然后将结果转换为整数。

     负载因子是一个表示 HashMap 元素填充程度的参数，默认情况下是 0.75。当 HashMap 中的元素数量超过了 threshold，就会触发扩容操作，以保持 HashMap 的性能。

     threshold 的计算公式是 threshold = (int)(capacity * loadFactor)，其中 capacity 表示当前 HashMap 的容量，loadFactor 表示负载因子。

     具体来说，capacity * loadFactor 的结果是一个浮点数，通过强制类型转换 (int) 将其转换为整数。强制类型转换会将浮点数的小数部分截断，只取整数部分。这样就得到了一个整数类型的 threshold。

     计算出的 threshold 值实际上代表了 HashMap 在什么时候需要进行扩容。当 HashMap 中的元素数量达到了 threshold，即超过了负载因子所允许的填充程度时，就会触发扩容操作。

     通过合理设置负载因子，可以在空间与时间的平衡中进行权衡。较小的负载因子可以减少空间消耗，但可能导致哈希冲突增加；较大的负载因子可以减少哈希冲突，但会增加空间消耗。根据具体的应用场景，可以调整负载因子以达到最佳性能。

     总结起来，threshold = (int)(capacity * loadFactor) 是根据当前容量和负载因子计算得出的触发 HashMap 扩容的阈值，当元素数量超过该阈值时，HashMap 将进行扩容操作。

2. 创建新数组：在扩容时，将会创建一个新的数组，其大小是原数组的两倍。新数组的容量是原数组容量的两倍，并且容量必须是 2 的幂次方。

   Node<K,V>[] newTab = new Node[newCap];

   • 在 HashMap 中，newTab 是一个新的 Node 数组，用于存储扩容后的元素。newCap 是扩容后的容量，代表了新数组的长度。

     Node<K,V>[] newTab = new Node[newCap] 是创建一个新的 Node 数组对象。其中 <K, V> 表示泛型类型参数，分别代表键和值的类型。

     通过 new Node[newCap] 创建出的新数组，每个元素都是一个 Node 类型的对象。Node 类型通常表示哈希桶中的一个节点，用于存储实际的键值对。

     在 HashMap 的扩容过程中，需要创建一个容量更大的新数组，并将原数组中的元素重新分配到新数组的对应位置上。这是因为扩容后 HashMap 需要有更多的桶来分散键值对，以减少哈希冲突的概率。

     在创建新数组时，使用 new Node[newCap] 声明并初始化一个新的 Node 数组。注意，newCap 是指定的新容量大小，是原容量的两倍或其他扩容方式计算得出的结果。

     通过创建新的 Node 数组，HashMap 就可以在扩容后使用更大的内部数组来存储元素，以适应更多的键值对。接下来，就可以将原数组中的元素重新插入到新数组的相应位置上，并更新 HashMap 内部的数据结构，完成扩容操作。

3. 数据迁移：接下来，需要将原数组中的数据逐个迁移到新数组中。这一过程称为重新哈希(Rehash)。对于每个非空的桶，会遍历链表或红黑树中的节点，并根据新数组的容量重新计算其在新数组中的位置。

   for (Node<K,V> e : oldTab) {
       while (e != null) {
           // 计算新的索引位置
           int newIndex = indexFor(e.hash, newCapacity);
           // 将节点添加到新数组中
           // 省略部分代码...
           e = e.next;
       }
   }

4. 更新引用：完成数据迁移后，需要更新 HashMap 对象内部的一些引用。主要包括数组的引用和阈值的更新。

   table = newTab;
   threshold = (int)(newCapacity * loadFactor);

   • table = newTab; 和 threshold = (int)(newCapacity * loadFactor); 是在 HashMap 扩容过程中更新数据结构的两个关键步骤。

     首先，table = newTab; 将引用指向新的数组 newTab。这意味着 HashMap 的内部数组 table 现在引用了扩容后的新数组，从而使 HashMap 在接下来的操作中使用新数组来存储元素。

     接着，threshold = (int)(newCapacity * loadFactor); 根据新的容量 newCapacity 和负载因子 loadFactor 计算得到新的阈值 threshold。这个阈值表示在何时需要再次进行扩容。

     解释一下这个计算过程：newCapacity 是新数组的容量，它可能是原容量的两倍或其他扩容方式计算得出的结果。负载因子 loadFactor 是一个参数，表示 HashMap 元素填充程度的比例，默认为 0.75。

     newCapacity 乘以 loadFactor 得到一个浮点数，然后通过强制类型转换 (int) 将其转换为整数形式。这样得到的 threshold 就是新容量和负载因子相乘后取整得到的结果。

     计算出的新阈值 threshold 可以用来判断何时再次触发扩容操作。当 HashMap 中的元素数量超过了新阈值时，就会触发下一次的扩容操作，以保持 HashMap 的性能。

5. 并发处理：在多线程环境下，可能存在并发情况下进行的插入、删除等操作。为了保证线程安全，HashMap 在扩容过程中会采取一些措施，如使用 synchronized 关键字或者 CAS（Compare and Swap）操作来避免并发问题。

总结起来，HashMap 的扩容步骤可以概括为：创建新数组、将原数组的数据迁移到新数组中、更新引用和处理并发情况。通过扩容，HashMap 可以提高容量，从而减少哈希冲突的概率，提高查询和插入操作的性能。

为什么HashMap扩容的容量必须是 2 的幂次方

HashMap 扩容的容量必须是 2 的幂次方，这是因为 HashMap 在计算元素在数组中存储位置时使用了位运算，通过将哈希值与 (capacity - 1) 进行与操作来得到索引值。具体而言，假设 HashMap 的容量为 n，那么对应的数组索引范围为 [0, n-1]。

原始的 HashMap 实现使用取模运算（%）来计算索引，例如 index = hash % capacity。然而，这种方式在计算机中是比较耗时的操作，而且对于不同的容量，取模的结果分布并不均匀。

为了提高计算速度和优化索引的分布，HashMap 使用位运算来计算索引，将取模操作转换为与运算（&）。具体地，假设容量是 2 的幂次方（即 n = 2^k），那么 (n - 1) 的二进制形式的所有位都是 1。这样，在进行与操作时，结果的最低 k 位就是哈希值的有效位，通过这些有效位可以获取到元素在数组中的索引。

例如，当容量为 16 （即 2^4）时，(n - 1) 的二进制形式为 1111，对任意哈希值进行与操作后，得到的结果只会影响哈希值的最低 4 位，即 hash & (capacity - 1)。这样，通过位运算而不是取模运算来计算索引，可以提高计算效率，并且保持了较好的分布性。

因此，在设计 HashMap 扩容机制时，为了保持元素在数组中的位置计算准确和高效，容量必须是 2 的幂次方。这样可以充分利用位运算来计算索引，提高 HashMap 的性能和效率。

为何HashMap中的扩容是<<1

在 HashMap 中，扩容操作使用的是位运算符 << 来实现容量的翻倍。<< 是位左移操作符，它将二进制数向左移动指定的位数，并在右侧填充零。

HashMap 扩容时，会将当前容量乘以 2，即进行容量的翻倍。这是因为 HashMap 内部使用一个数组来存储元素，扩容时需要重新创建一个更大的数组，并将原数组中的元素重新分配到新数组的对应位置上。

通过将当前容量左移一位，相当于将当前容量乘以 2。这种操作比起使用乘法运算符 * 来说更加高效，因为位运算通常比算术运算更快。

举个例子，假设当前容量为 n，那么 n << 1 的结果就是将 n 的二进制表示向左移动一位，并在右侧填充零。这样就得到了新的容量，即原容量的两倍。

使用位运算的方式进行扩容，可以通过简单的位移操作来达到容量翻倍的效果，而不需要进行乘法运算，从而提高了性能和效率。

因此，HashMap 中使用 << 运算符来进行扩容，是一种高效的方式，可以快速地将当前容量扩大一倍。

// 二进制1001左移一位
 10010 = 01001 << 1 
// 对应的的十进制数值为
 01001 = 9
 10010 = 18

HashMap的存储结构转换机制（链表->红黑树）

在 JDK 8 及之后的版本中，HashMap 对于哈希冲突的处理引入了红黑树来替代链表，以提高在桶中查找的效率。下面是链表转换为红黑树的机制：

1. 当链表中的节点数量超过阈值（默认为 8）时，会进行链表转换为红黑树的操作。
2. 在进行转换前，HashMap 会先判断当前桶中的元素是否已经符合红黑树的转换条件，即该桶的长度是否大于等于 8（默认值），如果不满足，则不进行转换，仍然维持链表结构。
3. 如果满足转换条件，在进行链表转换为红黑树之前，会先判断当前 HashMap 的容量是否达到了一个阈值（默认为 64），如果没有达到，则进行扩容，目的是为了提供红黑树所需的更多桶，防止红黑树因为容量不足而发生退化。
4. 执行链表转换为红黑树的操作，使用红黑树的插入算法将链表中的节点逐个转移到红黑树中，这个过程是一种链表节点的插入操作。
5. 在转换完成后，原本的链表就会被替换成一棵红黑树，这样就能够通过红黑树的高效查找算法快速定位到对应的元素。

需要注意的是，在进行红黑树的转换操作后，如果发现红黑树中的节点数量少于某个阈值（默认为 6），此时会将红黑树恢复成链表结构，以节省内存空间并降低维护成本。

总结起来，HashMap 的存储结构转换机制是通过在链表长度过长时，将链表转换为红黑树来提高查找效率，并在条件满足时进行桶容量的扩容。同时，为了节省内存空间和维护成本，红黑树节点数量过少时会恢复成链表结构。

// 看源码
for (int binCount = 0; ; ++binCount) {     //binCount遍历次数， 当binCount=0时，链表上有一个节点，故可以推出当当binCount=7即当链表上有8个节点时会进行红黑树的转换
  if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null); //这行代码表示，会先将新的set值插入到链表中在进行红黑树的转换，而不是先转红黑树在讲新的set值插入到红黑树中，所以说明当链表上有9个节点时才转换成的红黑树
    if (binCount >= TREEIFY_THRESHOLD - 1)  //TREEIFY_THRESHOLD常量值为8，这个判断为当遍历次数为7时就会将链表结构转为红黑树
      treeifyBin(tab, hash);   //链表转为红黑树的具体实现代码
    break;
  }
  if (e.hash == hash &&
      ((k = e.key) == key || (key != null && key.equals(k))))
    break;
  p = e;
}

后续补充中。。。

赏

谢谢你请我喝咖啡

支付宝

微信