Java中的HashMap是基于哈希表实现的键值对存储集合，它的底层核心数据结构由数组、链表和红黑树三部分组成，这种设计既保证了大部分场景下的查询效率，也能应对哈希冲突带来的性能问题。
HashMap底层结构的核心组成
1. 数组（Node数组）
HashMap底层首先是一个名为table的数组，数组的每个位置被称为一个桶（Bucket），桶的初始默认长度是16，长度始终保持为2的幂次方，这样可以通过位运算快速计算元素应该存放的桶位置。数组的类型是Node，这是HashMap内部定义的静态类，用来存储键值对数据。
Node类的基础结构如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 键的哈希值
final K key; // 键
V value; // 值
Node<K,V> next; // 指向下一个节点的指针，用于链表结构
// 构造方法和其他方法省略
}
2. 链表
当两个不同的键通过哈希计算后得到相同的桶索引时，就会产生哈希冲突。HashMap采用链地址法解决哈希冲突，也就是在同一个桶位置下，用链表把多个冲突的Node节点连接起来。链表的存在避免了哈希冲突时数据丢失的问题，但是链表的查询时间复杂度是O(n)，如果链表过长会影响HashMap的性能。
3. 红黑树
为了优化长链表的查询效率，当某个桶下的链表长度达到阈值（默认是8），并且当前HashMap的数组长度大于等于64时，这个桶下的链表就会转换为红黑树。红黑树是一种自平衡的二叉查找树，查询时间复杂度为O(log n)，比长链表的查询效率更高。如果后续红黑树中的节点数量减少到6及以下，红黑树又会退化为链表。
三者的配合工作流程
当我们往HashMap中插入一个键值对时，整体的处理流程如下：
- 第一步：计算键的哈希值，通过
(n - 1) & hash的位运算得到该键值对应该存放的桶索引，其中n是数组的长度。 - 第二步：检查对应桶位置是否为空，如果为空，直接把新的Node节点放到这个桶位置。
- 第三步：如果桶位置不为空，说明发生了哈希冲突，判断当前桶位置是链表还是红黑树：
- 如果是链表，遍历链表，如果找到键相同的节点就覆盖值，否则在链表尾部插入新节点，插入后如果链表长度达到8，就触发链表转红黑树的逻辑。
- 如果是红黑树，就按照红黑树的插入规则插入新的节点。
- 第四步：插入完成后，检查HashMap的元素数量是否超过阈值（数组长度 * 负载因子，默认负载因子是0.75），如果超过就触发数组扩容，重新计算每个节点的桶位置。
关键参数说明
HashMap中和底层结构相关的重要参数如下：
| 参数名 | 默认值 | 作用说明 |
|---|---|---|
| DEFAULT_INITIAL_CAPACITY | 16 | 数组的默认初始长度 |
| DEFAULT_LOAD_FACTOR | 0.75 | 负载因子，决定数组扩容的时机 |
| TREEIFY_THRESHOLD | 8 | 链表转红黑树的阈值 |
| UNTREEIFY_THRESHOLD | 6 | 红黑树退化为链表的阈值 |
| MIN_TREEIFY_CAPACITY | 64 | 链表转红黑树时数组的最小长度要求 |
简单代码示例
下面是一段简单的HashMap插入和查询的示例代码，帮助理解底层结构的作用：
import java.util.HashMap;
public class HashMapDemo {
public static void main(String[] args) {
// 创建HashMap实例，底层数组初始长度为16
HashMap<String, Integer> map = new HashMap<>();
// 插入键值对，会根据键的哈希值计算桶位置，若有冲突则形成链表或红黑树
map.put("apple", 1);
map.put("banana", 2);
map.put("orange", 3);
// 查询键值对，通过哈希定位桶，再在桶内的链表或红黑树中查找
Integer value = map.get("apple");
System.out.println(value); // 输出1
}
}
常见疑问解答
为什么数组长度必须是2的幂次方？
因为计算桶索引时用的是(n - 1) & hash，当n是2的幂次方时，n-1的二进制所有位都是1，位运算的结果和取模运算结果一致，但是位运算的效率比取模运算高很多，同时也能保证计算出的桶索引分布更均匀。
为什么链表转红黑树的阈值是8？
这是根据泊松分布计算得出的结果，在理想的哈希分布下，链表长度达到8的概率非常低，所以选择8作为阈值，既能避免频繁转换结构带来的性能损耗，也能在链表过长时及时优化查询效率。
扩容时为什么所有节点要重新计算桶位置？
因为扩容后数组的长度n发生了变化，原来的(n - 1) & hash计算结果也会变化，所以需要重新计算每个节点对应的新桶位置，保证节点分布到新的数组中。