HashMap的介绍以及扩容为什么是2的n次幂

发布时间：2021-09-04 21:25:37 作者：chen
来源：亿速云阅读：196

1. HashMap简介

HashMap是Java集合框架中一个非常重要的类，它实现了Map接口，提供了键值对（key-value）的存储和检索功能。HashMap基于哈希表（Hash Table）实现，允许使用null作为键和值，并且是非同步的（非线程安全）。

HashMap的内部结构主要由数组和链表（或红黑树）组成。数组是HashMap的主体，链表或红黑树则是为了解决哈希冲突而存在的。具体来说，HashMap的每个元素都是一个Node对象，Node对象包含键、值、哈希值以及指向下一个节点的指针。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // 省略其他代码
}

当向HashMap中插入一个键值对时，首先会根据键的哈希值计算出数组的索引位置。如果该位置为空，则直接插入；如果该位置已经有元素存在（即发生了哈希冲突），则通过链表或红黑树来处理冲突。

在JDK 1.8之前，HashMap在发生哈希冲突时只使用链表来处理。但在JDK 1.8中，当链表的长度超过一定阈值（默认为8）时，链表会转换为红黑树，以提高查找效率。

HashMap的扩容机制是其性能优化的关键之一。当HashMap中的元素数量超过当前容量与负载因子的乘积时，HashMap会进行扩容操作。扩容的主要目的是减少哈希冲突，提高查找效率。

扩容的过程主要包括以下几个步骤：

HashMap的扩容容量总是2的n次幂，这是为了优化哈希值的计算和索引的定位。具体原因如下：

在HashMap中，键的哈希值是通过hashCode()方法计算得到的。为了将哈希值映射到数组的索引位置，通常需要对哈希值进行取模运算。然而，取模运算的效率较低，尤其是在频繁操作时。

为了提高效率，HashMap使用了位运算来代替取模运算。具体来说，当数组的容量为2的n次幂时，hash % length等价于hash & (length - 1)。这是因为length - 1的二进制表示是一个全1的数，与哈希值进行按位与运算时，相当于取哈希值的低n位。

例如，假设数组的容量为16（即2^4），则length - 1的二进制表示为1111。此时，hash & (length - 1)等价于hash % 16。

int index = hash & (length - 1);

当数组的容量为2的n次幂时，哈希值的低n位决定了元素在数组中的位置。由于哈希值的低n位是均匀分布的，因此元素在数组中的分布也会更加均匀，从而减少哈希冲突的概率。

在扩容时，HashMap需要将原数组中的元素迁移到新数组中。由于新数组的容量是原数组的两倍，因此元素在新数组中的位置要么保持不变，要么在原位置的基础上加上原数组的容量。

具体来说，假设原数组的容量为oldCap，新数组的容量为newCap = oldCap << 1。对于每个元素，其在新数组中的位置可以通过以下方式计算：

if ((e.hash & oldCap) == 0) {
    // 位置不变
    newTab[j] = e;
} else {
    // 位置为原位置 + oldCap
    newTab[j + oldCap] = e;
}

这种计算方式非常高效，因为它只需要进行一次位运算即可确定元素在新数组中的位置。

HashMap是Java中常用的数据结构之一，它基于哈希表实现，提供了高效的键值对存储和检索功能。HashMap的扩容机制是其性能优化的关键，扩容容量总是2的n次幂，这是为了优化哈希值的计算和索引的定位。通过使用位运算代替取模运算，HashMap能够在扩容时高效地迁移元素，并减少哈希冲突的概率。

理解HashMap的扩容机制及其背后的原理，有助于我们更好地使用和优化HashMap，从而提高程序的性能。