底层实现#

HashMap内部维护了一个数组（称为桶数组），数组的每个元素称为一个桶。

transient Node<K,V>[] table; // 桶数组，每个元素是一个链表或红黑树的头节点

每个桶用于存储哈希值相同的键值对。哈希冲突时，多个键值对会存储在同一个桶中。

桶如何处理哈希冲突？#

当两个不同的键通过哈希函数计算出相同的索引（即哈希冲突），它们会被放入同一个桶中。
桶内部通过以下两种数据结构解决冲突：

链表（Java 8之前及低冲突场景）

结构：桶中的元素以链表形式链接。
插入方式：新元素插入链表末尾（JDK 1.8改为尾插法，解决JDK 1.7头插法的死循环问题）。
时间复杂度：
- 查找：O(n)（链表长度较小时性能可接受）。
- 插入/删除：O(1)（直接操作链表头或尾）。

红黑树（Java 8+高冲突场景优化）

触发条件：当链表长度 ≥ 8 且桶数组长度 ≥ 64时，链表转换为红黑树。
时间复杂度：
- 查找：O(log n)（显著提升高冲突场景的性能）。
- 插入/删除：O(log n)。
退化条件：当红黑树节点数 ≤ 6时，退化为链表以节省内存。

桶的索引计算#

键值对的存储位置由哈希函数和桶数组长度共同决定：

// 计算键的哈希值（扰动函数减少冲突）
int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

// 计算桶的索引（n为桶数组长度）
int index = (n - 1) & hash;

为什么用(n - 1) & hash？* 桶数组长度n始终是2的幂（如16、32），n-1的二进制形式为全1（如15=0b1111），按位与操作等效于取模运算（hash % n），但效率更高。

桶的扩容机制#

当元素数量超过阈值（capacity * loadFactor）时，桶数组会扩容（通常翻倍），所有键值对需要重新分配到新桶中。

扩容步骤如下：

创建新桶数组：容量为旧数组的2倍（如16 → 32）。

重新哈希分配：遍历旧桶数组中的每个元素，根据新容量重新计算索引。

JDK 1.7: 重新计算哈希值进行元素的插入
JDK 1.8优化：通过哈希值的高位判断元素在新桶中的位置（无需重新计算哈希值）。

// 旧容量为16（二进制0b10000），新容量为32（二进制0b100000）
if ((e.hash & oldCap) == 0) {
    // 索引不变（如原索引5 → 新索引5）
} else {
    // 索引 = 原索引 + 旧容量（如原索引5 → 新索引5+16=21）
}

桶的性能关键点#

哈希函数：均匀的哈希分布能减少桶内冲突。
负载因子（Load Factor）：默认0.75，权衡空间占用与冲突概率。
初始容量：预分配足够大的桶数组可减少扩容次数。

示例：桶的工作流程#

假设桶数组长度为16，插入三个键值对：

插入("A", 1)：
- 哈希值hash(A)计算得到索引5。
- 桶5为空，直接存入。
插入("B", 2)：
- 哈希值hash(B)也得到索引5（哈希冲突）。
- 桶5已有元素，将("B", 2)以链表形式链接在("A", 1)之后。
插入("C", 3)：
- 再次哈希冲突到索引5，链表长度达到8且桶数组长度≥64时，链表转换为红黑树。

总结#

桶的本质：哈希表中存储数据的基本单元，解决哈希冲突的核心结构。
设计目标：通过链表和红黑树的动态切换，平衡时间与空间效率。
优化方向：合理的哈希函数、初始容量和负载因子设置能显著提升性能。