Java中的HashMap在内部使用一个动态可调整容量的数组来存储元素，每个数组元素称为桶（bucket），桶中存放的是键值对对象（Node、TreeNode，在JDK1.8中是链表或红黑树）。当向HashMap中添加新的键值对时，会根据键的哈希码计算出对应的桶位置。随着元素数量的增加，如果继续添加元素导致负载因子（load factor）规定的阈值被超过，则会触发扩容操作。

扩容原理如下：

  1. 扩容时机：

    • 当HashMap中的元素个数（size）超过当前容量（capacity）与加载因子（默认为0.75）的乘积时，即 size > capacity * loadFactor，就会进行扩容。
    • 在JDK1.8中还有一个特殊的条件，对于单个桶内的链表长度大于8并且数组长度小于64时也会扩容，这是为了避免在处理大量hash冲突时链表过长影响性能。

  2. 扩容过程：

    • 扩容时，HashMap会创建一个新的数组，新数组的容量通常是旧数组容量的两倍加一（例如，从16扩容到32，从32扩容到64等，保证新容量始终为2的幂次方，这样可以确保索引计算的高效性）。
    • 然后，它会遍历原数组的所有桶，将原有的键值对重新映射到新的数组中。这个过程涉及到重新计算每个键值对在新数组中的位置，并将其移动到对应的新桶中。
    • 如果某个桶内是以链表形式存储的数据，则直接将链表复制到新桶中；而在JDK1.8中，如果桶内数据结构已经转换为红黑树，那么红黑树会被拆解并重新生成到新桶上。
    • 扩容完成后，原来的数组引用会被更新为指向新的数组。

  3. 性能考虑：

    • 扩容是一个相对耗时的操作，因为它需要重新分配内存和迁移所有现有元素，所以为了提高效率，应当合理预估并初始化HashMap的容量，避免频繁扩容。
    • 扩容的同时还会重新计算键的哈希值与新容量之间的关系，以尽量减少新的哈希碰撞，保持良好的查询性能。

通过这种方式，HashMap能够灵活地应对不断增长的数据量，同时尽可能地维持高效的查找、插入和删除操作。

Java中HashMap的默认初始长度（容量）是16。这意味着在创建一个未指定初始容量的新HashMap实例时，其内部数据结构将初始化为大小为16的数组。这个值被设计成2的幂（即2^4），是因为当进行哈希映射时，通过位运算来计算元素在数组中的索引位置能够更高效地实现均匀分布，并且在扩容时可以方便地翻倍数组容量，保持索引计算的有效性。此外，后续扩容也是以2的整数次幂的方式进行的，比如从16扩展到32，再从32扩展到64等。

名词解释

负载因子

负载因子（Load Factor）在Java集合框架中的HashMap类中是一个重要的性能参数，它表示哈希表在其容量范围内可以填充数据的程度。具体来说，负载因子是哈希表当前元素个数与它的容量之间的比率。

公式上，负载因子定义为：

1
负载因子 = 哈希表中元素数量 / 哈希表的容量

在Java HashMap中，默认的负载因子值为0.75，这意味着当哈希表中的元素数量达到了其容量的75%时，将会触发自动扩容操作。扩容时，HashMap会创建一个新的、更大的数组来存储键值对，并将现有的所有元素重新哈希到新的数组中。

选择合适的负载因子是为了平衡时间和空间效率：

  • 如果负载因子较小，则哈希表会在元素数量较少时就进行扩容，这样可以减少哈希冲突的可能性，提高查询速度，但会占用更多的内存空间。
  • 如果负载因子较大，则可以在有限的空间内存储更多的元素，但是当接近满负荷时，由于哈希冲突增多，可能导致查找和插入等操作的性能下降。

Java设计者们经过权衡后，选择了0.75作为默认负载因子，认为在这个比例下，时间和空间开销能够达到一个相对理想的平衡点。当然，在特定的应用场景下，可以根据实际需求调整这个参数。