Java HashMap 原理揭秘：深入解析其内部构造与工作原理
一、引言
HashMap 作为 Java 集合框架中最常用的 Map 实现，广泛应用于数据存储和查找等场景。其内部构造和工作原理也一直是 Java 开发者关注的焦点。本文将深入剖析 Java HashMap 的原理，帮助读者更好地理解其工作方式。
二、HashMap 的数据结构
HashMap 内部采用散列表（Hash Table）数据结构，通过哈希函数将键值对存储在散列表中。散列表由数组、链表和红黑树组成。
1. 数组：HashMap 的底层结构是一个数组，用于存储散列后的键值对。数组的长度必须是 2 的幂次方，这样在扩容时能够快速计算新数组的长度。
2. 链表：当多个键值对散列到同一个索引位置时，会形成一个链表。链表节点存储键值对的引用。
3. 红黑树：当链表长度超过一定阈值时，为了提高查找效率，将链表转换为红黑树。
三、HashMap 的构造函数
HashMap 的构造函数如下：
```java
public HashMap() {
this(16, 0.75f);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
```
构造函数接收两个参数：初始容量（initialCapacity）和加载因子（loadFactor）。
1. 初始容量：表示 HashMap 数组的长度。数组的长度必须是 2 的幂次方，以便在扩容时能够快速计算新数组的长度。
2. 加载因子：表示 HashMap 的负载系数。当 HashMap 的元素数量达到数组长度的加载因子时，会进行扩容操作。
四、HashMap 的哈希函数
HashMap 的哈希函数是核心，决定了键值对的存储位置。Java 8 之前，HashMap 的哈希函数如下：
```java
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
Java 8 之后，HashMap 的哈希函数进行了优化：
```java
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
哈希函数的作用是计算键值对的哈希码，然后根据哈希码确定键值对的存储位置。
五、HashMap 的 put 和 get 方法
1. put 方法：将键值对添加到 HashMap 中。
```java
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
```
put 方法首先计算键的哈希码，然后根据哈希码计算键值对的存储位置。如果该位置为空，则直接插入键值对；如果该位置已存在键值对，则需要解决冲突。
2. get 方法：根据键获取对应的值。
```java
public V get(Object key) {
Node
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
```
get 方法根据键的哈希码和键值计算存储位置，然后遍历链表或红黑树查找键值对。
六、HashMap 的扩容
当 HashMap 的元素数量达到数组长度的加载因子时，会进行扩容操作。扩容过程中，HashMap 会创建一个新的数组，并将原数组中的键值对重新散列到新数组中。
```java
void resize() {
int oldCapacity = threshold;
int newCapacity = oldCapacity << 1;
if (newCapacity - threshold > MAXIMUM_CAPACITY)
newCapacity = MAXIMUM_CAPACITY;
threshold = tableSizeFor(newCapacity);
Node
transfer(newTable);
table = newTable;
}
```
扩容操作会重新计算键值对的存储位置，并解决可能出现的冲突。
七、总结
通过对 Java HashMap 原理的分析，我们了解到其内部构造、工作原理以及扩容机制。HashMap 作为 Java 集合框架中最常用的 Map 实现，在实际开发中有着广泛的应用。掌握 HashMap 的原理，有助于我们更好地使用它，提高代码的效率。
