目录
在 Java 的世界里，HashMap 占据着极为重要的一席之地。它依托哈希表来构建，这种设计使得其在插入、删除以及查找操作上能够展现出相当快速的效率。不过，就像任何事物在面临规模增长时都会遭遇挑战一样，随着 HashMap 中元素数量的持续攀升，它的性能表现可能会大打折扣。为了能够始终维持高效的运行状态，HashMap 巧妙地引入了扩容机制。在接下来的内容中，我们将深入到 HashMap 的扩容机制内部，一探究竟，并且还会附上相应的代码示例来辅助理解。
一、HashMap 基本架构概览
在我们一头扎进扩容机制的复杂细节之前，先来简单回顾一下 HashMap 的基础结构。HashMap 主要是借助数组和链表（需要注意的是，在 Java 8 及其后续版本中，一旦链表的长度超出一定限度，链表就会被自动转换为红黑树）来实现数据存储的。HashMap 中的元素会被存放在数组的特定索引位置，而这个位置是通过哈希函数对键（Key）进行计算得出哈希值后确定的。
二、扩容机制全解析
当 HashMap 内部的元素数量累积到某个特定的界限时，扩容操作就会被触发，以此来确保操作效率不会因为元素过多而受到严重影响。这个特定的界限是由当前容量（capacity）与负载因子（load factor）这两个因素共同作用决定的。
负载因子
负载因子，从本质上来说，是一个用于衡量 HashMap 被填满程度的关键参数。它的计算方式是用 HashMap 中所包含的元素数量除以桶（bucket）的数量。在 Java 中，HashMap 默认设定的负载因子为 0.75f。
扩容阈值
扩容阈值的计算公式是：capacity * loadFactor。也就是说，当 HashMap 中的元素数量超过了由这个公式计算得出的阈值时，扩容操作就会紧锣密鼓地展开。
扩容操作步骤详解
- 首先，会创建一个全新的 Node 数组，这个新数组的容量将会是原数组容量的两倍。这就好比是为数据的存储开辟了一片更为广阔的空间，以容纳更多的元素。
- 接下来，需要对原 HashMap 中的每一个元素进行遍历操作。在遍历的过程中，针对每个元素，都要依据其键重新计算在新数组中的存储位置。这一步骤确保了元素在新的数组环境下能够被正确地安置。
- 最后，把原 HashMap 中的所有元素依次重新插入到新创建的数组之中，从而完成整个扩容过程，使得 HashMap 在新的容量基础上能够继续高效地运作。
三、代码实例呈现
以下是一段简化后的代码，用于展示 HashMap 的扩容机制：
import java.util.HashMap;
public class HashMapExample {
// 内部节点类，用于表示 HashMap 中的元素
private static class Node {
int key;
int value;
Node next;
Node(int key, int value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
// 存储元素的数组
private Node[] buckets;
// 当前 HashMap 中元素的数量
private int size = 0;
// 负载因子，设定为默认值 0.75f
private final float loadFactor = 0.75f;
// 扩容阈值
private int threshold;
// 构造函数，初始化 HashMap 的容量并计算扩容阈值
public HashMapExample(int initialCapacity) {
buckets = new Node[initialCapacity];
threshold = (int) (initialCapacity * loadFactor);
}
// 向 HashMap 中插入元素的方法
public void put(int key, int value) {
// 判断当前元素数量是否即将达到扩容阈值，如果是，则进行扩容操作
if (size + 1 >= threshold) {
resize();
}
// 计算元素在数组中的索引位置
int index = hash(key);
Node node = buckets[index];
// 遍历链表，查看是否存在相同的键，如果有则更新对应的值
for (; node!= null; node = node.next) {
if (node.key == key) {
node.value = value;
return;
}
}
// 如果不存在相同的键，则将新元素插入到链表头部
buckets[index] = new Node(key, value, buckets[index]);
size++;
}
// 哈希函数，用于计算键的哈希值并确定在数组中的位置
private int hash(int key) {
return (key ^ (key >>> 16)) & (buckets.length - 1);
}
// 扩容方法
private void resize() {
// 创建新的数组，容量为原数组的两倍
Node[] newBuckets = new Node[buckets.length * 2];
// 遍历原数组中的每个元素
for (Node node : buckets) {
while (node!= null) {
// 重新计算元素在新数组中的位置
int index = hash(node.key);
Node next = node.next;
// 将元素插入到新数组的对应位置
newBuckets[index] = new Node(node.key, node.value, newBuckets[index]);
node = next;
}
}
// 更新数组引用和扩容阈值
buckets = newBuckets;
threshold = (int) (buckets.length * loadFactor);
}
}
四、总结与启示
HashMap 的扩容机制无疑是保障其高性能表现的核心要素之一。通过在恰当的时机进行扩容操作，HashMap 能够有效地控制哈希冲突发生的概率，进而始终保持高效的操作效率。对于我们这些在日常开发工作中频繁使用 HashMap 的开发者来说，深入透彻地理解 HashMap 的扩容机制具有极为重要的意义，它能够帮助我们更加合理、高效地运用 HashMap 来解决各种实际的编程问题，避免因对其内部机制的不了解而导致的性能瓶颈或错误使用。
标签：扩容,Node,node,HashMap,int,key,机制 From： https://blog.csdn.net/weixin_73687229/article/details/144144028