Java HashMap在JDK 8前后的结构变化及影响
Java HashMap 基础概念回顾
在深入探讨 JDK 8 前后 HashMap 的结构变化之前，先来回顾一下 HashMap 的基础概念。HashMap 是 Java 集合框架中的一部分，它实现了 Map 接口，用于存储键值对（key - value pairs）。它允许使用 null 键和 null 值，并且不保证映射的顺序。
HashMap 基于哈希表实现，哈希表是一种数据结构，它通过计算键的哈希码（hash code）来确定键值对在表中的存储位置。这样可以在平均情况下以接近常数的时间复杂度（O(1)）进行插入、查找和删除操作。
哈希函数与哈希冲突
哈希函数是 HashMap 实现高效存储和检索的核心。它将键对象映射到一个整数值，即哈希码。在 Java 中，每个对象都有一个 hashCode() 方法，HashMap 会调用这个方法来获取键的哈希码。
然而，由于哈希码是一个有限的整数值范围，不同的键可能会产生相同的哈希码，这种情况称为哈希冲突。为了解决哈希冲突，HashMap 在 JDK 8 之前主要采用链地址法（separate chaining）。
JDK 8 之前 HashMap 的结构
在 JDK 8 之前，HashMap 的结构相对简单，主要由数组（Entry[] table）和链表组成。
数组与链表的结合
HashMap 内部维护了一个数组，数组的每个元素是一个链表的头节点。当向 HashMap 中插入一个键值对时，首先计算键的哈希码，然后通过哈希码与数组长度进行取模运算（hash & (length - 1)，这里假设数组长度是 2 的幂次方，这样可以保证均匀分布），得到该键值对在数组中的索引位置。
如果该位置没有元素，则直接将键值对插入到该位置；如果该位置已经有元素（即发生了哈希冲突），则将新的键值对插入到该位置对应的链表头部（JDK 7 及之前采用头插法）。
下面是一个简单的代码示例来展示 JDK 7 及之前 HashMap 的插入逻辑：
import java.util.HashMap;
public class PreJDK8HashMapExample {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);
}
}
在上述代码中，当执行 map.put("one", 1) 时，首先计算 "one" 的哈希码，然后通过取模运算确定其在数组中的位置，如果该位置为空，则直接插入；若不为空，则以链表形式插入。
性能特点
这种结构在哈希冲突较少的情况下，性能表现良好，插入、查找和删除操作的平均时间复杂度为 O(1)。然而，当哈希冲突严重时，链表会变得很长，此时查找操作的时间复杂度会退化为 O(n)，其中 n 是链表的长度。这会导致 HashMap 的性能显著下降。
JDK 8 中 HashMap 的结构变化
JDK 8 对 HashMap 的结构进行了重大改进，引入了红黑树（Red - Black Tree）来优化哈希冲突严重时的性能。
数组、链表与红黑树的结合
在 JDK 8 中，HashMap 仍然使用数组来存储键值对，但当链表长度超过一定阈值（默认为 8）时，链表会转换为红黑树。同时，当红黑树节点数量小于一定阈值（默认为 6）时，红黑树会退化为链表。
数组的每个元素现在可以是一个普通的 Node（链表节点），也可以是一个 TreeNode（红黑树节点）。
下面是 JDK 8 中 HashMap 部分关键代码结构：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//...
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red - black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
//...
}
在插入键值对时，逻辑如下：
- 计算键的哈希码，并通过取模运算确定其在数组中的索引位置。
- 如果该位置为空，直接插入新的
Node。 - 如果该位置已有元素且为链表节点：
- 遍历链表，检查是否有相同键的节点，如果有则更新值；否则在链表尾部插入新节点（JDK 8 采用尾插法）。
- 如果链表长度达到 8 且数组长度大于等于 64，则将链表转换为红黑树。
- 如果该位置已有元素且为红黑树节点，则按照红黑树的插入规则插入新节点。
以下是一个简单的 JDK 8 HashMap 插入代码示例：
import java.util.HashMap;
public class JDK8HashMapExample {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);
}
}
虽然代码表面上与 JDK 7 及之前类似，但内部实现已发生变化，尤其是处理哈希冲突的方式。
红黑树的特性与优势
红黑树是一种自平衡的二叉搜索树，它具有以下特性：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶子节点（NIL 节点，即空节点）是黑色。
- 如果一个节点是红色的，则它的两个子节点都是黑色的。
- 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
这些特性保证了红黑树在最坏情况下，查找、插入和删除操作的时间复杂度为 O(log n)，其中 n 是树中节点的数量。相比链表在哈希冲突严重时的 O(n) 时间复杂度，红黑树能显著提升 HashMap 的性能。
JDK 8 结构变化对性能的影响
JDK 8 中 HashMap 结构的变化对其性能产生了多方面的影响。
插入性能
在哈希冲突较少时，JDK 8 的 HashMap 插入性能与之前版本基本相同，都是接近 O(1) 的时间复杂度。然而，当哈希冲突严重，链表长度达到 8 且数组长度足够时，链表转换为红黑树，插入操作的时间复杂度从 O(n) 提升到 O(log n)，这使得插入性能在极端情况下得到显著改善。
例如，假设有一个 HashMap，不断插入哈希冲突严重的键值对：
import java.util.HashMap;
public class HashMapInsertPerformanceTest {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
long startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
// 模拟哈希冲突严重的情况
map.put("key" + i, i);
}
long endTime = System.currentTimeMillis();
System.out.println("Insertion time: " + (endTime - startTime) + " ms");
}
}
在 JDK 8 之前，随着插入元素增多，链表变长，插入时间会明显增加；而在 JDK 8 中，当链表长度达到阈值转换为红黑树后，插入时间增长速度会显著减缓。
查找性能
查找性能同样受益于红黑树的引入。在哈希冲突较少时，查找时间复杂度为 O(1)。当哈希冲突严重，链表转换为红黑树后，查找时间复杂度从 O(n) 变为 O(log n)。这意味着在大数据量且哈希冲突严重的情况下，JDK 8 的 HashMap 查找速度更快。
比如，在上述插入大量哈希冲突元素的 HashMap 基础上进行查找：
import java.util.HashMap;
public class HashMapLookupPerformanceTest {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < 100000; i++) {
map.put("key" + i, i);
}
long startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
map.get("key" + i);
}
long endTime = System.currentTimeMillis();
System.out.println("Lookup time: " + (endTime - startTime) + " ms");
}
}
JDK 8 中的 HashMap 在这种情况下查找性能会优于 JDK 8 之前的版本。
删除性能
删除操作在 JDK 8 中也因为红黑树的存在而有所变化。在链表中删除节点相对简单，时间复杂度为 O(n)；而在红黑树中删除节点后，需要进行自平衡调整，时间复杂度为 O(log n)。虽然删除操作总体时间复杂度有所增加，但在哈希冲突严重时，由于链表转换为红黑树，整体删除性能仍比 JDK 8 之前的链表结构更优。
JDK 8 结构变化对内存的影响
除了性能，JDK 8 中 HashMap 结构变化对内存使用也有一定影响。
红黑树节点的内存开销
红黑树节点相比链表节点需要额外存储父节点、左右子节点以及颜色信息，这使得红黑树节点的内存占用比链表节点大。例如，链表节点 Node 主要存储 hash、key、value 和 next 引用，而红黑树节点 TreeNode 除了这些还需要存储 parent、left、right 和 red 等信息。
然而，这种额外的内存开销在哈希冲突严重，链表长度较长时是值得的，因为它换来了性能的提升。并且，只有当链表长度达到一定阈值才会转换为红黑树，所以在哈希冲突不严重的情况下，对内存的影响较小。
数组扩容的变化
JDK 8 中 HashMap 在数组扩容时，重新计算元素位置的方式有所优化。在 JDK 8 之前，扩容时需要重新计算每个元素的哈希码并通过取模运算确定新的位置；而在 JDK 8 中，利用了哈希码的高位信息，使得扩容时部分元素的位置可以保持不变，减少了重新计算和移动元素的开销。
这一优化不仅提升了扩容性能，也在一定程度上减少了内存抖动（频繁的内存分配和释放），对整体内存使用有积极影响。
JDK 8 结构变化对遍历的影响
遍历 HashMap 在 JDK 8 前后也受到结构变化的影响。
遍历方式
HashMap 提供了多种遍历方式，如通过 keySet() 获取键集合进行遍历，通过 values() 获取值集合进行遍历，以及通过 entrySet() 获取键值对集合进行遍历。
在 JDK 8 之前，遍历链表结构相对简单，按照链表顺序依次访问即可。而在 JDK 8 中，当存在红黑树结构时，遍历需要考虑红黑树的特性。
红黑树遍历
对于红黑树部分的遍历，HashMap 采用了中序遍历的方式，以保证遍历结果的有序性（虽然 HashMap 本身不保证键值对的顺序，但红黑树内部是有序的）。在遍历过程中，需要从根节点开始，递归地访问左子树、根节点、右子树。
例如，以下代码展示了如何遍历 JDK 8 中的 HashMap：
import java.util.HashMap;
import java.util.Map;
public class HashMapTraversalExample {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);
// 通过 entrySet 遍历
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
}
}
在遍历过程中，如果遇到红黑树节点，会按照中序遍历规则进行访问，这在一定程度上增加了遍历的复杂性，但对于整体遍历性能影响不大，因为在大多数情况下，哈希冲突不会导致大量链表转换为红黑树。
总结 JDK 8 前后结构差异要点
- 数据结构：JDK 8 之前主要是数组 + 链表，JDK 8 变为数组 + 链表 + 红黑树。
- 冲突处理：JDK 8 之前靠链表解决冲突，冲突严重时性能受影响；JDK 8 在链表长到一定程度转红黑树，优化性能。
- 插入操作：JDK 8 之前头插法，JDK 8 尾插法，且链表长时转红黑树优化插入性能。
- 查找和删除：JDK 8 因红黑树存在，在冲突严重时查找和删除性能从 O(n) 提升到 O(log n)。
- 内存使用：红黑树节点内存开销大，但性能提升值得，且扩容优化减少内存抖动。
- 遍历：JDK 8 遍历要考虑红黑树中序遍历，整体影响不大。